Bernard Fabrot resuelve el problema LCS35 de Rivest (R de RSA)

Por Francisco R. Villatoro, el 2 mayo, 2019. Categoría(s): Ciencia • Informática • Noticias • Personajes • Science

En 1999 el famoso Ronald L. Rivest (la R del cifrado RSA) propuso un problema de criptoanálisis llamado LCS35. La solución se guardó en una cápsula del tiempo que solo sería abierta antes del 02 de abril de 2034 si alguien lograba resolver el enigma. El informático belga Bernard Fabrot ha publicado la solución el pasado 15 de abril de 2019. El problema se ha resuelto en 20 años, en lugar de los 35 años predichos por Rivet usando la ley de Moore.

Rivet ofreció un código en Java para resolver el problema. Pero Fabrot ha desarrollado un código propio escrito en C usando el software libre GMP (GNU Multiple Precision Arithmetic Library). Este algoritmo de fuerza bruta ha sido ejecutado de forma continua durante tres años y medio en uno de los núcleos (cores) de su ordenador personal. El algoritmo ha realizado unos 80 billones de operaciones de elevar al cuadrado para obtener la solución. Así se ha adelantado al proyecto Cryptophage, liderado por Simon Peffers del MIT, que está desarrollando un hardware específico basado en chips FPGA para resolver el problema de Rivet. Ya en funcionamiento, se estima que obtendrá la solución el próximo 10 de mayo de 2019, tras solo dos meses de trabajo. Por desgracia, Fabrot se les ha adelantado por muy poquito.

La ceremonia de apertura de la cápsula del tiempo de Rivet será el 15 de mayo de 2019. Para entonces Cryptophage ya debería haber obtenido la solución de forma independiente a Fabrot. Más información en Daniel Oberhaus, «A programmer solved a 20-year old, forgotten crypto puzzle,» Wired.com, 29 Abr 2019.

El problema LCS35 consiste en calcular w = 2^(2^t) (mod n), con t un número de 14 dígitos y n un número de 616 dígitos (ver la figura); una vez calculado w se usará para descifrar el mensaje cifrado en el número z, también de 616 dígitos (ver la figura), usando la operación lógica xor (o-exclusivo, o suma binaria sin acarreo). El mensaje descifrado contiene la factorización del número n en dos factores primos (así se verifica de forma sencilla si el problema ha sido resuelto correctamente).

El propio Rivet nos proponía un ejemplo sencillo del problema. Sea n = 11*23 = 253, y t = 10. Para resolver el problema hay que calcular:
2^(2^1) = 2^2 = 4 (mod 253)
2^(2^2) = 4^2 = 16 (mod 253)
2^(2^3) = 16^2 = 3 (mod 253)
2^(2^4) = 3^2 = 9 (mod 253)
2^(2^5) = 9^2 = 81 (mod 253)
2^(2^6) = 81^2 = 236 (mod 253)
2^(2^7) = 236^2 = 36 (mod 253)
2^(2^8) = 36^2 = 31 (mod 253)
2^(2^9) = 31^2 = 202 (mod 253)
w = 2^(2^t) = 2^(2^10) = 202^2 = 71 (mod 253)

Así se obtiene el valor w = 71 = 47 (hexadecimal). Si el valor de z = 13 (hex), entonces el mensaje será (47 xor 13) = 54 (hex). Este número se interpreta como un texto codificado en ASCII con 8 bits (dos dígitos hexadecimales) por carácter, es decir, ASCII 54 (hex) = «T».



Deja un comentario