Cómo romper RSA explícitamente con llaves OpenSSL

Todo el mundo habla de lo vulnerable que es RSA y de la importancia de los números primos involucrados en las llaves. Muchos saben que la seguridad radica en la dificultad de factorizar enteros y hace poco en twitter a muchos les interesó el cómo se hace. Ahora lo dejo aquí en mi blog para que lo hagan ustedes, vamos a romper una llave RSA de 256 bits la cual no es tan grande pero tampoco es tristemente pequeña en menos de 5 minutos. 

Esto es razón más para investigar otro tipo de esquemas de logaritmo discreto como los que ya he mencionado aquí y de los cuales me la paso dando charlas sobre Jacobianas con curvas algebraicas u otras variedades abelianas. 

Dejo antes una reseña de cómo funciona RSA y después a romper RSA :) 

Generación de llaves: 

 - Se generan dos números primos grandes (p,q) aleatorios 

 - Se computa n=pq el cual servirá como módulo 

 - Se computa phi(n)=(p-1)(q-1) (phi función de conteo de primos relativos con n, y es (p-1)(q-1) por ser primos p y q) 

 - Escoges un e tal que 1 menor que e menor que phi(n) y mcd(phi(n),e) = 1 (OpenSSL generalmente asigna algo cercano a 2^16 como 65537) 

 - Computas d = e^-1 mod phi(n) (d,p,q) es la llave privada (e,n) es la llave publica 

  Cifrado: 

 - a A le van a mandar M entonces A le manda a B (e,n) 

 - B computa c=M^e mod n y se lo manda a A 

  Descifrado: 

 - A computa m=c^d mod n que es lo mismo que m=(m^e)^d mod n que es m (es fácil demostrar que eso es m) 

La seguridad radica en que si alguien obtiene la llave pública (e,n) como d = e^-1 mod phi(n) , o sea d = e^-1 mod (p-1)(q-1) tendría que factorizar n=pq para obtener e^-1 mod (p-1)(q-1) 

Cómo romper RSA dada una llave pública SSL 

 

Primero generamos un ambiente de pruebas para romper la llave. Generamos llave privada (o sea p,q) en privada.pem 

openssl genrsa -out privada.pem 256 

Generamos llave pública con la privada (o sea e,n) en pub.pem 

openssl rsa -in privada.pem -pubout -out pub.pem 

Extraemos módulo n y exponente e, o sea n , y e de la llave publica que romperemos

openssl rsa -in pub.pem -pubin -text -modulus 

Lo cual nos dará mucha info, y en esa info vendrá lo siguiente: 

Exponent: 65537 (0x10001) Modulus=9ABAAD5BBE954A26BDBB15568B7AEB3651D0605EA5687329F849DB1F9871865F 

Exponent es "e" y Modulus es "n" Convertimos a decimal esa cosa: 

echo "ibase=16; 9ABAAD5BBE954A26BDBB15568B7AEB3651D0605EA5687329F849DB1F9871865F"|bc 69986008711415694391421268580269058232048146719704518153244714221529713444447 

Lo factorizamos con msieve que está disponible aquí el cual su funcionamiento, es con la criba numérica (GNFS) el cual es el algoritmo más rápido hasta ahora para factorizar, éste hay que compilarlo, solo requiere -lgmp (gnu multiprecision) y otras cosas estándar. Puedes tambien clonarlo de git, pero antes si quieres explora el parametro "march" del Makefile para optimizacion adicional a tu procesador.

git clone https://github.com/radii/msieve

cd msieve

make; make install

 

Si msieve compiló correctamente y se instaló, para factorizar ese número basta correr después de haber compilado , de la siguiente manera 

msieve -v 69986008711415694391421268580269058232048146719704518153244714221529713444447 

Tardará de 2 minutos en una computadora normal (esto es porque es de 256 bits, pero seguro en Kanbalam de la UNAM se puede romper 768 bits en cuestión de días, ya que es paralelizable y soporta resumen. Ya que termina te mostrará los factores. 

prp39 factor: 258903250452187592132630852021175987089 

prp39 factor: 270317226953240634960995990331891792623 

Construimos la llave privada, para esto, hice un programa hice un cgi en mi sitio sólo manda los p,q,e por GET, aquí e=65537 los factores p q que sacamos en otro paso atrás 

http://ff2.nl/cgi-bin/genpriv.cgi?p=258903250452187592132630852021175987089&q=270317226953240634960995990331891792623&e=65537 

y la página te sacará lo siguiente: 

Llave privada de 258903250452187592132630852021175987089,270317226953240634960995990331891792623 y 65537 por Eduardo Ruiz Duarte (beck) toorandom@gmail.com 

-----BEGIN RSA PRIVATE KEY-----

MIGqAgEAAiEAmrqtW76VSia9uxVWi3rrNlHQYF6laHMp+EnbH5hxhl8CAwEAAQIh

AIb+e6Vhn6p0JnCE618BvRfp5+WyQWSxb7Fz8aTB5FTBAhEAy100RZ5hZCzjbv48

M2I67wIRAMLG88hDEnjIwaItDgCYK5ECEE4kDBfMGaQCU4msirk7v2UCEFDOY1MA

6Iftmc+ja3y5pNECEF2g5ukd6W4XRpU1d9AwY/4= 

-----END RSA PRIVATE KEY----- 

Y si comparas la llave inicial (privada.pem) con esta que sacamos la cual guardé en "llaverota.pem" verás que son la misma y no utilizamos ninguna información de la llave privada generada originalmente para llegar a llaverota.pem 

md5sum privada.pem llaverota.pem 

9cd4b5a39be5717978b9035ddc5fc887 privada.pem 

9cd4b5a39be5717978b9035ddc5fc887 llaverota.pem 

Comentarios: Eduardo Duarte toorandom at gmail d0t com Twitter: @toorandom