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

Publié par Adrien le 13/03/2020 à 09:00
Source: CNRS INS2I

Les nombre premier ne sont divisibles que par 1 et eux-même
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 (assurant confidentialité, authenticité et intégrité) en s'aidant souvent de secrets ou clés.). Si le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) à 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 (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de développer les connaissances scientifiques. Par extension métonymique, la...) en informatique (L´informatique - contraction d´information et automatique - est le domaine d'activité scientifique, technique et industriel en rapport avec le traitement automatique de l'information par des machines...) 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 comptant plus de 14000 étudiants et près de 1000 enseignants et enseignants-chercheurs. Elle...) et de l'Université de Californie (L'université de Californie est une université américaine, fondée en 1868, dont le siège se trouve à Berkeley (Californie), comprenant dix campus situés dans l'État de Californie. Elle accueille...) à 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 d’information transmis dans la communication d’un message par un canal de communication,...) 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 visiteurs à l'aide d'un navigateur Web. Elle a une adresse Web. Techniquement, une page Web est souvent...) (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 (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.). 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 (En informatique, un logiciel est un ensemble d'informations relatives à des traitements effectués automatiquement par un appareil informatique. Y sont inclus les instructions de traitement,...) 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 d'exécuter des programmes enregistrés. C'est un ensemble de circuits électroniques...) 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 arbitraire.), 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 d’objets (les éléments de l'ensemble), « une multitude qui peut...) 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 Brisson (1723-1806) en 1760.) à l'échelle pour des calculs plus importants.
Cet article vous a plu ? Vous souhaitez nous soutenir ? Partagez-le sur les réseaux sociaux avec vos amis et/ou commentez-le, ceci nous encouragera à publier davantage de sujets similaires !
Page générée en 0.051 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique