Histoire des codes secrets – Simon
Singh
Pour approfondir certaines de mes idées j’ai été
faire un tour dans le monde des mathématiques. J’ai lu quatre ouvrages :
Histoire des codes secrets, de Simon Sigh ;
La symphonie des nombres premiers, de Marcus du Sautoy ;
Le dernier théorème de Fermat, de Simon Sigh ;
Métaphysique Quantique, de Sven Ortoli et
Jean-Pierre Pharabod.
INTRODUCTION
A la lecture de ces quatre ouvrages traitant des
grandes questions mathématiques, je souhaitais voir si certaines correspondances
pouvaient se faire entre mes idées et certains concepts mathématiques.
Quand on essaie de comprendre comment
ça marche, comment tout marche et pourquoi, (c’est ça, en gros,
l’épistémologie), il est indispensable d’aller faire un tour vers les mathématiques.
Les mathématiques sont la connaissance
par définition. C’est ce que nous apprend l’étymologie du mot. C’est aussi une
évidence quand on se rend compte du langage qu’elles ont façonné et qui les
façonne réciproquement. Les chiffres sont un alphabet qui nous ouvre les portes
sur un monde surprenant, un régal pour l’esprit.
Les mathématiques représentent un corpus de
connaissances fondamentales. Les mathématiques étudient des structures
fondamentales dont l’existence, une fois démontrée, ne peut être que difficilement
invalidée. Il n’y a pas d’autres disciplines où la rigueur de la méthode soit
autant recherchée.
Les mathématiques se sont divisées en plusieurs
branches à mesure que les travaux s’intensifiaient, c’est pourquoi j’ai choisi
comme porte d’entrée la théorie des nombres, branche la plus
« pure », la plus abstraite, la plus « logicienne » des
mathématiques. On verra cela de plus
près avec Marcus du Sautoy et les nombres premiers dans une seconde partie.
Etant donné la complexité du sujet abordé, je vais
reprendre les bouquins par ordre de lecture et développer les notes prises pour
chacun.
HISTOIRE DES
CODES SECRETS - Simon Singh
L’histoire du cryptage est
vraiment passionnante. Elle révèle des prouesses de subtilités fascinantes qui
apportent un éclairage sur notre façon de fonctionner.
Présentation de la
cryptographie
La toute première invention
qui a permis à deux personnes de se transmettre un message à l’insu des autres
personnes s’appelle la stéganographie. C’est la technique générale qui consiste
à dissimuler un message écrit. (« Stegano » veut dire couvert et « graphein »
veut dire écriture). Le message peut être écrit à l’encre invisible, ou bien il
peut être recouvert, bref le message original est caché quelque part. Par
exemple, sous l’antiquité, on rasait le crâne du messager, on y inscrivait un
message et on laissait repousser les cheveux. On envoyait ensuite le messager
(on n’avait pas nécessairement la même notion d’urgence).
La cryptographie diffère de
la stéganographie. En cryptographie, le sens
du message est caché dans son écriture. Par transposition ou par
substitution, les lettres originelles du message ont été changées par d’autres
qui rendent le message chiffré incompréhensible à toute personne ne détenant
pas la clé de déchiffrage.
On parle de chiffrage, de
chiffrement et de déchiffrement pour tout ce qui touche aux lettres. On parlera
de code lorsque l’on substitue des mots
ou des phrases par autre chose.
En anglais, chiffre se
traduit pas « Cypher » et est plus généralement emprunté pour tout ce
qui touche à la cryptographie. Difficile de ne pas faire un rapprochement entre
cypher et lucifer !
Depuis plusieurs milliers d’années,
les hommes ont eu besoin de cacher des informations à des yeux indésirables.
Depuis autant de temps, les hommes se sont employés à briser les chiffrements.
L’histoire des codes secrets est donc liée à la lutte acharnée que se sont
livrés les chiffreurs et les déchiffreurs.
Les techniques de
chiffrement d’une époque se basent sur les technologies nouvelles qui
existaient à cette époque. Souvent les besoins des cryptographes ont-ils permis
des avancées technologiques. Face à eux, les décrypteurs n’ont jamais cessé de
briser les codes, permettant eux-aussi de grandes avancées technologiques.
Pour qu’un message chiffré
puisse être déchiffré par son destinataire, il faut qu’une clé et un algorithme
de chiffrage soit connu des deux personnes concernées. L’algorithme, c’est la
procédure générale qui a été suivie par le cryptographe ; la clé est
propre à chaque message, une fois la procédure établie.
Par exemple :
« Le chiffre de
substitution monoalphabétique » est un algorithme. Cette procédure
consiste à remplacer chaque lettre du message original par une autre lettre.
Cette autre lettre provient d’un alphabet dont l’ordre des lettres est modifié.
La première lettre pouvant être D, par exemple.
Alphabet
« clair » : 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
Alphabet
« chiffré » : D E F
G H I J K L M N O P Q R S T U V W X Y Z A B C
Il existe 26 alphabets
chiffrés potentiels pour chiffrer un message selon la technique du chiffre de
substitution monoalphabétique. L’alphabet chiffré choisi pour crypter un
message constitue la clé de déchiffrage.
Le destinataire du message
doit être informé de deux choses pour déchiffrer le message :
-
il devra suivre
la procédure – l’algorithme- de
substitution monoalphabétique ;
-
il devra
prendre en particulier l’alphabet commençant par la quatrième lettre de
l’alphabet, « D », qui constitue la clé.
Cette technique est une des
plus anciennes et des plus faciles à utiliser. Elle repose cependant sur une
faiblesse majeure : l’émetteur et le destinataire doivent, d’une manière
ou d’une autre, échanger une information préalable au cryptage et décryptage, principalement
la clé. Si cette clé est interceptée par une personne indésirable, le message
sera déchiffré par cette personne indésirable.
Plutôt que de s’évertuer à
intercepter les clés, on a préféré développer une technique permettant de
déchiffrer les messages sans la clé.
Ce sont les arabes et les
musulmans qui ont brisé pour la première fois le chiffre de substitution monoalphabétique,
inventant ainsi la cryptanalyse.
La cryptanalyse désigne la
discipline qui consiste à briser les
chiffres, les codes et toute cryptographie imaginable et inimaginable.
Pour briser le chiffre de
substitution monoalphabétique, les cryptanalystes ont inventé l’analyse de fréquences.
Par exemple, supposons que
le message crypté que l’on cherche à décrypter soit écrit dans notre langue, le
français. On prend un texte quelconque d’une ou deux pages tirées d’un bouquin
et on compte combien de fois apparait chaque lettre dans tout le texte choisi.
On estime que le texte choisi est suffisamment long pour être représentatif de
l’usage général de la langue.
Les lettres sont ensuite
classées en fonction de leur nombre d’apparitions. En français, le E est la
lettre la plus fréquemment utilisée, suivie de A, I, S, T, N, etc… On établit
un tableau de fréquence des lettres.
On prend ensuite le texte
crypté et on va compter de la même manière la fréquence d’apparition de chaque
lettre. Si la lettre apparaissant le plus souvent est un D, on déduira avec
prudence que le D crypte la lettre A. Si l’on commence par les petits mots,
bien vite on pourra voir si un sens commence à apparaitre.
C’est donc avec beaucoup de
« déduction, d’intuition, d’astuce et de souplesse » - comme le dit
l’auteur Simon Singh - que la cryptanalyse s’attaque aux messages cryptés.
Biensûr, lorsque les
cryptographes ont compris que leurs messages pouvaient être déchiffrés sans
clé, ils ont complexifié le chiffrage. Par exemple, en recourant à un mélange
de plusieurs alphabets, ou bien en introduisant des caractères trompeurs, en
supprimant les espaces entre les mots, en ajoutant des nombres au hasard, etc. Il
existe donc des chiffres de substitution polyalphabétique ou homophonique, des
combinaisons de chiffres et de codes beaucoup plus complexes.
A chaque fois, la
cryptanalyse a développé des techniques qui sont venues à bout des
chiffrements.
Pendant plusieurs siècles,
les cryptanalystes étaient issus de la linguistique. La part mathématique se
limitait à des analyses statistiques soumises aux approches linguistiques. De
nos jours, la cryptographie est davantage une affaire de fervents
mathématiciens.
Un ordre préjudiciable ?
En regardant sur plusieurs
siècles la façon dont la cryptanalyse est régulièrement venue à bout des
chiffrements, on remarque ceci :
Il y a dans toute technique
de chiffrement, un algorithme. L’algorithme établit un ordre, un peu comme une loi, ou une fonction, et c’est parce qu’il
y a un ordre qu’on peut le retrouver, quelque soit sa complexité. La procédure de cryptage contient
intrinsèquement le moyen d’être décryptée.
Par exemple, avec un
chiffre de substitution monoalphabétique, un seul alphabet chiffré remplace les
lettres de l’alphabet clair, dans l’exemple donné plus haut, on voit que la
lettre « a » sera à chaque fois cryptée « D ». Cette
répétition dans le cryptage a constitué une brèche dans laquelle les
cryptanalystes se sont engouffrés pour mettre au point l’analyse de fréquences.
Autre exemple, si on
utilise un chiffre de substitution polyalphabétique, notre « a »
initial sera crypté une première fois par la lettre « D » puis
lorsque « a » devra a nouveau être crypté, ce sera à l’aide d’un
second alphabet, et ainsi de suite. Les cryptanalystes sauront tirer avantage
autant de l’absence de répétition que d’une éventuelle répétition parce que la
répétition, l’absence de répétition ou la répétition occasionnelle doit
nécessairement suivre un ordre, une logique liée au choix de la clé ou d’un
mot-clé.
C’est pendant la seconde
guerre mondiale que les cryptanalystes ont été auteurs de prouesses défiant le
bon sens. Pour venir à bout du code « Enigma », Alan Turing a inventé
les « bombes » qui sont l’ancêtre des tous premiers ordinateurs. La
machine « enigma » est une machine d’automatisation très poussée des procédures
de cryptages, de la taille d’une machine à écrire. Les bombes de Turing sont
des machines énormes (environ deux mètres de haut sur deux mètres de larges)
qui effectuaient des centaines de milliers de combinaisons de lettres pour
décrypter les messages d’ « enigma ». Le code
« enigma » était sensé être inviolable. Il a été brisé grâce aux
bombes mais surtout grâce aux négligences humaines des opérateurs
« enigma ».
Par exemple, chaque jour,
les réglages de la machine « enigma » changeaient. Cinq rotors
différents étaient disponibles pour la machine qui n’en nécessitait que trois.
Les cryptanalystes se sont aperçu que jamais deux mêmes rotors étaient utilisés
au même emplacement deux jours de suite. Le nombre de combinaisons potentielles
à étudier chutait drastiquement alors que les allemands pensaient que ne jamais
laisser deux jours de suite un même rotor au même emplacement compliquait les
choses.
Ensuite, les opérateurs avaient
la charge de choisir eux-mêmes pour chaque message une clé et cette clé cryptée
était répétée deux fois au début du message. Cette répétition a permis de
briser le code « enigma » une première fois. Les opérateurs tapaient leur
clé deux fois de suite, tout en haut du message crypté et ils choisissaient
souvent le nom d’une personne proche, un
ami ou un parent, ou bien ils tapaient des lettres proches les unes des autres
sur le clavier quand ils manquaient d’imagination ou pensait que l’aléatoire était
plus fiable. Or ce n’était pas le cas. Toute stratégie offrait immanquablement une
prise aux cryptanalystes.
Un autre exemple pour
souligner les prouesses du groupes de Bletchley Park qui rassemblaient les
cryptanalystes alliés pendant la seconde guerre mondiale: au bout de
plusieurs jours ou semaines de travail pour chercher à accélérer les
décryptages, à l’aide d’espions infiltrés dans les ministères ou départements
ennemis, toujours utiles, mettons que l’on soit informé de la « forme
protocolaire type » que revêt un message
envoyé depuis l’ambassade allemande en Espagne vers son correspondant à
Berlin. On sait à quel endroit du message se trouve mentionné une date, un
lieu, un verbe, un ordre, etc. Ce type d’information est une aide inestimable
pour le cryptanalyste. De même, les cryptanalystes savaient que vers 8 heures
tous les matins, un bulletin météo était transmis et que ce bulletin suivait
toujours le même protocole.
Qu’est-ce qui rendait si
« puissants » ces cryptanalystes ? Certes, Bletchley Park
regroupait certains des plus grands génies de son époque mais la véritable
richesse était dans la diversité et la complémentarité des personnalités :
des mathématiciens, des linguistes, des champions d’échecs, des cruciverbistes
d’exception, tous plus géniaux les uns que les autres, apportant chacun son
point de vue et multipliant les prises intellectuelles à chaque défis posé par
« enigma ».
Dans l’histoire d’ « enigma »,
le facteur humain a constitué une
force (pour les cryptanalystes) et une faiblesse (pour les opérateurs
d’ « enigma »).
Au regard de tous ces
exemples ponctuant l’histoire des codes secrets, on remarque que la présence
d’un ordre, quel qu’il soit, est préjudiciable au cryptage.
L’ordre pouvant prendre la forme de répétitions ou de fréquences. Même l’absence
de répétitions constitue un ordre.
Le fait qu’un message
crypté soit le résultat d’une procédure de cryptage implique que la procédure
puisse être inversée.
L’échange d’une clé entre
l’émetteur et le destinataire du message pose un problème qui s’illustre en
termes de symétrie. La clé qui sert
au cryptage sert également au décryptage.
Par exemple : pour
crypter un message, je choisis un premier algorithme qui crypte « a »
en « D », puis un second algorithme qui crypte mon « D » en
« 12 », chaque étape nécessitant une clé. La symétrie s’illustre
ainsi : avec la même clé que mon ami l’émetteur du message, je dois
décrypter « 12 » en « D », puis « D » en
« a », selon le principe de « dernier algorithme mis, premier
enlevé ».
Il y a :
-
symétrie car la
clé est la même pour la procédure de cryptage et celle de décryptage ;
-
symétrie dans
l’ordre des opérations à effectuer.
Cette symétrie est liée à
question de l’ordre préjudiciable
mentionné plus haut. Un ordre pourtant indispensable si l’on veut que le
destinataire puisse décrypter le message. Pour résoudre cependant le problème
lié à l’échange de clé, nous avons développé des techniques qui brisent la
symétrie de la clé et la symétrie des opérations.
La machine
« enigma » et les bombes de Turing relèvent d’une automatisation du
cryptage. Ces machines suivaient des algorithmes classiques, manipulables par
un cerveau entrainé. L’automatisation permettait simplement de multiplier les opérations.
Le cryptage était plus compliqué à suivre, mais il restait déchiffrable. C’est
bien plus tard que les algorithmes de cryptage ont changé. L’informatique, le
langage binaire et les mathématiques ont bouleversé la cryptographie et brisé
la symétrie, s’inspirant d’un ordre « nouveau ».
Les nouvelles techniques de
cryptographie concernent les informations que l’on échange sur internet,
notamment les numéros de cartes de crédit. Les milliards de données échangées
simultanément compliquent l’échange de clé : avant chaque échange de mail,
deux individus vont-ils se passer un coup de fil pour se mettre d’accord sur
une clé ?
Le principal problème était
donc de se passer de clé.
Nous avons développé la
cryptographie à clé publique ou à clé
asymétrique.
Le code RSA (Rivest, Shamir
et Adelman : les trois mathématiciens qui ont mis au point cette
technique) permet de ne plus avoir de clé identique et secrète. Il permet en
plus de rompre la symétrie dans l’ordre des opérations à effectuer.
Ce sont les propriétés des
nombres premiers qui ont permis de créer ce qu’on appelle une clé publique.
Voici le principe :
Maurice doit envoyer son numéro de carte de crédit à la société AAA. La société
choisit deux très grands nombres premiers -des ordinateurs s’en chargent- et
ces deux nombres choisis restent secrets. On multiplie ces deux nombres
ensemble pour obtenir un troisième nombre encore plus élevé. Ce nombre là peut
être public et est connu de Maurice (de son ordinateur en fait). Ce nombre
public est propre à AAA et est connu de toute personne qui échange des
informations avec AAA.
Le numéro de carte de
crédit est crypté grâce à une équation dans laquelle intervient notre grand
nombre public.
Pour qu’AAA décrypte le
numéro de carte de crédit, AAA entre le numéro crypté dans une équation différente qui contient les deux
nombres premiers secrets.
L’inviolabilité de cette
technique repose sur l’impossibilité de retrouver à partir d’un très grand
nombre, les deux nombres premiers qui, multipliés entre eux, l’ont produit.
Le plaisir de savoir
comment tout ça fonctionne est très grand mais ce qui m’intéresse et que je
souligne, c’est que cette technique repose sur une asymétrie dans l’information
échangée (la clé de cryptage et la clé de décryptage ne sont pas les mêmes à
proprement parler, bien qu’elles soient en fait deux expressions différentes d’une même information : deux nombres
premiers distincts dans un cas, factorisés dans l’autre).
Cette asymétrie n’est pas parfaite et ne peut donc garantir que le code
RSA reste longtemps aussi sûr qu’il l’est pour l’instant. Malgré les quelques
fois où le code RSA a été brisé, on renforce sa sécurité en prenant des nombres
premiers plus grands. Or trouver ces nombres premiers n’est pas une mince
affaire. C’est cependant plus « facile » que de chercher les deux
nombres premiers originels qui ont permis de trouver notre troisième très grand
nombre. Nous reviendrons sur ces questions mathématiques dans un prochain
article.
Pour aller encore plus
loin, nous avons développé une technique de cryptage basée sur la physique
quantique et ses lois étranges. La cryptographie quantique est de nos jours
réputée absolument inviolable. Elle est basée sur le comportement du photon. La
physique quantique a par ailleurs mis en évidence, par exemple, l’existence
d’un chaos subatomique (la théorie
du chaos). Le chaos quantique
pourrait-il remédier à l’ordre
préjudiaciable ?
Préjudiciable pour le
cryptographe, mais opportun pour le cryptanalyste.
Au final, l’histoire de la
cryptographie et de la cryptanalyse nous montre que malgré toutes les
inventions pour garantir le secret, les cryptanalystes ne sont jamais loin
derrière. Même l’automatisation des procédures de cryptages, leur
multiplication n’ont pu empêcher les cryptanalystes de briser les chiffrements
les plus alambiqués.
Puis, grâce aux ordinateurs capables de manipuler
des grandeurs inconcevables on a fait appel aux théories les plus abstraites
des mathématiques désormais exploitables. C’est à ce moment là que les
cryptanalystes ont commencé à se faire distancer. Car si un ordinateur peut
réaliser des milliers d’opérations en une seconde, il lui faut l’âge de
l’univers pour factoriser un très grand nombre en deux nombres premiers.
Les mathématiques sont encore jeunes et mystérieuses.
Elles reposent sur un ordre qui nous est encore inconnu en grande partie. Les
choses mathématiques se dévoilent difficilement aux regards des hommes.
De même, les mathématiciens sont des gens étranges.
En quête d’un degré de vérité frôlant l’absolu, l’esprit mathématique est
intuitif, esthétique et artistique. Les hommes doués de cet esprit sont
capables de voir des choses que le commun de l’humanité de peut concevoir s’il
se sait comment regarder…
A suivre…
Entropie : il y a dégradation de l’information
dès qu’un système n’est pas clos sur lui-même, autrement dit, dès qu’il y a
communication. La communication doit nécessairement suivre un procédé qui lie
les communicants. Le terme détériorer
est un terme connoté de manière négative. Quelque chose de détérioré est
quelques chose qu’il n’a plus son « harmonie » originelle
intrinsèque. Le fait de vouloir échanger un message secret s’apparente à
vouloir créer un système clos de communication. Un système qui serait clos aux
yeux du plus grand nombre, mais qui emploierait de manière détourné le moyen de
communication commun à tous, à savoir le langage (alphabétique, numérique ou
bien permettant l’élaboration d’algorithmes).
Il n’existe peut-être pas de système clos, et donc
il n’y a peut-être pas de détérioration. Par contre, il y a des échanges qui
sont complexes. Les choses en soi et les choses hors de soi sont différentes et
ce de manière irréductible.
Aucun commentaire:
Enregistrer un commentaire