NeoFronteras

Han conseguido factorizar un número de 307 cifras lo que constituye una marca mundial en factorización y acota el tamaño de los números por defecto que usan los sistemas de cifrado.
Desde los tiempos de Julio Cesar, que usaba una sistema de cifrado para mandar mensajes secretos a sus tropas, a la segunda guerra mundial, cuando los alemanes usaban la famosa máquina Enigma, la humanidad ha necesitado de comunicaciones seguras.
Ahora cuando usted se conecta con su banco a través de una web usa un protocolo especial: https. Éste es diferente del habitual http, la «s» extra nos garantiza que la comunicación con el banco es segura y que ningún ladrón va a transferir nuestros fondos a otro sitio.
Las compras en Internet o la conexión a una terminal remota mediante la shell ssh también están cifradas para mantener a terceros lejos de nuestra tarjeta de crédito o lejos de nuestra cuenta en un servidor Linux.
Todos esos sistemas usan un sistema de cifrado desarrollado a partir de un algoritmo de finales de los años setenta denominado RSA (por R. Rivest, A. Shamir y L. Adelman que lo desarrollaron) y basado en el uso de números grandes.

El RSA, sistema increíblemente elegante y bello, está basado en una clave numérica pública y otra privada. Supongamos que una tal Cleopatra adoptase este sistema. Entonces podría publicar su clave pública compuesta por un número m y otro e en los papiros amarillos del Nilo. De este modo cualquiera podría mandarle un mensaje secreto traduciendo a números las letras del mensaje, pero sólo ella podría descifrarlo usando su clave secreta d que es un número apropiado y relacionado matemáticamente con m y e. En RSA no se necesita mandar clave secreta a nadie y todo el sistema es «abierto».
Cleopatra también podría usar su clave privada d para cifrar un mensaje suyo y que cualquiera pueda descifrarlo con la clave pública que está en los papiros amarillos del Nilo.

Este sistema es tan elegante que incluso permite la firma electrónica. Si Marco Antonio quiere mandar un mensaje secreto a Cleopatra pero quiere convencerla de que ha sido él quien lo ha mandado puede hacer lo siguiente:

– Cifrar el mensaje con la clave privada de Marco Antonio y añadir su firma.
– Cifrar el conjunto con la clave pública de Cleopatra.

Cleopatra sólo necesita descifrar el mensaje recibido con su clave privada, eliminar la firma de Marco Antonio y descifrar el resto con la clave pública de Marco Antonio.
Sustitúyase a Cleopatra y a Marco Antonio por dos computadoras y ya tendremos el comercio electrónico funcionando.

Toda la seguridad del sistema RSA se basa en que el número m en cada caso (cada usuario tiene uno) es el producto de dos números primos aleatorios muy grandes p y q que se mantienen en secreto y que permiten el cálculo del descifrado sin mucha dificultad.
Aunque es relativamente fácil identificar números primos muy grandes, es muy difícil factorizar (descomponer en factores primos) un número compuesto en sus factores primos. No hay algoritmos eficientes que lo hagan o nadie los conoce aún. Aunque todo el mundo sepa el valor de m, si es muy grande no hay manera de calcular p y q de tal modo que p × q = m.
Bueno, sí hay manera si el número es lo suficientemente pequeño y disponemos de suficientes ordenadores potentes, entonces sí es posible.
La compañía RSA Laboratories publicó una lista con números muy grandes y desafió a la comunidad internacional a factorizarlos ofreciendo premios que van de 10.000 a 200.000 dólares. El desafío se ha convertido en una especie de juego o deporte entre algunos matemáticos y algunos han ganado un dinero con él.
En 2003 fueron capaces de factorizar RSA-576. En noviembre de 2005 y después de 18 meses de cálculos consiguieron factorizar el número RSA-640, un número de 200 cifras.

Ahora Thorsten Kleinjung de la Universidad de Bonn y sus colaboradores de la compañía japonesa NTT y de la Ecoles Polytechniques Fédérale de Lausannes (EPFL) ha conseguido factorizar un número específico no aleatorio de 307 cifras que en binario tiene 1017 bits, y que por cierto no está en la lista mencionada.
El sistema por defecto de RSA está basado ahora en números de 1024 bits. Ya en 1999 se aconsejó pasar del sistema de 512 bits al de 1024, y es de esperar que a partir de este momento se pase a un sistema de 2048, aunque quizás queden muchos años hasta que se rompa el sistema de 1024 bits. De hecho ya se aconseja el sistema de 2048 y algunos protocolos como el ssh usan claves públicas de ese tamaño desde hace tiempo.
Para factorizar el número que tratamos aquí usaron una criba de números especiales (GNFS o General Number Field Sieve) desarrollada en los ochenta por Arjen Lenstra (entonces en Bellcore), su hermano Hendrik (UC Berkeley), John Pollard y Mark Manasse (DEC) y un truco denominada «paso de matriz» que además han conseguido distribuir ahora en un conjunto de computadoras emplazadas en diferentes ubicaciones. La idea era buscar un sistema para poder distribuir un algoritmo sobre una arquitectura dada y sacar ventaja del comportamiento de la caché.

Necesitaron 11 meses de tiempo real y mucho tiempo de CPU (tiempo de computación) para factorizar este número. Los pasos efectuados y los tiempos empleados fueron los siguientes:

– Búsqueda de candidatos (tiempo de CPU: 125.7 años de Opteron-248).
– Criba (tiempo de CPU: 5 años de Pentium-D).
– Álgebra lineal (tiempo de CPU: dos meses en dos clusters de NTT con 146 PC).
– Cálculo de raíz (tiempo de CPU: varias horas en el cluster de la Universidad de Bonn).

Fueron capaces de factorizar este número un tanto especial porque al estar relacionado con un número de Mersenne su estructura permitió calcular su factorización fácilmente. Hacer lo mismo con números de tamaño equivalente pero aleatorios es casi imposible de momento.
Este equipo de investigadores pretende mejorar sus algoritmos en el futuro y afrontar el desafío RSA-704 en algún momento. Pero probablemente se tardarán muchos años antes de que se pueda romper el RSA-1024.
Para aquellos que quieran ganar el dinero del premio pueden consultar los desafíos RSA e intentarlo si saben suficiente informática y teoría de números.

Aunque algunos han propuesto que quizás ciertos individuos puedan esclavizar con un virus decenas de miles de videoconsolas en red tipo Play Station 3 (optimizadas para cálculos con números) para así romper los códigos aleatorios RSA y efectuar fraudes, la posibilidad es reducida, sobre todo si los demás les sacamos ventaja con claves más grandes.
Ordenadores más potentes permiten romper más fácilmente los códigos, pero también nos permiten a los demás cifrar mensajes con números más grandes.
Las matemáticas tienen a veces rentabilidad económica inmediata. El algoritmo RSA fue patentado (la patente expiró hace pocos años) y hay una empresa que explota la idea. Sin RSA el comercio electrónico sería imposible.
Por cierto, el número de 307 cifras en cuestión y su factorización son:

1 1 5 9 4 2 0 5 7 4 0 7 2 5 7 3 0 6 4 3 6 9 8 0 7 1 4 8 8 7 6 8 9 4 6 4 0 7 5 3 8 9 9 7 9 1 7 0 2 0 1 7 7 2 4 9 8 6 8 6 8 3 5 3 5 3 8 8 2 2 4 8 3 8 5 9 9 6 6 7 5 6 6 0 8 0 0 0 6 0 9 5 4 0 8 0 0 5 1 7 9 4 7 2 0 5 3 9 9 3 2 6 1 2 3 0 2 0 4 8 7 4 4 0 2 8 6 0 4 3 5 3 0 2 8 6 1 9 1 4 1 0 1 4 4 0 9 3 4 5 3 5 1 2 3 3 4 7 1 2 7 3 9 6 7 9 8 8 8 5 0 2 2 6 3 0 7 5 7 5 2 8 0 9 3 7 9 1 6 6 0 2 8 5 5 5 1 0 5 5 0 0 4 2 5 8 1 0 7 7 1 1 7 6 1 7 7 6 1 0 0 9 4 1 3 7 9 7 0 7 8 7 9 7 3 8 0 6 1 8 7 0 0 8 4 3 7 7 7 7 1 8 6 8 2 8 6 8 0 8 8 9 8 4 4 7 1 2 8 2 2 0 0 2 9 3 5 2 0 1 8 0 6 0 7 4 7 5 5 4 5 1 54 1 3 7 0 7 1 1 0 2 3 8 1 7 =

5 5 8 5 3 6 6 6 6 1 9 9 3 6 2 9 1 2 6 0 7 4 9 2 0 4 6 5 8 3 1 5 9 4 4 9 6 8 6 4 6 5 2 7 0 1 8 4 8 8 6 3 7 6 4 8 0 1 0 0 5 2 3 4 6 3 1 9 8 5 3 2 8 8 3 7 4 7 5 3
×
2 0 7 5 8 1 8 1 9 4 6 4 4 2 3 8 2 7 6 4 5 7 0 4 8 1 3 7 0 3 5 9 4 6 9 5 1 6 2 9 3 9 7 0 8 0 0 7 3 9 5 2 0 9 8 8 1 2 0 8 3 8 7 0 3 7 9 2 7 2 9 0 9 0 3 2 4 6 7 9 3 8 2 3 4 3 1 4 3 8 8 4 1 4 4 8 3 4 8 8 2 5 3 4 0 5 3 3 4 4 7 6 9 1 1 2 2 2 3 0 2 8 1 5 8 3 2 7 6 9 6 5 2 5 3 7 6 0 9 1 4 1 0 1 8 9 1 0 5 2 4 1 9 9 3 8 9 9 3 3 4 1 0 9 7 1 1 6 2 4 3 5 8 9 6 2 0 6 5 9 7 2 1 6 7 4 8 1 1 6 1 7 4 9 0 0 4 8 0 3 6 5 9 7 3 5 5 7 3 4 0 9 2 5 3 2 0 5 4 2 5 5 2 3 6 8 9

Referencias:
Heise.
Factorización RSA-640.
Más sobre números grandes en NeoFronteras.