Les commandements de la crypto [1] : La répétition tu banniras, avant que l'informatique passe par là

Du chiffre de César à la machine Enigma, les codes secrets ont eu pendant plusieurs siècles le défaut de répétition. Paradoxalement, cette tare s'est finalement transformée en avantage avec l'informatique.

Car la perfection n'est approchable que par la répétition

J'adore IAM, mais il faut tout de suite oublier leurs bonnes paroles si on veut crypter un message indécodable. Car les "casseurs de code" se servent précisément de la répétition comme faille principale jusqu'au milieu du XXe siècle.

Remplacer A par B, efficace pendant des siècles

César ne l'a pas inventé, mais son prestige impérial est historiquement associé à ce type de code très simple.

Il suffit de remplacer A par B, ou par C, ou une autre lettre de l'alphabet. En gros, superposer l'alphabet classique avec un alphabet décalé.

Image : ASCII Art réalisé sur Glassgiant.com

Exemple

Avec un chiffre de César décalé de deux crans :

L'ALSACE, C'EST VRAIMENT CHOUETTE

devient

N'CNUCEG, E'GUV XTCKOPV EJQWGVVG

On peut également augmenter la difficulté en enlevant la ponctuation et les espaces.

LALSACECESTVRAIMENTCHOUETTE

devient

NCNUCEGEGUVXTCKOPVEJQWGVVG

On est d'accord, ça ne veut rien dire. Pour décrypter ce chiffrement monoalphabétique, le destinataire du message doit simplement inverser le procédé.

Est-ce sûr pour autant ?

Si l'intercepteur est observateur, pas du tout !

Les érudits arabes des VIIe-VIIe siècle, nés dans une civilisation en plein essor, sont très sensibles aux fréquences. Mots sacrés et lettres récurrents, rien ne leur échappe.

Le philosophe Al-Kindi détaillera le décodage du chiffre de César grâce à l'analyse de fréquences.

Il s'agit de repérer les lettres cryptées qui se répètent, de noter la fréquence à laquelle elles se répètent, et de comparer avec les lettres de la langue de cryptage. Il est clair que plus le texte est long, mieux c'est.

Par exemple, imaginons que je demande à une fille prénommé Maëlle d'épeler les voyelles de la belle caravelle.

En appliquant le même chiffre de César qu'avant :

MAELLEEPELLELESVOYELLESDELABELLECARAVELLE

devient

OCGNNGGRGNNGNGUXQAGNNGUFGNCDGNNGECTCXGNNG

 

Attaquons-nous maintenant aux fréquences.

OCGNNGGRGNNGNGUXQAGNNGUFGNCDGNNGECTCXGNNG

La lettre G arrive en tête avec 13 lettres sur les 41 du message.

En se reportant à une table de fréquences du français, il serait aisé d'identifier G comme E, la lettre la plus couramment utilisée dans cette langue. On continuerait le raisonnement avec les autres lettres, et après quelques tâtonnements le code tomberait.

Les petits malins pourront ralentir le décryptage en faisant des fautes d'orthographe, mais ça ne rend pas plus sûr ce type de codes. Pareil pour les "alphabets inventés".

Pour finir, (re)voyez l'excellent Zodiac de David Fincher pour une belle démonstration de décryptage par analyse de fréquences !

Le carré de Vigenère, juste un chiffre de César amélioré

C'est après la Renaissance, au XVIe siècle plus précisément, que Giovan Battista Bellaso invente le chiffrement polyalphabétique.

Le principe est simple : utiliser un alphabet différent pour chaque lettre à coder.

Le français Blaise de Vigenère reprendra à son compte cette trouvaille en plaçant les différents alphabets dans un même carré (cliquez sur l'image pour agrandir).

Image : illustration de la page Wikipedia du chiffre de Vigenère

Le codage/décodage s'en trouve énormément simplifié et on peut même utiliser un mot-clé, succession des alphabets utilisés pour le cryptage.

Exemple

Prenons le mot-clé "mulhouse" pour coder le texte de la partie précédente.

La première lettre sera obtenue à partir de la ligne du carré commençant par "M", la deuxième à partir de la ligne "U", la troisième à partir de la ligne "L", etc...

En utilisant ce mot-clé :

MAELLEEPELLELESVOYELLESDELABELLECARAVELLE

devient

YUPRZYWTQJPLZYKZASPSZYKHQFLISFDIOUCHJYDPQ

Maintenant, on peut s'amuser à chercher les fréquences. Dans notre texte codé, Y apparaît quatre fois, mais il code à la fois un M et trois E. De plus, E est aussi remplacé par d'autres lettres comme P ou Q.

L'analyse de répétition des lettres du message ne peut donc pas venir à bout d'un carré de Vigenère.

N'y a-t-il pas une autre répétition ?

Si, mais elle est plus subtile que pour un chiffre de César. Le scientifique touche-à-tout Charles Babbage (1791-1871) est le premier à accomplir l'exploit.

Le déclencheur de sa découverte est la vantardise d'un dentiste anglais, John Thwaites, qui affirme au Journal of the Society of Arts vouloir breveter le carré de Vigenère qu'il vient d'inventer.

En plus de sa remarquable inculture, l'homme met au défi Babbage de décoder un texte chiffré avec un carré de Vigenère.

Babbage remarque la répétition de trois séquences dans le texte codé. Il note alors le nombre de caractères qui séparait chaque séquence, et en déduit des longueurs  de clé potentielles.

En recoupant les longueurs de clé potentielles de chaque séquence, il conclut que la clé de chiffrement est forcément composée de cinq lettres. Bon début.

Un chiffrement polyalphabétique est en fait basé sur plusieurs codes monoalphabétiques, que l'on peut résoudre individuellement en analysant les fréquences.

En connaissant la longueur de la clé, Babbage peut lister quelles lettres font partie du même alphabet. En analysant les fréquences "à l'ancienne", il peut déduire quelles lettres remplacent l'omniprésent E, et faire tomber petit à petit le mot-clé.

La chose est facilitée par le fait que Thwaites a codé un poème avec des rimes, et donc des répétitions de caractères. En plus de cela, sa clé très courte a permis de révéler encore plus clairement le texte codé.

Un peu plus d'un siècle plus tard, la mécanique allait refaire prendre l'avantage aux codeurs.

Enigma, une forteresse attaquable

Au début du XXe siècle, l'ingénieur allemand Arthur Scherbius mécanise un cryptage dérivé du chiffre de Vigenère. En reliant trois rotors (dans la version la plus commune) de 26 lettres reliés entre eux, il obtient 17 576 clés potentielles.

Moyennement sûr dans le cas où plusieurs personnes testeraient toutes les clés, Scherbius décide de pimenter la chose avec un tableau de connexions. Il permet d'inverser six paires de lettres (plus selon les modèles) dans les 26 que compte l'alphabet. Avec cette manip', on atteint l'air de rien un total qui dépasse les 100 milliards de possibilités.

En multipliant cet impressionnant résultat aux clés des rotors et aux six orientations possibles de chacun d'eux, la machine Enigma est capable de générer plus de 10 000 milliards de clés dans sa version la plus simple.

Avec l'arrivée imminente de la Seconde Guerre Mondiale, les Allemands étaient persuadés d'avoir pour eux une machine à coder inviolable. C'était sans compter sur la ténacité d'un cryptanaliste polonais.

Rejewski à l'assaut des clés répétées

Dans les années 1930, les Polonais, coincés entre les menaces expansionnistes de l'Allemagne à l'Ouest et de la Russie à l'Est, sont particulièrement motivés à décrypter les messages allemands.

En 1931, des espions français récupèrent grâce à un traître allemand des plans et une partie du protocole de fonctionnement d'Enigma. Ils confient ces précieuses données à leurs alliés polonais.

Le cabinet noir Biuro Szyfrów recrute Marian Rejewski alors qu'il n'a que 23 ans. Hyper intelligent, doué pour les maths et l'allemand, il a la tâche de trouver le point faible de la machine Enigma.

Grâce aux documents, il connaît grosso modo les pièces d'Enigma. Mieux encore, il sait comment les Allemands l'utilisent. C'est là qu'il va trouver sa première prise pour attaquer la machine à coder.

Tous les opérateurs allemands ont un carnet de clés quotidiennes. Ils ont bien conscience qu'utiliser la même clé pour crypter l'ensemble des milliers de messages du jour augmente statistiquement les chances de la trouver.

Ils décident par convention de se servir de la clé du jour pour échanger avec leur récepteur une nouvelle clé, composée de trois lettre et exclusive à leurs messages. Pour éviter qu'elle soit brouillée par les échanges radio, les Allemands l'écrivent deux fois.

Rejewski sait que les premiers messages interceptés composés de six lettres sont un cryptage de la même série de trois lettres. Il peut en déduire que la première lettre est liée à la troisième, la deuxième à la quatrième, et la troisième à la dernière.

En interceptant suffisamment de messages, il arrive à dresser l'ensemble des paires de lettres du jour. Ces paires forment des chaînes plus ou moins longues, des boucles qui relient les lettres entre elles.

Exemple :

A partir des lignes d'appariement

ABCDEFGHIJKLMNOPQRSTUVWXYZ

CBVNEPALMQSZUORXEWTFJKHGDY

on peut définir la boucle

A -> C ->V -> K -> S -> T -> F -> P -> X -> G ->A

et ainsi de suite pour les lettres manquantes.

Rejewski a un bon début, mais il lui faut impérativement réduire le nombre de clés à tester. Particulièrement inspiré, il remarque que la longueur des chaînes n'est pas liée au tableau de connexions.

Son problème se trouve donc amaigri de 10 000 milliards de clés possibles à seulement 105 456. Ca reste très conséquent, mais devient possible à plusieurs.

Rejewski accomplit un travail de titan pour répertorier l'ensemble des chaînes possibles. Grâce à son large répertoire de combinaisons, il peut placer les rotors dans les bonnes positions.

En débranchant le tableau de connexions et en tapant le message codé, certains mots apparaissent dans le fouillis de lettres. Cela permet à Rejewski de déduire petit à petit les lettres inversées. Les communications allemandes du jour deviennent alors transparentes.

Les travaux de Rejewski seront capitaux pour l'armée de cryptanalystes anglais de Bletchley. Mais il n'y aurait jamais pu y arriver sans une nouvelle répétition dans le code.

Le langage binaire allait inverser cette tendance.

Des 0 et des 1 qui se répètent, un code parfait

Dès 1945 avec l'Electronic Numerical Integrator Analyser and Computer (ENIAC), la cryptographie trouve un nouveau souffle. Plus rapides et plus performants, les ordinateurs surpassent n'importe quelle machine à coder.

Une force indiscutable vient de la façon dont les lettres et symboles sont codés par des groupes de 8 octets (0 ou 1) appelés bits. En résumé, chaque symbole est d'office traduit par une succession de 0 et de 1.

Avec ce premier code, on peut manipuler les octets d'un même symbole ou bien les mélanger entre eux. Les possibilités sont infinies et un cryptanalyste ne sait pas par quel bout commencer, puisqu'il se retrouve techniquement en face de séries de 0 et de 1.

Lucifer, un des premiers algorithmes de chiffrement, est précisément basé sur la manipulation des bits.

Il est incroyable de constater qu'un code extrêmement simple, impliquant uniquement deux symboles qui se répètent perpétuellement, puisse être d'une si redoutable efficacité.

D'où ce premier commandement de la crypto.

Pour aller plus loin

Je ne saurais que trop vous recommander la lecture d'Histoire des codes secrets de Simon Singh qui explore en profondeur les exemples cités plus haut comme d'autres tout aussi passionnants !

Comments

Comment by Nono on 2012-02-27 18:05:17 +0100

Tu m'as perdu avec :
"En interceptant suffisamment de messages, il arrive à dresser l'ensemble des paires de lettres du jour. Ces paires forment des chaînes plus ou moins longues, des boucles qui relient les lettres entre elles.

Exemple :

A partir des lignes d'appariement

ABCDEFGHIJKLMNOPQRSTUVWXYZ

CBVNEPALMQSZUORXEWTFJKHGDY

on peut définir la boucle

A -> C ->V -> K -> S -> T -> F -> P -> X -> G ->A

et ainsi de suite pour les lettres manquantes."

J'ai absolument pas compris comment tu obtiens ta boucle ...

Comment by Raphi on 2012-02-27 18:14:45 +0100

J'avoue que c'est un peu complexe. Au départ, tu as des messages avec six lettres. Ces six lettres sont deux codages de trois mêmes lettres. Un message est donc égal à trois paires de lettres liées : la première et la troisième codent la même lettre, tout comme la deuxième et la quatrième, etc...

Avec plein plein de messages, tu peux associer les 26 paires de lettres du jour. Dans mon exemple, A est lié à C. En repassant dans la ligne du haut, on voit que C est lié à V. On refait ce parcours jusqu'à retrouver A (notre lettre de départ). Cette chaîne (ou boucle) plus ou moins longue est liée de manière unique aux rotors.

J'espère avoir été assez clair 😉 !

Comment by H3 on 2012-02-27 18:14:50 +0100

Analyse, très intéressante, je connaissais le nombre de césar, au autres substitutions, mais il est pas mal de rappeler les bases... 🙂

Et sympa la référence à IAM... 😀

Comment by Nono on 2012-02-27 18:16:38 +0100

ok, c'est décalé les lettres, essaye de les mettre dans un tableau si tu peux ..

Comment by Raphi on 2012-02-27 20:06:26 +0100

Eh eh 😉 !

Comment by H3 on 2012-02-29 23:49:23 +0100

Ça m'intriguait, je viens de tester de faire un algo pour crypter/decrypter un Vigenere, puis le craquer... Le crack avec uniquement le chiffré connu, c'est super galère, le brute force a juste fait brûler ma machine...

Comment by Raphi on 2012-03-01 09:58:21 +0100

Merde, fait brûler ou planter o_O ? C'était quoi comme machine ?

Comment by H3 on 2012-03-05 10:31:56 +0100

Ok j'avoue c'est un petit AMD Dual Core tout mignon, au bout d'un quart d'heure de calcul j'ai commencé à avoir des java.OutOfMemory dans tout les sens... Faudrait que je réessaye en donnant plus de mémoire à la JVM... 🙂

Comment by Stone on 2014-06-10 01:11:26 +0200

00257784560034562749000213120804000010000705162738495061728394043412936218381263075021005676109600678240230162431596403500643130834540970662317433116002103607610554371531599014005798289830023546310453760050023702

Ce message codé signifie très exactement en clair :

mycodeishere (my code is here)

Avis aux amateurs de décryptage : vous avez le message en clair et sa version cryptée...

Il a été crypté avec un chiffre inviolable qui ne nécessite aucune compétence spéciale pour le codage ou le décodage. Il n'utilise aucune clé particulière qui doivent faire l'objet d'un échange, il est brouillable à volonté (injection d'éléments aléatoires par l'expéditeur dans chaque message), mutable (les valeurs peuvent changer à volonté sans altération du sens), élastique (la longueur du message codé peut être modifiée à volonté sans altération du sens), et autonome (aucune machine ou autre n'est nécessaire pour coder ou décoder), ainsi que réversible (les valeurs sont susceptibles d'inversion aléatoire sans altération du sens)..

Même en disposant des textes en clair avec leur équivalent codé, je doute fort qu'il puisse être cassé

Comment by Stone on 2014-06-10 01:18:11 +0200

Si un amateur de décryptage est intéressé, il lui suffit de me demander tel ou tel message précis que je lui coderai et diffuserai ici (svp pas trop longs : une phrase suffira, par exemple : Message contenant Maman est dans le jardin, et un autre contenant maman va dans le jardin, pour tenter de "casser "le code en décelant les différences, etc) : il sera ainsi en position d'attaque sur message en clair choisi avec chaque fois possession de l'équivalent codé : la meilleure situation possible. De mon côté, je suis curieux de voir la résistance.