LORIA Informatics collaboration: Open source software achieves new factorisation record
February / March 2020. French UMR7504 a research unit of CNRS, INRIA, Université de Lorraine, with collaboration of researchers in Germany and the United States achieved a new record in factorisation end of February. For the past three months, ever since the DLP-240 record announced in December 2019 1), we have been in a historically unique state of affairs: the discrete logarithm record (in a prime field) has been larger than the integer factorization record. We are pleased to rectify this situation with the factorization of RSA-250 from the RSA challenge list:
RSA-250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937
= 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
* 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711
This computation was performed with the Number Field Sieve algorithm, using the open-source CADO-NFS software 2). The total computation time was roughly 2700 core-years, using Intel Xeon Gold 6130 CPUs as a reference (2.1GHz):
RSA-250 sieving: 2450 physical core-years
RSA-250 matrix: 250 physical core-years
Here are the factors of p+/-1 and q+/-1:
p-1 = 2 * 6213239 * 101910617047160921359 * 4597395223158209096147 * p77
p+1 = 2^3 * 3 * 7 * 223 * 587131 * 6071858568668069951281 * p93
q-1 = 2 * 5 * 13 * 440117350342384303 * 8015381692860102796237 * p83
q+1 = 2^3 * 3^3 * 23 * 2531 * 11171 * 2100953 * p108
We used computer resources of the Grid'5000 experimental testbed in France (INRIA, CNRS, and partner institutions) 3), of the EXPLOR computing center at Université de Lorraine, Nancy (FR) 4), an allocation of computing hours on the PRACE research infrastructure using resources at the Juelich supercomputing center in Germany 5), as well as computer equipment gifted by Cisco Systems, Inc. at UCSD.
CNRS: Un logiciel open-source établit un nouveau record de factorisation
Mars 2020. Décomposer 15 en 3∗5, c'est facile ! C'est ce qu'on appelle "factoriser" un nombre, les facteurs 3 et 5 ne pouvant plus être décomposés, car ce sont des nombres premiers (divisibles seulement par 1 et eux-mêmes). Saurez-vous décomposer 2021 de la même façon ? C'est un peu plus difficile. C'est sur cette difficulté que repose la sécurité du système RSA utilisé couramment en cryptographie. Si le nombre à décomposer a 250 chiffres, alors cela devient franchement impossible. Ou presque... C'est pourtant ce qu'ont fait une équipe de chercheurs du Laboratoire lorrain de recherche en informatique et ses applications (Loria - CNRS/Université de Lorraine/Inria), avec des collègues de l'Université de Limoges et de l'Université de Californie à San Diego (USA).
Alice et Bob
Alice veut envoyer un message secret à Bob. Supposons pour simplifier que,ce message est un entier plus petit que n=2021. Bob a calculé une clé privée (disons d=923) et il en déduit une clé publique (ici e=1595) qu'il affiche sur sa page web (ou son compte Twitter). Pour envoyer le message m=1989 à Bob, Alice commence par le chiffrer. Pour cela, elle calcule memodn, ce qui donne 434. Alice envoie donc c=434 à Bob. Pour déchiffrer, Bob calcule cdmodn, ce qui donne bien 1989.
Le challenge RSA
Le procédé utilisé ci-dessus est l'algorithme RSA, du nom de ses inventeurs Rivest, Shamir et Adleman. Sa sécurité est basée sur le fait qu'il est difficile de factoriser 2021. Par contre, si le "méchant" Charlie arrive à factoriser 2021 en 43×47, il peut en déduire facilement la clé privée e à partir de la clé publique n. En effet, on a d=1/emod(43−1)×(47−1).
Charlie peut donc lui aussi déchiffrer le message d'Alice, qui n'est plus secret du tout. Pour encourager la recherche en factorisation d'entier, et donc pour attester de la sécurité du système RSA, le "RSA Factoring Challenge" a été créé en 1991.
Factorisation de RSA-250
Le nombre RSA-250, qui fait partie du "RSA Factoring Challenge", a été factorisé le 28 février 2020. C'est le produit de deux nombres premiers de 125 chiffres chacun. Ce résultat a été obtenu avec un algorithme spécifique appelé le crible algébrique, et un logiciel open-source (CADO-NFS) que les chercheurs du LORIA et leurs collègues développent depuis 2007, et qui comporte de l'ordre de 400 000 lignes de code. Pour établir ce nouveau record, il aurait fallu faire travailler un ordinateur pendant 2700 années ! À la place, ce sont environ 10000 ordinateurs qui ont calculé pendant quelques mois, dans plusieurs universités et centres de calcul en France (notamment la plate-forme Grid'5000/SILECS), en Allemagne, et aux États-Unis. L'une des difficultés principales de ce travail a été de maîtriser une telle puissance de calcul, en tirer parti pour l'ensemble des phases de l'algorithme, et démontrer ainsi que l'algorithme utilisé peut passer à l'échelle pour des calculs plus importants. Boudot F, Éducation Nationale and Université de Limoges (FR);Gaudry P, CNRS, Nancy (FR) ; Guillevic A, INRIA, Nancy (FR); Heninger N, University of California, San Diego (CA, US; Thomé E, INRIA, Nancy (FR; Zimmermann P, INRIA, Nancy (FR)
Footnote/s
We would like to dedicate this computation to Peter L. Montgomery, who passed away on February 18, 2020.
Reference/s
1+2) see.
3+4) see.
5) see.
Disclaimer: You agree that B2Bioworld is not responsible and will not be held liable for any third party content on its sites or any third-party content, products or services available on other web sites accessed through links from B2Bioworld sites. Links to third-party sites are for your convenience only, and their inclusion on B2Bioworld\'s sites does not imply any endorsement, guarantee, warranty or representation by B2Bioworld.
Other articles recommended
B2Bioworld offers you background information