L'INRIA et ses partenaires cassent une clé RSA de 768 bits

Les chercheurs de l'équipe CACAO de l'INRIA Nancy - Grand Est et leurs partenaires suisses, japonais, hollandais et allemands sont parvenu à démontrer la vulnérabilité d'une clé RSA de 768 bits, soit une clé numérique de 232 chiffres. Explications et recommandations.

Depuis 1998 et l’affaire Serge Humpich, on sait que les clés RSA (Rivest Shamir Adleman) peuvent être cassées. Mais comme souvent en matière de sécurité informatique, seul l’exemple est probant. En 1998, Serge Humpich avait cassé les clés RSA 320 bits utilisées à l’époque dans les cartes bancaires. Un an plus tard, en septembre 1999, c’était au tour d’un groupe de chercheurs de l’INRIA de casser une clé numérique de 155 chiffres et 512 bits. Depuis, les paliers tombent les uns après les autres. En décembre 2003, c’est au tour d’une clé RSA de 576 bits, soit 174 chiffres d’être violer, puis, en mai 2005, les chercheurs de l’INRIA parviennent à casser un clé de 663 bits soit une clé numérique de 200 chiffres. Aujourd’hui, un peu plus de quatre ans après leur précédent exploit, ces derniers récidivent. Ils sont parvenus, avec leurs partenaires, à démontrer la vulnérabilité d’un clé RSA de 768 bits, soit une clé numérique de 232 chiffres.

Mais comment ont-ils fait ?

Revenons tout d’abord sur le mode de fonctionnement du cryptosystème RSA. Chaque utilisateur possède une clé publique connue des autres utilisateurs et une clé privée connue de lui seul. La clé publique est constituée d’un couple (n,e) où n est le produit de deux grands nombres premiers p et q (la taille de n est dans le cas présent de 768 bits), et e est un nombre premier, plus petit que n, avec (p-1)*(q-1).La clé privée, quant à elle, est le couple (n,d) où d a la particularité que pour tout nombre M compris entre 0 et n-1 : (M^e)^d = M mod n. Ce cryptosystème permet alors deux fonctionnalités, le chiffrement et la signature. Ainsi, pour chiffrer un message M à destination d’un utilisateur dont la clé publique est (n,e), on calcule : C = M^e mod n, et on lui envoie C. Le destinataire peut alors retrouver M en calculant : M = C^d mod n.Ce système rend ainsi difficile l’obtention de la clé privée d à partir de la clé publique (n, e). Cependant si l’on peut factoriser n, alors on peut obtenir la clé privée d. C’est ce que sont parvenus à faire les chercheurs de l’INRIA. Nancy – Grand Est regroupés au sein de l’équipe CACAO (pour Courbes, Calculs, Arithmétique des Ordinateurs) avec leurs partenaires suisses, japonais, hollandais et allemands (EPFL, CWI, NTT, Université de Bonn).

Un record de calcul

Cet exploit a toutefois nécessité la mise en œuvre de moyens hors du commun. Pour parvenir à casser cette clé de 232 chiffres et à retrouver les facteurs premiers qui la composent, les chercheurs de l’INRIA et leurs partenaires ont dû mettre en commun différentes capacités de calcul. L’INRIA a utilisé une partie de l’infrastructure Grid’5000 qui relie en France 1.544 machines, soit plus de 5.000 cœurs. A cela, est venu s’ajouter la puissance de calcul de ses partenaires. Au total, ce sont l’équivalent de 1.700 coeurs qui ont ainsi été utilisés pendant un an, soit 425 PC quadri coeurs pendant un an.Parallèlement, différentes étapes ont été nécessaires pour mener à bien ce projet, rapporte le communiqué de presse de l’INRIA. » 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. » Au total, le calcul aura mis 2 ans et demi pour aboutir. Une tâche d’envergure à laquelle l’INRIA a contribué à hauteur de 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.. « , ajoute-t-il dans le communiquer.

En dessous de 2.048 bits, attention danger

Si l’on avait de sérieux doutes sur la solidité de cette clé RSA de 768 bits, preuve est faite aujourd’hui que ces soupçons étaient fondés. De fait, même si un tel décryptage n’est pas à la portée de n’importe qui, il est recommandé, ainsi que le fait l’Agence nationale de la sécurité des systèmes d’information (ANSSI), de ne pas utiliser de clé de taille inférieure à 2.048 bits pour une utilisation au-delà de 2010. Tout système utilisant des clés sous-dimensionnées serait donc inadapté. Notes[1] Une relation est une factorisation d’un entier de quelques dizaines de chiffres. Il faut en rassembler un grand nombre pour mener à bien la factorisation initiale, soit parvenir à casser la clé.La factorisation de RSA-768 (cf http://fr.wikipedia.org/wiki/RSA-768) est :RSA-768 = 33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489 * 36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917Pour plus d’informations, l’article scientifique » Factorization of a 768-bit RSA modulus » est téléchargeable depuis l’adresse http://eprint.iacr.org/2010/006.pdf. Il détaille les aspects techniques de ce calcul. Par A.L Béranger