« Sésame, ouvre-toi ! »

Transmettre ce qui doit rester secret. S’entendre, sur le codage et sur la clef à utiliser, pour d’un côté, brouiller le message, et de l’autre, le décrypter. Le tout dans le plus grand secret, afin que l’ennemi ne se doute de rien. Mais aussi percer son propre mode de communication et déjouer ainsi ses stratégies. Lire sans être lu. C’est là tout l’enjeu de la cryptographie : la science du chiffre. Une science faite, en somme, de verrous et de clefs. C’est aussi un affrontement perpétuel, qui n’a jamais cessé depuis plus de deux mille ans, et qui oppose les concepteurs et les briseurs de code. Armées de l’ombre, héros discrets, ce sont eux pourtant qui, en amont des décisions, dictent la guerre. La Troisième Guerre mondiale sera-t-elle celle du renseignement ? C’est ce que pensent certains… mais rendons à César ce qui lui appartient…

I. De César au monde contemporain

1. Les cryptosystèmes de César

On connaît de César bien des astuces pour communiquer avec ses acolytes. L’un de ses procédés consistait à raser la tête d’un esclave, d’inscrire le message sur le sommet de son crâne, puis d’attendre patiemment la repousse des cheveux – on n’avait pas à l’époque la même notion de l’urgence ! Un autre consistait à remplacer l’alphabet latin par le grec. Les Germains n’avaient ainsi aucune chance de le lire. Un autre encore, connu sous le nom de système de César, consistait à décaler toutes les lettres du texte clair un certain nombre de fois vers la droite. Apprenant, par exemple, que d’irréductibles gaulois tenaient tête à son armée dans une région reculée de l’empire, il aurait écrit au malheureux centurion : « Yhqldp, ylgher, ylqfdp ». Après décalage de trois crans, cette fois-ci vers la gauche, le dit centurion aurait découvert avec soulagement : « Veniam, videbo, vincam », promesse (vaine) d’une victoire prochaine.

Message caché, message brouillé, il n’en reste pas moins que le mode de transmission n’est pas exempt de tout risque. Dans le premier cas, l’esclave pouvait trahir, offrir ses bons et loyaux services à l’ennemi en échange d’une forte somme. La substitution des deux alphabets, quant à elle, n’offrait qu’un codage éphémère, nos barbares finiraient bien par apprendre les rudiments de la langue grecque ; pire encore, l’armée romaine abritait peut-être en ses rangs quelques traîtres grecophones. Le système de César, enfin, semble bien meilleur que les deux autres : le message tombant dans les mains de l’ennemi ne trahirait rien de son contenu. Mais un esprit avisé et patient du camp ennemi saura peut-être le déchiffrer, puisque ce système de cryptage ne dispose que d’un nombre limité de clefs : l’alphabet ne comportant que 26 lettres, il n’offre que 25 possibilités de codage.

2. La cryptanalyse des Arabes

Les concepteurs de code ont alors travaillé à découvrir un système de cryptage dont le nombre de clefs serait tel que les briseurs de code ne pourraient en venir à bout. L’un d’eux est le codage par substitution : chacune des lettres de l’alphabet est remplacée par une autre. Le a est remplacé par le x, le b par le t, etc. Le nombre de clefs est énorme : 26 possibilités pour le a, qui peut être remplacé par le a, le b, …, ou le z ; 25 possibilités pour le b, qui peut être remplacé par toutes les lettres de l’alphabet, exceptée celle qui remplace le a. Pour la substitution de ces deux premières lettres, il y a donc 26x25, soit 650 possibilités. On réitère le processus jusqu’à la dernière lettre de l’alphabet, z, et le nombre de clefs s’élève à 26x25x24x…x3x2x1, soit plus de 400 millions de milliards de milliards de clefs. Oups ! Impossible dans ces conditions de toutes les essayer… Aussi ce mode de cryptage était réputé inviolable.

Pourtant, dès le IXe siècle, les cryptographes arabes savaient briser ce code. Comment ? Chaque lettre étant remplacée par une autre et une seule, ce procédé cachait en fait un terrible défaut, celui de la conservation des fréquences. Si, dans le texte clair, la lettre e apparaît 24 fois, alors la lettre qui a pris sa place dans le texte chiffré apparaîtra également 24 fois, ni plus, ni moins. Ainsi, si l’on sait que le message est écrit en langue française, comme la lettre e en est la plus fréquente, il suffira de repérer la lettre la plus fréquente du texte chiffré, qui aura toutes les chances de correspondre à la lettre e. La seule analyse de la fréquence des lettres ne permet pas, évidemment, un déchiffrement complet du texte : il se peut qu’une lettre, bien qu’elle soit peu fréquente dans la langue utilisée, apparaisse de nombreuses fois dans le texte clair. Néanmoins, à force de tâtonnements, basés non seulement sur l’analyse de la fréquence des lettres mais aussi sur celle de groupements de deux lettres ou plus, le texte pourra avec un peu de bon sens être déchiffré. Intuition, conjecture, astuce et une dose certaine de patience font voler en éclat tout codage par substitution.

3. DES : un système sûr

Dans cette guerre secrète que se livrent depuis des siècles les cryptographes (les concepteurs de code) et les cryptanalystes (ceux qui tentent de les briser), il est clair que ces derniers avaient pris le dessus. Chaque message expédié était susceptible de tomber dans des mains ennemies et d’être lu par un expert en déchiffrement. Le 8 février 1587, la reine d’Ecosse Marie Stuart en fit d’ailleurs les frais, puisque le décryptage de ses lettres par l’analyse des fréquences mit au jour sa participation au complot contre la reine d’Angleterre Elizabeth, contrainte alors à la condamner à mort par décapitation.

Aussi, avec la multiplication des échanges, les cours européennes devaient se munir d’un code fiable. Un nouveau chiffre vit le jour dans la première moitié du XVIe siècle, dû à un diplomate français, Blaise de Vigenère. La grande avancée résidait dans le fait que plusieurs lettres pouvaient remplacer une seule et même lettre. Ainsi, la lettre e pouvait être remplacée, au sein d’un même message, tantôt par un t, un c, un s, etc. L’analyse directe des fréquences n’était donc plus possible. Le remplacement des lettres répondait à une procédure bien précise que l’expéditeur et le destinataire devaient suivre pour parvenir, l’un, à chiffrer le texte, l’autre, à le déchiffrer. Or, cette procédure, quoique construite autour d’un mot-clef secret échangé au préalable par nos deux protagonistes, faisait malheureusement apparaître quelques régularités. C’est ce que perçut un certain Charles Babbage, au milieu du XVIIIe siècle, soit deux siècles plus tard. La faille étant décelée, il ne fit alors qu’une bouchée du système de Vigénère. Les cryptanalystes prenaient à nouveau le dessus sur les cryptographes.

Cependant, plus d’un siècle plus tard, fut inventé un système standardisé de chiffrement, le DES^[1], répondant aux besoins nouveaux de l’information et de la communication. Il ne souffrait d’aucune régularité, d’aucune faille donc, et son nombre de clefs, qui s’élevait à 100 millions de milliards, assurait enfin la confidentialité des échanges. Ce système est toujours d’actualité.

4. Atouts et limites du DES

Pour que l’expéditeur du message puisse utiliser le système DES, il lui faut choisir une clef, autrement dit un nombre, qu’il entre dans son ordinateur, qui fera le reste, à savoir crypter le message – rappelons que tout texte tapé sur le clavier d’un ordinateur est immédiatement converti par celui-ci en un nombre composé de 0 et de 1. Véritable clef de voûte du système, ce nombre, sur lequel repose tout l’édifice et vers lequel convergent tous les regards, le destinataire l’entrera à son tour dans son propre ordinateur, qui décryptera le message. Plusieurs bonds ont été franchis depuis l’Antiquité. A l’inverse du système de César, le système DES est connu de tous : de l’expéditeur, du destinataire, mais aussi de l’ennemi. La force du DES ne réside plus dans le secret du mode de cryptage – ce qui était la force du système de César – mais dans son grand nombre de clefs qui est passé de 25 à un nombre qui dépasse l’entendement – on pourrait dire en quelque sorte que la force de la clef s’est substituée à celle du verrou. De plus, le système DES ne dépend plus de la fiabilité de l’intermédiaire, si ce n’est celle de l’ordinateur.

Mais ce système DES, comme tous les systèmes de cryptage qui l’ont précédé, repose sur l’échange d’une clef, d’un secret : tondre la tête d’un esclave, décaler les lettres de trois crans vers la droite, ou encore entrer un nombre dans son ordinateur. Or, ce secret, il a bien fallu que les principaux intéressés, l’expéditeur et le destinataire du message, se le communiquent. Avec la multiplication exponentielle des échanges, on se doute aisément que ce fut là un véritable problème. Comment transmettre la clef ?

II. Ne plus transmettre la clef

L’idée est la suivante : et s’il suffisait, non plus de se transmettre la clef, mais de la construire à partir d’une série de calculs élémentaires ? La première partie de cette série s’effectuerait au grand jour, afin que l’expéditeur et le destinataire partent sur les mêmes bases de calcul, et la seconde s’effectuerait secrètement, sans même que les deux protagonistes ne s’échangent quoi que ce soit. L’ennemi n’assisterait ainsi qu’à une partie de ces échanges, la première, et ne pourrait donc connaître la clef commune. C’est cette idée que poursuivirent dans les années 70 trois chercheurs acharnés, Diffie, Hellmann et Merkle. Mais avant de pénétrer leur système, il nous faut nous attarder sur une notion arithmétique : le modulo.

1. Modulo

Pour comprendre cette notion, prenons l’exemple le plus parlant : le modulo 12. Si l’aiguille de ma montre est positionnée sur le 7, et que je lui fais faire un tour de cadran, elle sera à nouveau positionnée sur le 7. Comme un cadran est composé de 12 positions, cela signifie qu’en modulo 12, le nombre 7 + 12 qui correspond à un tour de cadran à partir du 7, soit 19, équivaut au nombre 7. Ce résultat se note 19 = 7 mod 12, ou encore 19 = 7 [12]. Dire qu’il est 19h revient à dire qu’il est 7h de l’après-midi. Et si je recommence l’expérience, comme 19 + 12 = 31, j’obtiens une nouvelle égalité : 31 = 19 = 7 [12]. De 7 à 31, j’ai effectué deux tours de cadran. Que vaudrait alors 135, par exemple, en modulo 12 ? Pour le savoir, il me faut tout d’abord trouver le multiple de 12 se rapprochant le plus de 135. Ce multiple est 11, puisque 12x11 = 132. Dans ce cas, j’ai fait faire 11 tours de cadran à l’aiguille de ma montre. Ensuite, comme il manque 3 pour obtenir 135 (qui est donc égal à 12x11 + 3), j’obtiens : 135 = 3 [12]. Le résultat du modulo n’est autre que le reste de la division de 135 par 12.

Prenons garde au fait que les égalités obtenues en modulo 12 ne sont plus valables en d’autres modulos. Notre 135 n’est plus égal à 3 si l’on passe en modulo 10. En effet, 135 qui se décompose en 10x13 + 5, est égal à 5 modulo 10.

2. Fonction non réversible

Ce petit détour effectué, nous sommes maintenant en mesure de comprendre une notion clef – c’est le cas de le dire – de la cryptographie, celle de fonction à sens unique.

Commençons par les fonctions les plus simples, celles qui sont réversibles. Prenons pour comprendre l’exemple de la fonction 3^x.

Dans le sens direct, il est très simple de calculer 3^x pour x = 2 ou x = 4.

3² = 3x3 = 9. La fonction 3^x transforme 2 en 9.

3⁴ = 3x3x3x3 = 9x9 = 81. La fonction 3^x transforme 4 en 81.

Le sens inverse n’est pas foncièrement plus compliqué. Il consiste à retrouver le nombre initial à partir du résultat. Imaginons que ce résultat soit 27. On sait que 3² = 9 et que 3⁴ = 81. Le résultat 27 étant compris entre 9 et 81, il ne fait aucun doute que le nombre initial est 3, seul nombre compris entre 2 et 4. Vérifions : 3³ = 3x3x3 = 27.

La fonction 3^x est aisément réversible.

Le raisonnement que nous avons utilisé repose sur le fait que plus x est grand, plus le résultat 3^x l’est également. Remarque de bon sens mais qui a son importance, car en arithmétique modulo, ce n’est plus le cas. De manière générale, les fonctions ne sont plus aussi simples à inverser.

Pour s’en convaincre, essayons, à partir du résultat 7, de retrouver le nombre initial par la fonction 3^x en modulo 10. Essayons, autrement dit, de retrouver ce que vaut x.

3⁴ = 81 = 1 [10]. Le nombre 4 n’est donc pas le nombre initial, puisque le résultat ne doit pas être 1, mais 7. Si nous raisonnions comme en arithmétique classique, puisque le résultat est 7 et que nous n’avons obtenu que 1, nous serions tentés d’essayer un nombre plus grand que 4. Pourtant le nombre initial est 3 puisque 3³ = 27 = 7 [10]. Et pour compliquer le tout, 3 n’est même pas la seule réponse puisque 3⁷ = 3x3x3x3x3x3x3 = 2187 = 7 [10].

Conclusion, nous avons là une fonction difficilement réversible, ce qui est capital, comme nous allons le comprendre, pour l’affaire qui nous occupe ici : la transmission de la clef.

3. Alice, Bernard et … Estelle

a- Situation

Imaginons que Bernard veuille envoyer un message secret à Alice : l’heure et le lieu pour des amours illicites, qui sait… Bernard et Alice utiliseront sans doute le système DES pour assurer la confidentialité de leurs échanges. Reste qu’ils doivent, au préalable, s’entendre sur la clef, ce fameux nombre qu’ils devront entrer dans leurs ordinateurs pour, du côté de Bernard, crypter le message, et du côté d’Alice, le décrypter.

Sage précaution, car Estelle, la femme de Bernard, est d’une jalousie maladive – non sans raison d’ailleurs. Aussi, curieuse de connaître le contenu des messages envoyés par son mari, elle ira fouiller dans son ordinateur et parviendra à s’introduire dans sa boîte mail – l’histoire ne nous dit pas comment. Certes, Bernard aura bien du mal à justifier à sa femme l’envoi d’un message codé – de surcroît  à une autre femme –, mais elle n’aura aucun moyen, scientifique du moins, pour lire son contenu : trop de clefs. Comment s’y sont-ils pris pour communiquer ?

Par un message clair, Bernard informe Alice de son intention de lui envoyer un message, tout cela sur un ton neutre, comme s’il s’agissait d’une collègue de bureau, prévoyant ainsi le cas où sa femme aurait les oreilles baladeuses… En outre, notre Bernard précise à sa « collègue de bureau » qu’il veut utiliser le système DES et choisit pour cela un nombre quelconque N et un nombre premier p qui lui est supérieur et qui sera le modulo (par exemple N = 3 et p = 13). Estelle (l’ennemi) dispose à ce stade d’autant d’informations qu’Alice (le destinataire) : le système et les nombres choisis par Bernard (l’expéditeur). Or, comme nous allons le voir, cela n’altère en rien la sécurité de leurs échanges.

b- Procédé

Bernard choisit un nombre e (e comme expéditeur) qu’il garde secret. Par exemple le nombre 2.

Alice choisit un nombre d (d comme destinataire) qu’elle garde secret. Par exemple le nombre 4.

Publiquement, aux yeux de tous donc, Bernard envoie à Alice par ordinateur le nombre N^e [p], soit, dans notre exemple, 3² [13], c’est-à-dire 9 (3² = 3x3 = 9 [13])^[2].

De même, Alice envoie à Bernard le nombre N^d [p], soit 3⁴, c’est-à-dire 3 (3⁴ = 3x3x3x3 = 81 = 13x6 + 3 = 3 [13]).

Estelle voit ainsi passer sous ses yeux – on imagine qu’elle peut sans peine s’introduire dans leurs boîtes mail – les nombres envoyés par Bernard et Alice, soit 9 et 3, et avec un peu de patience, elle pourra sans difficulté deviner que leurs nombres secrets sont 2 et 4 : ici, les nombres sont tout petits. Dans la réalité en revanche, les nombres utilisés sont très grands^[3], et le temps de calcul pour trouver e ou d est de l’ordre de plusieurs décennies, même sur de puissants ordinateurs ; il en est ainsi grâce à l’utilisation de l’arithmétique modulo qui rend difficile l’inversion de la fonction puissance. Aussi, le risque pris par nos amants est infime.

Reprenons. Alice reçoit donc N^e, soit 9, et calcule, à l’abri des regards, (N^e)^d, soit 9⁴, grâce au nombre d qu’elle a choisi secrètement : 9⁴ = 9x9x9x9 = 6561 = 13x504 + 9 = 9 [13].

De son côté, Bernard reçoit N^d, soit 3, et calcule, à l’abri des regards, (N^d)^e, soit 3², grâce au nombre e qu’il a choisi secrètement : 3² = 3x3 = 9 [13].

On constate alors que le résultat de Bernard est le même que celui d’Alice : 9 [13]. Nos amants ont ainsi en main un nombre qu’ils sont les seuls à connaître, puisqu’il est obtenu à partir de leurs nombres secrets e et d. Ce fameux nombre^[4] devient alors la clef secrète du système qu’ils n’auront plus qu’à insérer dans leurs ordinateurs.

c- Epilogue

Nos trois chercheurs américains qui mirent au point ce procédé exposèrent leur découverte en 1976 devant un auditoire médusé. Un des axiomes de la cryptographie venait de tomber : deux personnes, désormais, peuvent communiquer en toute confidentialité sans partager le moindre secret. Sans doute, il faut bien que quelque part dans le procédé, il y ait secret : un échange entièrement public serait, par définition, lisible par tout le monde, mais le secret ne réside pas là où on l’attend habituellement. Il n’est ni dans la communication du système utilisé : l’utilisation du système DES est clairement annoncée ; ni dans celle de la clef. L’astuce, profondément géniale, est que la clef n’est pas transmise, mais construite, en deux temps. Le premier se fait publiquement : Estelle voit passer sous ses yeux N^e et N^d, mais elle ne peut trouver ni e, ni d. Le second voit la construction définitive de la clef commune, mais Estelle, elle, ne voit rien du tout : c’est Alice et Bernard qui, chacun dans leur coin et grâce à leurs nombres secrets respectifs, effectuent le dernier calcul de puissance.

Conclusion

Le procédé Diffie-Hellmann-Merkle élimine une bonne fois pour toutes le problème réputé insurmontable de la transmission de la clef. Associé au système DES dont le nombre colossal de clefs assure la confidentialité des échanges, il semble même donner un avantage définitif aux cryptographes. Mais cet avantage n’est que théorique, car surgit une nouvelle difficulté, a priori tout aussi insurmontable que celle de la transmission de la clef : la communication basée sur un tel procédé nécessite des échanges préalables : Bernard et Alice doivent être connectés en même temps pour pouvoir construire la clef. Or, comment Alice pourrait-elle savoir que Bernard souhaite communiquer avec elle ? Quand bien même, Alice, qui habite au Japon, devrait allumer son ordinateur en pleine nuit pour pouvoir communiquer avec son amant parisien ! Pas si grave s’il ne s’agit que d’un échange amoureux. Mais, à l’ère du tout informatique, qui implique toute la planète, la nécessité d’une connexion simultanée de l’expéditeur et du destinataire pose, on s’en doute, de véritables problèmes.

On pouvait penser qu’après plus de deux mille ans, les cryptograghes avaient définitivement gagné la guerre face aux cryptanalystes, mais ce n’était qu’une bataille, une de plus parmi tant d’autres. La guerre se poursuit…

Notes :

1- Le fonctionnement d’un tel système – tout comme celui de Vigénère – serait trop long à expliciter. Disons qu’il est constitué de câbles électriques, de rotors, bref, de tout un appareillage qui multiplie de manière considérable le nombre de clefs.

2- Nous avons précisé plus haut que le nombre p devait être premier (un nombre premier est, rappelons-le, un nombre qui ne peut être divisible que par 1 et par lui-même). Imaginons en effet que N = 6 et p = 4 (non premier donc, puisque 4 = 2 x2). Bernard envoie alors à Alice le nombre 0 ! En effet, N^e = 6² = 6x6 = 36 = 4x9 = 0 [4].

Le nombre p doit être supérieur à N. Imaginons en effet que N = 12 et p = 5. Bernard peut alors se ramener à un nombre N inférieur à p, puisque N = 12 = 5x2 + 2 = 2 [5]. 2 est bien inférieur à 5.

3- Bernard peut choisir un nombre N aussi grand qu’il le souhaite. En effet, comme il existe une infinité de nombres premiers, il n’a que l’embarras du choix pour le nombre premier p supérieur à N.

4- Ce résultat commun ne dépend nullement des nombres préalablement choisis. En fait, Bernard calcule (3⁴)², soit (3x3x3x3)², c’est-à-dire 3x3x3x3 x 3x3x3x3. De son côté, Alice calcule (3²)⁴, soit (3x3)⁴, c’est-à-dire 3x3 x 3x3 x 3x3 x 3x3, ce qui revient au même, puisque nos deux amants calculent tous les deux 3⁸.

De manière plus générale, quels que soient les nombres N, d et e, on a : (N^e)^d = (N^d)^e = N^exd. Cette propriété est la commutativité de l’exponentielle, et c’est ce tout petit rien mathématique, mêlé à l’arithmétique modulo, qui assure le secret des échanges.

Bibliographie :

- Simon Singh, Histoire des codes secrets, JC Lattès, 1999

- Gilles Dubertret, Initiation à la cryptographie, Vuibert, 2000,

- Douglas Stinson, Cryptographie, Théorie et pratique, International Thomson publishing France, 1996.