ALAN TURING AND HIS IMPACT ON SOCIETY
“Sometimes it is the people no one can imagine anything of who do the things no one can imagine.”
CRYPTOLOGY
CRYPTOLOGIE ET ENIGMA
La cryptologie est la science du secret, c'est-à-dire du chiffrement. Celle-ci comprend deux disciplines distinctes: la cryptographie (l'écriture secrète) et la cryptanalyse (étude des attaques contre les mécanismes de cryptographie).
La cryptographie est l’étude des algorithmes permettant la protection d’informations (numériques). Ces algorithmes sont appelés crypto systèmes. A l’origine, il s’agissait principalement de l’art des codes secrets et elle concernait principalement les procédés de chiffrement. Aujourd’hui, ses applications sont multiples, avec le chiffrement des informations qui transitent par exemple sur internet, ou encore la signature électronique.
La cryptographie peut protéger l’information de différentes manières, en apportant une garantie de:
Confidentialité : pour s’assurer que l’information ne soit seulement accessible qu’à ceux dont l’accès est autorisé (le message est chiffré par un émetteur et déchiffré par le destinataire; sans la clé de déchiffrement, le message est incompréhensible). Par analogie, c’est comme si l’émetteur et le destinataire parlent une langue qui est connue d’eux seuls. Par exemple, cela est utilisé pour le chiffrement des flux sur internet.
Authenticité : pour vérifier l’identité d’une personne ou d’un matériel informatique (on va ajouter une signature numérique qui ne peut être apposée que par l’émetteur du message). Par analogie, il s’agit d’apposer une signature sur un message généré ; seul l’émetteur légitime peut apposer sa signature. Par exemple, cela est utilisé dans les signatures électroniques de documents.
Intégrité : pour s’assurer qu’une information n’a pas été modifiée (on va ajouter au message transmis le résultat d’un calcul effectué à partir du message original avec une fonction mathématique particulière ; le message est transmis avec ce résultat ; le destinataire rejoue ce calcul à partir du message transmis et vérifie si le résultat qu’il a calculé est bien identique au résultat transmis avec le message). On peut faire une analogie avec un message dans une enveloppe scellée; si le message est modifié alors les scellés sont brisés. La limite de cette analogie réside dans le fait que, dans le monde numérique, la simple consultation du message ne brise pas le scellé. Ce dispositif est par exemple utilisé pour vérifier qu’un logiciel téléchargé sur internet est bien légitime et n’a pas été modifié.
Ces manières doivent reposer sur des secrets
cryptographie symétrique : repose sur une clé secrète utilisée pour chiffrer et déchiffrer les informations. Dans ce cas, la clé de déchiffrement est la même que la clé de chiffrement. Par exemple, un texte chiffré peut être déchiffré et chiffré autant de fois que l’on veut, sa forme chiffrée sera la même (avec la même clé). On peut comparer ce système à une boîte qui peut s’ouvrir avec deux clés identiques -- une personne met un message dans la boîte, la ferme avec sa clé, l’envoie par la poste, et le destinataire ouvre la boite avec sa propre clé (identique à la clé).
cryptographie symétrique: un couple clé publique et clé privée est utilisé par exemple pour chiffrer et déchiffrer l’information. Dans ce cas, seule la clé privée à besoin d’être secrète. On peut comparer cela à une boîte fermée par un cadenas. Le cadenas est détenu par l’émetteur ; le destinataire, quant à lui possède la clé. Pour “chiffrer” une information, on la met dans la boîte que l’on ferme avec le cadenas. Puis on envoie la boîte par la poste et seul le bon destinataire peut l’ouvrir avec sa clé.
Il existe plusieurs méthodes de chiffrement et déchiffrement.
Voyons-en quelques-unes :
LE MODE ECB
(CHIFFREMENT PAR BLOCS)
Pour chiffrer un texte clair appelé C, on découpe C en parties appelées blocs. On applique Ek, la clé choisie sur chacune des parties et l’on obtient notre texte C, chiffré. De même, on pourra déchiffrer C avec la clé de déchiffrement.
LA METHODE CESAR
La méthode César est une manière de chiffrer et déchiffrer par substitution. Il s’agit en effet de définir un décalage entre les lettres.
Ex : A → D ; B → E ; C → F etc. etc.
Voici une clé de (dé)chiffrement de César:
LA SUBSTITUTION
La méthode de substitution est simplement le fait de changer d’alphabet. C’est une forme évoluée de la méthode César vue précédemment. Pour être plus clair, c’est seulement un arrangement différent de lettres que celui de l’alphabet que l’on utilise et que l’on doit traduire pour arriver au message. C’est un chiffrement par lettres, contrairement à la méthode de transposition.
LA TRANSPOSITION
La transposition est une méthode qui consiste à donner un numéro à chaque lettre (en ordre clair) et après les mélanger pour se retrouver avec une suite illogique de nombre comme 267974138. Après cela, il suffit de remettre les chiffres dans un ordre précis (donné par celui qui a chiffré le texte) et ainsi dévoiler le message.
Toutefois, ce ne sont pas les seules manières de chiffrer des textes. Ces techniques de décodage sont pour la plupart déjà bien connues et extrêmement faciles à percer pour un intéressé aguerri. Elles sont automatisées dans les ordinateurs et dans les ordinateurs, les caractères sont codés en binaire.
01001100 01100101 00100000 01100010 01101001 01101110 01100001 01101001 01110010 01100101
Le binaire:
Pour comprendre le langage binaire, il faut comprendre les nombres binaires (la base 2) et pour cela… il faut reprendre le système décimal (la base 10)!
En effet, dans notre système décimal, nous avons 10 chiffres : 0,1,2,3,4,5,6,7,8,9. On dit donc qu’on compte en base 10 (puisque nous utilisons 10 chiffres pour tous nos nombres). Bien sur, pour compter 10, il faut changer de rang et utiliser 2 chiffres : le rang des unités étant plein, le rang des dizaines accueille un chiffre et ainsi de suite pour le rang des centaines, milliers…
Par exemple, arrivé à 9, il faut changer de rang, mettre 1 dans le rang des dizaines et ajouter 0. Donc, on peut en déduire que chaque rang est supérieur a une puissance de 10 du rang précédent.
Par exemple, 78= 70 + 8 = 7 x 101 + 8 x 100
En binaire toutefois, il n’y pas 10 chiffres. Il n’en y a que 2! Le langage binaire est en effet composé de 0 et de 1.
Par exemple : 3(en décimal) = 1x21 + 1 x 20=11 (en binaire)
Voici un tableau de conversion décimo-binaire
Comme on peut le voir, vu qu’on a seulement 2 chiffres, chaque rang est supérieur au précédent d’une puissance de 2.
Le binaire va nous être utile lorsque l’on va s’attaquer à la machine de turing....
Enigma:
Son histoire:
La cryptologie a été l’un des facteurs de la victoire des alliés lors de la Seconde Guerre Mondiale. Grâce aux avancées des britanniques notamment en matière de déchiffrement de messages nazis, la guerre a probablement été écourtée de 1 ou 2 ans.
Au début de la guerre, les alliés semblent avoir toujours un coup
de retard sur l’ennemi. La Pologne et la France sont tombées mais le Royaume Uni tient encore ses positions, difficilement. L’approvisionnement se fait de plus en plus rare, à cause des U-Boot, véritables machines destructrices qui font barrage, en meute, la nuit. Toute la tactique d’attaque est envoyée par radio, chiffrée par Enigma.
Enigma est une machine destinée au grand public. En 1919, Docteur
Scherbius utilise les idées de Hugo Alexander Koch et crée une société destinée
à fabriquer une machine à chiffrer mathématiquement. Près de 30 000 modèles
seront vendus et l’armée allemande, consciente de l’importance de la
cryptologie dans les conflits modernes (1ère guerre mondiale) achète en masse
une version militaire de la machine.
Le fonctionnement de la machine est basique puisque le chiffrement
ressemble à un mélange de méthode de César et de substitution. À chaque fois
qu’une lettre est appuyée sur le clavier, une ampoule s’allume, et les rotors
présents dans la machine tournent, changeant la substitution effectuée. Comme ça,si deux personnes ont réglé de la même manière les rotors présents sur leurs machines, l’un n’aurait qu’à taper le message chiffré envoyé par l’autre pour obtenir le message en clair.
Les allemands ont directement compris le potentiel de cette
machine au vu du nombre de clés cryptographiques possibles, de l’ordre de 1020. Pendant près de 19 ans (1919-1938), les allemands vont envoyer
des messages en tout impunité, faisant aveuglément confiance à Enigma.
Cependant, après la Première Guerre Mondiale, les polonais se
dotent d’un service spécialisé pour décrypter les communications allemandes,
pour essayer d’enrayer une seconde invasion. Ils vont alors essayer de décrypter
les messages allemands, sans succès, car les machines militaires étaient différentes de celles vendues aux civils (celle que les polonais s’étaient procurée). Jusqu’en 1931, les polonais font face à un mur, jusqu’à ce que les Français se procurent les plans de la machine militaire. Les plans sont immédiatement partagés avec les polonais. En 1932, les polonais inaugurent ce qu’ils appelleront “La Bombe”, machine capable de décrypter des messages envoyés par Enigma.
Seulement, en 1938, à l’aube de la Seconde guerre mondiale, les
nazis décident de changer le nombre de rotors de leurs machines et leur
protocole d’envoi. Cela met “la bombe” hors service. Le climat international étant de plus en plus tendu, les polonais transmettent toutes leurs découvertes aux anglais qui mettent en place le service de cryptologie, composé de milliers de mathématiciens, de linguistes et autre, à Bletchley Park, à environ 60 km de Londres pour éviter de se faire bombarder.
Parmi les nombreux mathématiciens : Alan Turing, inventeur de la machine de Turing, qui met au clair la fonction de l’algorithme. Il fabrique ainsi une copie de “La bombe” qui va permettre aux Anglais de comprendre les messages nazis. Les anglais interceptent tout message en parlant pour trouver la clé de la nouvelle Enigma. Comme cela permet de déjouer des attaques, ce travail colossal sera récompensé par l’augmentation considérable de bateaux ravitaillant les anglais. Il y aura plus de 50% de tonnes en plus d’approvisionnement au second trimestre 1941.
“La Bombe”
Toutefois, les nazis, trouvant étrange que leur efficacité soit diminuée de 50% lors d’attaques de bateaux de marchandises et autres, remplacent en 1942 l’ancienne Enigma par une nouvelle version ce qui empêchera les anglais de déchiffrer les messages. C’est seulement avec l’aide des Etats unis et le génie d’Alan Turing que les messages nazis recommencent à être décryptés en juin 1943.
Son fonctionnement:
Enigma est composée de plusieurs parties:
Un double clavier: un clavier de machine à écrire est relié à un clavier composé de lampes, qui correspondent aux lettres codées. Quand un soldat appuyait sur une lettre du clavier de machine à écrire, un système de courant électrique faisait s’allumer une lettre sur le clavier de lampes, la lettre chiffrée.
Des interrupteurs: Il en existe un pour chaque lettre; chaque interrupteur va permettre de fermer un circuit afin d’allumer une lampe à chaque fois que l’envoyeur va appuyer sur une des 26 lettres.
Des rotors: les rotors sont des connexions électriques qui ont pour particularité de pouvoir tourner sur leur axe. Sur une machine à 3 rotors, dès que le rotor n°1 avait tourné 26 fois, le rotor n°2 tournait une fois. La particularité de ces rotors était leur habilité à changer une lettre en une autre au hasard.
Ici par exemple, on a représenté un seul rotor qui va permuter le B en A et le A en E. Contrairement au tableau de connexions, il n’y a pas d’inversement.
En effet, on le voit ici, le premier rotor change le D en C, mais lorsqu’une lettre est retapée, le rotor change le C en A, ainsi, à la prochaine tape de lettre, le rotor change le D en C.
Un réflecteur: au bout des trois rotors, pour une sécurité ultime, un changement se fait ce qui fait que maintenant, le courant repasse à travers les rotors et le tableau de connexion. Ce système est fait en faisant permuter le A en D, et le B en C (par exemple).
Un réflecteur
Un tableau de connexions: il permet d’échanger des paires de l’alphabet par deux, avec 6 fiches. Cela implique donc que 12 lettres seront transformées. Tout cela se fait aux moyens de fils électriques que l’on branche selon les lettres utilisées.
Ici, A est changé en C et inversement; F est changé en D et inversement tandis que B et E ne le sont pas
Une pile électrique: elle permet d’alimenter les différents circuits fermés qui vont être réalisés en déclenchant un interrupteur (en tapant sur une lettre).
Tout cela nous amène donc à ce schéma :
Voici une Enigma simplifiée n’ayant que deux rotors ainsi que 6 lettres.
Nous allons donc chiffrer la lettre A. Celle-ci est changée en C lors de la traversée du tableau de connexion. Puis, le C est changé en A et puis en F au bout des deux rotors. En prenant le réflecteur, le F va devenir un E, qui va être changé en F et puis en A lors du retour dans les deux rotors. Pour finir, le A va être changé en C lors du retour dans le tableau de connexion.
Donc ici, avec ces réglages, A=C et C=A (amusez vous à suivre la ligne que va emprunter le courant électrique et vous verrez que le courant aurait simplement pris le chemin inverse).
Chiffrement:
Soit T la transformation faite par le clavier, R la transformation faite par le réflecteur et R1, R2, R3 les transformations faites par les rotors.
On code alors :
C= T*R3*R2*R1*R*R1-1 *R2-1 *R3-1 *T-1
Donc voici comment les allemands ont réussi à chiffrer une lettre en une autre. Il faut dire que ceux-ci savaient que Enigma n’allait pas être une forteresse impénétrable mais ils ne pensaient pas que les britanniques réussiraient à trouver chaque clé car il y a un nombre énorme de combinaisons possibles.
Pour calculer le nombre de combinaisons possibles de réglage, il faut calculer les possibilités de chaque partie de la machine. Pour ce calcul, on utilisera la dernière Enigma (5 rotors, un tableau de connexion de 20 lettres)
Pour les rotors, les chiffreurs devaient disposer 3 rotors parmi cinq dans la machine. Cela fait donc 60 possibilités.
Pour l’alphabet, chaque rotor dispose de 26 lettres, donc 26 x 26 x 26 = 17 576 possibilités pour chaque arrangement de 3 lettres.
Pour le tableau de connexions, 20 lettres sont permutées et 6 restent « normales ». Cela nous fait donc 150 738 274 937 250 possibilités.
Cela nous donne donc : 60 x 17 576 x 150 738 274 937 250 = 158 962 555 217 826 360 000 = 1,59 x 10*20 permutations possibles.
Les allemands étaient donc tellement confiants en leurs machines qu’ils n’ont pas vraiment été prudents et ont utilisé Enigma en tout impunité pendant près de 30 ans.