LCS35

La valeur de w peut servir à décrypter une donnée cryptée z, elle-même un entier de 616 chiffres décimaux. Le texte en clair fournit les informations cachées sur la factorisation de n, ce qui permet de vérifier facilement la solution. La motivation initiale étant de tester la possibilité de créer un fichier dont la lecture est garantie impossible avant une date fixée[1].

L'idée à la base du défi est que la seule façon connue de trouver la valeur de w sans connaître la factorisation de n est d'effectuer les t carrés successifs en commençant par 2 ; autrement dit on pose

${\displaystyle W(0)=2}$

${\displaystyle W(i+1)=W(i)^{2}({\bmod {n}})}$ pour ${\displaystyle i>0}$,

et on calcule ${\displaystyle w=W(t)}$.

La valeur de t a été choisie pour faire en sorte que ce calcul de force brute prenne environ 35 ans, en prenant comme point de départ les vitesses des chips de 1999 et en tenant compte de la loi de Moore. Rivest note que « tout comme un ralentissement dans la loi de Moore pourrait rendre le puzzle plus difficile à résoudre que prévu, une percée dans l'art de la factorisation rendrait le puzzle plus facile que prévu ». Dans les faits, c'est la mise au point de hardware spécifiquement conçu pour ce type de calcul qui va accélérer la conclusion de l'expérience[1].

Le défi a été lancé à l'occasion des célébrations du 35^e anniversaire du Laboratoire d'informatique du MIT, laboratoire qui fait maintenant partie du MIT Computer Science and Artificial Intelligence Laboratory (MIT CSAIL)[2].

Il a été confirmé, sur le site du MIT CSAIL que Bernard Fabrot a résolu le défi LCS35[3] 15 ans plus tôt qu'estimé par Rivest[1].

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « LCS35 » (voir la liste des auteurs).

• LCS35 Time Capsule Crypto-Puzzle : le casse-tête du MIT datant de 1999 a été résolu
• Un programmeur belge résout le casse-tête cryptographique du MIT vieux de 20 ans