Accueil > 02 - Livre Deux : SCIENCES > Introduction à la dialectique de la nature > Matérialisme dialectique et mathématiques : 2021 est-il un nombre favorable ?

Matérialisme dialectique et mathématiques : 2021 est-il un nombre favorable ?

lundi 12 avril 2021, par Alex

Matérialisme dialectique et mathématiques : 2021 est-il un nombre favorable ?

Pour ceux qui s’intéressent aux applications des mathématiques aux problèmes les plus concrets, le nombre 2021 apparaît tout de suite familier, en tant qu’un des membres de la famille des nombres notés N=pq, qui peuvent servir de clé publique en cryptographie (la science des codes secrets). Certains en déduiront que 2021 pourrait être une très bonne année, et ils n’auront pas entièrement tort.

Les camarades qui souhaitent transmettre des messages qui ne peuvent être décodés par aucun des ordinateurs les plus puissants devraient se familiariser avec ces méthodes de la cryptographie moderne, en particulier le système RSA

Les marxistes qui se posent la question de l’existence de la dialectique dans la nature en général, dans les mathématiques en particulier, peuvent trouver dans ce chapitre des mathématiques un matériel que Engels aurait sans doute inclus dans une nouvelle édition de sa Dialectique de la nature.

Précisons donc le lien entre 2021 et la cryptographie moderne. Si l’on multiplie 43 par 47 on obtient 2021 : 2021=43x47. C’est un cas particulier de la formule N=pq, dans laquelle p et q doivent être des nombres premiers. 43 et 47 sont des nombres premiers, car ils ne sont divisibles par aucun autre nombre, à part eux-mêmes et 1. L’an dernier on pouvait écrire 2020=10x202, mais 10 n’est pas un nombre premier car il est divisible par 2 et 5 ; 202 non plus. L’année 2021 est donc, à ce titre, remarquable.

La liste des nombres premiers est 2,3,5,7,11,13 etc. Les clés publiques les plus petites sont donc 15=3x5, 21=3x7, 35=5x7 etc.

Les nombres premiers jouent un rôle fondamental en arithmétique. Mais jusqu’en 1975, on n’imaginait pas que les nombres qui sont le produit de deux entiers premiers (comme 2021 est le produit de 43 et 47) peuvent avoir des applications à la science des messages secrets, la cryptographie. Tout nouveau théorème sur les nombres premiers peut donc poser un problème pour la « défense nationale » !

Quel lien avec le matérialisme et la dialectique ?

Premièrement, côté matérialisme, l’épisode de la découverte de la théorie de la cryptographie à clé publique donne un argument matérialiste contre ceux qui, en partisans de Platon, conscients ou non, pensent que les théories mathématiques en elles-mêmes sont déjà écrites quelque part et que les mathématiciens ne font que les « découvrir ». Or c’est seulement parce qu’une nouvelle activité humaine, liée étroitement aux transactions bancaires, donc au développement des forces productives, que des mathématiciens ont créé, plus que découvert, un nouveau procédé de cryptographie, un nouveau domaine des mathématiques.

Deuxièmement, côté dialectique, l’outil mathématique au coeur de ces nouvelles méthodes sont les « fonctions asymétriques ». Ces fonctions sont faciles à calculer dans un sens, impossible ou presque à calculer dans le sens inverse. Un même objet mathématique a donc des propriétés contraires l’une de l’autre.

Le livre de Simon Singh Histoire des codes secrets est une bonne introduction à l’histoire des codes secrets et aux termes techniques utilisés précédemment. L’extrait suivant de son livre décrit la révolution scientifique qu’a constitué la naissance de la cryptographie à clé publique, opposée à la cryptographie à clé secrète, qu’utilisait déjà Jules César.

Ce problème de distribution de la clef a été le fléau
constant des cryptographes au cours de l’histoire. Pendant la Seconde Guerre mondiale, le haut commandement allemand devait ainsi distribuer le registre
mensuel des clefs quotidiennes à tous les opérateurs
d’Enigma, ce qui constituait un problème de logistique
considérable. Les sous-marins allemands, de même, en
raison de longues périodes passées loin de leurs bases,
devaient d’une façon ou d’une autre être alimentés en
clefs. Plus loin de nous, les utilisateurs du chiffre de
Vigenère devaient trouver un moyen pour transmettre
le mot-clef de l’expéditeur au destinataire. Aussi sûr
que soit un chiffrement en théorie, il est fragilisé en
pratique par le problème de distribution de la clef.

Dans une certaine mesure, les gouvernements et les
armées ont pu résoudre ce problème en y consacrant
beaucoup d’efforts et en ne ménageant pas les investissements. Leurs messages sont d’une telle importance
qu’ils iront aussi loin que nécessaire pour assurer une
distribution sûre de la clef. Les clefs du gouvernement
américain sont gérées et distribuées par la COMSEC,
abrégé de Communications Security. Dans les
années 70, la COMSEC acheminait des tonnes de clefs
chaque jour. Quand des bateaux transportant du maté-
riel de la COMSEC arrivaient à quai, des crypto-gardes
montaient à bord, récupéraient des tas de cartes, des
rouleaux de papier, des disques souples, ou n’importe
quel autre support sur lequel les clefs avaient été stockées, et les portaient à leurs destinataires.

La distribution des clefs peut sembler une question
annexe, mais elle constitua le problème primordial
pour les cryptographes de l’après-guerre. Si deux per-
sonnes voulaient communiquer en toute sûreté, elles
devaient s’en remettre à une troisième pour acheminer
la clef, et ce maillon était le plus faible de la chaîne.
Pour les transactions commerciales, le dilemme se
posait clairement : si les gouvernements, avec tout leur
argent, avaient peine à garantir la sécurité de leurs
clefs, comment des entreprises civiles pourraient-elles
jamais espérer jouir d’une distribution de clefs sûre et
non ruineuse ?

Vers 1975, enfin, une bande de francs-tireurs trouva
la solution de ce problème réputé insoluble. Ils mirent
au point un système de chiffrement qui semblait défier
toute logique. Si les ordinateurs ont transformé l’ application du chiffrement, la plus grande révolution du
xx e siècle a été le développement des techniques pour
résoudre le problème de distribution des clefs. Aussi
cette découverte est-elle considérée comme la plus
grande réussite en cryptologie depuis l’invention
du chiffre monoalphabétique, il y a plus de deux
mille ans.

Ils passèrent des mois à chercher une solution. Chaque
idée aboutissait à un échec, mais ils agissaient en bons
fous, et persévéraient. Ils concentrèrent leur recherche
sur diverses fonctions mathématiques. Une fonction est
n’importe quelle opération qui transforme un nombre
en un autre nombre. Par exemple doubler est une fonction, puisque cette opération transforme le 3 en 6, ou
le 9 en 18. De plus, nous pouvons envisager toutes les
formes de chiffrement informatique comme des fonctions, puisqu’elles transforment un nombre - le texte
clair - en un autre nombre, le texte chiffré.
La plupart des fonctions mathématiques sont réversibles, puisqu’elles sont aussi simples à défaire qu’à
faire. Doubler est ainsi réversible puisqu’il est facile
de retrouver le nombre d’origine à partir de son double.
Si nous savons que le résultat du doublement est 26, il
est enfantin de déduire que le nombre d’origine est 13.

Diffie et Hellman n’étaient pas intéressés par ces
fonctions réversibles. Leur centre d’intérêt était les
fonctions à sens unique. Comme leur nom le suggère,
ces fonctions sont faciles à appliquer, mais très difficiles à inverser : elles sont virtuellement non-irréversibles. Voyons à nouveau un exemple du quotidien.
Mélanger de la peinture jaune et de la peinture bleue
pour obtenir du vert est une fonction à sens unique,
puisqu’il est facile le de mélanger les peintures et impossible de retrouver les couleurs d’origine. Une autre
fonction à sens unique est de casser un œuf, car il vous
est impossible ensuite de le reconstituer.

L’arithmétique modulo, parfois appelée à l’école
arithmétique de l’horloge, est un domaine des mathématiques riche en fonctions à sens unique. Dans l’arithmétique modulo, les mathématiciens considèrent un
ensemble fini de nombres arrangés en boucle, un peu
comme les nombres sur une horloge. La figure 46
montre une horloge pour un modulo 7 (ou mod 7) qui
a seulement 7 nombres de 0 à 6. Pour effectuer 2 + 3,
nous partons de 2 et nous avançons de 3 places pour
arriver à 5, ce qui donne la même réponse que l’arithmétique normale. Pour faire 2 + 6, nous partons de 2
et avançons de 6 places, mais cette fois nous avons
effectué un tour complet sur la boucle et nous atteignons le l, qui n’est pas le résultat habituel en arithmétique.

Ces résultats peuvent s’exprimer ainsi :

2 + 3 = 5 (mod 7) et 2 + 6 = 1 (mod 7)

L’arithmétique modulo est relativement simple, et
nous l’utilisons tous les jours lorsque nous parlons de
l’heure. S’il est 9 heures maintenant, et que nous avons
un rendez-vous dans 8 heures d’ici, nous pouvons dire
que notre rencontre aura lieu à 5 heures de l’ après-
midi, plutôt qu’à 17 heures. Nous avons calculé mentalement 9 + 8 (mod 12).

Imaginons le cadran de l’horloge, regardons le 9, puis tournons de 8 places, et nous arrivons à 5 :

9 + 8 = 5 (mod 12)

Plutôt que de visualiser des horloges, les mathématiciens appliquent souvent la recette suivante pour abréger les calculs de modulo. Effectuons d’abord le calcul en arithmétique normale. Ensuite, pour connaître le
résultat en (mod x), divisons la réponse normale par x
et notons le reste. Ce reste constitue la réponse en
(mod x). Pour trouver la réponse à 11 x 9 (mod 13),
nous procédons comme suit :

I1 x 9 = 99

99 : 13 = 7, reste 8

11 x 9 = 8 (mod 13)

Les fonctions effectuées en arithmétique modulo
tendent à se comporter de manière erratique, ce qui
les transforme parfois en fonction à sens unique. Cela
devient évident lorsqu’une fonction simple en arithmétique normale est comparée à la n1ême fonction en
arithmétique modulo. Dans la première, la fonction
sera à double sens et aisément inversible. Dans la
seconde, elle sera à sens unique et difficilement inversible. Prenons par exemple la fonction 3x. Cela veut
dire : prendre un nombre (x), puis multiplier 3 par lui-
même x fois pour trouver le nouveau nombre. Si x = 2,
effectuons cette opération :

3 ^2 = 3 x 3 = 9

Autrement dit, la fonction transforme 2 en 9. En
arithmétique ordinaire, plus la valeur de x croît, plus
le résultat croît. Si l’on nous donnait le résultat de
l’opération, il nous serait assez facile de revenir en
arrière et de déduire le nombre d’origine. Si le résultat
est 81, on peut en déduire que x = 4, puisque 3^ 4 = 81.

Si nous nous trompons et croyons que x = 5, nous
trouverons que 3 5 = 243, ce qui nous prouve que notre
valeur attribuée à x était trop grande. Bref, même si
nous nous trompons, nous pouvons retrouver l’exacte
valeur de x et effectuer à l’envers la fonction.

En arithmétique modulo, cette même fonction ne se
comporte pas si raisonnablement. Imaginons que l’on
nous dise que 3 x en modulo 7 = 1, et que l’on nous
demande de trouver la valeur de x. Aucune valeur ne
nous vient à l’esprit, car nous sommes peu familiers,
pour la plupart, avec l’arithmétique modulo. Nous pouvons supposer que x = 5 et chercher le résultat de 3^5
(mod 7). Le résultat donnera 5, ce qui est trop élevé
puisque nous cherchons un résultat égal à 1. Nous pouvons être tentés de réduire la valeur de x et d’essayer
à nouveau. Mais nous irons dans la mauvaise direction
puisque la réponse exacte est x = 6.

En arithmétique normale, nous pouvons essayer des
nombres et sentir si nous brûlons ou si nous gelons. Le
contexte de l’arithmétique modulo n’offre pas de prises
utiles, et inverser les fonctions est bien difficile. Sou-
vent, le seul moyen pour inverser une fonction en
modulo est de constituer une table en calculant la fonction avec diverses valeurs attribuées à x, jusqu’à ce que
l’on tombe sur la bonne solution. Le tableau 25 montre
les résultats obtenus en appliquant plusieurs valeurs à
la fonction, à la fois en arithmétique normale et en
arithmétique modulo. Si établir une telle table est un
peu fastidieux lorsqu’on travaille sur d’assez petits
nombres, cela devient extrêmement pénible avec une
fonction comme 453 x (mod 21 997). C’est un exemple
classique de fonction à sens unique, car je peux attribuer une valeur à x et calculer le résultat de la fonction,
mais si je vous donne un résultat, disons 5 787, vous
aurez une. immense difficulté à inverser la fonction et
à trouver quel x j’avais déterminé. Il ne m’a fallu que
quelques secondes pour effectuer mon calcul, mais il
vous en coûtera des heures pour établir une table et
trouver l’x que j’avais choisi.

Après deux années consacrées à l’arithmétique
modulo et aux fonctions à sens unique, la fantaisie de

Hellman commença à se révéler payante. Au printemps
1976, il eut l’idée d’une stratégie résolvant le problème
de l’échange de clefs. En une demi-heure de gribouillage frénétique, il prouva qu’Alice et Bernard poùvaient convenir d’une clef sans se rencontrer, Hellmàn
rendait ainsi caduc un axiome qui avait fait la loi pendant des siècles. Son idée reposait sur une fonction à
sens unique de forme y^x (mod P). D’abord, Alice et
Bernard se concertaient sur les valeurs attribuées à Y ,
et P. A peu près toutes les valeurs sont possibles, avec
cependant quelques restrictions, telles que : P doit être
premier et Y inférieur à P. Ces valeurs ne sont pas
secrètes, aussi Alice peut-elle téléphoner à Bernard et
suggérer, disons, que Y = 7 et P = Il. Même si la ligne
téléphonique n’est pas sûre et que la malveillante Eve
écoute la conversation, c’est sans importance, comme
nous allons le voir. Alice et Bernard sont maintenant
convenus de la fonction à sens unique 7^X (mod 11). À
cet instant, ils peuvent entamer le processus visant à
établir une clef secrète sans se rencontrer.

Alice et Bernard ont défini la
même clef, qu’ils peuvent utiliser pour chiffrer un mes-
sage. Par exemple, ils peuvent utiliser leur nombre, 9,
comme clef pour un chiffrement en DES.

Hellman avait renversé un des piliers de la cryptographie et prouvé qu’Alice et Bernard n’avaient pas
besoin de se rencontrer pour convenir d’une clef
secrète. Ensuite, quelqu’un devrait simplement arriver
avec un schéma plus efficace pour que le problème de
la distribution des clefs soit tout à fait surmonté.

(...)
Au cœur du chiffre asymétrique de Rivest se trouve
une fonction à sens unique basée sur le type des fonctions modulo décrites plus haut. La fonction à sens
unique de Rivest peut être utilisée pour crypter le message. On introduit dans la fonction ce message qui, en
fait, est un nombre, et le résultat est le texte chiffré, un
autre nombre. Je ne décrirai pas en détail la fonction
de Rivest (voir Annexe J), mais j’expliquerai un des
aspects qui lui sont propres, appelé simplement N parce
que c’est ce N qui rend la fonction réversible sous certaines conditions, et donc idéale pour être appliquée à
un chiffre asymétrique.

N est important parce qu’il est le composant variable
de la fonction à sens unique, ce qui entraîne que
chaque personne peut choisir pour N une valeur différente, et personnaliser la fonction. Pour choisir sa
valeur personnelle de N, Alice prend deux nombres
premiers, p et q et les multiplie l’un par l’autre. Un
nombre premier n’a pas de diviseur, hors lui-même et
1. Par exemple 7 est un nombre premier parce qu’aucun chiffre ne le divise sans qu’il Y ait un reste. De
même 13 est un nombre premier parce que seuls 1 et
13 le divisent sans laisser de reste. En revanche, 8 n’est
pas un nombre premier, puisqu’on peut le diviser par
2 et par 4.
Alice pourrait ainsi choisir comme nombres premiers p = 17 159 et q = 10 247. Multiplier ces nombres
l’un par l’autre donne :

N = 17 159 x 10247 = 175828273.

Le choix d’Alice pour N devient sa clef publique,
elle peut l’imprimer sur sa carte de visite, la mettre sur
Internet ou la publier dans un annuaire de clefs
publiques avec toutes les autres valeurs de N appartenant à d’autres personnes. Si Bernard veut crypter un
message pour Alice, il se, procure la valeur du N
d’Alice (175 828 273) et l’insère dans la formule générale de la fonction à sens unique, elle aussi de notoriété
publique. Bernard dispose maintenant d’une fonction à -
sens unique taillée sur mesure avec la clef d’Alice,
qu’on peut appeler la fonction à sens unique d’Alice.
Pour crypter un message pour Alice, il prend la fonction d’Alice, y insère le message, en note le résultat et
l’envoie à Alice.

Jusque-là, le message crypté est en sécurité puisque
personne ne peut le déchiffrer. Le message a été chiffré
par une fonction à sens unique ; inverser cette fonction
et décrypter le message sont, par définition, virtuelle-
ment impossibles. Pourtant, une question demeure :
comment Alice peut-elle décrypter le message ? Pour
lire les messages qu’on lui adresse, Alice doit avoir un
moyen d’inverser la fonction à sens unique. Un élément doit lui permettre de décrypter le message. Heureusement pour Alice, Rivest a élaboré une fonction à
sens unique qui peut être inversée par quelqu’un
connaissant la valeur de p et de q, les deux nombres
premiers qui ont été multipliés pour donner N. Bien
qu’Alice ait dit à tout le monde que sa valeur pour N
était 175 828 273, elle n’a pas révélé les valeurs de p
et de q ; elle seule dispose donc de cette information
nécessaire pour décrypter les messages.

Nous pouvons voir en N la clef publique, une information disponible pour n’importe qui, une information
nécessaire pour crypter les messages destinés à Alice.
Alors que p et q sont la clef privée, utilisable par Alice
seulement, l’information indispensable pour décrypter
ces messages.

Les modalités précises de l’utilisation de p et de q
pour inverser la fonction à sens unique sont décrites
dans l’Annexe J. Pourtant, il y a une question qui se
pose immédiatement. Si tout le monde connaît N, la
clef publique, alors n’est-il pas facile d’en déduire p et
q, la clef privée, et de lire les messages d’Alice ? Après
tout, N a été créé en partant de p et de q. En fait il se
trouve que si N est assez grand, il est pratiquement
impossible d’en déduire p et q, et c’est peut-être l’aspect le plus intéressant et le plus élégant du chiffre
asymétrique RSA.

Alice a créé N en choisissant p et q et en multipliant
l’un par l’autre. Le point fondamental est que cette
action est en elle-même une fonction à sens unique.
Pour démontrer l’irréversibilité de la multiplication de
nombres premiers, prenons deux nombres premiers
9 419 et 1933, et multiplions-les. Une machine à calculer fournit la réponse, en quelques secondes :
18 206 927. Si, au contraire, on nous donne 18 206 927
en nous demandant de trouver les facteurs premiers
(les deux nombres qui, multipliés l’un par l’autre, ont
donné 18 206 927), cela prendra beaucoup plus de
temps. Si vous en doutez, réfléchissez à ceci : cela m’a
pris dix secondes pour générer le nombre 1 709 023,
mais il vous faudra, avec votre machine à calculer,
presque tout un après-midi pour en sortir les facteurs
premiers.

Ce cryptosystème, le RSA, est une forme de
la cryptographie à clef publique. Pour vérifier sa sécu-
rité, mettons-nous à la place d’Ève, et essayons de saisir un message d’Alice à Bernard. Pour crypter son
message, Alice consulte la clef publique de Bernard.

Pour constituer sa clef publique, Bernard a choisi ses
propres nombres premiers, PB et qB et les a multipliés
l’un par l’autre pour obtenir NB. Il a gardé secret PB et
qB, qui forment sa clef privée, mais a rendu publique
NB qui est 408 508 091. Alice insère donc la clef
publique de Bernard dans la fonction générale à sens
unique de chiffrement, et crypte son message. Lorsque
le message lui parvient, Bernard peut inverser la fonction et le décrypter, en utilisant les valeurs de PB et
qB qui constituent sa clef privée. Entre-temps, Eve a
intercepté le message. Sa seule chance de le décrypter
est d’inverser la fonction à sens unique, ce qu’elle ne
peut faire sans connaître PB et qB. Bernard a tenu
secrets PB et qB mais Ève, comme tout le monde, sait
que NB est 408 508 091. Ève tente donc de déduire les
valeurs de PB et qB en sortant les nombres qui, multi-
pliés l’un par l’autre, peuvent donner 408 508 091, pro-
cédé appelé factorisation.

Combien de temps exactement faudra-t-il à Ève pour
trouver les facteurs diviseurs de 408 508 091 ? Il Y a
plusieurs recettes pour essayer de factoriser NB. Certaines sont plus rapides que d’autres, mais toutes exigent de vérifier si chaque nombre premier peut ou non
diviser NB sans laisser de reste. Par exemple, 3 est un
nombre premier mais n’est pas un diviseur de
408 508 091 puisque 3 ne divise pas parfaitement
408 508 091. Eve passe donc au nombre premier suivant, le 5. Le 5 ne convient pas non plus, Ève passe
au suivant, et ainsi de suite.

Enfin elle arrive à 18 313,
le 2 OOOe nombre premier, qui est un facteur de
408 508 091. Ayant trouvé l’un des facteurs, il devient
facile d’avoir l’autre, qui se révèle être 22 307 . Avec
une machine à calculer pouvant tester quatre nombres
premiers à la minute, Ève aurait mis 500 minutes, soit
plus de huit heures, pour identifier PB et qB. Autrement
dit, Ève trouverait la clef secrète de Bernard et pourrait
ainsi déchiffrer le message en moins d’un jour.

Ceci ne peut être considéré comme une sécurité de
haut niveau, mais Bernard aurait pu choisir des
nombres premiers beaucoup plus grands et augmenter
ainsi la défense de sa clef privée. S’il avait choisi des
nombres premiers aussi élevés que 10 65 (ce qui veut
dire 1 suivi de 65 zéros, ou cent mille millions de mil-
lions de millions de millions de millions de millions
de millions de millions de millions de millions), cela
aurait donné une valeur à N d’environ 10^ 65 x 10^65 =
10^ 13 0. Un ordinateur peut multiplier les deux nombres
premiers et générer N en une seule seconde, mais si
Eve tentait d’inverser le procédé et de trouver p et q,
cela lui prendrait un temps démesuré. Combien de
temps exactement ? cela dépend de la rapidité de son
ordinateur. L’expert en sécurité Simon Garfinkel estimait qu’un ordinateur à 100 MHz d’Intel Pentium avec
une RAM de 8 mégabits mettrait à peu près cinquante
ans à factoriser un nombre aussi élevé que 10 ^130. Les
cryptographes ont une certaine tendance à la paranoïa
et envisagent les pires circonstances, comme une
conspiration mondiale pour faire céder leurs chiffres.
Aussi Garfinkel étudia-t-il ce qui se passerait si cent
millions d’ordinateurs personnels (le nombre d’ordinateurs vendus en 1995) se liguaient. Le résultat serait
qu’un nombre tel que 10^130 pourrait être factorisé en
15 secondes environ. On a donc considéré que pour
assurer une réelle sécurité, il fallait utiliser des
nombres premiers vraiment géants. Pour des transactions bancaires importantes, N tend à être au moins de
10 308 , ce qui est dix millions de milliards de milliards
de milliards de milliards de milliards de milliards de
milliards de milliards de milliards de milliards de mil-
liards de milliards de milliards de milliards de milliards
de milliards de milliards de milliards de milliards de
fois plus élevé que 10 130 ! Les efforts combinés de cent
millions de personnes avec leurs ordinateurs prendraient plus de mille ans pour faire céder un tel chiffre.

Avec des valeurs suffisantes attribuées à p et q, RSA
était imprenable.

Le seul risque pour la sécurité du cryptosystème
RSA à clef publique serait que, dans le futur, quel-
qu’un trouve un moyen rapide pour factoriser N. On
peut imaginer que dans dix ans, ou pourquoi pas
demain, quelqu’un découvrira une méthode de factorisation rapide, et RSA deviendra immédiatement
périmé. Toutefois, depuis plus de deux mille ans les
mathématiciens ont essayé de trouver une voie rapide
sans y parvenir et, à l’heure actuelle, factoriser réclame
toujours un temps de calcul considérable. La plupart
des mathématiciens pensent que ces difficultés sont
inhérentes à la factorisation, et que certaines lois
mathématiques interdisent tout raccourci. S’ils ont rai-
son, le RSA semble sûr pour l’avenir immédiat.
Le grand avantage de la cryptographie à clef
publique RSA est qu’elle en finit avec tous les problèmes associés aux chiffres traditionnels et à
l’échange de clefs. Alice n’a plus à se soucier du trans-
port de la clef pour Bernard, ni à s’inquiéter d’une
interception d’Ève. En fait, peu importe à Alice que
quelqu’un d’autre voie la clef publique - plus on est
de fous, plus on rit - puisque cette clef ne sert qu’au
chiffrement et non au déchiffrement, et qu’Alice peut
la garder toujours sur elle.

RSA fut présenté pour la première fois en août 1977
dans un article signé par Martin Gardner et intitulé A
New Kind of Cipher that Would Take Millions of Years
to Break, dans sa rubrique de jeux mathématiques du
Scientific American. Après avoir expliqué comment
fonctionne la cryptographie à clef publique, Gardner
proposait un concours à ses lecteurs. Il publiait un texte
chiffré et donnait la clef publique utilisée pour son
chiffrement :

N = 114 381 625 757 888 867 669 235 779 976 146 612
010218296721 242362 562 561 842 935 70’6935
245 733 897 830 597 123 563 958 705 058 989 075
147 599290026 879 543 541.

Le jeu consistait à factoriser N en p et q, et à utiliser
ensuite ces nombres pour déchiffrer le message. Le
prix était de cent dollars. Gardner n’avait pas la place
pour expliquer en détail le RSA, il demandait donc
aux lecteurs d’écrire au Laboratoire du MIT qui leur
enverrait une note technique. Rivest, Shamir et Adleman furent étonnés de recevoir mille demandes. Ils n’y
répondirent d’ailleurs pas immédiatement, craignant
que la diffusion de leur idée ne compromette leurs
chances d’obtenir un brevet. Lorsque cela fut fait, le
trio organisa une réunion pour fêter l’événement. Pro-
fesseurs et étudiants eurent droit à des pizzas et à de
la bière, et furent invités aussi à mettre la note tech-
nique’ sous enveloppe pour les lecteurs du Scientific
American.

Quant au concours de Gardner, il a fallu dix-sept ans
pour que le chiffre soit brisé. En avril 1994, une équipe
de six cents volontaires révéla les facteurs de N.
q = 3490529510847650949 147 849619903 898
133 417 764638 493 387 843 990 820 577.
p = 32 769 132 993 266 709 549 961 988 190 834461
413 177 642 967 992 942 539 798 288 533.

En utilisant ces valeurs comme clef privée, ils furent
capables de déchiffrer le message. Celui-ci était une
série de nombres, qui convertis en lettre donnèrent :
The magic words are squeamish ossifrage. La factorisation avait été confiée à des volontaires appartenant à
des pays aussi éloignés que l’Australie, l’Angleterre,
les Etats-Unis et le Venezuela. Ils consacrèrent leurs
loisirs à travailler sur des ordinateurs, chacun étant
chargé d’une fraction du problème. Même en tenant
compte de l’organisation considérable nécessitée par
ces calculs en parallèle, certains lecteurs seront surpris
que le système RSA ait été brisé en un temps si court,
mais il faut noter que le concours portait sur une valeur
de N relativement petite, de l’ordre de 10 129 . Aujourd’hui, les utilisateurs de RSA prendraient une valeur
beaucoup plus élevée pour protéger une information
importante. Il est maintenant courant de crypter un
message avec une valeur de N telle que tous les ordinateurs de la planète auraient besoin d’un temps plus long
que l’âge de l’univers pour briser le chiffre.

Un message, un commentaire ?

modération a priori

Ce forum est modéré a priori : votre contribution n’apparaîtra qu’après avoir été validée par un administrateur du site.

Qui êtes-vous ?
Votre message

Pour créer des paragraphes, laissez simplement des lignes vides.