Cryptographions un peu

La question de la transmission d’information et de messages a toujours été cruciale au cours de l’Histoire. Comment faire savoir à quelqu’un quelque chose que mon ennemi ne doit absolument pas connaitre au cas où le message lui tomberait entre les mains ?
Comment cacher mon message, comment le rendre illisible ou incompréhensible pour une partie seulement de la population ?
De l’autre côté, la question du décodage devenait tout aussi importante ! Comment pénétrer les secrets de celui dont j’ai intercepté le message codé ?
Des guerres se sont gagnées, des complots se sont déjoués, des espions se sont fait démasquer par la réussite – ou non – à décoder un message secret.

Les premières techniques ancestrales tenaient plus de la stéganographie (art de cacher un message) que de la cryptographie (art de coder un message).
Par exemple un espion grec en Perse raconte comment il eut l’idée de graver sur le bois de ses tablettes un message et ensuite de les recouvrir de cire vierge. Il pouvait ainsi passer les points de contrôle, porteur de ses tablettes « vierges » en toute quiétude.
Ou bien encore, Nabuchodonosor, roi de Babylone qui rasait le crâne d’un esclave, lui tatouait dessus le message à transmettre, attendait que ses cheveux repoussent puis l’envoyait vers le destinataire (oui, la notion d’urgence était toute relative à cette époque…)

Le chiffre de César commence à être un peu plus développé. Il sert à Jules César à transmettre ses ordres à ses généraux. Le principe en est très simple : il consiste à décaler chaque lettre de l’alphabet de 3 rangs. A donne D, B donne E, C donne F, etc…

« Prenons cette phrase comme exemple » donne donc :
« MOBKLKP ZBQQB MEOXPB ZLLB BUBJMIB »
(En cryptographie, il est pour convention d’écrire en minuscule la phrase originale et en majuscules la phrase cryptée).

Aujourd’hui ce cryptage parait enfantin à n’importe qui mais, à l’époque, cela suffisait pour assurer la sécurité des transmissions.

Pour craquer ce type de codage, c’est simple, il suffit d’essayer de décaler d’une lettre, puis de 2 lettres, de 3, de 4, etc… jusqu’à tomber sur le bon décalage qui révèlera la phrase originale.

Du coup, l’évolution fut quelque temps plus tard d’affecter une lettre quelconque à chaque lettre, c'est-à-dire de ne pas rester dans l’ordre de l’alphabet mais d’être dans le désordre.
Par exemple :
a-> J ; b-> U ; c-> G ; d-> O, etc…
Il suffit juste d’établir la table des correspondances, que l’envoyeur et le récepteur ait la même et ils pourront alors communiquer.
Le carré de Polybe est le premier exemple de chiffrement par substitution homophonique.
On peut aussi – pour que ce soit plus simple - choisir un mot-clef pour définir les correspondances.
Imaginons que ma clef soit la phrase « Je pars en voyage ». Du coup, j’aurais la correspondance suivante (en virant les lettres redondantes) :

A b c d e f g h i j k l m n o p q r s t u v w x y z
J E P A R S N V O Y G B C D F H I K L M Q T U W X Z

Et « Prenons cette phrase comme exemple » devient alors :
« HKRDFDL PRMMR HVKJLR PFCCR RWRCHBR ».

On voit tout de suite que pour décrypter le message, on est mort si on ne dispose pas de la table des correspondances ou du mot-clef qui la définit. Cette fois, il n’y a plus d’ordre logique entre les lettres.

Ce système a très bien fonctionné pendant un bon millier d’années et il aurait pu parfaitement continuer jusqu’à l’avènement des ordinateurs. Or dès le 16e siècle, il est devenu obsolète et a été remplacé par un système beaucoup plus compliqué.

Mais comment en est on arrivé là ?

Au IXe siècle les Arabes sont les plus avancés en mathématiques, astronomie, médecine, etc. Ce sont même eux qui inventeront l’Arithmétique et l’ « Al-gèbre ». Je ne détaille pas ici les avancés et les progrès importants réalisés par les Arabes dans les différents domaines scientifiques mais il faut savoir que les Sciences connurent de grandes avancées grâce à eux.

Toujours est-il que les arabes vont également inventer la cryptanalyse. Ils découvrent que dans le langage, dans les mots que nous utilisons certaines lettres reviennent avec des fréquences plus importantes que d’autres.
En français par exemple, c’est le « e », le « a », etc. En allemand, c’est le « w » aussi.

Cette méthode de cryptanalyse découverte par Al-Kindi sera publié à cette époque sous le nom de « Manuscrit sur le déchiffrement des messages cryptographiques »

1ère page du manuscrit d'Al Kindi

Ils arrivent alors en analysant beaucoup d’écrits à établir une table de fréquence de chaque lettre de l’alphabet.

Ainsi, en français, la table est la suivante :
E = 15,87%
A = 9,42%
I = 8,41%
S = 7,90%
R = 6,46%
Etc…

Ce qui fait que si on connaît la langue d’origine d’un texte intercepté, on peut l’attaquer par ce biais.
Car si on effectue une analyse fréquentielle des lettres du message codé et que l’on trouve par exemple, que la lettre « P » revient 15% du temps, alors, il y a de fortes chances que cette lettre code pour le « e ». Et ainsi de suite.
Evidemment, il faut que le texte soit d’une certaine longueur pour que la fréquence d’apparition des lettres soit assez représentative.
D'autre part, il faut que le texte ne soit pas trop "axé". (La phrase "De Zanzibar à la Zambie et au Zaïre, des zones d'ozone font courir les zèbres en zigzags zinzins" peut vous illustrer ce que j'entends pas là...). Mais bon, de manière générale sur un texte long, l'analyse reste pertinente.
On peut aussi analyser les bigrammes. En français, les bigrammes les plus fréquents sont « mm », « ll », « pp » etc… Donc on pourra là aussi se servir de ça pour supposer des correspondances.
Bref, le travail peut être long, il faut aller à tâton bien souvent, mais on a dorénavant une accroche sur le texte et on peut le décoder !

Je trouve cette méthode de cryptanalyse absolument phénoménale.
L’idée est tout simplement géniale.

Mais du coup, comme toujours, les cryptographes vont réagir en améliorant leur système.
L’idée est alors d’ « effacer » la notion de fréquence d’apparition des lettres dans les message.
On peut, par exemple, utiliser un chiffre qui attribue plusieurs symboles pour une seule lettre, en fonction de sa fréquence (Par exemple, on utilisera 4 ou 5 symboles pour le E mais un seul pour le K). On dit alors que l'on utilise un code homophonique.
On peut également utiliser le surchiffrement qui consiste à recoder le texte chiffré par un autre type de chiffrement pour ne pas permettre de faire des hypothèses sur les lettres les plus fréquentes. Pour une combinaison de chiffrements bien choisie, un texte surchiffré sera donc plus difficile à déchiffrer.

L’aboutissement en la matière revient au français Vigénère, au XVIe siècle, avec son « Carré de Vigénère ».
Imaginez un carré de 26 sur 26 représentant sur chaque ligne l’alphabet, décalé à chaque fois d’un rang.
On définit ensuite une clef (un mot, une phrase).

Pour chaque lettre en clair du message original, on va alors sélectionner la colonne correspondante à cette lettre et pour une lettre de la clé correspondant au même rang, on sélectionne la ligne adéquate, puis au croisement de la ligne et de la colonne on trouve la lettre chiffrée.
La lettre de la clé est à prendre dans l'ordre dans laquelle elle se présente et on répète la clé en boucle autant que nécessaire.

Pour faire simple, cela consiste à attribuer une nouvelle table de correspondance à chaque lettre du message clair.

Cette méthode de cryptographie ne sera efficacement brisée qu’au XXe siècle par Babbage.
(je ne vous raconte même pas comment il faut s’y prendre. Il faut tout d’abord tenter de déterminer quelle est la taille de la clef puis repartir là aussi sur une méthode – patiente – d’analyse de fréquences).

De nombreuses méthodes de cryptage se succèdent au cours de l’Histoire.

Je peux par exemple citer le Grand Chiffre de Louis XIV qui était uniquement utilisé pour les communications les plus importantes de l’Etat. Il faudra là aussi attendre le XIXe siècle pour qu’il soit brisé.
Pour l’anecdote, ceci permettra de décoder une lettre du Roi désignant qui était le fameux « Masque de Fer ». (Pour connaître son identité, m’envoyer un mail flatteur accompagné d’un versement compensatoire de 500€).

Les deux premières guerres mondiales vont ensuite devenir le catalyseur de toute une série de perfectionnement tant dans l’élaboration de chiffrages complexes que dans les techniques de décryptage.

Toujours en terme d’anecdotes historiques, sachez par exemple que c’est l’interception et le décodage d’un message envoyé par les allemands aux mexicains (le célèbre télégramme de Zimmerman) leur demandant d’attaquer les Etats-Unis par le sud qui achèvera de convaincre Wilson de s’engager dans la guerre contre l’Allemagne.
C’est aussi grâce au travail d’un seul homme, la Lieutenant Painvin, que la victoire en novembre 1918 put arriver.
En effet, fin 1918, les Allemands veulent entreprendre leur plus grosse contre-offensive afin de renverser le cours de la guerre.
Les français le savent mais ce qu’ils ne savent pas, c’est où se fera cette contre-offensive.
Un message est intercepté et alors que le code ADFGVX réputé indécodable est utilisé par les allemands, la chef de la section de cryptanalyse française va travailler d’arrache pied jours et nuits pendant une semaine, perdant alors plus de 15 kg, pour le percer.
Il y arrivera, ce qui permettra aux français de masser leurs forces au bon endroit et ainsi de pouvoir repousser l’attaque allemande, précipitant leur reddition.

La seconde guerre mondiale est marquée quant à elle par l’utilisation de la célèbre machine de cryptographie Enigma.



Il s’agit d’une machine électro-mécanique composée de disques alphabétiques tournant aléatoirement et qui permettent de coder les messages en l’utilisant comme une machine à écrire.

L’histoire de la cassure de ce code est littéralement un roman d’aventure, ponctué de rebondissements, de retournement de situations, de découvertes par les cryptanalystes anglais de Bletchey Park. C’est tout simplement fascinant. (Je vous dirai à la fin quoi lire si cela vous intéresse de creuser un peu plus le sujet.)

Il y eut même une mission commando se faisant passer pour un équipage allemand en détresse de façon à se faire récupérer par un sous-marin allemand, en prendre possession, voler une machine Enigma et ses carnets de clef, le couler et disparaitre.



Il faut surtout savoir que c’est à l’occasion du décodage des messages issus de la machine Enigma que sera inventé l’ancêtre de l’ordinateur actuel : l’ordinateur Colossus mis au point par Alan Turing, issu de son travail sur les « bombes » polonaises qui servaient à chercher les clefs des machines Enigma. (Oui, les polonais n’ont pas fait grand-chose pendant la guerre, mais ils ont au moins initié le décryptage d’Enigma).

Enfin, une autre méthode de cryptage à signaler durant la seconde guerre fut celle utilisée à la fin de la guerre par les américains à l’encontre des japonais.
Ils eurent l’idée d’utiliser la langue des indiens Navajos pour traduire leurs communications.
Cette langue, par sa structure, est totalement hermétique aux linguistes et donc aux cryptanalystes.
Des indiens Navajos furent donc affectés dans toutes les unités au poste de radio afin de traduire les messages dans leur langue.
Les japonais n’auront jamais réussi à décrypter les messages interceptés.

D'autres déchiffrements célèbre eurent cours tout au long de l'Histoire.
Je peux citer celui du Linéaire-B, écriture mycénienne de la Grèce antique, ou bien le plus célèbre de tous : le déchiffrement des hiéroglyphes.
C'est tout aussi romanesque.

A la fin de la seconde guerre mondiale, on assiste à la victoire des décrypteurs sur les concepteurs de code.
Début des années 50, l'ordinateur fait son apparition, il se démocratise de plus, les entreprises s'en dotent, des langages de programmation apparaissent (le Fortran d'IBM, par exemple).
Les crypteurs utilisent alors des algorithmes de cryptage qui nécessitent de longs calculs pour coder et évidemment encore plus longs, infiniment plus longs pour décoder, ce qui met dans un abris artificiel le code. Ainsi l'algorithme de chiffrage Lucifer créé dans les années 70 est toujours valable aujourd'hui sous le nom de DES (Date Encryption Standard).

Mais voilà, il reste un problème. Un problème qui a toujours existé quelque soit la complexité du code, que ce soit le DES ou le chiffre de César : la transmission de la clef.

Eh oui, car si jamais la clef tombe entre les mains adverses, le code n'a plus aucune efficacité.
Si vous apprenez que ma phrase clef était "Je pars en voyage", mon code plus haut ne résistera guère longtemps à votre attaque.
La sécurité de la transmission de la clef est donc primordiale.

L'une des solutions apportée à ce problème est celle que je vais illustrer à présent.
Imaginons que Bernard veuille transmettre un message à Alice sans qu'Eve ne puisse le lire (ces 3 noms furent ceux choisis par les cryptanalystes tout au long de leurs travaux).

Bernard écrit son message, le place dans un coffre qu'il ferme avec son cadenas avec sa clef unique. Il envoie le coffre à Alice qui va alors apposer son propre cadenas avec là aussi une seule clef. Elle renvoit le coffre à Bernard qui retire son cadenas et renvoie à Alice. En recevant le coffre, Alice peut ouvrir son cadenas avec sa clef et lire le message de Bernard. Astucieux, non ?

Il "suffit" maintenant de convertir ces clefs physiques en algorithmes mathématiques réversibles pour pouvoir appliquer des fonctions à un code binaire. Il s'agit là du domaine de l'arithmétique modulo.

Ceci sera ensuite optimisé avec le principe des clefs publics et clefs privées. On supprime le problème de la navette entre Alice et Bernard en utilisant une clef public accessible à tous qui sert pour le chiffrement mais pas le déchiffrement. Seule l'utilisation de la clef privée d'Alice ou de Bernard appliquée sur la clef public permet de déchiffrer le message. On entre alors dans des fonctions mathématiques particulières asymétriques utilisant des factorisations en nombres premiers. Bref, c'est super chaud (ça se comprend malgré tout, mais je vous épargne les détails ici). Le RSA actuel est ainsi une système de cryptographie à clef public.

Ce code est virtuellement inviolable car factoriser en nombre premier des nombres de plusieurs millions de chiffres prendrait des milliards d'années à tous les ordinateurs de la planète.

Les cryptographes seraient alors en droit de se sentir peinard pendant un bon bout de temps aujourd'hui....

... Sauf que ceci serait sans compter l'apparition à venir des ordinateurs quantiques et leurs fabuleuses capacité de calcul instantané. Pensez que grâce à la maitrise des principes de la mécanique quantique, les ordinateurs quantiques seront capables de réaliser des millions d'opérations dans le temps d'une seule de nos ordinateurs actuels !

Mais heureusement, un jour viendra aussi le cryptage quantique qui lui sera par principe totalement inviolable...