« Nous ne doutions pas que cela allait marcher. Mais la dernière étape a duré plus longtemps que prévu et a donné des sueurs froides à notre collègue de l'EPFL [Ecole Polytechnique Fédérale de Lausanne] », se souvient Pierrick Gaudry responsable à l'Inria du calcul géant qui a permis, fin décembre, de casser une "clé" informatique*. Cette clé numérique est en fait un grand nombre de 232 chiffres (768 bits en écriture binaire avec des 0 et des 1) servant à protéger la confidentialité des transactions par cartes bancaires ou sur Internet (par la méthode dite RSA). Elle permet en effet de générer d'autres nombres servant à coder et décoder les informations sensibles lors de ces opérations.

La « casser » revient en fait à trouver deux nombres qui sont des nombres premiers de 116 chiffres dont le produit redonne le nombre de 232 chiffres. En terme plus mathématique, il s'agit d'une factorisation. Il aura fallu environ deux ans de calculs pour y parvenir et 1500 ordinateurs en réseau (notamment ceux de la grille de calcul française, Grid5000). « Sur le plus gros réseau d'ordinateurs, le Jaguar du Département américain de l'Energie, cela n'aurait pris qu'une dizaine de jours avec ses 200000 processeurs », estime Pierrick Gaudry. Fort heureusement les clés vraiment utilisées actuellement dans les cartes bancaires et sur Internet sont plus grandes : plus de 900 bits ; certaines dépassant les 4000 bits.

Un des plus gros calculs jamais réalisé

« C'est sans doute l’un des plus gros calcul algébrique qu'un ordinateur ait effectué à ce jour », estime Pierrick Gaudry. Une vingtaine de programmes différents ont été nécessaires pour venir à bout de ce calcul.

La première étape consiste, comme souvent en maths, à changer le problème à résoudre. Plutôt que de factoriser le grand entier N de 232 chiffres, la méthode vise à trouver un couple de nombres X et Y dont les carrés sont égaux « modulo N » (C'est-à-dire que Y² est le reste de la division euclidienne de X² par N))... Un théorème mathématique explique ensuite comment trouver les facteurs premiers de N à partir de X et Y. Reste donc à fabriquer pas à pas ces nombres.

C'est le but de la seconde étape, qui elle aussi a l'air de contourner encore le problème. Les mathématiciens construisent des polynômes et testent leurs valeurs sur un grand ensemble de points (plus exactement des paires d'entiers). Le test, ou crible, permet de trouver de nouveaux entiers dont le produit donnera X et Y. « C'est la phase la plus longue. Elle occupe les trois quarts du temps de calcul », précise Pierrick Gaudry. A la fin du crible, il reste tout de même quelques 64 milliards de nombres pour alimenter la troisième et avant-dernière étape.

Cette fois il s'agit d'effectuer un calcul algébrique sur une matrice géante de quelques 192 millions de lignes et autant de colonnes. Soit 100 Go occupé en mémoire. Le résultat de l'exploration de la matrice doit fournir les bons X et Y.

Le sprint avant Noël

Il ne reste alors plus qu'à faire une sorte de racine carré pour trouver les bons nombres premiers. « Cette étape n'aurait dû prendre qu'un jour. A cause de deux bogues elle a pris plus de temps et comme nous voulions finir avant Noël, nous avons travaillé dur pour résoudre ces difficultés », se souvient Thorsten Kleinjung, le responsable de cette ultime phase à l'EPFL. Le 12 décembre, Thorsten Kleinjung peut envoyer le mél de victoire contenant les deux nombres de 116 chiffres.

L'ascension d'une telle montagne numérique, qui plus est inutile pour vider les coffres d'une banque, n'est pas une simple épreuve de maths sportives. Enormément de calculs arithmétiques demandent à un moment de factoriser les nombres. La méthode du crible algébrique, utilisée ici, est donc très prisée. Le moindre progrès, même de quelques pourcents, est donc appréciable en temps de calcul. « Arithmétique, informatique, algèbre... ce calcul nous fait voyager dans plein de domaines », conclut Pierrick Gaudry.

David Larousserie
Sciencesetavenir.fr
29/04/2010

Retrouvez d’autres exploits dans notre numéro actuellement en vente :

- comment faire une transaction sans code PIN

- comment casser les cartes à puces en les « écoutant »

- comment crypter ses emails ou surfer anonymement

*L’équipe comprenant l'INRIA Nancy - Grand Est et ses partenaires suisses, japonais, hollandais et allemands (EPFL, CWI, NTT, Université de Bonn)

Authors: Nouvel Obs

pour en savoir plus...