|
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.
|
