Cryptographie moderne
Enigma
Durant la seconde guerre mondiale, l’armée nazie utilisait un système cryptographique nommé Enigma pour chiffrer les messages transmis entre ses différentes divisions.
Utilisé correctement, ce système aurait pu permettre une confidentialité totale: des chercheurs de l’époque considéraient en effet que les messages chiffrés avec Enigma étaient impossibles à déchiffrer. Mais grâce à un espion, les alliés ont eu accès à des documents techniques qui ont peu à peu permis d’en comprendre le fonctionnement. D’importants travaux ont été réalisés pour mettre sur pied un système efficace de décryptage d’Enigma; la machine servant à effectuer ce décryptage, Colossus, peut être considérée comme un des premiers ordinateurs.
Pour chiffrer un message avec Enigma, il fallait entrer une clé (de 3 ou 4 caractères selon le modèle) au moyen de rotors, puis taper chaque lettre du message à l’aide d’un clavier. Pour chaque lettre du message original ainsi entrée, la lettre du message chiffré s’allumait. Pour déchiffrer un message, on n’avait qu’à taper les lettres du message chiffré. Afin de rendre difficile le déchiffrement des messages, la clé changeait chaque jour.
Masque jetable (One-time pad)
Les chiffres de César, Vigenère et Enigma ont tous en commun de pouvoir être brisés: même sans avoir la clé, il est possible d’analyser les messages et de tester des hypothèses pour arriver progressivement à comprendre le chiffrement et à décoder un message. On peut donc se poser la question: existe-t-il un système cryptographique impossible à briser? Existe-t-il un système “parfait”, en ce sens que la seule manière de déchiffrer un message si on n’a pas le clé consiste à essayer toutes les clés possibles, une après l’autre (une technique qu’on appelle “force brutale”)?. Dans le cas du chiffre de César, le code est facile à briser car il existe 26 clés possibles; pour le chiffre de Vigenère, c’est déjà plus compliqué.
Les premiers mathématiciens à se spécialiser dans le domaine de la cryptographie ont imaginé un tel système: le “One-time pad” (aussi appelé chiffre de Vernam). Il y a deux conditions à satisfaire pour qu’un système cryptographique soit impossible à briser:
- La clé doit être aussi longue que le message
- La clé doit être générée de manière aléatoire
Par exemple, imaginons qu’on veut chiffrer le mot “ATTAQUE” avec une clé qui représente un décalage alphabétique, comme 12-2-4-5-1-20-1:
| Original | A | T | T | A | Q | U | E |
| Clé | 12 | 2 | 4 | 5 | 1 | 20 | 1 |
| Message chiffré | M | V | X | F | R | O | F |
Si on veut déchiffrer MVXFROF sans connaître la clé, la seule manière d’y arriver est de tester toutes les clés possibles. Puisque chaque “lettre” de la clé a 26 valeurs possibles et que la taille de la clé est de 7 (la même que le mot), on a 26⁷ clés possibles à tester soit 803 181 176 possibilités. Et surtout, si on arrive à les énumérer et les utiliser pour tenter de déchiffrer MVXFROF, on aura obtenu au passage tous les mots de 7 lettres possibles en français… Par exemple, le mot “Bananes”, si on le chiffre avec la clé 12-21-9-5-4-9-13 donne aussi MVXFROF. Comment alors savoir si le message original est “Attaque” ou “Bananes”, ou “Compter”, “Jardins”, etc? Il faut avoir la clé pour en être sûr.
Vous recevez le message suivant chiffré par le one-time pad:
- Texte chiffré:
r t f y i z n r p r k e y f. - Clé:
3-4-1-7-8-6-5-3-2-9-8-4-7-1
- Quel est le texte en clair?
- Combien de clés devrez-vous générer pour déchiffrer le message par force brutale?
XOR
Dans les systèmes cryptographiques modernes, on ne chiffre pas les messages en utilisant un décalage mais plutôt en utilisant l’opération logique XOR (“ou exclusif”) sur les bits du message en clair. L’opération XOR, symbolisée par “⊕”, est représentée par les valeurs suivantes:
| x | y | x ⊕ y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Le chiffrement du mot “POMME” consiste donc à se baser sur la représentation binaire du mot, par exemple l’encodage ASCII, à générer une clé binaire aléatoire de même taille et d’appliquer l’opération XOR:
| Message en clair | P | O | M | M | E |
| ASCII | 01010000 |
01001111 |
01001101 |
01001101 |
01000101 |
| Clé | 10000001 |
10101010 |
00011000 |
00000000 |
11111111 |
| Message chiffré | 11010001 |
11100101 |
01010101 |
01001101 |
10111010 |
Les octets dans le message chiffré ne donnent pas nécessairement des caractères alphabétiques; il est ainsi possible que le message chiffré ne puisse pas être écrit ni imprimé.
Application
L’intérêt du One-time pad est surtout théorique: malgré sa simplicité technique et sa robustesse, il n’est pas utilisé dans les systèmes cryptographiques modernes. Les deux principales raisons sont les suivantes:
- Il est difficile de générer des nombres réellement aléatoires par ordinateur. Les programes et librairies qui génèrent des nombres aléatoires (comme
Math.random()) peuvent être analysés et il n’est pas impossible que ces nombres puissent être devinés. - Si la clé doit être unique et de la même taille que le message, alors chaque fois qu’on envoie un message, on doit aussi envoyer la clé pour le déchiffrer. Comment s’assurer que cet échange de clé se fera secrètement? Un système cryptographique fonctionnel doit avoir un mécanisme d’échange de clés sécuritaire.
Les messages suivants sont chiffrés avec l’opération XOR et les valeurs ASCII des caratcères. Si la clé n’a pas la même taille que le message d’origine, répétez-la comme pour le chiffre de Vigenère.
- Si le message chiffré est
00001111 00010111 00000010 00000110 00000111et que la clé estabc, quel est le message en clair? - Si le message en clair est
machineet que le message chiffré est00001111 00001000 00001110 00001010 00000000 00000011 00000111, quelle est la clé (en caractères)?