|
An
1994
Un message de 127 chiffres déchiffré après 17 ans
de progrès informatiques.
Le
message crypté:
Message publié en 1977 par
Martin Gardner
dans Scientific American et proposé par trois
chercheurs du Massachusetts Institute of Technology
MIT [èm-aï-ti]): Ronald Rivest, Adi Shamir et
Léonard Adleman.
Il s'agit d'un système de cryptographie à clef publique, nommé RSA d'après leurs initiales.
On pensait qu'il faudrait des milliards
d'années avant de percer
le code.
Pourtant en 1994, Arjen Lenstra, des Laboratoires
Bell, aidé de passionnés d'informatique
et de plus de 600 abonnés au réseau
Internet, ont cassé le code après huit mois de travail.
Le
codage:
Le codage RSA transforme
un texte en un nombre.
Celui-ci est
élevé à un certain exposant. On détermine le reste de la division
entière du résultat par un grand nombre donné, nommé module.
Le module et
l'exposant sont publiés, rendus
publiques.
Le décodage nécessite la
connaissance
de deux nombres
premiers qui, multipliés l'un par
l'autre, donnent la clef publique.
Or, il est extraordinairement
difficile de déterminer les facteurs
premiers des grands nombres.
La résolution:
Le code du message objet de la
récompense utilisait un module de
129 chiffres.
La factorisation ainsi
obtenue est l'un des calculs les
plus compliqués qu'on n'ait jamais
effectué.
Plus de 1600
ordinateurs ont été utilisés à travers le monde, débitant leurs résultats
dans une base de données exploitée ensuite par un superordinateur
massivement parallèle.
Le nombre de
129 chiffres a été décomposé en
deux nombres de 64 et 65 chiffres.
Le message était: " Les mots magiques
sont un ossifrage
nauséeux ", formé de
mots tirés au hasard.
On ne connaît pas
d'algorithmes
efficaces de factorisation des très grands nombres. On n'a pas démontré
qu'ils n'existent pas.
|
