Un equipo de personas de todo el mundo, con casi 300 ordenadores,
consigue completar la factorización RSA-155 en poco más de 5 meses.
Este resultado demuestra de forma patente, una vez más, que las
claves públicas RSA de 512 bits no suponen un obstáculo frente a
cualquier organización de medianas proporciones.
El pasado 26 de Agosto (aunque la fecha real del hito fue el día 22),
RSA hizo pública una nota de prensa en la que anunciaba que su reto
RSA-155 había caído, fruto del esfuerzo conjunto de un equipo
multinacional y sus 8000 MIPS-año. Dado que 155 dígitos decimales
suponen unos 515 dígitos binarios, y la mayoría de las soluciones de
comercio electrónico y navegadores web implementan sólo claves de 512
bits, está claro que cualquiera de las claves comúnmente empleadas en
Internet con fines comerciales es susceptible de ataque. Este tipo de
claves son empleados, por ejemplo, para la emisión de certificados,
empleados en S/MIME y SSL (HTTPS).
Lamentablemente la legislación actual norteamericana no permite exportar
al extranjero productos con claves RSA de longitud superior a los 512
bits, a pesar de que todos los expertos coinciden en que se requieren
claves de 768 bits (unos 231 dígitos decimales) para poder disfrutar de
una seguridad mínimamente confortable.
Algunos datos de interés:
El número a factorizar era
RSA-155 =
1094173864157052742180970732204035761200373294544920599091384213147634\
9984288934784717997257891267332497625752899781833797076537244027146743\
531593354333897
que puede escribirse como el producto de dos números primos de 78 cifras:
102639592829741105772054196573991675900716567808038066803341933521790\
711307779
*
106603488380168454820927220360012878679207958575989291522270608237193\
062808643
Se puede obtener más información sobre el tiempo necesario
-aproximadamente- para factorizar un número, en función de su número de
dígitos, en http://www.argo.es/~jcea/artic/hispasec08.htm.
El tiempo estimado de CPU fue de 8000 MIPS-año. El reto RSA-140,
resuelto en Febrero de este año, fue tasado en unos 2000 MIPS-año. Según
la fórmula mostrada en la URL anterior, RSA-155 hubiera requerido
12000-14000 MIPS-año; la diferencia es debida a una mejor selección de
los polinomios generadores, mecanismo también descrito en la URL
proporcionada.
Pueden leerse todos los detalles, en inglés, en
http://www.argo.es/~jcea/artic/hispasec09-2.txt
Más Información:
Para recibir por email la lista de números pendientes de factorizar, hay
que enviar un mensaje a «challenge-rsa-list@rsa.com».
Para recibir por email la lista de números factorizados, por quien, etc,
hay que enviar un mensaje a «challenge-honor-rolls@rsa.com».
Informe Oficial:
http://www.rsasecurity.com/rsalabs/factoring/rsa155.html
Preguntas frecuentes sobre RSA-155
http://www.rsasecurity.com/rsalabs/challenges/factoring/rsa155_faq.html
Nota de prensa oficial:
http://www.rsa.com/pressbox/html/990826.html
Factorización RSA-140:
http://www.rsasecurity.com/rsalabs/factoring/rsa140.html
Retos RSA:
http://www.rsasecurity.com/rsalabs/challenges/
RSA Factoring Challenge:
http://www.rsasecurity.com/rsalabs/challenges/factoring/
Factorization of a 512-bits RSA key using the Number Field Sieve:
http://www.argo.es/~jcea/artic/hispasec09-2.txt
Nuevo dispositivo óptico para factorizar más rápido:
http://www.argo.es/~jcea/artic/hispasec08.htm