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 (La cryptographie est une des disciplines de la cryptologie s'attachant à protéger des messages...). Si le nombre (La notion de nombre en linguistique est traitée à l’article « 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 (L´informatique - contraction d´information et automatique - est le domaine...) et ses applications (Loria - CNRS/Université de Lorraine/Inria), avec des collègues de l'Université de Limoges (L’Université de Limoges est une université française pluridisciplinaire...) et de l'Université de Californie (L'université de Californie est une université américaine, fondée en 1868, dont...) à San Diego (USA).

Alice et Bob

Alice veut envoyer un message (La théorie de l'information fut mise au point pour déterminer mathématiquement le taux...) 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 (Une page Web est une ressource du World Wide Web conçue pour être consultée par des...) (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 (Un ordinateur est une machine dotée d'une unité de traitement lui permettant...) pendant 2700 années ! À la place, ce sont environ 10000 ordinateurs qui ont calculé pendant quelques mois (Le mois (Du lat. mensis «mois», et anciennement au plur. «menstrues») est une période de temps...), 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 (Le mot puissance est employé dans plusieurs domaines avec une signification particulière :) de calcul, en tirer parti pour l'ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection...) des phases de l'algorithme, et démontrer ainsi que l'algorithme utilisé peut passer (Le genre Passer a été créé par le zoologiste français Mathurin Jacques...) à l'échelle pour des calculs plus importants.