Fabrice Boudot de l’Éducation nationale et de l’université de Limoges, Pierrick Gaudry du CNRS de Nancy, Aurore Guillevic, Emmanuel Thomé et Paul Zimmermann, INRIA de Nancy (Loria), et Nadia Heninger, des universités de Pennsylvanie et de Californie, viennent de battre deux nouveaux records en cryptographie.
Il s’agit du record de factorisation d’entiers, avec la factorisation d’un nombre à 240 chiffres et 795 bits : RSA-240 = 12462036678171878406583504460810659043482037465167880575481878888328966680118821 08550360395702725087475098647684384586210548655379702539305718912176843182863628 46948405301614416430468066875699415246993185704183030512549594371372159029236099 = 509435952285839914555051023580843714132648382024111473186660296521821206469746700620316443478873837606252372049619334517 * 244624208838318150567813139024002896653802092578931401452041221336558477095178155258218897735030590669041302045908071447.
Et du record de calcul de logarithmes discrets dans un corps fini défini par un nombre premier de même taille.
Ils battent le record précédent établi en 2009 avec la factorisation de RSA-768, un nombre à 232 chiffres et 768 bits, et du calcul de logarithmes discrets dans les corps finis de même taille en 2016.
C’est la première fois que ces deux records sont battus en même temps, et c’est la première fois qu’ils sont battus par le même logiciel (libre), CADO-NFS, qui implémente en c/c ++ le crible algébrique, un algorithme de décomposition d’un nombre entier en produits de facteurs premiers ; et sur le même matériel.
Au total, il aura fallu 4 000 cœurs-années, mesurées sur des processeurs Intel Xeon Gold 6130 à 2,1 GHz, pour obtenir ces deux records.
Les performances du logiciel ont aussi été mesurées sur des machines identiques à celles citées pour les deux records précédents : il aurait pris 25 % de temps en moins pour résoudre les mêmes problèmes.
On assiste donc à une avancée logicielle considérable.
Quelle est la portée de ces records ?
La cryptographie moderne s’appuie sur les difficultés à factoriser des entiers très grands en deux facteurs premiers, à calculer des logarithmes discrets dans les corps finis et à la construction de nouvelles primitives cryptographiques avec les courbes elliptiques.
Ces records permettent donc de confirmer ou d’actualiser les recommandations sur les longueurs (en bits) de clés de chiffrement pour garantir qu’il sera impossible de déchiffrer des données pendant un certain nombre d’années, dans un temps et avec un budget raisonnable.
À la lumière de ces nouveaux résultats, il fait peu de doute que calculer des logarithmes discrets modulo des nombres premiers de 1 024 bits est à la portée de quelques services étatiques.
En général, on recommande des clés d’une longueur de 2 048, voire 4 096 bits.
Cependant, les clés utilisées dans certains contextes peuvent être dangereusement inférieures.