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

Décomposer 15 en 3 x 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 m^e mod n, ce qui donne 434.

Alice envoie donc c=434 à Bob. Pour déchiffrer, Bob calcule c^d mod 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 x 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 mod (43-1) x (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.