Weak RSA

2 minutes to read

We are given a public key in PEM format for an RSA implementation (key.pub):

$ python3 -q
>>> from Crypto.PublicKey import RSA
>>> key = RSA.import_key(open('key.pub').read())
>>> key.n
573177824579630911668469272712547865443556654086190104722795509756891670023259031275433509121481030331598569379383505928315495462888788593695945321417676298471525243254143375622365552296949413920679290535717172319562064308937342567483690486592868352763021360051776130919666984258847567032959931761686072492923  
>>> key.e
68180928631284147212820507192605734632035524131139938618069575375591806315288775310503696874509130847529572462608728019290710149661300246138036579342079580434777344111245495187927881132138357958744974243365962204835089753987667395511682829391276714359582055290140617797814443530797154040685978229936907206605

RSA works as follows: We take two large primes $p$ and $q$ and set the modulus $n = pq$. Then we choose an exponent $e$ (typically $e = 65537$) and encrypt a message $m$ in decimal format:

$$ c = m^e \mod{n} $$

The public key is the tuple $(n, e)$, and the private key is composed of the two prime numbers. To decrypt, we need to compute $\phi(n) = (p - 1) (q - 1)$ in order to find the multiplicative inverse of $e$, which is $d = e^{-1} \mod{\phi(n)}$. Then the decryption of $c$ is:

$$ m = c^d \mod{n} $$

This works because

$$ c = m^e \mod{n} \iff c^d = (m^e)^d = m^{ed} = m \mod{n} $$

The problem of this RSA implementation is that $e$ is really big. This fact makes it vulnerable to Wiener’s attack. We can use owiener Python module to extract the private exponent $d$:

>>> import owiener
>>> d = owiener.attack(key.e, key.n)
>>> d
44217944188473654528518593968293401521897205851340809945591908757815783834933

At this point, we can decrypt the flag (available in flag.enc):

>>> c = int(open('flag.enc', 'rb').read().hex(), 16)
>>> m = pow(c, d, key.n)
>>> from Crypto.Util.number import long_to_bytes
>>> long_to_bytes(m)
b'\x02!\xcf\xb2\x98\x83\xb0o@\x9ag\x9aX\xa4\xe9{Dn(\xb2D\xbb\xcd\x06\x87\xd1x\xa8\xab\x87"\xbf\x86\xda\x06\xa6.\x04,\x89-)!\xb36W\x1e\x9f\xf7\xac\x9d\x89\xba\x90Q+\xacL\xfb\x8d~J9\x01\xbb\xcc\xf5\xdf\xac\x01\xb2{\xdd\xd3_\x1c\xa5SD\xa7YC\xdf\x9a\x18\xea\xdb4L\xf7\xcfU\xfa\x0b\xaap\x05\xbf\xe3/A\x00HTB{s1mpl3_Wi3n3rs_4tt4ck}'  
>>> long_to_bytes(m).split(b'\0')[-1]
b'HTB{s1mpl3_Wi3n3rs_4tt4ck}'