Últimos Cambios
Blog personal: El hilo del laberinto
|
|
|
Últimos Cambios |
|
Blog personal: El hilo del laberinto
|
|
|
Última Actualización: 24 de Septiembre de 1.999 - Viernes
La compañía RSA hace público un documento analizando el dispositivo TWINKLE, diseñado por Adi Shamir. Este dispositivo permitiría acelerar una de las dos etapas necesarias para factorizar un número, en tres órdenes de magnitud (unas mil veces más rápido).
Como ya se comentaba en el boletín enviado el pasado 2 de Septiembre, los algoritmos actuales de factorización se basan en dos etapas: en la primera varios ordenadores buscan, en paralelo, una serie de relaciones de congruencia. En una segunda etapa, un superordenador con una gran cantidad de memoria procede a resolver la ecuación matricial obtenida en el paso anterior.
El dispositivo de Shamir, llamada TWINKLE, permite acelerar unas mil veces la primera etapa, aunque no aporta ninguna mejora adicional a la segunda etapa.
En el documento que comentamos en este boletín, uno de los investigadores de RSA realiza un análisis detallado de las implicaciones prácticas de dicho dispositivo.
El primer paso consiste en evaluar cuánto se hubiera tardado en factorizar RSA-140 (el mayor reto RSA factorizado en aquel momento; recientemente se ha factorizado el RSA-155).
Para igualar las características de los equipos empleados en el reto RSA-140, hubieran bastado sólo 7 dispositivos TWINKLE. Toda la primera etapa de criba hubiera podido completarse en 6 días, en vez de las cuatro semanas y 200 ordenadores utilizados realmente. La segunda etapa, la resolución de la ecuación matricial, seguiría necesitando 100 horas de cálculo en un superordenador. Se hubiera pasado de 33 días a 10 días. Incluso con una criba infinitamente rápida, el tiempo requerido para completar la segunda etapa hubiera sido de unas 100 horas. La ganancia óptima no hubiera superado un factor del 800%.
RSA-140 tiene 465 bits. A medida que crece el tamaño de los números a factorizar, aumenta el tiempo de criba, y el tamaño y tiempo para resolver la ecuación matricial final. Operación, ésta última, que no se puede paralelizar fácilmente.
Como comparación, factorizar RSA-140 (465 bits) consumió 64Mbytes de RAM en cada una de las máquinas que colaboraron en la criba, y 825 Mbytes en el superordenador. Factorizar un número de 768 bits supondrá 10Gigabytes en cada ordenador que cribe y 160Gbytes en el superordenador. Factorizar un número de 1024 bits necesitaría 256Gbytes en cada máquina de criba, y 10TeraBytes en el superordenador.
Se puede ver una estimación de tiempos para cada tamaño de número en http://www.argo.es/~jcea/artic/hispasec08.htm.
A la vista de estos datos, es razonable pensar que las claves RSA de 768 bits son seguras a medio plazo, y las claves de 1024 bits están fuera de las posibilidades de nada que podamos imaginarnos en este momento tecnológico.
Más información:
An Analysis of Shamir's Factoring Device
http://www.rsa.com/rsalabs/html/twinkle.html
ftp://ftp.rsa.com/pub/pdfs/bulletn12.pdf
Nuevo dispositivo óptico para factorizar más rápido
http://www.argo.es/~jcea/artic/hispasec08.htm
http://www.hispasec.com/unaaldia.asp?id=310
Factorización de RSA-155
http://www.argo.es/~jcea/artic/hispasec09.htm
http://www.hispasec.com/unaaldia.asp?id=322
Más información sobre los OpenBadges
Donación BitCoin: 19niBN42ac2pqDQFx6GJZxry2JQSFvwAfS
