In this challenge from the first ever CTF competition organized by the H4x0rPsch0rr team, …

Your task is simple:

`ssh -i id_rsa -p 1122 ctf@1.ctf.link`

The (RSA) private key is…

`-----BEGIN RSA PRIVATE KEY----- MIMIECICAQACgggBANRFHE8WEB/STSEH+Coqqdw6sI3CyaLGNuH1A46qBC5JzXeX Kg9KPSkbwydPj5HVZ+i2d9nDK5ifYv0mC7CCHAE2RuYqOwDJe3LKt0ZBHI11nomm [...roughly 11k more lines of base64...] 4ZcP2zJaIKd7LKH7b79gxtJyMJCHt+34AzdJqRGHwRef9FHp4j+VxtGdtycoUkvk 4oPCAd4tUhJuj35AlMWcXQHCYOH+opKBAgEBAgEBAgEAAgEAAgEA -----END RSA PRIVATE KEY-----`

**…extraordinarily huge.**

Trying to simply log in, as demanded by the task, quickly turns out to be quite hopeless: The SSH client immediately eats 100% CPU power and even after waiting a considerable amount of time, there is no significant progress in authenticating to the server.

So what’s wrong with the key? As it turns out (using `openssl asn1parse`

and some regex magic to shorten the output), all private parts
except $d$ are set to zero or one, that is, blanked out, and $d$ has
over **four million bits**, much more than the modulus ($16384$ bits).

(Fun fact: OpenSSH does in fact accept
keys of that format, i.e. without $p$, $q$, $d\bmod{\varphi(p)}$,
$d\bmod{\varphi(q)}$, $q^{-1}\bmod p$. Hence
** the key is actually functional!**, just a little

It is a defining property of the exponents in the RSA signature system
that $e$ and $d$ satisfy
\[ ed\equiv1\pmod{\lambda(n)} \text, \]
where, in this context,
$\lambda$$(n)=\operatorname{lcm}(p-1,q-1)$.
On the other hand, this implies that there is an infinite number of
working private exponents $d$ for a given public key $(n, e)$ — and
the one we are given seems to be a rather large one `;-)`

. Now how can we
obtain a smaller representant $d’$ of those possible exponents? Clearly we
still need $ed’\equiv1\pmod{\lambda(n)}$. Since the canonical projection
$\mathbb Z\to\mathbb Z/\lambda(n)\mathbb Z$ is a ring homomorphism, we
can just replace $d$ by $d\bmod\lambda(n)$ without changing the validity of the congruence
$d$ must satisfy.

**But…** We don’t know $\lambda(n)$, and it can’t easily be derived from
$n$ since this task is essentially equivalent to factoring $n$. However,
there is an efficient algorithm to **determine the factors** of $n$ given a pair
$(e, d)$ which satisfies the usual congruence! A nice description of such a method
can be found in
Dan Boneh’s paper, proof of
fact 1. (Also make sure to check out the implementation below. It’s the block
commented “magic!”.)

After a factorization $n=pq$ has been obtained, one can simply compute \[ d’ := d\bmod \operatorname{lcm}(p-1,q-1) \] and create a new keyfile filling in the exponent $d’$ in place of $d$ and, if one wishes, the numbers missing from the given key (although that’s not strictly necessary, as commented above). The resulting key should work quickly enough to authenticate to the server in time.

Here’s the resulting script:

```
#!/usr/bin/env sage
import os, base64
from pyasn1.type import univ
from pyasn1.codec.der import encoder, decoder
################################################################################
# parse id_rsa and convert to a more workable format.
f = open('id_rsa', 'r').read()
f = ''.join(l for l in f.split('\n') if l and not l.startswith('-----'))
f = base64.b64decode(f)
dec = decoder.decode(f)
_, n, e, d, p, q, dp, dq, qi = map(int, dec[0])
print('decoded asn1.')
################################################################################
# magic! compute p, q from n, e, d.
g = 2 # may need to change this if "bad root" occurs
t, r, k = 0, e * d - 1, e * d - 1
while not r & 1:
t += 1
r >>= 1
x0 = Zmod(n)(g) ** (k >> t)
print('done with huge exponentiation.')
xs = [x0 ** (2 ** i) for i in reversed(range(t))]
for x in xs:
if int(x) in [1, n - 1]:
continue
p = gcd(int(x) - 1, n)
print('\x1b[32mp = {:#x}\x1b[0m'.format(p))
assert p not in [1, n]
break
else:
print('\x1b[31moops, bad root\x1b[0m')
exit(1)
q = n // p
print('\x1b[32mq = {:#x}\x1b[0m'.format(q))
################################################################################
# fix key.
d = d % lcm(p - 1, q - 1)
print('\x1b[32md := {:#x}\x1b[0m'.format(d))
p = q = 1
dp = dq = qi = 0
################################################################################
# encode new key.
key = ''
k = univ.SequenceOf(univ.Integer()).setComponents(0, n, e, d, p, q, dp, dq, qi)
enc = base64.b64encode(encoder.encode(k)).decode()
key += '-----BEGIN RSA PRIVATE KEY-----\n'
for i in range(0, len(enc), 64):
key += enc[i:i+64] + '\n'
key += '-----END RSA PRIVATE KEY-----\n'
open('id_rsa.good', 'w').write(key)
os.chmod('id_rsa.good', int('0600', 8))
```

Using the resulting key file
`id_rsa.good`

,
we can easily log in to the server and get the flag:

```
$ time ./pwn.sage
decoded asn1.
done with huge exponentiation.
p = 0xe5e99b73e1342107941b90b8b707e784eea7c2422d3a350b748776e31aef0e6[...]
q = 0xec5b07c03300cca94083a838da72d57fd78da1d4568c1434ce1e579b3324dca[...]
d := 0x13cb09f3b9ebf0fbac237b59c19ccecff14d0b3af1905309451292ad57df21e[...]
real 7m43.803s
user 7m42.330s
sys 0m1.337s
$ ssh -i id_rsa.good -p 1122 ctf@1.ctf.link
[...]
hxp{n0T_ev3N_j4vA_B1gNum_c4n_h0lD_mY_k3yZ}
$
```