Weak RSA
2 minutos de lectura
Se nos proporciona una clave pública en formato PEM de una implementación de RSA (key.pub):
-----BEGIN PUBLIC KEY-----
MIIBHzANBgkqhkiG9w0BAQEFAAOCAQwAMIIBBwKBgQMwO3kPsUnaNAbUlaubn7ip
4pNEXjvUOxjvLwUhtybr6Ng4undLtSQPCPf7ygoUKh1KYeqXMpTmhKjRos3xioTy
23CZuOl3WIsLiRKSVYyqBc9d8rxjNMXuUIOiNO38ealcR4p44zfHI66INPuKmTG3
RQP/6p5hv1PYcWmErEeDewKBgGEXxgRIsTlFGrW2C2JXoSvakMCWD60eAH0W2PpD
qlqqOFD8JA5UFK0roQkOjhLWSVu8c6DLpWJQQlXHPqP702qIg/gx2o0bm4EzrCEJ
4gYo6Ax+U7q6TOWhQpiBHnC0ojE8kUoqMhfALpUaruTJ6zmj8IA1e1M6bMqVF8sr
lb/N
-----END PUBLIC KEY-----
$ python3 -q
>>> from Crypto.PublicKey import RSA
>>> key = RSA.import_key(open('key.pub').read())
>>> key.n
573177824579630911668469272712547865443556654086190104722795509756891670023259031275433509121481030331598569379383505928315495462888788593695945321417676298471525243254143375622365552296949413920679290535717172319562064308937342567483690486592868352763021360051776130919666984258847567032959931761686072492923
>>> key.e
68180928631284147212820507192605734632035524131139938618069575375591806315288775310503696874509130847529572462608728019290710149661300246138036579342079580434777344111245495187927881132138357958744974243365962204835089753987667395511682829391276714359582055290140617797814443530797154040685978229936907206605
RSA funciona de la siguiente manera: Se cogen dos números primos grandes $p$ y $q$ y se toma $n = pq$ como módulo. Luego, se coge un exponente $e$ (típicamente $e = 65537$) y se cifra el mensage $m$ en formato decimal:
$$ c = m^e \mod{n} $$
La clave pública es la tupla $(n, e)$, y la clave privada está compuesta por los dos números primos. Para descifrar, se necesita calcular $\phi(n) = (p - 1) (q - 1)$ para calcular el inverso de $e$ respecto a la multiplicación, que es $d = e^{-1} \mod{\phi(n)}$. Luego, el texto cifrado $c$ se descifra como:
$$ m = c^d \mod{n} $$
Y esto funciona debido a que
$$ c = m^e \mod{n} \iff c^d = (m^e)^d = m^{ed} = m \mod{n} $$
El problema de esta implementación de RSA es que $e$ es muy grande. Este hecho lo hace vulnerable al ataque de Wiener. Podemos usar el módulo owiener de Python para extraer el exponente privado $d$:
>>> import owiener
>>> d = owiener.attack(key.e, key.n)
>>> d
44217944188473654528518593968293401521897205851340809945591908757815783834933
En este punto, podemos descifrar la flag (disponible en 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}'