Le monde est mathématique
Codage et cryptographie
Le 4 septembre 2019 Voir les commentaires (11)
Cet article a été écrit en partenariat avec L’Institut Henri Poincaré
En 2013, l’Institut Henri Poincaré et Images des Mathématiques avaient uni leurs efforts pour superviser la réédition de la collection Le monde est mathématique, publiée par RBA en partenariat avec Le Monde. En 40 ouvrages, cette collection de qualité, issue d’un projet collectif de mathématiciens espagnols, vise à présenter, à travers une grande variété de points de vue, de multiples facettes des sciences mathématiques, sous un aspect historique, humain, social, technique, culturel ... Reprise et améliorée au niveau de la forme, cette édition avait été entièrement lue et corrigée par l’équipe d’Images des Mathématiques ; des préfaces et listes bibliographiques rajoutées.
En 2019, cette collection est de nouveau éditée, présentée par Étienne Ghys et distribuée par L’Obs.
Chaque semaine, à l’occasion de la sortie d’un nouveau numéro de la série, un extrait sélectionné sera présenté sur Images des Mathématiques. Il sera également accompagné du sommaire du livre et d’une invitation à prolonger votre lecture.
Extrait du Chapitre 5. Un secret de polichinelle : la cryptographie à clé publique
La cryptographie n’a pas échappé à l’irruption du traitement informatique et à son développement postérieur. Employer un ordinateur pour le chiffrement d’un message est une opération en grande partie identique au chiffrement sans lui, à trois différences près... La première, c’est qu’un ordinateur peut être programmé pour simuler le travail d’une machine conventionnelle de chiffrement de, par exemple, mille rotors, sans avoir besoin de la fabriquer physiquement. Deuxièmement, un ordinateur ne travaille qu’avec des chiffres binaires, et, par conséquent, tout chiffrement se fait à ce niveau (même si par la suite les informations numériques sont de nouveau décodées en informations textuelles). Enfin, les ordinateurs se caractérisent par une vitesse de calcul et de traitement extraordinaire.
Dans les années 1970, les premiers chiffrements ont été conçus pour tirer parti du potentiel des ordinateurs, comme Lucifer, un chiffrement qui divisait le texte en blocs de 64 bits et en cryptait une partie par un remplacement complexe, avant de les réunir dans un nouveau bloc chiffré de bits et de répéter l’opération. Le système exigeait un ordinateur équipé d’un programme de cryptage ainsi qu’une clé numérique à la fois pour l’émetteur et le récepteur. Une version de 56 bits de Lucifer, dénommée DES, fut lancée en 1976 aux États-Unis et constituait toujours, en 2009, l’un des standards de chiffrement dans ce pays.
Le chiffrement a indubitablement tiré parti de la capacité de traitement des ordinateurs, mais, tout comme leurs prédécesseurs millénaires, ceux-ci continuaient d’être exposés au risque qu’un récepteur indésirable parvienne à obtenir les clés et, connaissant l’algorithme de chiffrement, à déchiffrer le message. Cette faiblesse élémentaire de tout système « classique » de cryptographie est connue comme le problème de la distribution de clé.
Le problème de la distribution de clé
Depuis que la communauté cryptographique s’est mise d’accord sur le fait que la protection des clés, davantage que celle de l’algorithme, était l’élément fondamental qu’il fallait garantir pour assurer la sécurité des cryptosystèmes, leur implantation a dû
s’attaquer au problème de la distribution des clés en toute sécurité. Dans le meilleur des cas, cela occasionnait de véritables problèmes logistiques : par exemple, au moment de distribuer les milliers de livres de clés générés par une armée importante ou de le faire à des centres de communication mobiles opérant dans des circonstances extrêmes, comme l’équipage des sous-marins ou les unités sur le front de bataille. La sophistication d’un système de cryptage « classique » n’a pas d’importance : ils sont tous vulnérables à l’interception de leurs clés respectives.
L’algorithme de Diffie-Hellman
La notion d’« échange sûr de clés » peut sembler une contradiction : la transmission même de la clé est en soi un message, si bien qu’elle doit aussi être cryptée et avec une clé qui a préalablement dû être échangée. Cependant, si l’échange est envisagé comme un processus de communication en plusieurs phases, il est possible d’imaginer une solution au problème, du moins en théorie.
Supposons qu’un émetteur quelconque dénommé Alice crypte un message avec une clé propre et l’envoie à un récepteur, Bob. Ce dernier crypte de nouveau le message chiffré avec une autre clé propre et le renvoie à l’émetteur. Alice déchiffre le message avec sa clé et envoie ce nouveau message, qui n’est alors plus chiffré qu’avec la clé de Bob, lequel commence à le déchiffrer. Le problème millénaire d’échange sûr de clés vient d’être résolu. Mais cela se passe-t-il vraiment comme cela ? La réponse est non. D’ailleurs, dans tout algorithme de chiffrement complexe, l’ordre d’application de la clé est fondamental, et nous avons vu dans notre exemple théorique que Alice doit déchiffrer un message déjà chiffré avec une autre clé. L’inversion de l’ordre des chiffrements aboutirait à un galimatias. La théorie ne sert à rien dans ce cas, mais elle a tracé la voie à suivre.
LES HOMMES À L’ORIGINE DE L’ALGORITHME
Bailey Whitfield Diffie (ci-dessous) est né en 1944 aux Etats-Unis. Mathématicien formé au Massachusetts institute of technology (MIT), il est depuis 2002 le directeur de la sécurité et vice-président de Sun Microsystems, dont le siège est en Californie.
Quant à Monte Hellman, ingénieur, il est né en 1945 et a effectué sa carrière professionnelle chez IBM et au MIT, où il fit la connaissance de Diffie.
En 1976, deux jeunes scientifiques américains, Whitfield Diffie et Monte Hellman, ont trouvé un moyen pour que deux personnes échangent des messages chiffrés sans avoir pour cela à échanger de clé. Cette méthode repose sur l’arithmétique modulaire, ainsi que sur les propriétés des nombres premiers des opérations où ils interviennent.
L’idée est la suivante :
1) Alice choisit un nombre quelconque, qu’il maintient secret. Nous appellerons ce nombre $N_{j1}$.
2) Bob choisit un autre nombre quelconque, qu’il maintient aussi secret. Nous appellerons ce nombre $N_{p1}$.
3) Ensuite, Alice et Bob appliquent tous deux sur leur nombre respectif une fonction du type $f(x) = a^x$ mod $p$, où $p$ est un nombre premier connu.
- Alice obtient comme résultat un nouveau nombre, $N_{j2}$, qu’il envoie cette fois à Bob.
- Bob obtient comme résultat un nouveau nombre, $N_{P2}$, qu’il envoie à Alice.
4) Alice résout une équation du type $N_{P2}^{N_{j1}}$(mod $p$) et obtient comme résultat un nouveau nombre : $C_J$.
5) Bob résout une équation du type $N_{J2}^{N_{P1}}$ (mod $p$) et obtient comme résultat un nouveau nombre : $C_P$.
Bien que cela semble étonnant, $C_J$ et $C_P$ seront égaux. Et voici donc la clé. Notez que le seul moment où Alice et Bob ont échangé des informations, c’est lorsqu’ils
ont convenu de la fonction $ f(x) = a^x$ mod $p$ et qu’ils se sont envoyé $N{_J2}$ et $N_{P2}$ , qui ne constituent pas la clé et dont l’éventuelle interception, par conséquent, ne compromet pas la sécurité du cryptosystème. La clé de ce système aura la forme générale
\[ a^{N_{J1}⋅N_{P1}} \text{(mod} \, p).\]
Par ailleurs, il est important de tenir compte du fait que la fonction originale a la particularité de ne pas être réversible. Autrement dit, si l’on connaît la fonction ainsi que le résultat de son application à une variable $x$, il est impossible (ou du moins très difficile) d’obtenir la variable $x$ originale.
Pour que tout soit bien clair, répétons l’opération avec des fonctions et des chiffres concrets. La fonction choisie est, par exemple,
\[f(x) = 7^x \text{(mod} \,11)\]
1) Alice choisit un nombre $N_{j1}$ , par exemple 3, et calcule $f(x) = 7^x $(mod 11)
- ce qui donne $f(3) = 7^3 ≡ 2$ (mod 11).
2) Bob choisit un nombre $N_{P1}$ , par exemple 6, et calcule $f(x) = 7^x$ (mod 11)
- ce qui donne $f(6) = 7^6 ≡ 4$ (mod11).
3) Alice envoie à Bob son résultat, 2, et Bob fait de même avec le sien, 4.
4) Alice calcule $4^3 ≡ 9$ (mod 11).
5) Bob calcule $2^6 ≡ 9$ (mod 11).
Cette valeur, 9, sera la clé du système.
Alice et Bob ont échangé la fonction $f(x)$ ainsi que les chiffres 2 et 4. Quelles informations apportent réellement ces deux données à un éventuel espion ? Supposons que notre récepteur inattendu connaisse la fonction ainsi que les chiffres. Il est maintenant confronté au problème de la résolution de  $7^{N_{J1}} ≡ 2$ (mod 11) et $ 7^{N_{P1}} ≡ 4$ (mod 11) modulo 11, où $N_{J1}$ et $N_{P1}$ sont les nombres que Alice et Bob maintiennent secrets. S’il arrive à les obtenir, il lui suffira pour obtenir la clé de résoudre $a^{N_{J1}⋅N_{P1}}$ modulo $p$. La solution à ce problème, au fait, s’appelle en mathématiques un logarithme discret.
Par exemple, dans le cas de
\[f(x) = 3^x \text{(mod 17)},\]
on observe que $3^x ≡ 15$ (mod 17), et, en essayant avec différentes valeurs de $x$, on obtient que, si $x = 6$, la relation $3^x ≡15$ (mod 17) est vérifiée.
Les algorithmes de ce type et le problème du logarithme discret n’ont reçu aucune attention particulière avant le début des années 1990, et ce n’est que ces dernières années qu’ils ont été réellement développés. Dans cet exemple, on dit que 6 est le logarithme discret de 15 en base 3 modulo 17.
La particularité des équations de ce type, comme mentionné ci-dessus, c’est qu’elles sont difficilement réversibles (elles sont dites asymétriques). Pour des valeurs de $p$ de plus de 300 chiffres et de $a$ de plus de 100, la solution, et donc la rupture de la clé, devient extrêmement difficile.
VIRUS ET « PORTES DÉROBÉES »
Même le plus sûr des chiffrements à clé publique dépend du fait que la clé privée soit maintenue secrète. En conséquence, un virus qui s’installerait dans le système d’un émetteur, localiserait et transmettrait cette clé privée ferait tomber à l’eau tout le cryptosystème.
En 1998 s’est fait jour l’histoire d’une entreprise suisse leader en matière d’élaboration et de vente de produits cryptographiques, qui avait inclus dans ces produits des « portes dérobées » qui détectaient les clés privées des utilisateurs et les renvoyaient à l’entreprise. Une partie de ces informations fut remise au gouvernement américain, qui pouvait de cette façon, à tous les effets, surveiller les communications entre les ordinateurs infectés.
Cet algorithme est l’un des piliers de la cryptographie moderne. Diffie et Hellman ont exposé leur idée lors d’un Congrès national de l’informatique, à l’occasion d’un séminaire qu’il convient de qualifier d’historique. Ce travail peut être consulté dans sa totalité à l’adresse www.cs.berkeley.edu/ christos/classics/diffiehellman.pdf, sous le titre New Directions in Cryptography (« Nouvelles directions en cryptographie »).
L’algorithme de Diffie-Hellman a démontré, en théorie, la possibilité de créer une méthode cryptographique qui n’aurait besoin d’aucun échange de clés, mais, paradoxalement, qui reposerait sur la communication publique d’une partie du processus (les deux nombres initiaux qui servent à déterminer la clé).
Autrement dit, cet algorithme a démontré la viabilité d’un cryptosystème dont les émetteurs et les récepteurs n’ont pas besoin de se retrouver pour établir les clés. Mais il reste toutefois certains inconvénients : si Alice souhaite envoyer un message à Bob alors que celui-ci dort, par exemple, elle devra attendre qu’il se réveille pour pouvoir générer la clé.
Dans la quête de découvrir de nouveaux algorithmes plus efficaces, Diffie a théorisé sur un cryptosystème dont la clé de chiffrement serait distincte de celle de déchiffrement, aucune des deux ne pouvant évidemment être obtenue à partir de l’autre. Dans ce cryptosystème théorique, l’émetteur disposerait de deux clés : celle de cryptage et celle de décryptage. Des deux, seule la première serait rendue publique, pour que quiconque souhaitant envoyer un message puisse le crypter. Une fois le message reçu, l’émetteur procéderait à son déchiffrement à l’aide de la clé de décryptage, qui serait évidemment restée secrète. Cela dit, comment réussir à mettre en œuvre ce système ?
Les nombres premiers au secours : l’algorithme RSA
En août 1977, Martin Gardner, divulgateur scientifique américain de renom, a publié dans sa colonne de récréations mathématiques de la revue Scientific American un article intitulé « Un nouveau type de chiffrement qui prendrait des millions d’années pour être déchiffré ». Après avoir expliqué en détail à ses lecteurs les fondements du système à clé publique, il fit observer le message chiffré ainsi que la clé publique N utilisée pour cela :
\[N=114.381.625.757.888.867.669.235.779.976.146.\]\[612.010.218.296.721.242.362.562.561.842.935.706.935.245.733.\]\[897.830.597.123.563.958.705.058.989.075.147.599.290.026.879.\]\[543.541.\]
Gardner mit ses lecteurs au défi de déchiffrer le message à partir des informations données, en précisant que la solution exigeait de factoriser $N$ en ses composants premiers $p$ et $q$. Pour finir, Gardner promit une récompense de 100 dollars (montant important à l’époque) à celle ou celui qui trouverait la bonne réponse en premier. Toute personne souhaitant davantage d’informations sur le chiffrement en question, précisa Gardner,devait envoyer une demande au Laboratoire d’informatique du MIT à l’attention de ses créateurs Ron Rivest, Adi Shamir et Len Adelman.
La bonne réponse ne fut reçue que 17 ans plus tard, et la collaboration de plus de 600 personnes fut nécessaire pour la trouver. Les clés étaient
\[p = 32.769.132.993.266.709 .549.961.988.190.834.461.413.177.642.967.992.942.539. 798.288.533\]
et
\[q = 3.490.529.510.847.650.949.147.849.619.903.898.133.417.764. 638.493.387.843.990.820.577,\]
et le message chiffré : « The magic words are squeamish ossifrage » (« Les mots magiques sont délicats et cruels »).
L’algorithme présenté par Gardner est connu sous la dénomination RSA, sigle des noms de famille Rivest, Shamir et Adelman. Il s’agit de la première mise en œuvre pratique du modèle à clé publique imaginé par Diffie, et il est aujourd’hui assidûment employé. Il offre une sécurité extrême, car le processus de déchiffrement est incroyablement laborieux bien que, comme nous le verrons plus tard, pas impossible. Nous présentons ci-après les fondements du système de manière élémentaire, sans trop entrer dans la technique.
L’algorithme RSA en détail
L’algorithme RSA repose sur certaines propriétés des nombres premiers, que vous pourrez consulter dans les annexes du présent volume si vous souhaitez plus d’informations. Nous nous limiterons ici à exposer les règles de base qui en sont à l’origine.
- L’ensemble des nombres inférieurs à $n$ et premiers avec n est dénommé fonction d’Euler et est exprimé sous la forme $\varphi(n)$.
- Si $n = pq$, $p$ et $q$ étant deux nombres premiers, alors  $\varphi(n) = (p – 1)(q – 1).$
- D’après le petit théorème de Fermat, on sait que si $p$ est un nombre premier entier positif et $a$ un entier premier avec $p$ (ce qui signifie pgcd $(a, p) = 1$), l’équation $a^{p−1} ≡1$(mod p) doit être
vérifiée. - D’après le théorème d’Euler, si pgcd$(n,a) = 1$, alors $a^{\varphi(n)} ≡ 1$ (mod 1).
Comme nous l’avons mentionné précédemment, le système est dit à « clé publique » car la clé de cryptage est portée à la connaissance des émetteurs qui souhaitent envoyer des messages. Chaque récepteur possède une clé publique propre. On part du principe que les messages seront transmis convertis en nombres, à l’aide d’un code ASCII ou de tout autre moyen souhaité.
En premier lieu, Alice génère une valeur $n$ qui est le produit de deux nombres premiers $p$ et $q$ $(n = p·q)$, puis choisit une valeur $e$ de telle sorte que le pgcd$(\varphi (n), e) = 1$. Rappelons que $\varphi(n) = (p – 1)(q – 1)$. Les valeurs rendues publiques sont $n$ et $e$ (en aucun cas les valeurs $p$ et $q$ ne sont fournies). Le couple $(n,e)$ est la clé publique du système, et les valeurs $p$ et $q$ sont dénommées nombres RSA. Parallèlement, Alice calcule la valeur unique $d$ modulo $\varphi (n)$ qui vérifie $d·e = 1$, à savoir l’inverse de $e$ modulo $\varphi (n)$. On sait que cet inverse existe parce que pgcd $(\varphi(n),e)=1$. Cette valeur $d$ est la clé privée du système. Pour sa part, Bob emploie la clé publique $(n,e)$ pour crypter le message $m$ à l’aide de la fonction $M ≡m^e$ (mod $n$). À la réception du message chiffré, Alice réalise l’opération $M^d ≡{ (m^e)}^d$ (mod $n$), équivalent à $M^d ≡ (m^e)^d ≡ m$ (mod $n$), ce qui démontre que le message peut être déchiffré.
Nous allons maintenant appliquer le procédé exposé avec des valeurs numériques concrètes.
- Soit $p=3$ et $q=11$, d’où $ n=33. \varphi(33)=(3–1)·(11–1)=20$. Alice choisit $e$ de manière à n’avoir aucun diviseur commun avec $20$, par exemple, $e = 7$. La clé publique de Alice est $(33,7)$.
- Entretemps, Alice a calculé une clé privée $d$ qui sera l’inverse de 7 modulo 20, à savoir $7·3 ≡ 1$ (mod.20), d’où $d = 3$.
- Bob obtient la clé publique et souhaite envoyer le message « 9 » ou bien, $m=9$. Pour le chiffrer, il utilise la clé publique de Alice et résout l’équation suivante :
\[9^7 = 4.782.969 ≡ 15 \text{(mod 33)}.\]
Le message chiffré est « 15 ». Bob envoie le message.
Alice reçoit le message « M = 15 » et le déchiffre comme suit :
\[15^3=3.375 ≡ 9 \text {(mod 33)}. \]
Le message a bien été déchiffré.
Au fur et à mesure que sont choisis des nombres premiers $p$ et $q$ plus élevés, la difficulté de mise en œuvre de l’algorithme RSA augmente, au point que l’emploi de l’ordinateur devient nécessaire pour le calcul des congruences. Par exemple, soit $p = 23$ et $q = 17$, d’où $n = 391$. La clé publique qui en résulte pour $e = 3$ est (391,3). En conséquence, $d = 235$. Pour un message simple comme « 34 », l’opération de déchiffrement est la suivante :
\[204^{235} = 34 \text{(mod 391)}.\]
Observez le degré de la puissance et pensez à la gigantesque capacité de calcul nécessaire pour trouver la congruence.
[...]
- Sommaire du livre
Pour aller plus loin
- Les tresses : de la topologie à la cryptographie (piste bleue).
- Des corps, des courbes, des couplages, des messages codés… et des logarithmes discrets. (piste rouge).
- Abraham Albert est mort il y a 40 ans] (actualité)
- Centenaire d’Alan Turing (actualité)
L’extrait proposé est choisi par le préfacier du livre : Vincent Beffara. Celui-ci répondra aux commentaires éventuels.
Partager cet article
Pour citer cet article :
Joan Gómez — «Codage et cryptographie» — Images des Mathématiques, CNRS, 2019
Laisser un commentaire
Articles suggérés
Si vous avez aimé cet article, voici quelques suggestions automatiques qui pourraient vous intéresser :
-
le 18 janvier 2021[Rediffusion d’un article publié en 2015] Une approche du problème du logarithme discret pour les enseignantslire l'article -
le 15 juin 2014La cryptographie du futur comme un jeu vidéo. Cryptris, un jeu de briques, propose d’explorer les travaux de recherche récents sur les « réseaux euclidiens », pour...lire l'article -
le 14 novembre 2013Quel est le lien entre la géométrie algébrique, la théorie des nombres, les records de calcul et le respect de votre vie privée ? La cryptographie ! Quelques explications dans cet...lire l'article
Dossiers
Actualités des maths
-
5 mars 2023Maths en scène : Printemps des mathématiques (3-31 mars)
-
6 février 2023Journées nationales de l’APMEP, appel à ateliers (9/4)
-
20 janvier 2023Le vote électronique - les défis du secret et de la transparence (Nancy, 26/1)
-
17 novembre 2022Du café aux mathématiques : conférence de Hugo Duminil-Copin (Nancy et streaming, 24/11)
-
16 septembre 2022Modélisation et simulation numérique d’instruments de musique (Nancy & streaming, 22/9)
-
11 mai 2022Printemps des cimetières
Commentaire sur l'article
Codage et cryptographie
le 5 avril 2013 à 23:13, par Christophe Boilley
Codage et cryptographie
le 18 avril 2013 à 15:44, par Vincent Beffara
Codage et cryptographie
le 18 avril 2013 à 19:02, par Christophe Boilley
Codage et cryptographie
le 6 avril 2013 à 01:08, par Cronos
Codage et cryptographie
le 9 avril 2013 à 02:00, par Cronos
Codage et cryptographie
le 13 avril 2013 à 11:04, par Jacques Jousset
Codage et cryptographie
le 18 avril 2013 à 16:00, par Vincent Beffara
Truffé d’erreurs
le 10 juin 2013 à 12:05, par Jérôme ^
Truffé d’erreurs
le 15 février 2022 à 13:58, par Yann Coudert
Codage et cryptographie
le 20 août 2013 à 12:29, par Audibert
Algo minimal d’échange de clé
le 24 mai 2019 à 09:50, par Yann Coudert