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