Cryptanalyse du chiffre de Vigenère

Le chiffre de Vigenère est un chiffrement basé sur une substitution polyalphabétique : une lettre de l'alphabet dans le texte en clair peut être chiffrée de plusieurs manières. Ce principe remonte à des travaux antécédents à ceux de Blaise de Vigenère au XVI^e siècle mais Vigenère fut l'un des premiers à présenter ce type de chiffrement sous la forme d'une table avec la présence d'une clé secrète. Le chiffre de Vigenère restera inviolable pendant plusieurs siècles.

On pense que Charles Babbage effectua la première véritable cryptanalyse du chiffre de Vigenère vers 1854. En parallèle, un officier prussien à la retraite, Friedrich Wilhelm Kasiski parvint au même résultat sans avoir eu vent des travaux de Babbage puisque ce dernier ne les avait pas publiés. Kasiski rédigea Die Geheimschriften und die Dechiffrierkunst en 1863 où il présentait le test qui allait porter son nom : le test de Kasiski qui permet d'estimer la taille de la clé.

Première étape : déterminer la longueur de la clé

Il consiste à chercher des répétitions dans le texte chiffré. Considérons par exemple le mot-clé « ABCD » qui sert à chiffrer « MESSAGER TRES MESQUIN MESOPOTAMIEN ».

Clé répétée

A

B

C

D

A

B

C

D

A

B

C

D

A

B

C

D

A

B

C

D

A

B

C

D

A

B

C

D

A

B

C

Texte en clair

M

E

S

S

A

G

E

R

T

R

E

S

M

E

S

Q

U

I

N

M

E

S

O

P

O

T

A

M

I

E

N

Texte chiffré

M

F

U

V

A

H

G

U

T

S

G

V

M

F

U

T

U

J

P

P

E

T

Q

S

O

U

C

P

I

F

P

Dans l'exemple ci-dessus, le trigramme « MES » est chiffré en « MFU » deux fois et « PET » une fois. Babbage et Kasiski comprirent que des répétitions de cette sorte leur offraient la prise dont ils avaient besoin pour attaquer Vigenère.

Ces séquences redondantes peuvent indiquer deux caractéristiques :

• soit la même séquence de lettres du texte clair a été chiffrée avec la même partie de la clef.
• soit deux suites de lettres différentes dans le texte clair auraient (possibilité faible) par pure coïncidence engendré la même suite dans le texte chiffré.

Le premier cas étant le plus probable, on calcule le nombre de lettres entre deux séquences identiques. Dans notre cas, il y a 12 lettres entre les deux « MFU », on en déduit que la longueur de la clé est un diviseur de 12 (sinon la clé et les deux « MES » ne seraient pas alignés). La clé peut donc posséder soit 12, 6, 4, 3 ou 2 lettres (avec une lettre, nous aurions un chiffrement monoalphabétique facilement cassé avec une analyse fréquentielle). Avec un texte plus long, on découvrirait d'autres séquences qui permettraient d'affiner le résultat et réduire la taille de la clé à une ou deux possibilités.

Exemple sur un texte plus long

Soit un texte chiffré de plusieurs centaines de caractères avec une clé de longueur inconnue. Ce texte paraît a priori aléatoire et pourtant il contient des redondances intéressantes.

---

KQOWEFVJPUJUUNUKGLMEKJINMWUXFQMKJBGWRLFNFGHUDWUUMBSVLPS
NCMUEKQCTESWREEKOYSSIWCTUAXYOTAPXPLWPNTCGOJBGFQHTDWXIZA
YGFFNSXCSEYNCTSSPNTUJNYTGGWZGRWUUNEJUUQEAPYMEKQHUIDUXFP
GUYTSMTFFSHNUOCZGMRUWEYTRGKMEEDCTVRECFBDJQCUSWVBPNLGOYL
SKMTEFVJJTWWMFMWPNMEMTMHRSPXFSSKFFSTNUOCZGMDOEOYEEKCPJR
GPMURSKHFRSEIUEVGOYCWXIZAYGOSAANYDOEOYJLWUNHAMEBFELXYVL
WNOJNSIOFRWUCCESWKVIDGMUCGOCRUWGNMAAFFVNSIUDEKQHCEUCPFC
MPVSUDGAVEMNYMAMVLFMAOYFNTQCUAFVFJNXKLNEIWCWODCCULWRIFT
WGMUSWOVMATNYBUHTCOCWFYTNMGYTQMKBBNLGFBTWOJFTWGNTEJKNEE
DCLDHWTYYIDGMVRDGMPLSWGJLAGOEEKJOFEKUYTAANYTDWIYBNLNYNP
WEBFNLFYNAJEBFR

---

KQOWEFVJPUJUUNUKGLMEKJINMWUXFQMKJBGWRLFNFGHUDWUUMBSVLPS
NCMUEKQCTESWREEKOYSSIWCTUAXYOTAPXPLWPNTCGOJBGFQHTDWXIZA
YGFFNSXCSEYNCTSSPNTUJNYTGGWZGRWUUNEJUUQEAPYMEKQHUIDUXFP
GUYTSMTFFSHNUOCZGMRUWEYTRGKMEEDCTVRECFBDJQCUSWVBPNLGOYL
SKMTEFVJJTWWMFMWPNMEMTMHRSPXFSSKFFSTNUOCZGMDOEOYEEKCPJR
GPMURSKHFRSEIUEVGOYCWXIZAYGOSAANYDOEOYJLWUNHAMEBFELXYVL
WNOJNSIOFRWUCCESWKVIDGMUCGOCRUWGNMAAFFVNSIUDEKQHCEUCPFC
MPVSUDGAVEMNYMAMVLFMAOYFNTQCUAFVFJNXKLNEIWCWODCCULWRIFT
WGMUSWOVMATNYBUHTCOCWFYTNMGYTQMKBBNLGFBTWOJFTWGNTEJKNEE
DCLDHWTYYIDGMVRDGMPLSWGJLAGOEEKJOFEKUYTAANYTDWIYBNLNYNP
WEBFNLFYNAJEBFR

---

On regarde ensuite la distance entre les répétitions. On cherche les facteurs pour chaque paire :

		Longueurs de clef possibles (diviseurs de la distance)
Séquence répétée	Distance entre les répetitions	2	3	5	19
WUU	95			x	x
EEK	200	x		x
WXIZAYG	190	x		x	x
NUOCZGM	80	x		x
DOEOY	45		x	x
GMU	90	x	x	x

Les facteurs premiers du nombre de caractères entre deux débuts de séquences figurent dans le tableau (ex. 95 = 5 x 19). Il apparaît dans le tableau que toutes les périodes sont divisibles par 5. Tout se cale parfaitement sur un mot-clef de 5 lettres. Une autre méthode pour trouver la longueur de la clef utilise l'indice de coïncidence.

Une fois la longueur de la clef trouvée, on peut découper le texte en autant de sous-textes, 5 dans le cas présent, chacun d'entre eux étant obtenu par un même chiffre de César, et peut être décrypté par analyse de fréquences. Chaque texte k étant la suite des lettres qui sont à la position k modulo 5 La comparaison entre les distributions des lettres dans chacun des sous-textes (on peut utiliser un indice de coïncidence défini entre deux distributions), permet de découvrir les décalages entre les lettres du mot clef, et facilite la résolution.

Programme informatique de cryptanalyse

Le programme suivant en Python calcule la longueur de la clef utilisée en cherchant à maximiser l'indice de coïncidence.

#frequence des lettres
frequence_theorique = [8.4, 1.06, 3.03, 4.18, 17.26, 1.12, 1.27, 0.92, 7.34, 0.31, 0.05, 6.01, 2.96, 7.13, 5.26, 3.01,0.99, 6.55, 8.08, 7.07, 5.74, 1.32, 0.04, 0.45, 0.3, 0.12]

#fonction decaler = chiffre de cesar de clef d
decaler = lambda code, d : ''.join([chr((ord(lettre)- 65 + d) % 26 + 65)if lettre.isalpha() else lettre for lettre in code])


def calculer_IC (code, pas):
    """
        calcule l'indice de coincidence de 'code'
        en decoupant'code' en 'pas' sous-textes
    """
    somme = lambda nb : nb * (nb - 1)
    IC = []
    for i in range (pas):
        nb_lettre = [0] * 26
        for compteur, lettre in enumerate(code [i::pas]):
            nb_lettre [ord(lettre)- 65] += 1
        IC.append(sum(map(somme, nb_lettre)) / float(compteur * (compteur + 1)))
    return sum(IC) / float(len(IC))

def calculer_decalage (code):
    """
        casse un chiffre de cesar en renvoyant la clef utilisee
    """
    longueur = float(len(code))
    m = [0, 100]
    for i in range (26):
        diff = sum(abs(b - frequence_theorique[a]) for a, b in enumerate([100 * lettre / longueur for lettre in map(code.count, "ABCDEFGHIJKLMNOPQRSTUVWXYZ")]))
        if diff < m[1]: m = i, diff
        code = decaler (code, 1)
    return m [0]

def recoller (liste):
    """
        recolle les sous-textes
    """
    f = ''
    try :
        for i in range (len(liste[0])):
            for z in liste: f += z[i]
    except : pass
    return f

def decrypter (code, plancher = 0.065):
    code = code.upper()
    pas = 1
    while calculer_IC (code, pas) < plancher :
        pas += 1
    code_fractionne = [code[dep::pas] for dep in range (pas)]
    code_fractionne_decode = [decaler (bout, calculer_decalage(bout)) for bout in code_fractionne]
    return recoller (code_fractionne_decode)

Chiffre de Vernam

La cryptanalyse du chiffre de Vigenère par la méthode de Kasiski ou par d'autres méthodes comme celles de l'indice de coïncidence demande un texte suffisamment long vis-à-vis de la clé. Dans le cas extrême où la clé est de longueur égale à celle du message, et n'est utilisée qu'une seule fois, tous les textes de longueur égale à celle du message chiffré sont possibles : le chiffre ne peut être cassé ; c'est le chiffre de Vernam, ou masque jetable.

Notes et références

• Cet article contient tout ou une partie d’un document provenant du site Ars Cryptographica. L’auteur autorise Wikipédia à utiliser les textes présents sur son site si la source originale est mentionnée.

Annexes

Bibliographie

• Simon Singh, « Chapitre 2 : le chiffre indéchiffrable », dans Histoire des codes secrets: de l'Égypte des Pharaons à l'ordinateur quantique, Fourth Estate, 1999 (ISBN 9781857028799)