TP Cryptographie – Attaque d’un chiffre de Vigenère

Salut à tous,

Le héro du jour : Vigenère
Le héro du jour : Vigenère

Dans la série des TPs en cryptographie, je vais continuer à remonter le temps et les principaux algorithmes de cryptographies historiques.
Dans ce premier TP sur la cryptographie on avait vu comment mener une attaque statistique sur un chiffre de césar. Je n’avais pas souhaité vous montrer le brute-force pour la simple et bonne raison que qu’il me semble vraiment inintéressant à implémenter sur une clé de taille 26 au maximum…

Du coup, aujourd’hui on va passer au chiffre de Vigenère, avec un vrai texte de plusieurs lignes et une clé un peu plus complexe.

Prérequis

Pour que tout fonctionne bien j’ai dû faire quelques modifications sur les fonctions du TPs précédent. Notamment pour la gestion des caractères spéciaux, espaces, et autres ponctuation. Ça s’est traduit par une fonction Remove-AllButAlphabet que je vous donne ci-dessous (et que j’ai lâchement pompé ici).

<#
.SYNOPSIS
Retire tous les caractères autres que a-z dans un texte
.DESCRIPTION
Retire tous les caractères autres que a-z dans un texte, remplace les spéciaux par leur forme "classique" (ç->c ; é->e)
.INPUTS src
Le message à nettoyer
.OUTPUTS
La chaîne sans les spéciaux
.EXAMPLE
PS C:\Mon\Pc> Remove-AllButAlphabet -src 'Chiffre par Vigenère une chaîne en entrée avec la clé fournie'
ChiffreparVigenereunechaineenentreeaveclaclefournie
.AUTHORS
TiTi
.LASTUPDATE
 2015-06-05
#>
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
}

Énoncé du problème de cryptographie:

Mamy Bomb a intercepté le message chiffré suivant :

xnsgwanqahiswypnqtjshqerxjxfyjlhsihgwhrzcxqyrjjjwmrhfmsoqwhasqtzwxhksjhrgteajzchijsyquotusxfjgxjsiqeliwfxarjcwixqvhclzfbahradnfjwxgbjfudejsaqwwxgbjfmhcwqtyyutfrwqaltfrjbuxhwbrqbmjysrqwwhiijontjagjbahhwbyqadxlgnoudxjsrqwwtlgnprviabhfnptfhfyxqtkdwuctjwxjznxhksfglxcwchojvxgbiquhbwhydnhcvczfnotkshawgswrnhrvtjqmmlxcwrjemluxwhguwtkezqshmsanznupagjzjxisbypnspjqjxuhhiinxbhegiwdjliwhvgrohwffucutiineyrjjzjevltmlwqbrjvfjxnwggwxunptvshawgjafjbjudjrwqvhhhssenhhwbhavptfqfzcspjzjexeywhxxnvedixerpedsxqcotkdqgbdxksxmlrcfonfahegiwyxqiwfuqddewihavpthowpnjgwgogbtjwgfxjfdfbfubvpfqjpnvedixoxpeggjenwhmduabdclajyngtdcwpahtfhwqlhjpezuwhhwdwqlhswbybxlclbffdutdzjynqidsxgwvawgfgcutksyxngtjbnqagtxondnspjhtgcgtkrjzxpqjsrqwwhkwjzcltjgjfmhhjsagnvhaujznupdsxcdhywtzebhpkgzdngtfswunqdesyfah

Elle a également réussi à savoir que le message est chiffré via un chiffre de Vigenère… Et c’est déjà pas mal vu son âge !

Cryptanalyse

Étape n°1 – Déterminer la taille de la clé

A – rechercher les séquences répétés

Oui la taille ça compte (On revient souvent à ça dans mes articles…), en fait c’est même la faiblesse du chiffre de Vigenère, en effet si on devine la taille de clé, on sera en mesure d’isoler des blocs dans le message. Sur ces blocs de taille fixe (de la clé), on sait que chaque lettre pour une position donnée sera toujours chiffrée de la même manière dans un autre bloc pour la même position, ce qui ouvre une brèche pour les attaques statistiques. Ensuite, le décalage entre les lettres de la clé étant fixe, si on arrive à deviner une partie de la clé (voir entièrement, si elle est simple) sur un des blocs, on pourra la réutiliser sur tous les blocs du message.

Pour cela on va chercher les répétitions de séquences dans le texte, plus exactement les digrammes ou trigramme (ou plus) dans le texte. Je prends un exemple, les 2 premières lettres du chiffré sont ‘xn’ on va donc chercher l’ensemble des apparitions de ‘XN’ dans le texte.

xnsgwanqahiswypnqtjshqerxjxfyjlhsihgwhrzcxqyrjjjwmrhfmsoqwhasqtzwxhksjhrgteajzchijsyquotusxfjgxjsiqeliwfxarjcwixqvhclzfbahradnfjwxgbjfudejsaqwwxgbjfmhcwqtyyutfrwqaltfrjbuxhwbrqbmjysrqwwhiijontjagjbahhwbyqadxlgnoudxjsrqwwtlgnprviabhfnptfhfyxqtkdwuctjwxjznxhksfglxcwchojvxgbiquhbwhydnhcvczfnotkshawgswrnhrvtjqmmlxcwrjemluxwhguwtkezqshmsanznupagjzjxisbypnspjqjxuhhiinxbhegiwdjliwhvgrohwffucutiineyrjjzjevltmlwqbrjvfjxnwggwxunptvshawgjafjbjudjrwqvhhhssenhhwbhavptfqfzcspjzjexeywhxxnvedixerpedsxqcotkdqgbdxksxmlrcfonfahegiwyxqiwfuqddewihavpthowpnjgwgogbtjwgfxjfdfbfubvpfqjpnvedixoxpeggjenwhmduabdclajyngtdcwpahtfhwqlhjpezuwhhwdwqlhswbybxlclbffdutdzjynqidsxgwvawgfgcutksyxngtjbnqagtxondnspjhtgcgtkrjzxpqjsrqwwhkwjzcltjgjfmhhjsagnvhaujznupdsxcdhywtzebhpkgzdngtfswunqdesyfah

Du coup, j’ai rapidement implémenté une double boucle pour rechercher le nombre d’apparition de séquences d’une longueur maximum données dans un texte et me renvoyer leurs listes triées par le nombre d’apparitions. À l’époque de l’utilisation de Vigenère, ça n’existait pas : il fallait donc se « palucher »  la recherche des séquences fréquentes dans le texte, essayez un peu pour voir !

Deux remarques :

  • La fonction ci-dessous ne s’occupe pas des problématiques de complexité et de vitesse, notamment si vous chercher des séquences de 42 de long. Mais, elle est simple à comprendre si vous avez suivi le TP sur les Regex et que vous voyez à quoi ressemble une table de hash ; et pour aller plus en avant :
  • sur un texte très long je vous recommande de passer à des algorithmes plus sérieux, genre : « Boyer-Moore« , « Knuth–Morris–Pratt« , ou encore « Aho-Corasick » et ‘Karp-Rabin‘.

Du coup la fonction :

<#
.SYNOPSIS
Cherche les N-grammes dans un texte en entrée
.DESCRIPTION
Retourne le nombre d’occurrences des séquences de caractères jusqu’à un taille demandé en entrée dans le texte en entrée.
.INPUTS text
Le message à analyser
.INPUTS MaxSeq
La taille maximum des séquences à chercher, au minimum 2, au maximum MaxSeq = text.length / 2.
.OUTPUTS
Une table de hash séquence->nb_occurences
.EXAMPLE
C:\PS> Search-Ngrammes -text $chiffre -MaxSeq 5
.AUTHORS
TiTI
.LASTUPDATE
 2015-06-05
#>
Function Search-Ngrammes {
    param (
        [Parameter(ValueFromPipeline=$True ,Mandatory=$True,HelpMessage="Text à analyser")] [String] $text,
        [Parameter(ValueFromPipeline=$True ,Mandatory=$True,HelpMessage="Max sequence Search")] [String] $MaxSeq = 5
    )
    #on va travailler avec 2 compteurs pour se déplacer dans le string
    #et utiliser une table de hash séquence->nb_occurence(s) pour les résultats.
    $ResTable = @{}
    for($i=0; $i -lt (($text.Length)-$MaxSeq); $i++){
        for($j=2; $j -le $MaxSeq; $j++){
            
            #On extrait la séquence recherchée Substring(indice de début, taille)
            $Seq = $text.Substring($i,$j)
            
            #sauf si on a déjà compter les occurences de notre séquence avant, le cas échéant on saute simplement la séquence
            if(-not $ResTable.ContainsKey($Seq)){
                #Sinon, on utilise les Regex pour trouver les occurrences de la séquence dans le texte :    
                $matchs = [regex]::Matches($text,$Seq)
                #si on a des correspondances    
                if($matchs.count -ne 0){
                    $ResTable.Add($Seq,$matchs.count)
                }
            #et on passe à la séquence de taille j+1.
            }
        }
    }
    
    #On retourne notre résultat
    # pour le trier ".GetEnumerator() | Sort-Object -Property Value,Name -Descending" 

    return $ResTable.GetEnumerator() | Sort-Object -Property Value,Name -Descending
}

Fonction qu’on va donc exécuter sur notre chaîne :

PS C:\Mon\Pc> $res = Search-Ngrammes -text $chiffre -MaxSeq 5

Alors du coup, toutes les séquences de 2 à 5 caractères dans le texte (y compris ceux qui n’apparaissent qu’une fois et qui ne nous intéresse pas) ; le nombre de résultats est « un peu gros », soit :

PS C:\Mon\Pc> $res.count
2523

Donc on va filtrer un peu tout ça pour se permettre de garder que les plus courantes :

#j'ai empiriquement décidé que c'était 6 car ça nous retourne 14 séquences. 
PS C:\Mon\Pc> $res | Where-Object {$_.value -ge 6} 
Name                           Value
----                           -----
wh                             10
jz                             8
tj                             7
rj                             7
js                             7
wq                             6
wg                             6
tk                             6
tf                             6
hw                             6
hh                             6
ha                             6
gt                             6
ah                             6

# Sinon on peut aussi choisir de prendre que les 10 premiers arbitrairement : 
PS C:\Mon\Pc>$res[0..9]
Name                           Value
----                           -----
wh                             10
jz                             8
tj                             7
rj                             7
js                             7
wq                             6
wg                             6
tk                             6
tf                             6
hw                             6
# => C'est vous qui voyez!
# Remarque : Notez aussi que on ne s'est pas trompé pour le digramme 'WM' qui apparait bien 4 fois.
PS C:\Users\SAURON> $res | Where-Object {$_.name -eq 'xn'}
Name                           Value
----                           -----
xm                             4

Bon, on est content : on a nos séquences les plus fréquentes dans le texte. Et maintenant on en fait quoi ?

B – Compter les « espacements » entre les séquences

En fait ces séquences redondantes peuvent correspondre à 2 choses :

  1. Cas n°1 : La même séquence de N-lettres du texte clair a été chiffrée par le même morceau de la clé, à deux endroits différents dans le texte ; ou bien
  2. Cas n°2 : deux séquences de lettres complètement différentes du texte clair, auraient aléatoirement terminées chiffrées par la même suite dans le texte protégé.

Vous vous doutez bien que le cas n°1 est clairement le plus probable, surtout dans un texte de cette longueur.

Mais ça signifie quoi ? En fait cela veut dire que l’écart entre nos lettres dans notre message chiffré est un multiple de la longueur de notre clé. On va logiquement exploiter cette faiblesse.

Prenons l’exemple ci-dessous pour illustrer avant d’implémenter ça :

u n t o t o r e n t r e s u r u n c o c o
m a c l e m a c l e m a c l e m a c l e m
-----------------------------------------Vigenère
h o w a y b s h z y e f v g w h o f a h b

Ici, on voit que ‘un’ a été protégé par ‘ma’ 2 fois dans le message. Et en comptant l’écart entre nos 2 séquences on trouve 15 caractères. Vous noterez que 15 est un multiple de 5 qui est bien la longueur de ‘macle’ (qui est ma clé, pour ceux qui n’auraient pas compris, hein), c’est beau quand ça fonctionne, non ?

Du coup dans notre message, pour chacun de nos digrammes les plus courants dans le texte, on va compter la taille des écartements. Les plus assidus auront noté que la classe « regex » du .NET utilisée tout à l’heure dans Search-Ngrammes nous indiquait gentiment les index de chaque séquence dans le texte traité. J’ai donc implémenté une jolie fonction utilisant ça, qui prend en entrée nos di/tri-grammes et nous renvois les distances d’écarts par rapport à la première occurrence de la séquence dans le texte :

<#.SYNOPSIS
Retourne les valeurs d’écart entre les n-séquences les plus fréquentes trouvées dans un chiffré.
.DESCRIPTION
Cherche les séquences de longueur 1 à 5 dans le texte, sélectionne les N plus fréquentes.
Calculs les écarts entre la première séquence et toutes les suivantes (y compris entre elles) dans le texte et retourne leur position dans une table de hash du type 'seq'->@(écart1,ecart2,...,ecartN-1).
.INPUTS text
Le message sur lequel on réalise l’analyse.
.INPUTS n
Le nombre de séquence les plus fréquentes à prendre en compte dans le calcul
.OUTPUTS
La table de hash 'seq'->@(écart1,ecart2,...,ecartN-1)
.EXAMPLE
C:\PS> $stat =  Get-SequenceGapLength -text $chiffre -n 3
.AUTHORS
TiTi
.LASTUPDATE
 2015-06-02
#>
Function Get-SequenceGapLength {
     param (
        [Parameter(ValueFromPipeline=$True ,Mandatory=$True,HelpMessage="Texte à analyser")] [String] $text,
         [Parameter(ValueFromPipeline=$True ,Mandatory=$True,HelpMessage="Nombre de séquence à prendre en compte, 3 par défaut")] [int] $n = 2
    )
    #On récupère les statistiques des séquences
    $stat = Search-Ngrammes -text $text -MaxSeq 5
    #On prend les N plus courantes/probables
    $PrivilegeSequence = $stat[0..($n-1)]

    $TabEcart = @{}
    #Pour chaque séquence à traiter
    foreach($seq in $PrivilegeSequence.Name){
        #On ajoute un clé $seq' dans notre objet en sortie
        $TabEcart.Add($seq,@())
        #On cherche les occurrences de la séquence
        $matchs = [regex]::Matches($text,$seq)
        #Pour chacune d'entre elles
        for($i=0; $i -lt ($matchs.count)-1; $i++){
            #on compare avec chacune des suivantes 
            for($j=$i+1; $j -lt $matchs.count; $j++){
                #et on calcule l'écart entre qu'on ajoute dans un tableau sous la clé associé à '$seq'
                $TabEcart.$seq += @(($matchs[$j].Index) - ($matchs[$i].Index))
            }
        }
    }
    return $TabEcart
}

Et si je teste sur mon chiffré :

PS C:\Mon\Pc>  Get-SequenceGapLength -text $chiffre -n 3
Name                           Value
----                           -----
tj                             {174, 230, 287, 531...}
jz                             {175, 266, 320, 390...}
wh                             {21, 148, 241, 284...}

Je vous laisse vérifier par vous-même que cela correspond, par exemple : pour ‘tj’ entre la n°1 et la n°2 ça se passe plutôt bien dans un Notepad++ vu que ça fait 194-20.

Et sans transition, passons à la suite.

C – les diviseurs possible des écarts entre les séquences.

J’ai expliqué tout à l’heure que l’écart entre nos séquences correspond « probablement » à un multiple de la taille de notre clé. Donc pour chaque écart entre une même séquence, il faut chercher tous les diviseurs possibles de cette distance, soit toutes les divisions entières entre 2 et notre distance, dont le reste est égal à zéro.
On va ensuite chercher l’écart qui nous donne le plus de correspondance entre nos blocs de lettres, en espérant que ce soit le bon.

Dans la mesure où le texte est assez long, on a de bonne chance d’avoir des collisions et que certains écarts ne correspondent pas à la longueur de la clé. D’où cette approche statistique, sur un texte plus court, on pourrait avoir une seule et unique correspondance sans problème.

Bref, comme d’habitude, j’ai implémenté une fonction pour ça :

<#
.SYNOPSIS
Retourne la taille probable d’une clé sur un texte chiffré avec Vigenère
.DESCRIPTION
Cherche les séquences de longueur 1 à 5 dans le texte, sélectionne les 5 plus fréquentes. Calculs les écarts sur ces dernieres et retourne tous les multiples possibles de ces écarts.
.INPUTS text
Le message sur lequel on réalise l’analyse.
.OUTPUTS
Une taille probable de clé ;
.EXAMPLE
C:\PS> $stat = Get-VigenereKeyLength -text $chiffre
.AUTHORS
TiTi
.LASTUPDATE
 2015-06-30
#>
Function Get-VigenereKeyLength {
     param (
        [Parameter(ValueFromPipeline=$True ,Mandatory=$True,HelpMessage="Texte à analyser")] [String] $text
    )
    $PossibleDividers = @{}
    $TabEcart =  Get-SequenceGapLength -text $text -n 5
    foreach($seq in $TabEcart.Keys){
        foreach($ecart in $TabEcart.$seq){
            for($i=2;$i -lt [System.Math]::Round($ecart/2) ; $i++){
                if(($ecart%$i) -eq 0){
                    if($PossibleDividers.ContainsKey("$i")){
                        $PossibleDividers."$i"+=1 
                    }else{
                        $PossibleDividers.Add("$i",1)
                    }
                }
            }
        }
    }
    return $PossibleDividers.GetEnumerator() | Sort-Object -Descending -Property Value | where-object {$_.value -gt 10}
}

Et si on test sur notre chiffré, on obtient ça qui compte les multiples entiers possibles pour la distance entre 2 de nos séquences :

PS C:\Mon\Pc> Get-VigenereKeyLength -text $chiffre
Name                           Value
----                           -----
2                              66
7                              58
3                              46
4                              31
5                              30
14                             27
9                              21
6                              18
10                             17
8                              16
11                             13
21                             13
28                             12
17                             12

D – Interprétation des résultats

Et si on test sur notre chiffré, on obtient ça :

  • 2 parait un peu court pour faire une clé, on va l’éliminer d’office (sachant qu’en plus il a matché pour tout écart pair trouvé);
  • 7 remonte ensuite le plus comme longueur de clé probable ensuite ;

Dans les valeurs restantes,

  • Je passe sur 4 et 3 qui semble un peu juste comme 2 ;
  • 5 pourrait passer, mais reste moins volumineux que 7 ;
  • Ensuite viens 14 (tient c’est un multiple de 7 : donc en fait pour 7 ça pourrait être 58+27) ; et
  • On tombe plus loin sur 21 et 28 (tient c’est encore des multiples de 7).

Bref, je ne sais pas vous… mais moi, je trouve que 7 est un bon candidat pour la taille de la clé de notre chiffre de Vigenère. On va continuer avec.

Remarque sur le calcul taille de la clé

Il existe d’autres méthodes pour trouver la taille d’une clé de Vigenère : grâce à l’indice de coïncidence du texte, qu’on peut facilement calculer. Cet indice est connu pour une langue donnée, mais aussi pour des lettres tirées aléatoirement. En calculant cet indice pour une taille de clé donnée jusqu’à obtenir une valeur proche de celle de la langue cible. Je vous laisse cette partie en exercice pour l’instant, mais j’y reviendrai dans un autre TP, plus tard.

Casser la ... clé
Casser la … clé

Étape n°2 – Casser la clé

A – Isoler ensemble les éléments protégés par la même lettre de la clé

À ce moment, on sait que la taille de notre clé est de 7 lettres : ce qui signifie que les lettres dont la position est un multiple de 7 sont toutes chiffrées avec la 1ère lettre de la clé. On va donc chercher à séparer notre message en 7 blocs pour avoir ensemble toutes les lettres chiffrées par la un même lettre de la clé.

C’est assez simple à implémenter en jouant avec le modulo et son reste, dans la fonction ci-dessous :

<#
.SYNOPSIS
Récupère les caractères chiffrés par un même élément de la clé de Vigenère dans un texte
.DESCRIPTION
Récupère tous les éléments à la position multiple de n. utiliser r pour décaler "d’un cran"
.INPUTS text
Le message sur lequel on réalise l’analyse.
.INPUTS n
Le modulo sur lequel faire le calcul
.INPUTS r
Le reste du modulo pour se déplacer dans les sous-ensembles de taille n.
.OUTPUTS
Tous les éléments aux positions indiquées
.EXAMPLE
C:\PS> Get-VigenereKeyPosText -text 'abcdefgh' -n 7 -r 0
ah
.AUTHORS
TiTi
.LASTUPDATE
 2015-06-05
#>
Function Get-VigenereKeyPosText {
     param (
        [Parameter(ValueFromPipeline=$True ,Mandatory=$True,HelpMessage="Texte à analyser")] [String] $text,
        [Parameter(ValueFromPipeline=$True ,Mandatory=$True,HelpMessage="les caractères modulo n qu'on veut récuperer")] [int] $n,
        [Parameter(ValueFromPipeline=$True ,Mandatory=$True,HelpMessage="la position dans le modulo")] [int] $r
    )
    $outsubset = ''
    for($i=0; $i -lt $text.Length ; $i++){
        if(($i%$n) -eq $r){
            $outsubset += [string]$text[$i]
        }
    }
    
    return $outsubset
}

On exécute cette fonction une fois pour chaque position dans la longueur de la clé :

$tab = @()
for($i=0; $i -lt 7; $i++){
    $tab+=Get-VigenereKeyPosText -text $chiffre -n 7 -r $i
}

Ce qui nous donne le tableau suivant :

0 - xqpqygqmqzhzqfqaqbffqfyqbqqobqoqpfyuzgoqdfahmegqzzpxxdgueeqxuabqeazexeqgmfyqapgxupoeaypquqbfyggxqdgzqzfgzceduf
1 - nanejwyrwwrcujervajuwmyaubwnaauwrnxcnljunnwrlmusnjnubjrcyvbnnwjvnvcxnrcblaxdvnbjbnxnbnalwlxdnwcnancxwcmnndbnna
2 - shqrlhrhhxghogljhhwdwhulxmwthddwvpqtxxvhhogvxlwhuxshhlourlrwpguhhpsevpodrhqdpjtfvvpwdghhhhluqvuggsgpwlhvuhhgqh
3 - gitxhrjfahtitxiccrxexctthjhjhxxtittjhcxbctstcutmpipheihtjtjgtjdhhtpyeetxceietgjdpeehcttjhsctiatttptqhthhpyptd
4 - wsjjszjmskejujwwlagjgwffwyiawljlafkwkwgwvkwjwxksasjigwwijmvgvajhwfjwddkkfgwwhwwffdgmldfpwwlddwkjxjkjkjjadwkfe
5 - awsxicjsqsasssfizdbsbqrrbsigbgsgbhdxscbhcsrqrweagbqiihfizlfwsfrsbqzhisdsoifioggbqigdachedbbzsgsbohrswgsustgss
6 - nyhfhxwotjjyxixxfnjajtwjrrjjynrnhfwjfhiyzhnmjhznjyjnwvfnjwjxhjwshfjxxxqxnwuhwoffjxjujwwzwyfjxfynntjrjjajxzzwy

Dont je vous laisse vérifier la bonne correspondance.

B – Analyse fréquentielle pour chaque lettre de la clé

Analyse fréquencielle
Analyse fréquentielle

À ce moment, on sait que chaque ligne a été chiffrée comme pour un chiffre de césar, c’est-à-dire avec le même décalage pour tous les caractères de chaque ligne. Et ça, on a vu dans le TP sur le chiffre de César que c’est vulnérable à une attaque par analyse des fréquences, j’ai repris la fonction Get-StringCharStats du TP précédent, et je l’ai testée sur la première ligne :

Get-StringCharStats -Message $tab[0]
Name                           Value
----                           -----
q                              0,2090
f                              0,0909

 

Qui nous indique que le caractère le plus fréquent est le ‘a’, qui d’après la table des fréquences dans la langue française doit être le ‘e’. Si le ‘e’ devient un ‘q’, cela signifie que l’on a l’équation suivante à résoudre pour connaître le décalage créé par la première lettre de notre clé, soit :

'e' + n = 'q' soit n = 'q' - 'e'

En PowerShell ça donnera :

n = [int][char]'q' - [int][char]'e'

On trouve n = 12. Cela signifie que la première lettre de notre clé est celle qui génère un décalage de 12 lettres dans l’alphabet, soit la douzième lettre de l’alphabet le ‘L’, ce qu’on peut vérifier facilement

[char]([int][char]'a'-1 + 12) 
#Ici, on case un '-1' car la lettre a décale de 1 dans Vigenère et non pas de 0 comme en informatique

Et du coup on a trouvé la première lettre de notre clé !

On recommence sur la n°2 et ainsi de suite, du coup j’ai automatisé le truc :

$clef = ''
for($i=0;$i -lt 7;$i++){
    $mostfreq = (Get-StringCharStats -Message $tab[$i])[0]
    $decalage = ([int][char] $mostfreq.Key)-([int][char]'e')
    $clef += [String][char]([int][char]'a'-1 + $decalage)
}
Write-host -ForegroundColor Red "$clef"
licorne

Et on a trouvé notre clé !

Étape n°3 – Déchiffrer le message

A – Écrire la fonction de déchiffrement

Je récapitule, on a trouvé notre clé : ‘licorne’ pour lemessage chiffré. Il y a plus qu’à reprendre la fonction de chiffrement et d’en faire une variante pour le déchiffrement pour récupérer le message :

<#
.SYNOPSIS
Chiffre par Vigenère une chaîne en entrée avec la clé fournie
.DESCRIPTION
Chiffre par Vigenère une chaîne en entrée avec la clé fournie
.INPUTS Message
Le message à chiffrer
.INPUTS clé
Le décalage ou clé de l’algorithme
.INPUTS DeCypher
Effectue l’opération inverse : le déchiffrement
.OUTPUTS
La chaine chiffrée
.EXAMPLE
S C:\> Get-VigenereCypher -message $chiffre -cle 'licorne' -DeCypher
lepremieretaitdenerecevoir...
.AUTHORS
TiTi
.LASTUPDATE
 2015-05-28
#>
function Get-VigenereCypher {
    param (
        [Parameter(ValueFromPipeline=$True ,Mandatory=$True,HelpMessage="Message à chiffrer")] [String] $message,
        [Parameter(ValueFromPipeline=$False,Mandatory=$True,HelpMessage="Clé pour chiffrer")] [String] $cle,
        [Parameter(ValueFromPipeline=$False,Mandatory=$false,HelpMessage="mode déchiffrement")] [Switch] $DeCypher=$false
    )
    $message = $message.ToUpper()
    $cle = $cle.ToUpper()
    $chiffre = ''
    $j = 0
    for ($i = 0; $i -lt $message.length; $i++) {
        if($message[$i] -ne ' ') {
            if(-not $DeCypher){
                $chiffre += [char](([int][char]$message[$i] -[int][char]'A' + [int][char]$cle[$j]-[int][char]'A'+1)%26 + [int][char]'A')
            }else{
                $decalage = ([int][char]$message[$i] -[int][char]'A') - ([int][char]$cle[$j] - [int][char]'A'+1)
                if($decalage -lt 0){
                    $chiffre += [char]([int][char]'Z'+$decalage+1)
                }else{
                    $chiffre += [char]([int][char]'A'+$decalage)
                }
            }
        } else {
            $chiffre += ' '
        }
        $j++ 
        if ($j -eq $cle.length) {
            $j = 0
        }
    }
    return $chiffre.toLower()
}

À part mon padding un peu naze pour compte le négatif/positif quand on fait un tour dans l’alphabet en négatif au déchiffrement (où il faut refaire passer A de +1 à -1), dont je ne suis pas super satisfait (mais il est tard, là). La fonction fait parfaitement le boulot :

PS C:\Mon\Pc> Get-VigenereCypher -message $chiffre -cle 'licorne' -DeCypher
lepremieretaitdenerecevoirjamaisaucunechosepourvraiequejenelaconnusseevidemmentetretellecestadiredevitersoigneusementlaprecipitationetlapreventionetdenecomprendreriendeplusenmesjugementsquecequisepresenteraitsiclairementetsidistinctementamonespritquejeneusseaucuneoccasiondelemettreendouteleseconddediviserchacunedesdifficultesquejexamineraisenautantdeparcellesquilsepourraitetquilseraitrequispourlesmieuxresoudreletroisiemedeconduireparordremespenseesencommencantparlesobjetslesplussimplesetlesplusaisesaconnaitrepourmonterpeuapeucommepardegresjusquesalaconnaissancedespluscomposesetsupposantmemedelordreentreceuxquineseprecedentpointnaturellementlesunslesautresetledernierdefairepartoutdesdenombrementssientiersetdesrevuessigeneralesquejefusseassuredenerienomettre

Et ça marche !

B – Recomposer le texte “à la main”

Je vous laisse détacher les morceaux vu que les espaces ne sont pas présents dans le message source et à la fin ça nous donne un extrait du discours de la méthode de Descartes, considéré par beaucoup comme la première définition de l’algorithmique :

René Descartes
René Descartes
Le premier était de ne recevoir jamais aucune chose pour vraie, que je ne la connusse évidemment être telle : c’est-à-dire, d’éviter soigneusement la précipitation et la prévention; etde ne comprendre rien de plus en mes jugements, que ce qui se présenterait si clairement et si distinctement à mon esprit, que je n’eusse aucune occasion de le mettre en doute.
Le second, de diviser chacune des difficultés que j’examinerais, en autant de par-celles qu’il se pourrait, et qu’il serait requis pour les mieux résoudre.
Le troisième, de conduire par ordre mes pensées, en commençant par les objets les plus simples et les plus aisés à connaître, pour monter peu à peu, comme par degrés, jusques à la connaissance des plus composés; et supposant même de l’ordre entre ceux qui ne se précèdent point naturellement les uns les autres.
Et le dernier, de faire partout des dénombrements si entiers, et des revues si générales, que je fusse assuré de ne rien omettre.

C’est tout, et déjà pas mal pour un début en Cryptographie, j’espère que vous avez réussi à arriver jusqu’ici n’hésitez pas à laisser vos questions dans les commentaires !

Fin

 

Laisser un commentaire

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