Rompiendo claves RSA

Aunque hoy por hoy no es posible romper una clave RSA de más de 1024 bits ni con miles de computadoras trabajando en paralelo, los algoritmos de factorización no dejan de mejorar. A continuación voy a explicar cómo romper una clave RSA relativamente pequeña usando uno de estos algoritmos.

Primero crearemos un entorno de pruebas con el que cifrar y descifrar. Usaremos la herramienta openssl.

Generamos un par de claves RSA de 256 bits.
$ openssl genrsa -out privkey.pem 256

# Extraemos la clave publica
$ openssl rsa -in privkey.pem -pubout -out pubkey.pem
$ cat pubkey.pem
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAK1/eaHlW68OrwaeT/X6V9mx4pkvE8mW
QScrI2z8UVBhAgMBAAE=
-----END PUBLIC KEY-----

# Algo que cifrar
$ echo ";)" > msg.txt

# Ciframos (con la clave publica)
$ openssl rsautl -encrypt -pubin -inkey pubkey.pem -in msg.txt -out msg.enc

# Desciframos (con la clave privada)
$ openssl rsautl -decrypt -inkey privkey.pem -in msg.enc
;)

Ya tenemos nuestro entorno de pruebas con un par de claves que nos pemiten cifrar y descifrar mensajes. Como RSA es un criptosistema asimétrico se supone que deberíamos distribuir la clave pública, mientras que guardaríamos con recelo la clave privada.

Nuetro objetivo será obtener la clave privada partiendo únicamente de la clave pública. Una vez obtenida descifraremos el mensaje.

RSA basa su fuerza en el problema de factorización de números grandes. Un problema matemático para el que no se conoce un algoritmo que lo resuelva de forma eficiente. Entre los algoritmos más rápidos destacan QS y NFS. Ambos implementados por la genial herramienta msieve (Instalar).

Lo primero que necesitamos es el módulo n y el exponete de cifrado. Los dos se pueden obtener facilmente a partir de la clave pública.

$ openssl rsa -in pubkey.pem -pubin -text -modulus
Modulus (256 bit):
00:ad:7f:79:a1:e5:5b:af:0e:af:06:9e:4f:f5:fa:
57:d9:b1:e2:99:2f:13:c9:96:41:27:2b:23:6c:fc:
51:50:61
Exponent: 65537 (0x10001)
Modulus=AD7F79A1E55BAF0EAF069E4FF5FA57D9B1E2992F13C99641272B236CFC515061
writing RSA key
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAK1/eaHlW68OrwaeT/X6V9mx4pkvE8mW
QScrI2z8UVBhAgMBAAE=
-----END PUBLIC KEY-----

Observemos que el módulo está en hexadecimal. Para continuar será necesario pasarlo a decimal. A continuación, lo factorizamos con msieve:

$ msieve -v 78475351858145546395020889284272950035474797715255953445997961959441362407521

Obteniendo como resultado los factores:
262908038773065572592762474383232893183
298489738938272421513567914663780208287

Únicamente nos quedará recuperar la clave original a partir de los datos obtenidos. Usaremos el programa get_priv_key.

$ ./get_priv_key 262908038773065572592762474383232893183 298489738938272421513567914663780208287 \ 

65537
-----BEGIN RSA PRIVATE KEY-----
MIGrAgEAAiEArX95oeVbrw6vBp5P9fpX2bHimS8TyZZBJysjbPxRUGECAwEAAQIg
L/uaWxEAq0iHVXBBMwk6dDC0mJubL4dVLLdiaA01NPUCEQDgjwhah0l/hqX+D3Xh
3s6fAhEAxco/F01rh+Uzf+LV2K6A/wIRANOCxcqHPRpKGFV5+H3cYF8CEEN8O0Sf
JNZsTMMQyXgyKk8CEQCRfomgf/LY71boM54D8a5C
-----END RSA PRIVATE KEY-----

Con la nueva clave privada ya podemos acceder al mensaje cifrado.

$ openssl rsautl -decrypt -inkey cracked_privkey.pem -in msg.enc
;)

Referencias:
- RSA Labs.
- Ataque de factorización a RSA (hakin9 nº19).
- On the cost of factoring RSA 1024.