Enfin la partie la plus intéressante.

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.

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.

Le deuxième problème est dû au tableau de connexions (les fiches). Ceux-ci augmentent de 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.

Pour un texte aléatoire, le calcul devient :

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