Le commerce électronique en danger ?
G. Guillerm1
,
J. Marchand2
,
F. Morain3
,
P. Zimmermann4
26 août 1999
Les codes secrets ont toujours fasciné le grand public. Décrypter
les dépêches ennemies a très souvent joué un rôle dans
l'Histoire, dans la diplomatie, pendant les conflits. De nos jours,
les systèmes de chiffrement sont employés dans les transactions
numériques (commerce électronique) et plus près de nous dans
nos portefeuilles (cartes à puce pour le paiement, pour la
santé). Le record décrit ici montre que ces systèmes sont en danger.
Casser les codes de protection se ramène très fréquemment au problème
suivant : étant donné un nombre, comment le brise-t-on (on dit
encore qu'on le factorise) en ses
parties élémentaires, les nombres premiers ? Par exemple, on
peut écrire 6 sous la forme 2× 3 et on ne peut aller plus
loin, 2 et 3 sont premiers. Les nombres considérés dans le
cadre des systèmes de chiffrement modernes (comme le célèbre
RSA, du nom de ses inventeurs Rivest, Shamir et Adleman en 1976) sont
bien sûr plus grands que 6, ils s'écrivent avec 100 à 200
chiffres, et pour les implantations les plus courantes, avec 155
chiffres ou encore 512 chiffres binaires (bits). Factoriser ces
nombres est un problème ardu sur lequel les mathématiciens se
cassent les dents depuis des millénaires. À l'époque où RSA a
été inventé, factoriser des nombres de 512 bits relevait de la
Science-Fiction. Vingt-cinq années ont passé et cette barrière
psychologique vient d'être franchie, l'inconcevable est devenu réalité.
Les meilleures méthodes de factorisation connues à ce jour sont très
sophistiquées et difficiles à mettre en oeuvre. Les temps de
calcul mis en jeu sont colossaux : plusieurs dizaines d'années
de temps d'ordinateur...Pour les atteindre en quelques mois de temps
humain, on répartit les tâches entre plusieurs centaines de
machines, généralement des stations de travail ou des ordinateurs
personnels (PC).
Pour être à même de mesurer les progrès établis dans le
domaine de la factorisation, la firme américaine RSA, Inc. (du nom
du cryptosystème) parraine un concours de factorisation de
nombres. Des listes sont disponibles sur leur site
Web
et des prix sont accordés chaque trimestre. Dans
cette liste, on trouve ainsi le nombre appelé RSA155, qui
matérialise cette barrière psychologique des 512 bits.
S'attaquer à RSA155 nécessite d'utiliser la meilleure méthode de
factorisation connue, qu'on appelle le crible algébrique,
inventé par J. Pollard en 1988. Cet algorithme présente deux
phases. Dans la première, la plus gourmande en temps, des milliards
de données sont calculées pour préparer la deuxième phase qui
aboutira à la découverte des facteurs du nombre.
Les meilleurs spécialistes du domaine, A. K. Lenstra et
P. L. Montgomery se sont attelés à l'écriture des programmes
nécessaires, et les calculs ont été répartis entre 300
ordinateurs de 11 équipes triées sur le volet, représentant 6
pays (Pays-Bas, USA, Canada, Australie, Royaume Uni, France), sous la
coordination de H. te Riele au CWI (Amsterdam). On y
trouve ainsi trois laboratoires français : deux à l'École
polytechnique (Laboratoire d'Informatique --
LIX,
F. Morain,
avec l'aide de G. Guillerm du SITX ;
l'UMS Medicis,
J. Marchand),
et le Centre Charles Hermite
(P. Zimmermann à Nancy).
Nos trois équipes ont
fourni un tiers de l'effort nécesaire. Ce n'est pas une surprise,
car ces trois laboratoires disposent de fortes compétences reconnues
internationalement en calcul formel, théorie des nombres et
cryptographie, alliées à de puissants moyens de calcul.
Donnons quelques détails sur le record. Les calculs ont commencé
le 27 avril 1999 et la première phase s'est terminée
le 13 juillet. La seconde s'est achevée le 22 août, par
la découverte des deux facteurs premiers du nombre :
RSA155 =
1094173864157052742180970732204035761200373294544920599091384213147634\
9984288934784717997257891267332497625752899781833797076537244027146743\
531593354333897
=
102639592829741105772054196573991675900716567808038066803341933521790711307779
*
106603488380168454820927220360012878679207958575989291522270608237193062808643
La première phase a nécessité environ 8000 années de
MIPS5
, la seconde 224 heures
sur le Cray-C916 du SARA à Amsterdam.
Un pas important a été franchi. Utiliser RSA (et plus
généralement tout système dont la sécurité repose sur la
factorisation des entiers) avec des clefs de 512
bits assure une protection qui n'est plus inviolable mais
limitée dans le temps. Il n'a fallu que quelques mois et finalement
assez peu de ressources pour casser cette clef. 300 PC sont faciles à
rassembler (1 PC coutant 5 kF, l'attaque revient tout compris à
environ 2 MF), même si la phase finale des calculs demande à
l'heure actuelle un super-ordinateur et une grande mémoire centrale.
Dans le combat éternel entre l'épée et le bouclier, celle-là
vient de reprendre un peu d'avance sur celui-ci. Aujourd'hui,
les systèmes utilisant des clefs de 768 ou 1024 bits restent hors
d'atteinte. Pour combien de temps ?
- 1
- École polytechnique, SITX
- 2
- École polytechnique, UMS MEDICIS
- 3
- DGA/École polytechnique, UMR LIX, morain@lix.polytechnique.fr
- 4
- INRIA Lorraine, UMR LORIA, Paul.Zimmermann@loria.fr
- 5
- Le MIPS est l'acronyme de ``Million Instructions Per
Second'', correspondant à la puissance d'un VAX 780, exécutant 1
million d'opérations à la seconde. Même si une telle machine
n'existe plus, la dénomination a perduré. On peut traduire en
disant que 8000 années de MIPS correspondent à
32 années d'un processeur à 250 MHz.
This document was translated from LATEX by HEVEA.