Cryptanalyse des codes de Louis XIV () ()

Ma page cryptographique

Les codes de Louis XIV

  • Introduction (introduction)
  • L'invention du grand chiffre (invention)
  • Analyse des codes de Louis XIV (analyse)
  • Cryptanalyse
    • Méthodes pour casser un code
    • Le cœur de la méthode : l’indexation des groupes (indexation)
    • Analyse préalable : la méthode de Friedman (Friedman)
    • Le déchiffrement fait par Bazeries du code de 1691 (Bazeries)
    • Les déchiffrements anglais (J. Wallis, …) (anglais)
    • Les méthodes espagnoles de déchiffrement à l’époque de Louis XIV (espagnol)
  • Exemples de codes (exemples)
  • L'énigme du masque de fer (masque)

Méthodes pour casser un code, introduction

En cryptologie, il y a essentiellement deux méthodes de chiffrement:

  • Les chiffres (qui se divisent en substitution et transposition)
  • Les codes

Les méthodes de cryptanalyses de ces deux types sont très différentes.

Remarque: Du fait que les codes dérivent de la substitution simple, il y a quelques analogies entre le cassage des codes et le cassage d'une substitution.

Pour casser un code, le coeur de la méthode est l'indexation des groupes et ensuite la recherche de la signification de chacun des groupes en fonction du contexte. C'est pour cela que l'on commence ce document par décrire cette méthode.

Ensuite on décrit l'approche théorique de Friedman, l'un des plus célèbre cryptanalyste de l'histoire. On poursuit par la méthode que Bazeries a utilisé pour casser pour la première fois de l'histoire un code à double tables (tout au moins la première fois de manière publique). On poursuit par les déchiffrements anglais qui ont été en partie tenus secret pendant longtemps. On termine en décrivant les méthodes des cryptanalystes Espagnol, notamment quand ils se sont attaqués aux codes français du XVII.

Le cœur de la méthode : l’indexation des groupes

Description de la méthode

Le livre « The American Black Chamber » de Yardley nous décrit le cœur de toute méthode de cryptanalyse d’un code :

Chaque cryptogramme est reporté sur un ensemble de cartons (autant qu’il y a de groupes dans l’ensemble des cryptogrammes). Chaque carton contient un groupe (qui servira d’index) et qui correspond à chaque groupe dans l’ordre d’apparition ainsi que les quatre groupes précédent et suivant le groupe indexé. A la fin du carton est indiqué une référence qui spécifie le numéro du cryptogramme et la ligne où apparaît le groupe.

On classe ensuite les cartons en fonction de l’index (le numéro du groupe). On obtient ainsi la fréquence du groupe. Ultérieurement on étudiera que les groupes les plus fréquents (et puis ensuite les autres groupes). Au fur et à mesure des déductions on remplace les codes précédents et suivant le groupe index par leur valeur en clair, ce qui permet souvent d’en déduire la signification du groupe index.

On le constate, cette méthode à deux gros inconvénients :

  • Elle demande beaucoup de travail. L’utilisation d’une équipe nombreuse devient vite indispensable si le code est complexe et comporte beaucoup de groupes.
  • Il faut connaître quelques codes avant de pouvoir utiliser cette méthode (il faut amorcer la pompe).

On peut noter également que cette méthode nous livre facilement la fréquence des groupes et les répétitions.

Remarque: De nos jours, un programme informatique simplifie l'usage de cette méthode.

Exemple

Pour illustrer cette méthode, on va prendre les messages qui ont permit à Bazeries de casser le code de 1691. Voici le début du 2ième cryptogramme : 

Ligne 1:  480 367 029 270 479 163 167 128 024 207 229 234
Ligne 2:  508 099 094 469 289 260
...
Chacune des lignes suivantes est reproduit sur un carton : 
                <<480>> 367 029 270 479    2:1 
            480 <<367>> 029 270 479 163    2:1 
        480 367 <<029>> 270 479 163 167    2:1 
    480 367 029 <<270>> 479 163 167 128    2:1 
480 367 029 270 <<479>> 163 167 128 024    2:1 
...
024 207 229 234 <<508>> 099 094 469 289    2:2
Ensuite, on classe les cartons en fonction des index, par exemple: 
034 282 255 097 <<508>> 405 024 484 097    1:17
026 125 454 022 <<508>> 556 119 573 502    1:33
... 
024 207 229 234 <<508>> 099 094 469 289    2:2
...
Au fur et à mesure des déchiffrements, un des cartons précédents devient comme suit: 
026  125 454 022 <<508>> 556 119 573 502    1:33
vous ne  m   en  <<--->> y   e   z   rien
Il est facile de déduire que le code 508 correspond à la lettre «a». Bien sur dans la vrai méthode, on préfère qu’il y ait des confirmations.

Références

  • The American Black Chamber, par Herbert O. Yardley, aux éditions Aegean Park Press. Reproduction sans modification d'un livre publié en 1931.

La méthode de Friedman

Friedman a analysé les codes allemands pendant la 1ère guerre mondiale. Il a écrit un rapport qui décrit la méthode pour les résoudre. Cette méthode est faite de deux parties : la classification et l’identification.

La première phase consiste à répartir chacun des groupes dans une classe : nombres, mots et phrases, les lettres et les syllabes, les signes de ponctuation, … La seconde phase est l’identification de chacun des groupes. Voici les principales classes :

  1. Les nombres : ils sont très fréquents, les nombres 1 et 2 étant les plus nombreux. Ils sont en connexion avec des groupes de la classe « Unité militaire ». Ces groupes sont regroupés en groupes de deux, trois, quatre groupes, exceptionnellement plus de quatre. Il y a une grande diversité dans l’arrangement des permutations de ces groupes.
  2. Les groupes pour épeler (lettres et syllabes) L’objectif des ces groupes est d’épeler les mots qui n’appartiennent pas au code. En fait, par incompétence, plusieurs chiffreurs épellent souvent des mots qui existent dans le code.

    Ils sont très fréquent. Ils surviennent en chaîne. Contrairement aux nombres, on a de fréquentes répétitions de suites de groupes.

  3. Les mots et les phrases …
  4. Les signes de ponctuation …

En plus de la méthode précédente appelée « Par les premiers principes », Friedman, décrit une méthode plus rapide, celle «  Par Analogie ». Elle consiste a rapprocher les cryptogrammes non résolus de messages utilisant un code déjà connu. Notamment en analysant les groupes les plus fréquents, en comparant les débuts des messages et en comparant les messages de mêmes longueurs.

Références

  • Solving German Codes in World War I, with an added special "Code Problem" for the student, par William F. Friedman, aux éditions Aegean Park Press, 1977. Ce livre a été écrit par Friedman à la fin de la guerre de 1914-1918 lorsqu'il était encore en France.

Le déchiffrement fait par Bazeries du code de 1691

A la fin du XIX siècle, le commandant Bazeries réussi à déchiffrer des lettres chiffrés datant du 1691. Elles contenaient la correspondance entre Louvois ou Louis XIV et le maréchal de Catinat qui guerroyait dans le Dauphiné (cf. le code de 1691).

Bazeries, à la suite de ses travaux écrit un livre, parru en 1893 qui relate son hypothèse surl'identité du masque de fer. Il repose son hypothèse sur ses déchiffrements. En annexe de son livre, il décrit la méthode qu'il a suivi pour casser le code de Louis XIV de 1691.

Voici des extraits du livre de Bazeries qui décrit sa méthode:

Jusqu’à ce jour, les chiffres du genre de celui de Louis XIV avaient été considérés comme absolument indéchiffrables. Chaque groupe ayant une valeur arbitraire, il ne paraissait pas possible de déterminer cette valeur. Aussi le déchiffrement du commandant Bazeries a-t-il produit une grande émotion dans le mondes des cryptologues.

En 1891, le commandant Gendron, de l’état-major général de l’armée, faisait une étude sur les campagnes de Catinat. Il se trouvait arrêté dans ses recherches par des dépêches en chiffres. Il les communiqua au commandant Bazeries, qui après examen, se fit fort de les déchiffrer. …

Le travail exigé par la reconstitution du chiffre a passé par trois phases successives. La première a consisté dans le pointage ou plus exactement, dans l’enregistrement des groupes employés, pour obtenir l’ordre de fréquences et les répétitions. … Ce travail fut long et monotone …

Il ne paraît pas utile de donner ici, in extenso, le résultat de cet enregistrement des groupes. On signalera seulement que le groupe le plus employé était 22 existant 187 fois. Venaient ensuite les groupes : 

      124 existant 185 fois,
       42 ---      184 fois,
      341 ---      145 fois, 
      125 ---      127 fois,
       24 ---      124 fois,
      145 ---      122 fois, etc.

Il est clair que c’est dans les groupes souvent employés qu’il fallait rechercher les mots, syllabes et lettres revenant le plus fréquemment dans le discours. Quand aux répétitions, c’est à dire aux groupes se reproduisant ensemble, 2 par 2, 3 par 3, 4 par 4, etc. Il est très important de les marquer spécialement, car ces répétitions comportent le même mot ou le même membre de phrase. …

(deuxième phase) … Le point de départ de toute reconstitution de chiffre est toujours la recherche d’un mot supposé. Quel mot supposer ? Dira-t-on ? Dans l’espèce, le commandant Bazeries a opéré sur le mot « les ennemis » qu’il comptait, à juste raison, rencontrer dans les correspondances militaires qui lui étaient soumises. « Ennemi » pouvait être représenté par un seul groupe, ce qui pour : « les ennemi s » devait donner 3 groupes revenant fréquemment ensemble. « Ennemi » pouvait être syllabé ; alors « les en ne mi s » formaient 5 groupes. Après examen des répétitions, on s’est déterminé pour « ennemi » syllabé et on a conjecturé que c’étaient les groupes ci-après reproduits souvent avec une légère variante qui chiffraient « les ennemis » 

      124.  22.  146.  46.  469.
      124.  22.  125.  46.  574.
      124.  22.  125.  46.  120
      124.  22.  125.  46.  584.
      124.  22.  125.  46.  345.
      les   en   ne    mi   s

La supposition des mots « les ennemis » et des groupes qui les reproduisaient s’étant trouvée exacte, tout le chiffre de Louis XIV a été livré par la seule donnée de ce point de départ. …

La troisième phase est la plus attrayante. Le travail consiste, dès qu’on a une partie du chiffre, à trouver l’autre partie. Point n’est besoin pour cela d’être cryptologue consommé ; de la sagacité et de la droiture de raisonnement suffisent à cette tâche Il faut cependant procéder avec prudence. Un groupe mal déterminé est une source d’erreurs dont le redressement peut devenir impossible ; avant d’adopter définitivement la valeur de chaque groupe, il faut lui faire faire ses preuves. …

(Exemple) 

… pour bien défendre la place 436. 291.  53. 154. 22. 465.
                              et   j’ay  ??? e    en  mesme
48.   52. 255. 556. 281. 115. 9. 450. 201. 578.
temps que lon  y    fi   st   re me   t    t
93. 34. 548. 503. 311. 272.  22. 412. 115. 525.
re  de  l    ???  pour qu’il y   en   eu   au
259.  503. 437. 424. 385. 129. 273.  42. 454. 583 …
moins pour u    n    a    n    et    de  m    y

Évidemment, c’est bien « ordonn » et « argent » qui sont chiffrés par « 53 » et « 358 ». Cela ne fait par l’ombre d’un doute, car c’est le sens nécessaire de la phrase.

Remarques :

  1. On le constate, Bazeries n’est pas au courant des déchiffrements réalisées par les Anglais.
  2. Bazeries insiste sur la prudence qu’il faut appliquer sur l’identification d’un groupe. Pourquoi n’a-t-il pas fait usage de cette prudence pour déterminer la signification du groupe 330 (cf. le masque de fer) ?

Référence

  • Le masque de Fer, Révélation de la correspondance chiffrée de Louis XIV. Emile Burgaud et commandant Bazeries, 1893, librairie de Fimin-Didot.

Les méthodes espagnoles de déchiffrement à l’époque de Louis XIV

Un ouvrage extrêmement rare a été découvert dans les archives de Bruxelles par DEVOS et SELIGMAN : L’ART DE DESCHIFFRER. Cet ouvrage décrit les méthodes de cryptanalyse utilisés par les Espagnols à la fin du XVII siècle. Il traite au début de la substitution simple (la méthode usuelle de séparation voyelles / consones est présentée) et ensuite de l’usage de codes qui mélange les lettres, les syllabes et des mots. Chacune des deux parties est suivi d’exemples de décryptements en espagnol et en français. Ainsi, la lettre de 1676 présenté plus loin.

Dans les deux cas, les auteurs de ce rapport s’appuient sur les caractéristiques du langage utilisé dans le cryptogramme. Les auteurs ne traitant que le français et l’espagnol. Pour la suite, je n’indiquera leurs conclusions qu’en ce qui concerne le français. Voici un résumé de la méthode d’analyse d’un code présentée dans la deuxième partie de l’ouvrage.

En français, les lettres les plus courantes sont E, A, N, R, S, T et U. le E étant de loin la lettre la plus fréquente. La lettre Q est le plus souvent suivi d’un U. Les syllabes les plus courantes étant ce, de, le, la, me, ne, que, re, se, te, en, on, er, is, il, et. On le remarque beaucoup de syllabes fréquentes se terminent par « E ». Voici quelques groupes qui se suivent parmi les plus fréquents : n-s, n-t, r-t, r-s, de-s, le-s. Les doubles les plus fréquents sont aa, ff, pp, tt. Certains modèles d’enchaînement sont particulièrement utiles: soit le groupe chiffré Y encadré du même groupe chiffré X (X. Y. X.). Cette configuration peut correspondre à me-s-me, que-l-que, te-s-te, che-r-che, … Le modèle X. Y. X. Y. peut correspondre à che-r-che-r, me-s-me-s, … Le modèle X.Y. X. Z. W. X. peut correspondre à re-p-re-n-d-re.

Remarque : les cryptanalystes qui ont écrit l’ouvrage, on le constate décrivent de manière très précise la langue du point de vue du cryptologue. Ces descriptions n’ont rien à envier à celles réalisées au XX siècle par le célèbre cryptologue Friedman.

Pour analyser un code, on commence par répertorier les groupes les plus fréquents. On les analyse le plus minutieusement : leur fréquence, leur associations entre eux et où ils se répartissent dans le cryptogramme.

Au départ on détermine les groupes nuls. Ils sont facilement repérables: ils sont en début et fin de paragraphe.

Il faut ensuite trouver les groupes qui codent les lettres et les syllabes. Dans le cas de la substitution simple, il était aisé de trouver le E qui est la lettre la plus fréquente. Dans un code sa fréquence est diluée dans l’utilisation de syllabes se terminant par cette lettre mais ces syllabes sont parmi les plus fréquentes ! Le S, comme il termine les mots se retrouve souvent spatialement avec un écartement qui correspondent aux mots : lesS grandeS et petiteS preuveS que leS fidèleS alliéS … [l’exemple de l’ouvrage est en espagnol].

En se basant sur la description de la langue que l’on a faite précédemment, on essaiera de déterminer un ou plusieurs groupes.

Quand on est sur d’un groupe, il est aisé de trouver la signification de ceux qui le suivent ou le précèdent. Par exemple si on a déterminé qu’un groupe correspond à la lettre N, celui-ci peut être suivi d’un « S » (actions, fortifications, dans, …) ou d’un « T » (ment, tant, élément, sont, …). Si un groupe correspond à la syllabe DE, il peut former les mots grande ou monde.

Pour un groupe très courant, on peut aussi trouver sa signification par élimination en déterminant ce qu’il ne peut pas être.

Pour déterminer les groupes qui correspondent à des mots, il y a plusieurs indications. On les reconnaît parce qu’ils ne peuvent pas former de mots (ils ne servent pas à épeler).

Pour les noms propres (villes, personnages, ...), ils correspondent souvent à des groupes numériques élevés car ils ont été ajoutés à la fin du code. D’autre part, ils sont souvent précédés de groupes signifiant le, la, de, Monsieur, …

Si on n’est pas sur qu’un groupe soit une lettre ou une syllabe, il faut l’étudier dans tous les endroits où le groupe survient et on détermine si son hypothèse se vérifie ou est à rejeter.

Certains principes aident à la reconstitution du code :

Il faut rechercher les répétitions de groupes (X. Y., X. Y. Z., …) et la répétition de modèles (X. Y. X., …). Si on croit deviner la signification d’une suite de groupes, de légères modifications vont nous livrer des équivalents, par exemple les différents groupes signifiant la lettre O [un exemple en espagnol est donné].

Si on a déterminé quelques groupes, comme BA, BE, BI et que l’on trouve une règle qui relie les groupes chiffrés qui les représentent, par exemple, 42, 53, 64, on peut en déduire les valeurs pour les autres groupes BO et BU : 75 et 86.

Je ne sais pas si le service du chiffre espagnol a réussi à déchiffrer les codes français à double tables en fin XVII ou au XVIII, mais je pense qu’il en avait assurément la compétence.

Références

  • L’ART DE DESCHIFFRER, Traité de déchiffrement du XVII siècle de la secrétairie d’état et de Guerre espagnole. Traité édité par J.P. DEVOS et H. SELIGMAN en 1967 aux UCL presses universitaires de Louvain.

Les déchiffrements anglais (J. Wallis, ...)

John Wallis qui a réalisé des cassages de codes pour le gouvernement anglais a publié dans son livre « Opera Mathematica » (qui traite essentiellement de mathématique), deux décryptements qu’il avait réalisé : l’un concernant un code français de 1689 utilisé pour les échanges entre le Marquis de Bethune et le Cardinal d'Estré, l’autre concernant un autre code français de la même année utilisé pour les échanges entre D. de Teil et le roi Louis XIV. Les codes utilisés dans ces deux lettres sont du type mono-table et semi-ordonné. John Wallis n’a donc pas eu trop de mal à les décrypter. Il n’empêche qu’il n’a pas publié sa méthode de résolution, ce qui a contrarié son confrère mathématicien Leibniz.

Dans l’ouvrage de Kahn (The Codebreakers), on trouve un autre décryptement de John Wallis d’un cryptogramme du roi Louis XIV de 1693. La encore, il s’agit d’un code à une seule table semi-ordonné (a : 2, b : 5, c : 8, … la : 185, le : 195, …).

Toujours dans l’ouvrage The Codebreakers, une dépêche française datée de 1716 (un an après la mort du roi Louis XIV) est déchiffrée par le service de déchiffrement anglais (J. Wallis était déjà mort). Par contre, ici, il s’agit d’un code à double tables. Bazeries n’était donc pas le premier à casser ce type de code !

Références