LCS35
LCS35 est un défi cryptographique ou casse-tête posé par Ronald Rivest en 1999. Le défi est de calculer la valeur
- ,
où t=79 685 186 856 218 est un entier de 14 chiffres décimaux (ou 47 bits),et où n est un entier de 616 chiffres décimaux (ou 2048 bits) qui est le produit de deux grands nombres premiers (qui ne sont pas donnés).
Description
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
- pour ,
et on calcule .
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].
Historique
Le défi a été lancé à l'occasion des célébrations du 35e 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].
Notes et références
- Jean-Paul Delahaye, « Envoyer des messages à retardement », Pour la Science, no 518, .
- Ronald L. Rivest « Description of the LCS35 Time Capsule Crypto-Puzzle », 4 avril 1999.
- « Programmers solve MIT’s 20-year-old cryptographic puzzle | MIT CSAIL », sur www.csail.mit.edu
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « LCS35 » (voir la liste des auteurs).
