# Bro-key-n

## Challenge Overview

We are given a **broken** private key file, which is encoded in Privacy-Enhanced Mail (PEM).

:::spoiler Key_Redacted.pem

-----BEGIN RSA PRIVATE KEY-----
MIIJJAIBAAKCAgASUWUVXgOvRLJkI77YJ6BlG5t6en55ysW40HpawMJb9bTyWMIn
NIkWpL7+swa+eddajk+sL32Fkdf38eUAbq/y0y6T/LGlDLW9RJqEhAxx+fC62Zmu
7tUA3DK3CS0LAhrd4oWdU8YE9LFhOID7StpmxaGdoFi8emZGuTXE0ooyG60KObs4
dGV3Xbwq1xhM4iG9Drw94PwOlXS5UqDNfCcY0GlrorKsUSJwjNlkPIoos5FtR7KP
Rsau1+kd8aeCeAObkZciPRqLDojy3cVXZqKO6qpXHk2qfyEy1AKAFaNyt4sEt3WY
ex9qQg9a2W0w12zD01QZnJaKhTkMhdThLHrrBQsbBPQwsjcl7FwT0DQBOPZsas+k
WUYbTr++WvKy1pB7j6eC4WUlFFKf3zQ2Z+aHXX0UmPPYDLdlJFgLbyrwEULxW7EO
kTZt2IL3c4+ywkK0F6Ty4M+lzW/Wtj0ZcpAd9pudXEgXeCSUMJ6AlU0ckOl1WSpH
zORHYZ9aPVt2Ertme7sU4XdJZLFOqXzqN1+Z96GdpUOptOmpeL2/sv/4816OlZdH
OIjLErLv73CNhxSJ592zymSZesb0rSnH4T01ResFai6HLOMvE99ezt0lt73XwyRk
MGRm0uW35Ir5rOioHkKVgas3dGjH8DED73WOrvt5p0BImSb9jyYzT9odZQIDAQAB
AoIB/0WfF5MewOJnN59kPPdRpU6kn0vkRtCg4N6PgntsJ0tdlV+F+mkIRALMJyHn
TrqmXNzSB/9ogKwqpa68tKXwDM______________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________YM4i/wJBudIGNGxwJRfOR9HUI2G/wchfC1772bxdFev5+0YM
PiuBRnypiaHcf2/AAOmDMZJFyrTqrfy8jmxfdwKCAQAMVay1pGR15Pyz/AEqJvO4
lrw09/BHA1xhDTc5uYzlChRuxJEn5ehmc1Lgbawr+jciSkfCnNkEueQYv0+EhPYF
lJBsztrCJX3hzcVEU7qJLR4aAP6Px+G0Fd/kxQVbyrCvCKM1ptmpNPqYZE2IR5Ri
Fzj4eD7rl1qEaBNIEdNs2VRMmsRwhrqIZcgRVbzcOf5cE3agelmTT/JeGFVFF+Ri
knxvhVcSScPKgsfdhpFwcYbeLqbLac7ZQcb1+Qz7XU______________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
________________________________________________________________
______________________________________________________
-----END RSA PRIVATE KEY-----

:::

About half of the file is redacted, and our goal is to recover the file. Then use it to connect the server and capture the flag.

## Solution

### Reveal Leakage

First of all, we need to investigate how the file is generated. The private key contains the information

RSAPrivateKey ::= SEQUENCE {
  version           Version,
  modulus           INTEGER,  -- n
  publicExponent    INTEGER,  -- e
  privateExponent   INTEGER,  -- d
  prime1            INTEGER,  -- p
  prime2            INTEGER,  -- q
  exponent1         INTEGER,  -- d mod (p-1)
  exponent2         INTEGER,  -- d mod (q-1)
  coefficient       INTEGER,  -- (inverse of q) mod p
  otherPrimeInfos   OtherPrimeInfos OPTIONAL
}

Then we apply Distinguished Encoding Rules (DER) to encode those info into binary data. Basically, all data will be encoded into following form

::: info
ASN.1 Tag + Length Octet + Data Content + End-of-Contents Octets
:::

Finally, PEM file is created by encoding DER with Base64. Let's use the broken file to explain the details. The first line is

`3082092402010002820200125165155e03af44b26423bed827a0651b9b7a7a7e79cac5b8d07a5ac0c25bf5b4f258c227`

The first byte is $0x30$ indicating the data is SEQUENCE, and it follows $0x82$, which means the length of data is given in the next $2$ bytes, say $0x0924$. Now, we move to the data wrapped in the SEQUENCE.

The next byte is $0x02$, which means the first data is an integer. The length is $0x01$ and the value is simply $0x00$. Note that it's a little different to what we do above.

:::warning
There are two forms for length octet:

1. Short form [One byte]. where the most significant bit (MSB) has value "0" and other bits give the length.
2. Long form [Two or more bytes (at most 127)]. MSB of first octet has value 1 and remaining bits give the number of additional octets. Second and following octets give the length.
:::

Keep doing, we will find the partial values! This is left as an exercise to the reader :P

:::spoiler Leakage

n = 0x125165155e03af44b26423bed827a0651b9b7a7a7e79cac5b8d07a5ac0c25bf5b4f258c227348916a4befeb306be79d75a8e4fac2f7d8591d7f7f1e5006eaff2d32e93fcb1a50cb5bd449a84840c71f9f0bad999aeeed500dc32b7092d0b021adde2859d53c604f4b1613880fb4ada66c5a19da058bc7a6646b935c4d28a321bad0a39bb387465775dbc2ad7184ce221bd0ebc3de0fc0e9574b952a0cd7c2718d0696ba2b2ac5122708cd9643c8a28b3916d47b28f46c6aed7e91df1a78278039b9197223d1a8b0e88f2ddc55766a28eeaaa571e4daa7f2132d4028015a372b78b04b775987b1f6a420f5ad96d30d76cc3d354199c968a85390c85d4e12c7aeb050b1b04f430b23725ec5c13d0340138f66c6acfa459461b4ebfbe5af2b2d6907b8fa782e1652514529fdf343667e6875d7d1498f3d80cb76524580b6f2af01142f15bb10e91366dd882f7738fb2c242b417a4f2e0cfa5cd6fd6b63d1972901df69b9d5c4817782494309e80954d1c90e975592a47cce447619f5a3d5b7612bb667bbb14e1774964b14ea97cea375f99f7a19da543a9b4e9a978bdbfb2fff8f35e8e9597473888cb12b2efef708d871489e7ddb3ca64997ac6f4ad29c7e13d3545eb056a2e872ce32f13df5ecedd25b7bdd7c32464306466d2e5b7e48af9ace8a81e429581ab377468c7f03103ef758eaefb79a740489926fd8f26334fda1d65
e = 0x010001
d_high_bits = 0x459f17931ec0e267379f643cf751a54ea49f4be446d0a0e0de8f827b6c274b5d955f85fa69084402cc2721e74ebaa65cdcd207ff6880ac2aa5aebcb4a5f00cc0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
q_low_bits = 0x60ce22ff0241b9d206346c702517ce47d1d42361bfc1c85f0b5efbd9bc5d15ebf9fb460c3e2b81467ca989a1dc7f6fc000e983319245cab4eaadfcbc8e6c5f77
dp_high_bits = 0x0c55acb5a46475e4fcb3fc012a26f3b896bc34f7f047035c610d3739b98ce50a146ec49127e5e8667352e06dac2bfa37224a47c29cd904b9e418bf4f8484f60594906ccedac2257de1cdc54453ba892d1e1a00fe8fc7e1b415dfe4c5055bcab0af08a335a6d9a934fa98644d884794621738f8783eeb975a8468134811d36cd9544c9ac47086ba8865c81155bcdc39fe5c1376a07a59934ff25e18554517e462927c6f85571249c3ca82c7dd8691707186de2ea6cb69ced941c6f5f90cfb5d4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

:::

Here, the unknown hex digits are replaced by $0$.

### Key Recovery

As we have low bits of the factor $q$, it's easy to find the low bits of $p$ as well.

p_low_bits = (n % m) * pow(q_low_bits, -1, m) % m # m=2^512

On the other hand, by definition, $$dp \equiv d \pmod{p-1}$$ Multiply both sides by $e$, we get $$e \times dp \equiv e \times d \equiv 1 \pmod{p-1} $$ since $e$ is the multiplicative inverse of $d$ w.r.t to $(p-1)(q-1)$ Thus, there exists an integer $k$ less than $e$ so that $$e \times dp = k(p-1) + 1$$ Because we have partial values of $dp$ and $p$, we should rewrite the equation as $$ e \times (dp_{high\_bits} + j \times m + dp_{l}) = k(p_h + p_{low\_bits} - 1)+1 $$ for some $j < 16$ (Because there are $129$ zeros in the end, `dp_high_bits = dp % (4 * m)`. We need to add $j \times m$). Here $x_h, x_l$ represents high and low bits of $x$. In python,

x_h = x - (x % m)
x_l = x % m

Take $\pmod{m}$, the equation becomes $$e \times dp_l \equiv k(p_l-1)+1 \pmod{m}$$ And we deduce the low bits value of $dp$: $$dp_l \equiv dp_l \equiv e^{-1} (k(p_l-1)+1) \pmod{m} $$

This give us one factor $$p = \frac{e \times dp - 1}{k}$$ We decide whether this is true $p$ by checking `n % p == 0`. For completeness, here is my script.

from output import * # store the leakage as output.py
from Crypto.Util.number import *

k = 512
m = 1 << k

p_low_bits = (n % m) * pow(q_low_bits, -1, m) % m 

for i in range(1, e):
    dp_low_bits = (i * (p_low_bits - 1) + 1) * pow(e, -1, m) % m
    for j in range(16):
        dp = dp_high_bits + j * m + dp_low_bits	

        p = ((dp * e - 1) // i) + 1
        if isPrime(p):
            if n % p == 0:
                print(f"Found!")
                print(p)
                print(n // p)
                exit()

### Capture The FLAG

Now, it suffices to recover the PEM file.

from output import *
from result import * # p = ...
from Crypto.PublicKey import RSA

q = n // p

phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
key = RSA.construct([n, e, d])

with open("key.pem", "wb") as f:
        f.write(key.export_key('PEM'))

:::danger
Use the command `chmod 600 key.pem` to change permission! Or you may fail to connect to the server ...
:::

Finally, type `ssh [e-mail] -p 1337 -i key.pem` on the terminal and press enter!

:::success
FLAG. uiuctf{hidden_in_plain_sight}
:::