Sites Inria

Télécoms, réseaux, multimédia

8/01/2010

Inria et ses partenaires battent un nouveau record de calcul et démontrent la vulnérabilité d’une clé RSA de 768 bits

Quatre ans après le dernier record qui a permis de casser une clé RSA de 663 bits, Inria et ses partenaires démontrent la vulnérabilité d’une clé RSA de 768 bits. En conjuguant différentes capacités de calcul mises à leur disposition pendant deux ans et demi, ils sont parvenus à casser cette clé de 232 chiffres en retrouvant les facteurs premiers qui la composent. Ce nouveau record est une belle illustration de l’efficacité des systèmes de calcul distribué. Il confirme les recommandations de l’Agence nationale de la sécurité des systèmes d’information (ANSSI) en démontrant la vulnérabilité d’une clé RSA de 768 bits.
 

Un nouveau record de calcul réalisé sur une architecture distribuée

L’équipe CACAO ("Courbes, algèbre, calculs, arithmétique des ordinateurs") d’Inria Nancy - Grand Est (commune à Nancy-Université et au CNRS) et ses partenaires suisses, japonais, hollandais et allemands (EPFL, CWI, NTT, université de Bonn) ont mis en commun différentes capacités de calcul pour réussir à factoriser une clé RSA de 768 bits. Pour réaliser ce calcul à grande échelle, Inria a recouru à une partie de l’infrastructure Grid’5000 qui relie en France 1544 machines, soit plus de 5 000 cœurs. Au total, avec l’intervention des autres partenaires, ce sont l’équivalent de 1 700 cœurs utilisés pendant un an, soit 425 PC quadricœurs pendant un an, qui ont été mobilisés.
Différentes étapes ont été nécessaires pour mener à bien ce projet dont la première a consisté à collecter plus de 64 milliards de relations (1). Cela a nécessité plusieurs espaces disque (5 Tera-octets, copies de sauvegarde et espace de travail). Pour garantir la bonne exécution du calcul, l’intégrité des données, qui ont circulé d’un bout à l’autre de la planète, a dû être vérifiée en permanence.
Le calcul a démarré il y a deux ans et demi. Inria, seul intervenant français, a rejoint le projet en 2008 et a contribué à 37% du résultat global (en ressources de calcul). L’équipe a notamment apporté son expertise pour élaborer un protocole d’utilisation des machines et rassembler le nombre nécessaire de relations. Selon Paul Zimmermann, directeur de recherche au sein de l’équipe CACAO « Réaliser un tel calcul en recourant à un outil comme Grid’5000 montre l’efficacité de solutions de calcul distribué ou grilles de calcul. Ces dernières représentent une alternative très sérieuse aux supercalculateurs. En rassemblant des ressources simples, à l’échelle d’un PC, elles sont efficaces à moindre coût.  »

De la nécessité de démontrer la vulnérabilité des systèmes cryptographiques

Les systèmes cryptographiques garantissent la sécurité des échanges de données sur Internet, ils sont au cœur du commerce électronique. S’assurer de leur fiabilité est dès lors crucial. Casser les codes de protection d’un système de cryptographie conduit à chercher de nouvelles solutions et donne les arguments pour favoriser l’adoption de systèmes plus sécurisés.
Les systèmes à clé publique (les clés pour chiffrer et déchiffrer sont différentes, destinataire et expéditeur du message n’utilisent pas la même clé) permettent d’échanger des informations confidentielles ou de signer électroniquement des documents allant de l’Internet aux cartes à puces. L’algorithme RSA (pour Rivest Shamir Adleman ) fait partie de cette famille de systèmes.
Pour casser de telles clés, il faut retrouver les facteurs premiers qui la composent. Une clé RSA-768 qui a été factorisée est un nombre de 232 chiffres d’où le besoin d’utiliser de grandes capacités de calcul pour la factoriser.
D’après la loi de Moore, la puissance des ordinateurs double tous les 18 mois. Il convient donc de s’assurer régulièrement de la solidité des clés mises sur le marché au vu des capacités de calcul sans cesse croissantes des ordinateurs et des progrès algorithmiques.
Le résultat atteint par Inria et ses partenaires prouve de manière catégorique la fragilité d’une clé RSA de 768 bits.
Il confirme les recommandations de l’ANSSI (Agence nationale de la sécurité des systèmes d’information) qui invite à ne pas utiliser de clé de taille inférieure à 2048 bits pour une utilisation au-delà de 2010. Ce résultat lui donne l’argument décisif, pour convaincre les derniers utilisateurs de clés RSA de 768 bits (ou moins) de changer de solution. Tout système de chiffrement basé sur de telles clés sous-dimensionnées, qui serait encore inclus dans les transactions numériques (commerce électronique), les puces de cartes bancaires ou autre système, s’avère en effet dès lors résolument inadapté.

La factorisation de RSA-768 est :

RSA-768 =
3347807169895689878604416984821269081770479498371376856891
243138898288379 38780022876147116 52531743087737814467999489 * 367460436667995904282446337996279526322791581643430876426760
322838157396665112792 333734171 43396810270092798736308917

À propos

Inria

Établissement public à caractère scientifique et technologique, sous tutelle des ministères chargés de la Recherche et de l'Industrie. Dirigeants : Michel COSNARD, Pdg d'Inria - Jean-Pierre VERJUS, directeur général adjoint. Budget annuel (2009) : 200 M€ dont 21% de ressources propres. Centres régionaux de recherche : Paris - Rocquencourt, Sophia Antipolis – Méditerranée, Grenoble - Rhône-Alpes, Nancy - Grand Est, Rennes - Bretagne Atlantique, Bordeaux – Sud Ouest, Lille - Nord Europe, Saclay - Île-de-France. 2800 chercheurs, dont plus de 1000 doctorants, travaillant dans plus de 160 équipes-projets dontla plupart sont communes avec d’autres organismes, des grandes écoles, des universités. 790 contrat s de recherche actifs. 79 équipes associées dans le monde. 94 entreprises créées depuis 1984.

Mots-clés : Sécurité des données Algorithme RSA Equipe CACAO Architecture distribuée Cryptographiqe Communiqué

Haut de page

Suivez Inria