LCS35

LCS35 es un desafío criptográfico y un rompecabezas de bloqueo de tiempo creado por Ron Rivest en 1999. El desafío consiste en calcular el valor

$${\displaystyle w=2^{2^{t}}{\pmod {n}}}$$

donde t es un entero específico de 14 dígitos (o 47 bits) , concretamente 79685186856218, y n es un entero específico de 616 dígitos (o 2048 bits) que es el producto de dos primos grandes (que no se proporcionan). El valor de w se puede utilizar para descifrar el texto cifrado z , otro entero de 616 dígitos. El texto plano proporciona la información oculta sobre la factorización de n , lo que permite verificar fácilmente la solución.

La idea detrás del desafío es que la única forma conocida de hallar el valor de w sin conocer la factorización de n es mediante t elevaciones al cuadrado sucesivas. El valor de t se eligió de manera que este cálculo por fuerza bruta requiriera aproximadamente 35 años, tomando como punto de partida las velocidades de los chips de 1999 y teniendo en cuenta la ley de Moore . Rivest señala que "así como un fallo de la ley de Moore podría hacer que el problema sea más difícil de lo previsto, un avance en el arte de la factorización lo haría más fácil de lo previsto".

El desafío se planteó durante (y toma su nombre de) las celebraciones del 35 aniversario del Laboratorio de Ciencias de la Computación del MIT, que ahora forma parte del Laboratorio de Ciencias de la Computación e Inteligencia Artificial del MIT .

El desafío LCS35 fue resuelto el 15 de abril de 2019, veinte años después, por el programador Bernard Fabrot. ^{[ 1 ] [ 2 ]} El texto plano comienza con "!!!  Feliz cumpleaños LCS  !!!". ^{[ 3 ]}

El 14 de mayo de 2019, Ronald L. Rivest publicó una nueva versión de LCS35 (llamada CSAIL2019) para extender el rompecabezas hasta el año 2034. ^{[ 4 ]}

• Descripción del rompecabezas criptográfico Cápsula del Tiempo LCS35 , Ronald L. Rivest
• Ceremonia de apertura de la cápsula del tiempo