Grands entiers : leur factorisation difficile protège RSA

Intervenant 10:00

Bienvenue dans le podcast du magazine Tangente.

Intervenant 20:03

Salut Sam ! Je suis vraiment ravie de replonger dans l'histoire des maths aujourd'hui.

Intervenant 10:07

Oui, surtout qu'aujourd'hui, on explore un truc assez incroyable. Pour donner un peu de contexte à ceux qui nous écoutent, il faut savoir que toute l'économie mondiale, les transactions bancaires sécurisées et même les secrets d'État, tout ça repose sur une seule chose.

Intervenant 20:21

C'est vrai. Une chose qui paraît presque absurde quand on y pense.

Intervenant 10:24

Mais carrément. C'est l'incapacité criante de nos ordinateurs à faire une division d'école primaire. Enfin, à très grande échelle, bien sûr.

Intervenant 20:32

C'est exactement ça.

Intervenant 10:33

Et le plus dingue, c'est que les bases de cette immense faille de sécurité, elles ont été posées à la plume en 1643.

Intervenant 20:41

Par deux mathématiciens français, oui.

Intervenant 10:43

Voilà, deux gars qui voulaient juste se lancer un petit défi intellectuel par courriel. On s'appuie d'ailleurs sur des sources exceptionnelles pour cette plongée documentaire, notamment un article très fouillé issu d'une conférence de Daniel Perrin à la Bibliothèque nationale de France.

Intervenant 20:57

Ce qui est fascinant ici, c'est que le système de cryptographie le plus répandu au monde repose sur un problème mathématique que nos ordinateurs les plus puissants sont incapables de résoudre. C'est quand même une ironie folle.

Intervenant 11:08

Ah ça c'est sûr.

Intervenant 21:09

Une abstraction théorique du XVIIe siècle qui devient le bouclier technologique de notre époque.

Intervenant 11:14

C'est fou. Et on sait tous que démonter un entier en facteur premier, pour des petits nombres, c'est facile. 45, c'est 5 x 9, donc 5 x 3², on le fait tête, c'est réglé.

Intervenant 21:24

Oui, l'arithmétique de base.

Intervenant 11:25

Mais l'échelle change absolument tout. Dès que les nombres s'allongent, les critères de divisibilité qu'on apprend à l'école rendent l'âme. La méthode basique, la force brute, ça devient vite un cauchemar absolu.

Intervenant 21:37

Et un cauchemar que nos savants du 17ème affrontaient sans la moindre calculatrice. Il faut se remettre dans le contexte.

Intervenant 11:44

Ah oui, pas d'ordinateur,

Intervenant 21:45

rien ? Rien du tout. On est en 1643. Le moine marin Mersenne, qui est un peu le réseau social de l'époque à lui tout seul, écrit à Pierre de Fermat. Et il lui lance un défi vraiment costaud.

Intervenant 11:58

Il lui demande de factoriser un nombre précis, c'est ça ?

Intervenant 22:00

Exactement. Le nombre 2 milliards 27 millions 651 milles 281. Waouh ! Un monstre à 10 chiffres ! Pour l'époque, c'est colossal.

Intervenant 12:13

Bon, décortiquons tout ça. S'attaquer à plus de 2 milliards à la main, en essayant de diviser par 3 puis par 5 puis 7, c'est du suicide mental.

Intervenant 22:23

Totalement.

Intervenant 12:24

Fermat le calcule lui-même, en plus. Pour arriver au bout, avec la méthode naïve, il aurait fallu tester tous les nombres premiers jusqu'à 44 000.

Intervenant 22:33

Une vie entière n'y suffirait pas, surtout à la plume.

Intervenant 12:36

Mais Fermat, en génie absolu, il contourne le mur. Il part d'une propriété algébrique toute bête. N'importe quel produit de deux nombreux impairs, ça peut s'écrire comme la différence de deux carrés.

Intervenant 22:46

Le raisonnement est hyper limpide. Faire masser que tous les nombres premiers, mis à part le 2, sont impairs.

Intervenant 12:52

Logique.

Intervenant 22:53

Donc ce grand nombre n qu'il doit factoriser, s'il est composé de deux facteurs, disons P et Q, il peut s'écrire sous la forme d'un grand carré R moins un autre carré S.

Intervenant 13:03

Donc on a l'équation n égale R au carré moins S au carré.

Intervenant 23:08

Et là, la magie opère.

Intervenant 13:09

Ah bah oui, l'identité remarquable classique. R au carré moins S au carré, ça se transforme direct en R moins S, le tout multiplié par R plus S.

Intervenant 23:19

Voilà. Si on arrive à isoler ces fameuses valeurs R et S, on a automatiquement nos deux facteurs.

Intervenant 13:25

L'idée est géniale, mais il y a quand même un gros problème. Pour trouver ce fameux R, Ferm a dit de partir de la racine carrée du nombre géant et de monter pas à pas.

Intervenant 23:34

C'est ça. On prend la partie entière de la racine, on l'appelle petit c, et on teste.

Intervenant 13:39

Mais la racine carrée de 2 milliards, c'est environ 45 000. Il faudrait calculer le carré de 45 030, soustraire 2 milliards, vérifier si le reste est un carré parfait. Et si ce n'est pas le cas, on recommence avec 45 031. C'est un travail de titan à faire à la main. Il doit forcément y avoir une ruse, non ?

Intervenant 23:57

Il y a effectivement une ruse. Et c'est là qu'on voit la différence entre un mec qui calcule bien et un vrai génie mathématique.

Intervenant 14:03

Ah, je me disais bien.

Intervenant 24:05

Fermat, il va absolument pas s'amuser à élever des nombres à 5 chiffres au carré à chaque étape. Il simplifie complètement l'équation pour manipuler que des petits chiffres.

Intervenant 14:15

Je vois. Au lieu de se coltiner la grosse équation, le carré de C plus 1 moins N, il développe l'algèbre.

Intervenant 24:22

Exactement. Il pose que N c'est égal au carré de la racine initiale plus un reste qu'on appelle R.

Intervenant 14:28

D'accord. Donc si on développe, les C au carré s'annulent purement et simplement. Et il ne reste qu'une toute petite opération. 2C plus 1 moins le reste R. C'est super brillant !

Intervenant 24:38

C'est un gain de temps faramineux. Si on prend les vrais chiffres de sa lettre de 1643. N vaut 2 milliards et des poussières. Sa racine, C, est 45 029. Le reste, R, est 40 440. Ok, j'ai les chiffres en tête. Eh bien pour sa toute première étape, faire ma calcul juste 2 x 45 029, plus 1, moins 40 440. Ce qui

Intervenant 15:03

se fait de tête en fait.

Intervenant 25:04

Totalement. Il trouve 49 619. Bon,

Intervenant 15:07

le calcul est devenu ultra léger, mais il doit quand même vérifier si 49 619 est un carré parfait.

Intervenant 25:14

Et là, c'est son intuition des nombres qui joue. En regardant 49 619, Fermat note immédiatement, aucun carré ne finit par 19. Ah

Intervenant 15:22

ouais, direct.

Intervenant 25:23

Il l'élimine de candidats en un quart de seconde. C'est une propriété arithmétique de base des carrés modules au 100.

Intervenant 15:29

Mais du coup, pour l'étape suivante, il doit refaire l'équation ?

Intervenant 25:32

Même pas. Pas besoin. La différence entre les carrés successifs forme une progression arithmétique. Il a juste ajouté un petit nombre impair qui grandit de 2 en 2 à chaque fois.

Intervenant 15:42

Donc il fait plus que des petites additions ?

Intervenant 25:43

Que des additions.

Intervenant 15:45

C'est dingue. Et la source indique qu'il a eu besoin de faire ça que 12 fois. 12 petites additions et paf, à la douzième étape, il tombe sur 1 080 400.

Intervenant 25:53

Et pour lui, ça saute aux yeux. C'est le carré de 1 020. Le piège s'est refermé.

Intervenant 15:57

Ah c'est beau. Donc il a sa valeur de R, il a sa valeur de S et il trouve ses deux facteurs premiers 44 021 et 46 061. Des dizaines de milliers de divisions réduites à 12 additions.

Intervenant 26:10

C'est l'élégance absolue.

Intervenant 16:11

Mais attends une seconde. Si on regarde bien la mécanique du truc, il y a une faille évidente. Tu

Intervenant 26:16

penses à

Intervenant 16:16

quoi ? L'algorithme démarre à la racine carrée et il avance. 12 étapes. Ok, c'est super rapide. Mais ça, ça marche que parce que les deux facteurs premiers étaient hyper proches l'un d'autre.

Intervenant 26:28

Absolument. L'analyse est parfaite.

Intervenant 16:30

Parce que si on a un petit facteur et un autre immense, Fermat, il va devoir faire des millions d'additions avant de tomber sur son carré parfait.

Intervenant 26:38

C'est tout le problème. Sa méthode est redoutablement spécialisée. Elle avance de la moyenne géométrique vers la moyenne arithmétique. Si les facteurs sont proches, c'est génial. S'ils sont éloignés, la méthode des carrés devient pire que la division naïve.

Intervenant 16:51

C'est un outil de précision, pas un marteau-piqueur quoi. Et c'est là que ça devient vraiment intéressant. Parce que Mersenne, il devait bien s'en douter. Toujours en 1643, il lui renvoie un autre défi.

Intervenant 27:02

Oh que oui ! Et avec une petite provocation en plus.

Intervenant 17:05

Il lui balance un nombre de 100 milliards cette fois. 100 milliards, 895 millions, etc. Et il lui dit « Trouve les facteurs, mais je veux la méthode pour le faire en un seul jour. »

Intervenant 27:16

Et Fermat répond avec son flegme habituel. Il balance les deux facteurs 898 423 et 112 303. Le résultat est irréprochable. Mais parce qu'il y a un mais, il ne donne aucune explication.

Intervenant 17:32

Zéro explication. Et pour cause, sa propre méthode des carrés était inapplicable ici.

Intervenant 27:38

Inapplicable, c'est le mot.

Intervenant 17:40

On l'a vu dans l'article de Daniel Perrin, ces deux facteurs sont super éloignés. Si on forçait l'algorithme de Fermat sur ce nombre, il aurait fallu faire 187 723 étapes.

Intervenant 27:52

Autant dire que c'est impossible à faire à la main en 24 heures. Donc s'il n'a pas utilisé son algorithme, comment il a fait ? Ça a été une vraie enquête forensic pour les historiens. La clé, en fait, elle est dans les obsessions mathématiques de Mersenne. Il était fasciné par les nombres multiparfaits.

Intervenant 18:08

C'est quoi déjà un nombre parfait ?

Intervenant 28:11

Un nombre parfait, c'est un nombre dont la somme des diviseurs est égale au nombre lui-même. Par exemple, 6. Ces diviseurs sont 1, 2 et 3. 1 plus 2 plus 3, ça fait 6.

Intervenant 18:21

OK. Et multiparfait ?

Intervenant 28:23

C'est quand la somme des diviseurs est un multiple entier du nombre de départ.

Intervenant 18:27

D'accord, un terrain de jeu très spécifique.

Intervenant 28:29

Totalement. En maths, cette somme des diviseurs, on la note avec la lettre grecque sigma. Et il s'avère que Mersenne construisait son nombre géant en explorant justement ces structures. Fermat le savait. Il a compris qu'il y avait une porte

Intervenant 18:42

dérobée. Mais attends, il faut qu'on clarifie ça. Comment on passe de cette théorie sur les multiparfaits à la factorisation de ce nombre de 100 milliards ?

Intervenant 28:52

Eh bien, Fermat a ciblé un autre nombre du même réseau de diviseurs étudié par Mersenne, le nombre premier 616 318 177. OK. Quand on étudie ça, on calcule constamment la fonction sigma. Et quelle est la somme des diviseurs d'un nombre premier ?

Intervenant 19:08

Le nombre lui-même plus 1, vu qu'il n'est divisible que par 1 et lui-même.

Intervenant 29:12

Exactement. Donc le sigma de ce nombre, ça donne 616 318 178.

Intervenant 19:18

Un nombre paire. Du coup, il devient super facile à factoriser par deux, puis par d'autres petits nombres.

Intervenant 29:23

C'est toute l'astuce. En décomposant ce nouveau nombre paire, Fermat trouve une série de facteurs. 2 x 73 x 898 423. Oh,

Intervenant 19:33

le fameux facteur !

Intervenant 29:34

Eh oui ! Les propriétés de leur réseau impliquaient que ce nouveau facteur premier devait forcément diviser le grand nombre de Mersenne. Fermat a juste posé la division et c'est tombé juste.

Intervenant 19:47

C'est un vrai coup de maître. Pour donner une image, c'est comme si ce nombre de 100 milliards, c'était un coffre-fort super blindé. Au lieu de tester les combinaisons une par une avec un pied de biche, ce qui correspondrait aux 187 000 étapes de calcul brutale, Fermat a juste trouvé les plans du concepteur du coffre.

Intervenant 210:04

C'est une excellente métaphore. Il a lu les plans, il a repéré la faille dans le mécanisme des nombres multiparfaits et il a déduit le code.

Intervenant 110:12

Paf, direct !

Intervenant 210:13

Si on relie ça à la situation globale, c'est là qu'on touche à une transition historique majeure. Au XVIIe siècle, factoriser des grands nombres, ça ne servait strictement à rien.

Intervenant 110:23

C'était juste pour frimer entre savants.

Intervenant 210:25

C'était un sport de l'esprit, oui. Mais aujourd'hui, cette résistance naturelle des grands nombres à se laisser désassembler, c'est devenu l'infrastructure fondamentale de notre ère numérique.

Intervenant 110:36

Alors, qu'est-ce que tout cela signifie concrètement ? Comment un défi de l'époque de d'Artagnan protège nos cartes bleues aujourd'hui ?

Intervenant 210:43

Tout repose sur la cryptographie asymétrique.

Intervenant 110:46

Oui, le concept de clé publique et clé privée.

Intervenant 210:49

Exactement.

Intervenant 110:50

Pour ceux qui visualisent mal, imaginons que la clé publique, c'est comme un cadenas ouvert qu'on distribue à tout le monde sur internet. N'importe quel site web peut prendre ce cadenas et fermer un message avec.

Intervenant 210:59

Et une fois fermé, le mécanisme est tellement complexe que personne ne peut le forcer.

Intervenant 111:04

Voilà. La seule façon d'ouvrir le cadenas, c'est d'avoir la clé privée. Et le petit dessin microscopique des dents de cette clé, ce sont précisément les facteurs premiers d'un nombre gigantesque.

Intervenant 211:14

C'est le principe du système RSA, inventé en 1977. Ce système génère un immense nombre composé, qu'on appelle N. Ce nombre est public. Et il est le résultat de la multiplication de deux nombres premiers titanesques, P et Q, qui eux sont gardés secrets.

Intervenant 111:32

Donc, pour pirater le message, le pirate doit retrouver P et Q. Il doit factoriser N.

Intervenant 211:38

Et c'est là que les mésaventures de Fermat prennent tout leur

Intervenant 111:41

sens. Ah oui. Parce que pour que RSA tienne le coup, on fabrique des nombres qui esquivent les méthodes de Fermat. On choisit des facteurs P et Q qui ne sont surtout pas proches l'un de l'autre.

Intervenant 211:51

Exactement. Pour neutraliser la méthode des différences de carrés.

Intervenant 111:54

Et on s'assure qu'il n'y a aucune porte dérobée arithmétique. Pas de faille liée au nombre multiparfait ou autre. On force les pirates à utiliser la force brute.

Intervenant 212:03

Sauf que la force brute, à cette échelle, c'est sans espoir. Mais attention, la méthode de Fermat, elle a évolué. En 1981, le mathématicien Karl Pomerance a créé le crible quadratique. C'est une méthode informatique surpuissante, directement inspirée de l'idée des carrés de Fermat. D'accord. En 1994, avec ce crible, ils ont mis en réseau des centaines d'ordinateurs dans le monde entier pendant des mois. Juste pour factoriser un nombre à 129 chiffres. Le fameux RSA 129.

Intervenant 112:35

Des mois de calculs mondialisés pour 129 chiffres. Et aujourd'hui, le record de factorisation, on est où ?

Intervenant 212:41

On approche les nombres à 250 chiffres.

Intervenant 112:43

D'accord. Mais du coup, pour sécuriser les banques du monde entier, on utilise des clés de combien de chiffres aujourd'hui ?

Intervenant 212:49

Les standards actuels exigent un nombre N d'au minimum 600 chiffres.

Intervenant 112:53

Ah ouais, la marge est

Intervenant 212:55

colossale ! Ah, c'est énorme ! Ça veut dire multiplier deux nombres premiers d'environ 300 chiffres chacun. La distance entre les facteurs est tellement vaste que les algorithmes modernes, même inspirés de Fermat, pédalent dans le vide. Même si on reliait tous les serveurs de la planète aujourd'hui, ça prendrait des millions d'années pour trouver la réponse.

Intervenant 113:16

En gros, en l'état actuel de la technologie, le système est inviolable.

Intervenant 213:19

Pour le moment, oui.

Intervenant 113:21

C'est vertigineux. On confie vraiment la stabilité de nos sociétés à une énigme que personne n'a la puissance de résoudre.

Intervenant 213:27

Et cela soulève une question importante. Une question qui donne d'ailleurs des sueurs froides aux agences de renseignement.

Intervenant 113:33

Dis-moi tout.

Intervenant 213:34

Toute notre sécurité tient sur une conviction. On croit qu'il n'y a aucun raccourci miracle pour factoriser ces très grands nombres. Mais les mathématiques, c'est un continent en grande partie inexploré. Que se passerait-il si, demain matin, un chercheur anonyme, avec une intuition fulgurante à la Fermat, découvrait une nouvelle propriété cachée des entiers ?

Intervenant 113:54

Un nouvel algorithme qui permettrait de casser des nombres de 600 chiffres en une fraction de seconde ?

Intervenant 214:00

Exactement. Ce n'est pas une loi physique qui protège nos données, c'est juste notre ignorance d'une méthode plus rapide. Une faille théorique de ce genre rendrait le système RSA obsolète du jour au lendemain. L'infrastructure d'Internet s'effondrerait.

Intervenant 114:14

Une simple équation griffonnée sur un bout de papier qui fait sauter tous les cadenas numériques de la planète. L'idée est vraiment fascinante et carrément terrifiante.

Intervenant 214:22

C'est toute la beauté et le danger de la recherche fondamentale. On ne sait jamais ce qu'on va trouver.

Intervenant 114:27

C'est clair. C'était un immense plaisir de partager cette plongée arithmétique avec vous aujourd'hui. On part d'une époque de joutes intellectuelles par lettres interposées pour finir sur la cybersécurité mondiale. C'est magique. Gardons l'esprit curieux et continuons d'interroger ces structures invisibles qui régissent notre monde. Merci à notre experte pour cet éclairage passionnant.

Intervenant 214:47

Merci, c'était super.

Intervenant 114:50

À très vite pour une nouvelle exploration de l'univers des sciences.