B.2 Records de calculs de factorisation
Les principaux records successifs en termes de calcul de factorisation de modules produits de deux nombres premiers de taille comparable sont listés dans la table 3.
Table 3 – Records de factorisation d’entiers de type RSA.
| Date | Bits | Chiffres | Auteurs |
|---|---|---|---|
| 1993-06-12 | 397 | 120 | Denny, Dodson, Lenstra et Manasse |
| 1994-04-02 | 426 | 129 | Atkins, Graff, Lenstra, Leyland |
| 1996-04-10 | 432 | 130 | Lenstra et al. |
| 1999-02-02 | 466 | 140 | te Riele et al. |
| 1999-08-22 | 512 | 155 | te Riele et al. |
| 2002-01-18 | 524 | 158 | Bahr, Franke, Kleinjung |
| 2003-04-01 | 530 | 160 | Bahr, Franke, Kleinjung, Lochter et Boehm |
| 2003-12-03 | 576 | 174 | Franke et Kleinjung |
| 2005-05-09 | 663 | 200 | Bahr, Boehm, Franke et Kleinjung |
| 2009-12-12 | 768 | 232 | Kleingjung et al. |
| 2019-12-02 | 795 | 240 | Thomé et al. |
| 2020-02-28 | 829 | 250 | Thomé et al. |
Les deux premiers records ont utilisé l’algorithme du crible quadratique et les suivants l’algorithme du crible algébrique, le plus efficace connu à ce jour pour factoriser de grands entiers quelconques. La plupart de ces challenges ont été proposés par la société RSA.1
B.2.1 Factorisation par des machines dédiées
De même qu’il est possible de concevoir des machines dédiées conçues exclusivement à des fins de calculs exhaustifs sur des clés de chiffrement symétrique, il est aujourd’hui sérieusement envisagé de concevoir de telles machines afin de factoriser de grands modules RSA. Le projet le plus abouti a été présenté par Adi Shamir et Eran Tromer en août 2003. Les estimations de coût indiquent qu’il semblerait possible de réaliser pour quelques dizaines de millions d’euros une machine capable de factoriser des modules de 1024 bits en moins d’un an. À ce jour aucune annonce de conception concrète n’a cependant été faite.
B.2.2 Autres records de factorisation
Notons enfin que dans certains cas il est possible d’employer des algorithmes de factorisation particuliers, plus efficaces que les algorithmes généraux mais ne s’appliquant pas à tous les entiers (et en particulier, à ce jour, ne s’appliquant pas aux modules RSA).
L’algorithme SNFS (crible algébrique dit « spécial ») a ainsi permis de factoriser le nombre de Mersenne de 809 bits (244 chiffres décimaux) début 2003, puis le nombre de Mersenne de 1039 bits (313 chiffres décimaux) en 2007, un nombre qui est donc plus grand qu’un module RSA de 1024 bits.
-
Les challenges de la société RSA étaient disponibles sur http://www.rsasecurity.com/rsalabs/challenges, mais ont été retirés en 2007. ↩