Un logiciel open-source établit un nouveau record de factorisation

25 juin 2025

Résultats scientifiques Informatique

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).

Leur logiciel CADO-NFS, développé depuis 2007 pour réaliser ce type de calculs extrêmes, leur a récemment valu une prestigieuse récompense internationale : le Prix Levchin 2025. Au Loria, Pierrick Gaudry, directeur de recherche CNRS, Emmanuel Thomé et Paul Zimmermann, directeurs de recherche Inria, ont été distingués lors de la conférence Real-World Crypto, qui réunit chaque année les grands acteurs académiques et industriels de la cryptographie appliquée. Ce prix salue l’impact exceptionnel de CADO-NFS dans l’analyse de la robustesse des clés de chiffrement.

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 $m^e\bmod n$ , ce qui donne $434$ .

Alice envoie donc

$c=434$ à Bob. Pour déchiffrer, Bob calcule

$c^d\bmod n$ , 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\times 47$ , il peut en déduire facilement la clé privée

$e$ à partir de la clé publique

$n$ . En effet, on a

$d=1/e \bmod (43-1)\times(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.

Pour en savoir plus

Retrouvez l'actualité publiée par le Loria à l'occasion de leur prix Levchin 2025 : L’équipe Caramba lauréate du Prix Levchin pour le logiciel CADO-NFS

Contact

Pierrick Gaudry

Directeur de recherche CNRS au LORIA

pierrick.gaudry@loria.fr

Aurore Guillevic

Chargée de recherche Inria au LORIA

Aurore.Guillevic@inria.fr

Paul Zimmermann

Directeur de recherche Inria au LORIA

paul.zimmermann@loria.fr