Cryptanalyse d’Enigma par l’indice de coïncidence

Enfin la partie la plus intéressante.

Enigma
Cryptanalyse d’Enigma

Cryptanalyse d’Enigma – Historiquement

Détermination du câblage interne des rotors

Même après la première guerre mondiale, les états continuaient à surveiller et décrypter les conversations des pays voisins. À partir de 1926, les messages allemands commencèrent à être chiffrés par Enigma. Les cryptanalystes alliés renoncèrent vite à briser Enigma, du à sa difficultés, et surement pensant qu’une invasion serait impossible.

Mais la Pologne, se sentant menacé par ses voisins (5400km de frontière, entouré seulement par des états ennemis), décida de se lancer dans la cryptanalyse d’Enigma. Trois spécialistes s’en chargèrent dont Maksymilian Ciezki. Malgré tout leur possible, et la version commerciale d’Enigma (qui avait des rotors différents, et qui ne possédait pas de fiches) la cryptanalyse n’avançait pas. C’est grâce à un espion Allemand, Hans-Thilo Schmidt que le bureau polonais trouva une faille. Il leur transmit les instructions d’utilisation de la machine, les directives pour fixer une clé, et plusieurs fois le cahier des configurations du mois, ainsi que quelques informations.

Des mathématiciens se joignirent au Bureau du Chiffre polonais, donc un certain Marian Rejewski un jeune étudiant de 23 ans. Précédemment, nous avons vu que les messages chiffrés étaient précédé de 6 lettres (la clé chiffrée). La première stratégie de cryptanalyse se basait dessus. Dans les instructions fournit par Hans-Tilo, ils savaient que la première lettre correspondait à la quatrième, la seconde a la cinquième et la troisième à la sixième.

Répétition de la clé sur les 6 premiers caractères des messages
Répétition de la clé sur les 6 premiers caractères des messages

Dans le premier message on sait donc que le L et le R représente la même lettre, mais que les rotors ont tourné deux fois entre. Le but était de recueillir assez de message pour pouvoir reconstituer l’alphabet.

Correspondances entres les 6 premier caractères et les décalages à cause de la répétition de la clé au début du message.
Correspondances entres les 6 premier caractères et les décalages à cause de la répétition de la clé au début du message.

Le deuxième problème est dû au tableau de connexions (les fiches). Ceux-ci augmentent de equation 6 la complexité. Rejewski a donc cherché un moyen d’annuler ses permutations ne recherchant des chaines de lettre.

Pour l’alphabet ci-dessus :

  • A -> T -> E -> R -> K -> J -> P -> I -> O -> X -> C -> U -> M -> A = 13 liens
  • B -> W -> H -> Z -> D -> Q -> G -> N -> F -> V -> L -> Y -> S -> B = 13 liens

Ensuite, Rejewski répéta la même opération avec les couple deuxième/cinquième et troisième/sixième lettres. Il remarqua qu’il y avait trois configurations de cycle :

  • 2 chaines de 13 liens chacun ;
  • 6 chaines de 9, 9, 3, 3, 1, 1 liens chacun ;
  • 6 chaines de 10, 10, 2, 2, 1, 1 liens chacun.

Il comprit aussi que le rotor le plus à droite était le rotor rapide, celui qui tourne d’un cran à chaque fois. On comprend bien que pendant que l’opérateur tapait, dans 21 cas sur 26 seul ce rotor rapide tournais et que les 2 autres restaient fixes. Il réussit à faire plusieurs équations pour déterminer le câblage interne de ce rotor rapide. Malheureusement le nombre d’inconnus est trop élevé. Avec les carnets de code de Hans-Tilo, cela lui permit de dévoiler des inconnus et donc de simplifier les équations. Il réussit donc à déterminer le rotor rapide et à cette époque la configuration des rotors changeaient par chance tous les trois mois. Il put ainsi déterminer les câblages des autres rotors lorsqu’ils occupaient la position du rotor rapide dans le brouilleur.

Pour décrypter Enigma, nous partirons de ce moment-là, où nous connaissons le câblage interne des rotors.

Détermination de la position des rotors et des fiches

Après avoir trouvé le câblage des rotors, les polonais purent fabriquer une version d’Enigma. En utilisant les clés fournies par Hans-Tilo, ils ont pu décrypter les clés, et donc les messages chiffrés des allemands. L’équipe du Bureau de Chiffre répertoria toutes les structures cycliques pour toutes les dispositions du brouilleur dans un répertoire. Ceci leur a pris un an.

Ainsi, chaque jour, l’équipe recueillait le maximum de message allemand, pour pouvoir faire les tableaux d’alphabet comme ci-dessus et regardait dans le cahier qu’ils ont créé à quel position ces chaines référaient. Une fois ceci terminé, à l’aide d’une attaque par statistique, ils déterminaient les fiches. Ils obtenaient donc le message en clair.

Malheureusement, après plusieurs années, les allemands ont changé les câblages des rotors. Le bureau du chiffre polonais décida donc de concevoir une version automatisé de son répertoire qui en fonction des longueurs de chaines, donnait les réglages possibles du brouilleur. Cette « bombe » cryptographique pouvait vérifier 17 546 alignements de rotors en plusieurs heures, voir une journée. Ils ont donc construis 6 bombes afin de tester en même temps tous les agencements de rotors possibles. Lorsque les allemands augmentèrent le choix de rotors (3 rotors parmi 5) , il existe alors 60 combinaisons de rotors possible, ce qui indique qu’il aurai fallu 10 fois plus de bombe, mais qu’en plus il aurait fallu découvrir les câblages interne des nouveaux rotors. En plus d’avoir modifié les rotors, les allemands supprimèrent la clé chiffrée de 6 lettres au début du message, ce qui représente une difficulté supplémentaire pour les Polonais, car leur méthode ne fonctionne alors plus.

Les polonais décident donc de mettre les Français et les anglais dans leurs recherches, et leur fournir une copie de la machine Enigma. Les anglais fondèrent à Bletchley Park un bureau d’étude : le Government Code & Cipher School, et recrutèrent bon nombre de mathématiciens et cryptographes, dont Alan Turing, un jeune mathématicien surdoué.

Alan Turing mis au point une technique ce basant sur le mot probable. Il remarqua qu’on pouvait prédire une partie du contenu du message ou quelques mots. Par exemple, un bulletin météo était envoyé tous les jours avec le mot Wetter (temps). Il devait alors deviner la position du mot en se souvenant qu’une lettre n’est jamais codée par elle-même. Ensuite pour tester les positions de rotors (soit 105 456 possibilités) il modifia la bombe cryptographique de Rejewski. Une fois l’alignement des rotors il ne lui restait plus qu’à trouver les fiches.

Au total 16 bombes de Turing furent utilisées. Elles permettaient dans l’idéal de trouver la clé en deux heures. Quand il fallait changer le mot cible, cela pouvait aller jusqu’à deux jours. Mais une fois la clé trouvée, ils étaient capable de déchiffrer tous les messages allemands de la journée.

Voilà comment Enigma a été cryptanalyser durant la seconde guerre mondiale. Mais de nos jours, comment pouvons-nous faire pour accélérer le processus ?

Cryptanalyse d’Enigma – Modernement, comment qu’on fait ?

Les bombes de Turing étaient très efficaces à l’époque, mais nous avons maintenant des ordinateurs beaucoup plus puissants, capables de tester beaucoup plus de cas par seconde.

On part du principe que nous connaissons les câblages des rotors. On cherche donc le positionnement, le réglage des rotors et les fiches.

Pour la cryptanalyse d’Enigma, nous allons utiliser l’indice de coïncidence d’un texte. Pour que cela fonctionne correctement, il est nécessaire d’avoir un texte assez long (plusieurs centaines de caractère).

Il faut savoir qu’à l’époque, ils ne connaissaient pas encore l’indice de coïncidence et donc que cette méthode est anachronique.

L’indice de coïncidence représente la probabilité d’avoir deux lettres identiques dans un texte.

Cryptanalyse d’Enigma - incide de coincidence

 

 

Pour un texte aléatoire, le calcul devient : Cryptanalyse d’Enigma - incide de coincidence

Pour un texte Français, on se base sur la fréquence d’apparition des lettres en français. Pour un texte en Français, on a donc un IC = 0.0746.

Le but va être de calculer l’IC du texte pour toutes les positions de rotors et de prendre la plus haute valeur. On cherche à cryptanalyser la machine Enigma M3 :

 

Code Powershell

Rappel des constantes nécessaires : Voir le TP n°1 : Chiffrement avec Enigma

$Rotors = @{
    'alphabet'  = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
    'I'         = 'EKMFLGDQVZNTOWYHXUSPAIBRCJ';
    'II'        = 'AJDKSIRUXBLHWTMCQGZNPYFVOE';
    'III'       = 'BDFHJLCPRTXVZNYEIWGAKMUSQO';
    'IV'        = 'ESOVPZJAYQUIRHXLNFTGKDCMWB';
    'V'         = 'VZBRGITYUPSDNHLXAWMJQOFECK';
    'RefB'      = 'YRUHQSLDPXNGOKMIEBFZCWVJAT';
    'RefC'      = 'RDOBJNTKVEHMLFCWZAXGYIPSUQ'
}

$R = [int][char]'R'- [int][char]'A'
$F = [int][char]'F'- [int][char]'A'
$W = [int][char]'W'- [int][char]'A'
$K = [int][char]'K'- [int][char]'A'
$A = [int][char]'A'- [int][char]'A'

$changementsRotors = @{
    'I'    = @($R);
    'II'   = @($F);
    'III'  = @($W);
    'IV'   = @($K);
    'V'    = @($A);
}

Nous allons avoir besoin d’une fonction qui supprime tous les caractères autres que des lettres : Reprise du TP sur Vigenere

Function Remove-AllButAlphabet {
    param (
        [String]$src = [String]::Empty
    )
    
    $normalized = $src.Normalize( [Text.NormalizationForm]::FormD )
    $sb = new-object Text.StringBuilder
    $normalized.ToCharArray() | % {
        if([Globalization.CharUnicodeInfo]::GetUnicodeCategory($_) 
           -ne [Globalization.UnicodeCategory]::NonSpacingMark){
            [void]$sb.Append($_)
        }
    }
    $tmp = $sb.ToString()
    $res = $tmp -replace '[\s.,!?;:\-'']',''
    return $res
}

Nous allons aussi avoir besoin d’une fonction qui calcule l’indice de coïncidence d’un texte :

Fonction écrite par moi-même.

Function Get-IndiceCoincidence {
    param(
        $Texte
    )

    if ($texte.length -lt 2) { Return 0}
    # On enlève les espaces et les caractères spéciaux sont remplacés par leur ‘normal’ ex : è -> e
    $Texte = Remove-AllButAlphabet $Texte
    $Alphabet = ([int][char]'A'..[int][char]'Z' | foreach{[char]$_}) 
    $hashtableFreq = @{}

    $l=0
    for($l=0 ; $l -lt $alphabet.length ; $l++) { 
        $hashtableFreq.Add([char]$alphabet[$l],0) 
    }
    
    # On compte le nombre de A, B, etc.
    $l = 0
    for($l=0 ; $l -lt $Texte.length ; $l++){
        if($Texte[$l] -match '[a-zA-Z]'){
            $hashtableFreq.([char]$Texte[$l]) += 1
        }
    }

    # On calcule Ic
    $Ic = 0
    for($l=0 ; $l -lt $alphabet.length ; $l++){
        $Ic += ($hashtableFreq.Item($alphabet[$l])*($hashtableFreq.Item($alphabet[$l])-1))/($Texte.length*($Texte.length-1))
    }
    return $Ic
}

Les variables nécessaires à la recherche de position des rotors :

$cypher = “” # Le texte a déchiffrer
$texteADecrypter = Remove-AllButAlphabet $cypher.ToUpper() # On enlève tous les caractères spéciaux
$RotorsPossible = @('I','II','III','IV','V') # Dans la Enigma M3 qu’on étudie, il y avait 3 rotors à choisir parmi ces 5 là
$ReflectorsPossible = @('RefB','RefC') # On doit choisir un parmi les deux réflecteurs existants
$tab = @() # Notre tableau de solution

Programme de recherche par force brute (il n’est pas possible d’utiliser deux fois un même rotor, d’où les tests au début des foreach).

Après plusieurs tests, nous pouvons remarquer que pour une bonne position de rotors, l’indice de coïncidence s’élèvera à un peu plus de 0.045.

Je rappelle que pour déchiffré un texte, il suffit de réutilisé la même machine que pour le chiffrement avec la même configuration. Nous avons pour cela besoin de la fonction de chiffrement/déchiffrement que nous avons vu dans la première partie du cours sur Enigma.

# Quels rotors, quel ordre ?  
foreach($rotor1 in $RotorsPossible){ 
    foreach($rotor2 in $RotorsPossible){ 
        if($rotor2 -eq $rotor1){ Continue }
        foreach($rotor3 in $RotorsPossible){ 
            if($rotor3 -eq $rotor1 -or $rotor3 -eq $rotor2){ Continue }

            foreach($Reflector in $ReflectorsPossible){
                # Quelles positions initiales ?
                for($i=0; $i -lt 26; $i++){
                    for($j=0; $j -lt 26; $j++){
                        for($k=0; $k -lt 26; $k++){

                            # On a une clé, on la teste
                            $RotorSetup = @($rotor1, $rotor2, $rotor3)
                            $RotorInitPos = @($i, $j, $k)
                            $Reflector = $Reflector

                            # On déchiffre le texte 
                            # et on calcul l'indice de coincidence
                            $decypher = Get-HistoriqueEnigmaCypher -tabconnexion @() 
                            –RotorSetup $RotorSetup -RotorInitPos $RotorInitPos 
                            -Reflector $Reflector -Message $texteADecrypter
                            
                            $ic = Get-IndiceCoincidence $decypher
                            if ($ic -gt 0.045) {
                                # Une combinaison possible
                                write-host "($rotor1, $rotor2, $rotor3), 
                                            ($i, $j, $k) = $ic"
                            }
                        }
                    }
                }
            }
        }
    }
}

Nous allons donc récupérer quels rotors sont utilisés et la position des bagues. Il est possible de mettre un affichage (barre de progression) mais cela ralentit l’exécution, et le programme peut être long. Il est conseillé aussi de tronquer le texte initial à 1000 caractères (ou moins ?) au début si jamais le texte est supérieur à cela. 1000 caractères sont suffisants pour le calcul de l’indice de coïncidence, et cela rendra le calcul plus rapide.

Il nous reste donc à déterminer quelles fiches sont branchées. De la même manière, nous allons utiliser l’indice de coïncidence pour nous rapprocher.

Nous allons calculer pour chaque couple de lettre, l’indice de coïncidence, et nous prendrons les 6 meilleurs (car 6 fiches historiquement).

Les variables que l’on récupère de précédemment :

$cypher
$RotorSetup
$RotorInitPos 
$reflector

Les variables :

$texteADecrypter = Remove-AllButAlphabet $cypher.ToUpper()
$tabconnexion = @()
$tabMax=@{}

Le programme :

# On parcours de A à Y pour la première lettre
for($k = 0; $k -lt $Rotors.'alphabet'.length-1; $k++) {
    $lettre1 = $Rotors.'alphabet'[$k] 
    # On parcours de lettre1+1 à Z pour la deuxième pour ne pas retester qqch qu’on a 
    # déjà tester.
    $tab = @{}
    for ($j = $k+1; $j -lt $Rotors.'alphabet'.length; $j++) {
        $lettre2 = $Rotors.'alphabet'[$j]

        # on calcule l'indice de coïncidence du texte avec notre test 
        # en table de connexion
        $RotorPos = $RotorInitPos.clone()
        $ic = Get-IndiceCoincidence(Get-HistoriqueEnigmaCypher 
        -tabconnexion @("$lettre1$lettre2") -RotorInitPos $RotorPos 
        -RotorSetup $RotorSetup  -reflector $reflector -Message $texteADecrypter)
        $tab.add("$lettre1$lettre2",$ic)
    }
    # On prend l’IC du plus grand et on garde en mémoire la valeur
    # a la fin on prendra les plus grande valeur pour remplir notre tableau de fiche.
    $max = ($tab.GetEnumerator() | Sort-Object -Property Value -Descending)[0]
    $tabMax.add($max.Name, $max.value)
}

# On ajoute à la table de connexion les 6 premières valeurs
$tabMax = $tabMax.GetEnumerator() | Sort-Object -Property Value -Descending
$tabMax[0..5].Name | foreach {$tabconnexion += $_ }
return $tabconnexion

Je n’ai pas rencontré l’erreur mais il est possible que dans les 6 premiers de TabMax des lettres se répètent. Il n’est pas possible que dans la table de connexion on ait deux A par exemple. Il faudra alors regarder plus en détail la table pour ne pas prendre de répétition de lettre.

Conclusion

Les cryptologues anglais et polonais ont travaillés pendant plusieurs années sur la cryptanalyse d’Enigma avant de trouver les bombes cryptographiques qui ont permis de trouver les clés journalière. Et même vers la fin, certaines clés n’ont pas réussi à être cassés, du à peu de message ce jour-ci, à un message sans que le mot probable soit trouvé, etc. Avec les moyens modernes il est possible de décrypter (plus ou moins) rapidement les anciennes versions d’Enigma (câblage des rotors connus) mais il serait très compliqué si le câblage des rotors était inconnu. Mais dans ce cas-ci, il faudrait qu’Alice partage le secret avec Bob et cela représente une faille dans la sécurité.

 

Exercice :

Petit test pour vérifier que vous avec tous compris : Qu’est ce qu’il y a écrit ?

OAZAL NXONL MKNVY XVUQM HWMEO SXDLB TIOWC MTEYV WTGWV IHEAR XKPGI NXQCM MPSJH KDVUO JEZLB MIDBG KXYMD KMGJX NMWRY ZTFGB NRDWV ZEDRQ PKNQP MRPJM VHWQG ZELFG AHZQC GXPQN LOVMJ DNJXZ FQYUS BJAHM SKGRI MQHFH KQICD ZZBBZ PLWPS NOMNL EOBTZ ZGJRK WVBQP OWWAT BNOHP ARLNP JKHKW PMZNK DODSD JCTJV LUSDA KOWLU SKRGK JJOCI HJJTW VALFN SMYOH NVOVR PVYRA PZJBT VLEXS OLSJH CAKNG WOBYM IAFJP AOGUZ IBFSL

5 commentaires on “Cryptanalyse d’Enigma par l’indice de coïncidence

  1. Bonjour, je viens de recoder votre example en python, et je m’aperçois malheureusement que votre méthode est en réalité mathématiquement fausse, à partir du moment ou le message a été chiffré avec le plugboard de connexion ( ce qui est prévu dans une utilisation normale );
    Vous ne pouvez retrouver la position des rotors et du ring uniquement par brut force sur l’indice de coincidence car l’indice de coincidence est dépendant du pluboard

    Exemple :

    Chiffrement du message avec plugboard :

    plaintext a chiffrer = BETWEENSUBTLESHADINGANDTHEABSENCEOFLIGHTLIESTHENUANCEOFIQLUSION avec un ic de ic = 0.06503
    plugboard = AV BS CG DL FU HZ IN KM OW RX
    python pyenigma.py -r I II III -i 1 2 3 -u B -s AAA -t BETWEENSUBTLESHADINGANDTHEABSENCEOFLIGHTLIESTHENUANCEOFIQLUSION -p AV BS CG DL FU HZ IN KM OW RX
    —–> message chiffré = PNOQFGPEKDCMQITLVOZIZGWFRTIDVDCVXVDFAEYEOBBPEEWHRIAXGLGUYQIQZDO

    Déchiffrement du message SANS plugboard ( équivalent à lorsque la methode par force brut tombe sur la bonne valeur ) :

    ciphertext = PNOQFGPEKDCMQITLVOZIZGWFRTIDVDCVXVDFAEYEOBBPEEWHRIAXGLGUYQIQZDO
    python pyenigma.py -r I II III -i 1 2 3 -u B -s AAA -t PNOQFGPEKDCMQITLVOZIZGWFRTIDVDCVXVDFAEYEOBBPEEWHRIAXGLGUYQIQZDO
    —–> message retrouvé = SOZOHNIBCKFBEAZUHACMPDHAGEJORAEYTDFSLCZTPEHBTZQWGSQFLYTZQDZBDMB (avec un ic de 0.0384 )

    On voit bien que l’IC n’est pas identique et celui retrouvé proche d’une valeur aléatoire.. Dans votre code cette clé ne serait même pas remonté car ic < 0.045

    Par contre cela fonctionne si le message a été chiffré SANS plugboard mais bon comme vous l'avez bien expliqué cela réduit considérablement l'espace des clés.

    Merci pour votre retour.

    • Bonjour et Merci pour votre message et votre lecture attentive ! Concernant la cryptanalyse d’enigma par indice de coïncidence, je vous assure que ça fonctionne avec mon code… et mathématiquement !
      Plusieurs raison pour que je puisse affirmer cela sans trop me mouiller :

        Ensuite, ce n’est pas moi qui ai rédigé cet article, mais ma stagiaire de l’époque à qui j’avais donné l‘article précédent sur Enigma… et un texte chiffré (et c’est tout).

      Je vous garantie que sa solution fonctionne : pour l’avoir testée, relue et fait fonctionner à plusieurs reprises sur des textes chiffrés différents. Sinon elle n’aurait pas retrouvé le message source.
      Concernant les bases mathématiques, il faut comprendre qu’Enigma est un substitution poly-alphabétique et que L’indice de coïncidence peut distinguer un texte aléatoire d’un texte clair. Dans note cas, on s’en sert pour déterminer l’ordre des rotor et réduire drastiquement le nombre de possibilités ce qui permet de distinguer une texte chiffré d’un texte « moins chiffré ». Pour simplifier, la variation de l’indice de coïncidence quand le tableau de permutation est juste permet de deviner quel branchement sont fait. La base c’est de calculer la différence de probabilité de probabilité de répétition des lettres dans un texte chiffré par Enigma avec et sans le tableau de permutation. Je ne vais pas tout redétailler ici mais je vous remet quelques sources ci-dessous.

      En conclusion : Je ne doute pas de votre ré-implémentation en Python de mon code (vous partagez les sources ?), par contre le texte de votre exemple me parait bien trop court pour qu’une analyse de coïncidence après chiffrement ressorte un résultat probant.

      Pour finir n’oubliez pas la cryptanalyse n’est pas une « science exacte », même les alliés à la fin de la guerre ne déchiffraient par tout…
      Dans mon cas, le texte que j’avais rédigé à ma stagiaire comportait bien plus de caractères, un vrai petit paragraphe…

      Voilà, j’espère que ça vous aidera, après ça fait bientôt 3 ans que j’ai rédigé l’article, je ne vais pas me replonger dedans plus que ça…

      • merci de m’avoir répondu !

        Pour les futurs lecteurs : mon problème se justifie par le peu d’efficience de cette méthode en réalité qui est expliquée dans « Modern Breaking of Enigma Ciphertexts ».

        « His only success with ten plugs was for a message with a length of 1463 letters  »

        L’indice de coincidence va légerement tendre sur des ciphertext long, uniquement et seulement si il y a sur le plugboard des lettres non interchangés, en l’occurence 6 lettres sur 26 en utilisation normale. Le rapport : longeur / %connexions est déterminant. L’explication est simple : même si l’on connait pas les connexions dans la méthode 1, certaines lettres sont quand même déchiffrés totalement si l’on a la bonne configuration des rotors, et par conséquent l’ic augmente d’autant le texte est long. Mais si il y a 13 connexions donc 13 paires de lettres interchangés, cela ne fonctionne plus du tout.

        Le projet M4 dont le but est de déchiffrer des messages de la WW2 , a utilisé une autre méthode qui fonctionne sur des messages plus court mais demande beaucoup de temps et puissance, ils utilisent du Hillclimbing et Trigramme.
        http://www.bytereef.org/m4_project.html

  2. Bonjour,
    J’essaye de recomposer le code pour déchifrer un message codé par enigma.
    Mais j’ai un message d’erreur car l’objet Get-HistoriqueEnigmaCypher n’existe pas.

    Ou puis-je me le procurer ?

    Bonne soirée,
    Nicolas

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.