Cryptanalyse du chiffre de Vigenère

Le chiffre de Vigenère est une méthode de chiffrement devenue populaire au XVIème siècle et qui est restée inviolable pendant près de 300 ans. Cette méthode de chiffrement est à substitution poly-alphabétique : une même lettre peut être remplacée par des lettres différentes en fonction de sa position dans le texte en clair, ce qui rend l'analyse fréquentielle inefficace.

J'ai créé pour les besoins de l'article une page permettant de chiffrer et déchiffrer du texte en utilisant la méthode de Vigenère.

Fonctionnement du chiffre de Vigenère

Le fonctionnement du chiffre de Vigenère est simpliste : on décide d'une clef constituée de lettre de l'alphabet et on utilise la table suivante :

On utilise alors la première lettre de notre texte à chiffrer pour définir la colonne à utiliser et on descend à la ligne correspondant à la première lettre de notre clef. Puis on continue pour chacune des lettres du texte que l'on souhaite chiffrer en utilisant les lettres de notre clef et en recommençant du début une fois celle-ci épuisé.

Par exemple, si l'on a la phrase Ô de notre bonheur, toi, le fatal emblème et que l'on utilise comme clef le mot PALIMPSESTE, on obtient :

Ô de notre bonheur, toi, le fatal emblème
P AL IMPES TEPALIM  PES  TE PALIM PESTEPA
-----------------------------------------
D dp vaivw uschpcd, isa, ei uaeix tqteibe

On notera que dans la texte chiffré qu'on obtient (D dp vaivw uschpcd, isa, ei uaeix tqteibe) les caractères accentué on été remplacé par leur équivalence non accentuée et qu'on peut toujours voir les espaces dans le texte et la ponctuation. Certaines implémentations du chiffre de Vigenère supprime ces caractères de manière à complexifier la cryptanalyse du message chiffré.

Identifier la longueur de la clef

La première chose à faire pour pouvoir déchiffrer un message chiffré avec Vigenère est d'être en mesure de détecter la longueur de la clef. Deux méthodes en particulier ont été utilisée au cours des siècles et se base sur le fait que la clef de chiffrement soit répétée pour faire la même longueur que le texte à chiffrer.

Si la longueur de la clef non-répétée est identique à la longueur du texte, il devient alors impossible de déchiffrer le texte avec certitude (par exemple le mot chiffré IAUHZ chiffré avec une clef de 5 caractères pourrait être déchiffré en n'importe quel mot de 5 lettres ; pomme, verger, table, etc). Le terme de clef n'est alors plus adapté et on parle de masque jetable ou chiffre de Vernam

À l'inverse, si on utilise une clef composée d'un unique caractères, le chiffrement devient identique à un chiffrement de César.

Méthode de Kasiski

Bien que devenue désuette suite à l'apparition du calcul de l'indice de coïncidence, la méthode de Kasiski reste la première solution historique permettant de déchiffrer un texte chiffré avec Vigenère. Publiée en 1863 par Friedrich Kasiski, cette méthode se base sur la répétition de groupes d'au moins 3 lettres (dit trigrammes) au sein du texte chiffré pour calculer la longueur probable de la clef de chiffrement.

En effet, il est mathématiquements peu probable qu'un groupe de lettres se répètent plusieurs fois au sein d'un texte chiffré, à moins qu'il ne représentent les mêmes lettres du texte en clair chiffrées avec les mêmes lettres de la clef.

Pour illustrer cela prenons l'exemple du texte suivant chiffré avec la clef joue :

Ils sont contraints et forcés
jou ejou ejouejouej ou ejouej
----------------------------
RZM WXBN GXBNVJWHX BS NJXFWIB

Dans le texte chiffré résultant on peut remarquer la répétition du trigramme XBN qui, étant donné la distance séparant chaque occurence, laisse penser que la clef a été répétée entre elles et a donc une longueur de 4 caractères.

Prenons un nouvel exemple avec un texte suffisament long :

Le mérite d’un ouvrage se compose de son utilité ou de son agrément, et même de tous deux, quand il en est susceptible : mais le succès, qui ne prouve pas toujours le mérite, tient souvent davantage au choix du sujet qu’à son exécution, à l’ensemble des objets qu’il présente, qu’à la manière dont ils sont traités. Or ce recueil contenant, comme son titre l’annonce, les lettres de toute une société, il y règne une diversité d’intérêts qui affaiblit celui du lecteur. 

Si on chiffre le texte avec la méthode de Vigenère et la clef liaisons on obtient le lessage chiffré suivant :

WMMMJWGWOCNWMJESRMSMUCZHZAELWGBFFBITAHRGFLEAGBNYCMMMFHRLXMMMVSGGFADMMLDMLVDQDSAWDBSCKQRHEQBTWANADTEAMQPWDYUQFSCJZCVMHOFLZCJWMFFDPUEZAHRLTMNBKCHNPVTLSJNFEIGMSIPZZQXLMGHBPBQCSGBFPFEKMHVGYILMFGREMTELWGBTUMTAIIVDAZEAWBGWBCATSANFTMRMVCALTTSAGBGLCIIBWGBJNMRMUIRAWKOVLSASYBCWEARKZVTQLFRDLVNWFQRDPALMLHEWDLEBGIGWFVEAGQVWEMITQFRYYMUVWRVNPZSQLSQAYBEZWHFIFQANXOVTWQTKWZHAOCLMUHRMC

On peut noter la répétition de plusieurs groupes de 3 caractères ou plus suivants : WMMMJWGWOCNWMJESRMSMUCZHZAELWGBFFBITAHRGFLEAGBNYCMMMFHRLXMMMVSGGFADMMLDMLVDQDSAWDBSCKQRHEQBTWANADTEAMQPWDYUQFSCJZCVMHOFLZCJWMFFDPUEZAHRLTMNBKCHNPVTLSJNFEIGMSIPZZQXLMGHBPBQCSGBFPFEKMHVGYILMFGREMTELWGBTUMTAIIVDAZEAWBGWBCATSANFTMRMVCALTTSAGBGLCIIBWGBJNMRMUIRAWKOVLSASYBCWEARKZVTQLFRDLVNWFQRDPALMLHEWDLEBGIGWFVEAGQVWEMITQFRYYMUVWRVNPZSQLSQAYBEZWHFIFQANXOVTWQTKWZHAOCLMUHRMC

Si l'on présente la répétition de trigrammes sous forme d'un tableau on obtient :

Ici si on prend le premier trigramme, MMM, on peut aisément remarquer que le PGCD de la distance de ses occurences est 8. Par ailleurs, à l'exception du trigramme TSA, tous les autres trigramme ont également une distance qui est un multiple de 8, ce qui permet de déduire que c'est la distance la plus probable de la clef.

Indice de coïncidence

L'indice de coïncidence est une méthode de cryptanalyse inventée en 1920 par William Friedman et qui permet d'identifier à la fois si un message est chiffré via une méthode de substitution mono ou poly-alphabétique ainsi que la longueur probable de la clef.

Le concept est relativement simple ; il s'agit de mesurer la probabilité d'obtenir des lettres identiques en tirant au hasard 2 lettres dans un texte.

Par exemple, dans un texte de longueur ${\textstyle N}$ contenant ${\textstyle n_a}$ fois la lettre ${\textstyle a}$, la probabilité en tirant une lettre au hasard d'obtenir la lettre ${\textstyle a}$ est de :

La probabilité de tirer deux fois d'affilé la lettre ${\textstyle a}$ est alors de :

L'indice de coïncidence est la somme des probabilités de tirer une paire de lettres d'affilé pour l'ensemble des lettres de l'alphabet (où ${\textstyle c}$ représente le nombre de lettres dans l'alphabet) :

La formule de l'indice de coïcidence peut donc être écrite sous la forme suivante :

On peut implémenter cette logique via quelques lignes de Python :

encrypted = "WMMMJWGWOCNWMJESRMSMUCZHZAELWGBFFBITAHRGFLEAGBNYCMMMFHRLXMMMVSGGFADMMLDMLVDQDSAWDBSCKQRHEQBTWANADTEAMQPWDYUQFSCJZCVMHOFLZCJWMFFDPUEZAHRLTMNBKCHNPVTLSJNFEIGMSIPZZQXLMGHBPBQCSGBFPFEKMHVGYILMFGREMTELWGBTUMTAIIVDAZEAWBGWBCATSANFTMRMVCALTTSAGBGLCIIBWGBJNMRMUIRAWKOVLSASYBCWEARKZVTQLFRDLVNWFQRDPALMLHEWDLEBGIGWFVEAGQVWEMITQFRYYMUVWRVNPZSQLSQAYBEZWHFIFQANXOVTWQTKWZHAOCLMUHRMC"

N = len(encrypted)
letter_map = {}

for letter in encrypted:
    if(letter in letter_map):
        letter_map[letter] += 1
    else:
        letter_map[letter] = 1

IC = 0
for n in letter_map.values():
    IC += (n / N) * ((n-1)/(N-1))

print("IC:", IC)

Avec le texte chiffé de la section précédente on trouve l'indice de coïncidence : 0.0448. À titre de comparaison l'indice de coïncidence moyen pour un texte français non chiffré est de 0.0778. La différence s'explique par le fait que le texte soit chiffré avec Vigenère qui est un mode de chiffrage polyalphabétique, ce qui change la fréquence d'apparition des lettres.

La méthode pour trouver la clef est ici de se souvenir que si la clef fait ${\textstyle L}$ caractères de long, alors tous les ${\textstyle L}$ caractères du texte d'origine ont été chiffré avec la même lettre de la clef, ce qui n'est ni plus ni moins qu'un chiffrement de César, ou chiffrement mono-alphabétique.

De fait, si l'on mesure l'indice de coïncidence tous les x caractères, on obtient le tableau suivant représentant l'indice de coïncidence en fonction de la longueur de clef testée :

def compute_ic(encrypted):
    N = len(encrypted)
    letter_map = {}

    for letter in encrypted:
        if(letter in letter_map):
            letter_map[letter] += 1
        else:
            letter_map[letter] = 1

    IC = 0
    for n in letter_map.values():
        IC += (n / N) * ((n-1)/(N-1))
    return IC

encrypted = "WMMMJWGWOCNWMJESRMSMUCZHZAELWGBFFBITAHRGFLEAGBNYCMMMFHRLXMMMVSGGFADMMLDMLVDQDSAWDBSCKQRHEQBTWANADTEAMQPWDYUQFSCJZCVMHOFLZCJWMFFDPUEZAHRLTMNBKCHNPVTLSJNFEIGMSIPZZQXLMGHBPBQCSGBFPFEKMHVGYILMFGREMTELWGBTUMTAIIVDAZEAWBGWBCATSANFTMRMVCALTTSAGBGLCIIBWGBJNMRMUIRAWKOVLSASYBCWEARKZVTQLFRDLVNWFQRDPALMLHEWDLEBGIGWFVEAGQVWEMITQFRYYMUVWRVNPZSQLSQAYBEZWHFIFQANXOVTWQTKWZHAOCLMUHRMC"

for key_length in range(1, 10):
    groups = {}
    for index in range(len(encrypted)):
        group = index % key_length
        if(group in groups):
            groups[group].append(encrypted[index])
        else:
            groups[group] = [encrypted[index]]
    sum = 0
    for group in groups.values():
        sum += compute_ic("".join(group))
    print(key_length, sum / key_length)

L'indice de coïncidence le plus proche de celui de la langue française (en général le plus grand), ici 0.0769 nous donne la longueur de la clef qui est donc de 8 caractères.

Trouver la clef lettre par lettre

Une fois la longueur de la clef calculée, il devient trivial de trouver celle-ci.

En effet ici chacun des caractères de la clef de chiffrement est utilisé pour chiffrer toutes les lettres espacées de 8 caractères (correspondant à la longueur de la clef) :

• la première lettre de la clef a servi à chiffrer les caractères en position 1, 9, 17, 25, etc
• la seconde lettre de la clef a servi à chiffrer les caractères 8, 10, 18, 26, etc
• ... et ainsi de suite pour les autres lettres de la clef

Si l'on sépare en groupe distincts tous les caractères chiffrés par une même lettre de la clef, on peut alors faire une anaylse fréquentielle pour établir la lettre de la clef la plus probable pour ce groupe.

Par exemple si on prend les lettres chiffrées avec la première lettre de la clef on a :

WORZFFCXFLDEDDZZPTPEZPPYMUABTTCNWYZLPDFEYPYFWOC

On peut alors tester l'ensemble des lettres de l'alphabet pour déchiffrer cette chaîne de caractères :

L'indice de proximité indiqué dans la colonne de droite est calculé en comptant l'occurence de chaque caractère et en comparant le résultat à la fréquence d'apparition de chaque lettre dans la langue française. La ligne avec l'indice de proximité le plus faible ; 0.0108 et correspond à la lettre L. C'est donc de manière probable la première lettre de notre mot de passe.

Si l'on fait cela pour trouver l'ensemble des caractères de la clef en utilisant Python on trouve que la clef est LIAISONS et le texte déchiffré est :

LEMERITEDUNOUVRAGESECOMPOSEDESONUTILITEOUDESONAGREMENTETMEMEDETOUSDEUXQUANDILENESTSUSCEPTIBLEMAISLESUCCESQUINEPROUVEPASTOUJOURSLEMERITETIENTSOUVENTDAVANTAGEAUCHOIXDUSUJETQUASONEXECUTIONALENSEMBLEDESOBJETSQUILPRESENTEQUALAMANIEREDONTILSSONTTRAITESORCERECUEILCONTENANTCOMMESONTITRELANNONCELESLETTRESDETOUTEUNESOCIETEILYREGNEUNEDIVERSITEDINTERETSQUIAFFAIBLITCELUIDULECTEUR

letters_frequency_french = {
    "A": 0.0942, "B": 0.0102, "C": 0.0264, "D": 0.0339, "E": 0.1587, "F": 0.0095,
    "G": 0.0104, "H": 0.0077, "I": 0.0841, "J": 0.0089, "K": 0.0001, "L": 0.0534,
    "M": 0.0324, "N": 0.0715, "O": 0.0514, "P": 0.0286, "Q": 0.0106, "R": 0.0646,
    "S": 0.0790, "T": 0.0726, "U": 0.0624, "V": 0.0215, "W": 0.0001, "X": 0.0030,
    "Y": 0.0024, "Z": 0.0032,
}

encrypted = "WMMMJWGWOCNWMJESRMSMUCZHZAELWGBFFBITAHRGFLEAGBNYCMMMFHRLXMMMVSGGFADMMLDMLVDQDSAWDBSCKQRHEQBTWANADTEAMQPWDYUQFSCJZCVMHOFLZCJWMFFDPUEZAHRLTMNBKCHNPVTLSJNFEIGMSIPZZQXLMGHBPBQCSGBFPFEKMHVGYILMFGREMTELWGBTUMTAIIVDAZEAWBGWBCATSANFTMRMVCALTTSAGBGLCIIBWGBJNMRMUIRAWKOVLSASYBCWEARKZVTQLFRDLVNWFQRDPALMLHEWDLEBGIGWFVEAGQVWEMITQFRYYMUVWRVNPZSQLSQAYBEZWHFIFQANXOVTWQTKWZHAOCLMUHRMC"


def frequency_distance(chars):
    N = len(chars)
    letter_map = {}
    distance = 0

    for letter in chars:
        if letter in letter_map:
            letter_map[letter] += 1 / N
        else:
            letter_map[letter] = 1 / N

    for letter in letters_frequency_french:
        if letter not in letter_map:
            letter_map[letter] = 0
        distance += (letter_map[letter] - letters_frequency_french[letter]) ** 2

    return distance


key_length = 8
encrypted_section = {}
for index in range(len(encrypted)):
    section = index % key_length
    if section in encrypted_section:
        encrypted_section[section].append(encrypted[index])
    else:
        encrypted_section[section] = [encrypted[index]]

decrypted_section = []
key = []
for section in encrypted_section:
    min_distance = None
    min_distance_char = None
    min_distance_section = None
    for candidate_letter in range(65, 91):
        computed_group = []
        for char in encrypted_section[section]:
            computed_char = chr(((ord(char) - candidate_letter + 26) % 26) + 65)
            computed_group.append(computed_char)
        distance = frequency_distance(computed_group)
        if not min_distance or distance < min_distance:
            min_distance = distance
            min_distance_char = chr(candidate_letter)
            min_distance_section = computed_group
    key.append(min_distance_char)
    decrypted_section.append(min_distance_section)

decrypted_text = []
for index in range(len(max(decrypted_section, key=len))):
    decrypted = []
    for section in decrypted_section:
        if(index < len(section)):
            decrypted.append(section[index])
    decrypted_text.append("".join(decrypted))

print("Probable key is:", "".join(key))
print("Decrypted text:", "".join(decrypted_text))

Conclusion

Si le chiffre de Vigenère est resté une méthode de chiffrement sure pendant des siècles il est aujourd'hui facile d'en venir à bout dès le moment où le texte chiffré est suffisamment long pour que nos calculs soient statistiquements pertinents.

Bien que de nombreux algorithmes de chiffrement modernes offre une sécurité (presque) infiniment plus élevée, on trouve toujours le chiffre de Vigenère dans de nombreux challenges en ligne, notamment celui du logo de l'ANSSI de 2012 ou encore la sculpture Kryptos.