Ron Rivest en persona –lo cual siempre es agradable– explica en este vídeo de Numberphile unas cuantas cosas sobre el RSA-129, un número de 129 dígitos decimales (y 426 bits) que usaron como un reto criptográfico que tardó 17 años en resolverse.
Originalmente se decía que se necesitarían 40.000 billones de años para resolver el problema, que se publicó en la columna de Martin Gardner en Scientific American en agosto de 1977, pero de hecho se resolvió en abril de 1994. ¿El premio? Fama mundial y 100 dólares, lo primero que se les ocurrió a los matemáticos.
Siempre he pensado que los 100 dólares que pagamos a los que resolvieron el reto debieron ser la compra más barata de potencia de computación que se haya hecho jamás.
– Ron Rivest
Los problemas de factorización son una de las bases del algoritmo criptográfico RSA que protege todo tipo de comunicaciones y sistemas. Básicamente aprovecha la asimetría que hay entre un problema y su función inversa, algo que se conoce técnicamente como función de un solo sentido. En este caso en concreto: es muy fácil multiplicar dos números, pero es bastante más complicado descomponer un número en factores primos si resulta que esos factores son dos números primos relativamente grandes – como descubre cualquier estudiante de matemáticas de ESO tan pronto como aprende el concepto de factorización.
Rivest cuenta que ni siquiera se acuerda de cómo eligieron los números, que seguramente probaron con diversos números grandes al azar, comprobando si eran primos (lo cual es relativamente fácil mediante diversos algoritmos) y luego los multiplicaron. El «reto RSA» era encontrar esos dos números, llamados p y q cuyo producto fuera el número publicado. Si la gente les enviaba un resultado solo tenían que multiplicarlos para comprobar si la solución era correcta. ¿Por qué? Ni siquiera apuntaron los números p y q originales que generaron. De ese modo, dice, «queríamos evitar que la gente pudiera robarlos o hacer algún truco raro».
RSA-129 =
114381625757888867669235779976146\
612010218296721242362562561842935\
706935245733897830597123563958705\
058989075147599290026879543541
y sus factores p y q son
p = 349052951084765094914784961990\
3898133417764638493387843990820577
y
q = 327691329932667095499619881908\
34461413177642967992942539798288533
Para dar con la solución un equipo de expertos combinó tres factores a principios de los 90: mejores algoritmos de factorización, ordenadores mucho más potentes y un equipo humano que trabajaba unido a través de –la por entonces todavía primitiva– Internet.
Más adelante se superaron otros retos y se factorizaron números de 200 dígitos (el RSA-200) y más allá, hasta el RSA-768 [Nota: la numeración a veces corresponde con dígitos decimales, como el RSA-129, a veces con dígitos binarios, como el RSA-768, que tiene 232 dígitos decimales). Los números mayores que el RSA-768 no han sido factorizados todavía. El más inabarcable de los planteados hasta la fecha es el legendario RSA-2048, con nada más y nada menos que 617 dígitos decimales.
Lo mejor del algoritmo RSA, que todavía se usa, es que como dice Rivest si se descubre que alguien tiene potencia computacional como para romper las claves de un tamaño determinado, «simplemente se usan otras más grandes y problema resuelto». Hoy en día son muchos los productos que permiten usar 1024 bits (ya se hablaba en 2005 de este nivel), 2048, 4096 o más para esos gigantescos números pseudo-primos.
Por cierto para el reto del RSA-2048 sigue en pie un premio de 200.000 dólares y para los anteriores también hay suculentos dinerillos esperando.
Relacionado:
- Nuevo récord de factorización de números «casi-primos»: 307 dígitos
- El número RSA-576, factorizado
- Factorizado un número RSA de 200 dígitos
- RSA de 1.024 bits ya no es suficiente
- La base matemática de los sistemas de cifrado en criptografía
- The Music of the Primes
- Sneakers y la máquina de factorización universal
