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
An Analysis of Shamir’s Factoring Device (PDF)
Nuevo dispositivo óptico para factorizar más rápido (jcea)
Nuevo dispositivo óptico para factorizar más rápido (HispaSec)
Factorización de RSA-155 (jcea)
Factorización de RSA-155 (HispaSec)
jcea@argo.es
http://www.argo.es/~jcea/
Deja un comentario