Últimos Cambios
Blog personal: El hilo del laberinto
|
|
|
Últimos Cambios |
|
Blog personal: El hilo del laberinto
|
|
|
Última Actualización: 14 de Septiembre de 1.999 - Martes
Adi Shamir, la "S" del popular algoritmo RSA, ha diseñado un dispositivo óptico (presentado en EuroCrypt'99) capaz de acelerar, en órdenes de magnitud, uno de los pasos clave de los modernos algoritmos de factorización. Ello permitirá "romper" claves asimétricas, consideradas seguras hasta ahora, en un tiempo razonable.
Recordemos que muchos de los algoritmos criptográficos asimétricos basan su seguridad en la dificultad de factorizar un número "n" cuando éste es muy grande. Es decir, en encontrar los factores "p" y "q" tales que "n=p*q". El RSA, por ejemplo, uno de los algoritmos asimétricos más populares que existe, basa su seguridad en esta premisa.
La mayoría de los algoritmos modernos de factorización se basan en el concepto de criba. En una primera etapa se localizan una serie de números cuyos cuadrados módulo "n" tengan descomposiciones "suaves" ("smooth", en inglés) en factores primos pequeños. Esta primera etapa es la más lenta, ya que un ordenador personal rápido requiere varios segundos para validar cada valor tentativo, y la mayoría de los valores evaluados resultan no ser válidos. Afortunadamente la comprobación de cada valor puede realizarse de forma independiente, por lo que es posible realizarlo en paralelo, en máquinas distintas.
Es interesante comentar que el número de valores "suaves" necesarios para pasar a la siguiente etapa es un parametro que puede fijarse de forma arbitraria. No obstante, este parámetro especifica también la probabilidad de que un valor tenga una descomposición "suave". Es decir, que si fijamos el parámetro para requerir muchos valores "suaves", la probabilidad de que un valor dado sea "suave" es mayor que si cambiamos el parámetro para requerir menos valores. Dado que evaluar y descartar un valor, por no ser "suave", es una operación lenta, es preferible aumentar las probabilidades de éxito aún a costa de necesitar más valores "suaves" antes de pasar a la siguiente etapa. En la práctica se suele trabajar tomando como base los primeros 200.000 números primos, con lo que se necesitarán unos 200.000 valores "suaves".
Una vez localizados un cierto número de valores "suaves", un superordenador (se requiere muchísima memoria RAM) procede a realizar una eliminación gaussiana de la matriz resultante de combinar los números "suaves" obtenidos en la etapa de criba, y tras una simple operación de "máximo común denominador", se obtiene la factorización de "n". Esta etapa tiene una duración reducida, comparada con la anterior. No es fácilmente paralelizable, pero se trata de un paso muy rápido.
Adi Shamir, uno de los creadores del propio RSA, ha diseñado un dispositivo óptico, de coste comparable al de una estación de trabajo de gama media (5.000 dólares) capaz de realizar la etapa de criba, la operación más costosa, mil veces más rápido que un ordenador de altas prestaciones. En la práctica ello hubiera supuesto que la factorización del reto RSA-140, completada en Febrero de 1.999 y que supuso el empleo de doscientas estaciones de trabajo calculando a lo largo de cuatro semanas, se hubiera podido completar en apenas unas pocas horas.
El dispositivo es un cilindro de un tamaño aproximado de 6*10 pulgadas (aproximadamente 15*25 centímetros). Se llama TWINKLE, es muy sencillo y barato de fabricar (no requiere componentes de precisión). Funciona, básicamente, operando diodos electroluminiscentes (LEDs), cada uno de ellos parpadeando con un período fijado en relación con el primo que representa. Un ordenador conectado a TWINKLE le va enviando valores a comprobar, proceso que consume menos de una centésima de segundo. TWINKLE devolverá, a su vez, una estimación de la "suavidad" del número. Bastará, por tanto, que el ordenador verifique informáticamente si el número es o no "suave", tal y como lo hacía previamente. Pero ahora se limitará a realizar esta operación exclusivamente con los valores que TWINKLE marque como más probables, lo que supone una impresionante mejora de rendimiento.
¿Cuáles son las implicaciones prácticas?. Una mejora de tres órdenes de magnitud en el rendimiento de los algoritmos de factorización constituye una ganancia considerable. Como ya hemos dicho, romper el reto RSA-140 supuso el empleo de 200 potentes máquinas durante cuatro semanas (criba), más 100 horas de cálculo en un superordenador para la reducción Gaussiana. Si se hubiesen empleado 200 TWINKLEs, el tiempo de criba se hubiera reducido a apenas 40 minutos. Las 100 horas de cálculo finales tendrían que efectuarse de todos modos, eso sí.
El reto RSA-140 factorizó una clave de 465 bits. Considerando exclusivamente el tiempo de criba, la complejidad del NFS (Number Field Sieve) es de O(e^(1.92*(ln(n)^(1/3))*(ln(ln(n))^(2/3))), obteniendo la siguiente tabla aproximada:
| Longitud de la clave | Tiempo de criba | |
|---|---|---|
| BITS | Dígitos | |
| 465 | 140 | X |
| 512 | 154 | 6*X |
| 565 | 170 | 47*X |
| 615 | 185 | 278*X |
| 665 | 200 | 1508*X |
| 768 | 231 | 39154*X |
| 1024 | 308 | 47285717*X |
| 2048 | 616 | 5.3*10^16*X |
A la luz de esta tabla, y mientras no se descubran algoritmos de factorización más avanzados, las claves RSA de 1024 bits son todavía seguras. Pero las claves de menos de 768 bits, especialmente las de 512 bits, son tremendamente vulnerables. Si tenemos en cuenta que las versiones internacionales de los navegadores sólo pueden utilizar claves asimétricas de 512 bits, vemos claramente que los certificados de usuario que se generan en la actualidad son susceptibles de ataque por entidades con recursos moderados.
Por cierto, TWINKLE es la abreviatura de "The Weizmann INstitute Key Locating Engine".
Más información:
TWINKLE
http://www.rsa.com/rsalabs/html/twinkle.html
http://www.rsa.com/pressbox/html/990504.html
http://www.rsa.com/rsalabs/html/twinkle_qa.html
http://jya.com/twinkle.eps
http://ceu.fi.udc.es/art-gpul/RSA_512bit_optic_cracker_design.txt
http://catless.ncl.ac.uk/Risks/20.38.html
Factorización RSA-140:
http://jya.com/rsa140.htm
Más información sobre los OpenBadges
Donación BitCoin: 19niBN42ac2pqDQFx6GJZxry2JQSFvwAfS
