1A.algo - Casser le code de Vigenère

Links: notebook, html, PDF, python, slides, GitHub

La lettre la plus fréquente en français est la lettre E. Cette information permet de casser le code de César en calculant le décalage entre la lettre la plus fréquente du message codé et E. Mais cette même méthode ne marchera pas pour casser le code de Vigenère. Babbage a contourné cet obstacle en étudiant la fréquence des groupes de trois lettres.

Charles Babbage s’est dit qu’un groupe de trois lettres consécutives avaient toutes les chances, à chaque fois qu’il apparaissait dans le message chiffré, d’être la conséquence du chiffrement des mêmes lettres du message avec les mêmes lettres de la clé (voir Cryptanalyse du chiffre de Vigenère). Pour un groupe de quatre lettres, c’est encore plus probable. Par conséquent, l’espacement entre deux mêmes groupes de lettres chiffrées est un multiple de la longueur de la clé. Par exemple, si la répétition d’un groupe est espacée de 30 lettres, puis celle d’un autre de 25, le plus grand diviseur commun de 25 et 30 est 5. La clé possède donc dans ce cas 5 lettres.

La première fonction crypte et décrypte le code de Vigenère connaissant la clé.

def code_vigenere ( message, cle, decode = False) :
    message_code = ""
    for i,c in enumerate(message) :
        d = cle[ i % len(cle) ]
        d = ord(d) - 65
        if decode : d = 26 - d
        message_code += chr((ord(c)-65+d)%26+65)
    return message_code

def DecodeVigenere(message, cle):
    return code_vigenere(message, cle, True)

def CodeVigenere(message, cle):
    return code_vigenere(message, cle)

Les deux fonctions suivantes estime la longueur de la clé.

def PGCD (m,n) :
    if m <= 0 or n <= 0 : raise Exception("impossible de calculer le PGCD")
    if m == 1 or n == 1 : return 1
    if m == n : return m
    if m < n : return PGCD (m, n-m)
    return PGCD (n, m-n)

def DecodeVigenereLongueurCle (message, mot = 3) :
    """
    cette fonction determine la longueur de la clé, elle
    repère les groupes de trois lettres qui se répète dans le message codé
    et suppose qu'il y a une très forte probabilité qu'un même groupe de trois
    lettres soit codé avec les mêmes trois lettres du message et les mêmes trois
    lettres de la clé

    message  : .....DES...........DES...........DES.........DES....DES
    cle      : ABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCD
    code     : .....EGV.........................EGV.........EGV..........
    distance :      <----------24--------------><----8----->

    la longueur de la clé divise le PGCD de 24 et 8
    """
    al = "".join([ chr(97+i) for i in range(0,26) ]) # l'alphabet
    al = al.upper ()

    # parcours du message pour recenser toutes les positions
    dico = {}
    for i in range (0, len (message)-2) :
        t = message [i:i+mot]
        if t in dico : dico [t].append (i)
        else : dico [t] = [i]

    # on va garder toutes les distances entre
    # entre deux occurrences du meme mot de n lettres
    dis = []
    for d in dico :
        p = dico [d]
        if len (p) > 1 :
            for i in range (0, len (p)-1) :
                #print d, p [i+1] - p [i], " --- ", float (p [i+1] - p [i]) / 8
                dis.append ( p [i+1] - p [i] )

    # on extrait le PGCD
    if len (dis) == 0 :
        raise Exception("impossible de determiner la clé")

    if len (dis) == 1 : return dis [0]

    longueur = PGCD (dis [0], dis [1])
    for d in dis :
        longueur = PGCD (longueur, d)

    if longueur > 5 :
        # si la longueur est suffisante, le resultat a des chances d'etre bon
        return longueur
    else :
        # sinon, on relance l'algorithme avec des mots plus grand
        return DecodeVigenereLongueurCle (message, mot+1)

La fonction suivante casse le code de Vigenère connaissance la longueur de la clé.

def DecodeVigenereCle (code, l) :
    """
    Détermine la cle du message code, connaissant sa longueur,
    on suppose que la lettre E est la lettre la plus fréquente

    @param      code        message codé
    @param      l           longueur probable de la clé
    @return                 message décodé
    """
    al  = "".join([ chr(97+i) for i in range(0,26) ])
    al  = al.upper ()
    cle = ""
    for i in range (0, l) :
        nombre = [ 0 for a in al]
        sous   = code [i:len (code):l]  # on extrait toutes les lettres
                                        # i, i+l, i+2l; i+3l, ...

        # on compte les lettres
        for k in sous : nombre [ al.find (k) ] += 1

        # on cherche le maximum
        p = 0
        for k in range (0, len (nombre)) :
            if nombre [k] > nombre [p] : p = k

        # on suppose que al [p] est la lettre E code,
        # il ne reste plus qu'a trouver la lettre de la cle
        # qui a permis de coder E en al [p]
        cle += al [ (p + 26 - al.find ("E")) % 26 ]

    return cle

Enfin, la dernière fonction qui casse le code en appelant toutes les autres :

def CasseVigenere(message):
    """
    appelle les deux fonctions @see fn DecodeVigenereLongueurCle et
    @see fn DecodeVigenereCle pour casser le code de Vigenère

    @param      message     message codé
    @return                 message décodé (sans la clé)
    """
    l = DecodeVigenereLongueurCle(message)
    cle = DecodeVigenereCle(message,l)
    decode = DecodeVigenere(message, cle)
    return decode

Un petit example avec le dernier jour d’un condamné qu’on récupère depuis le site Gutenberg :

from ensae_teaching_cs.data import gutenberg_name
text = gutenberg_name("condamne", load=True)
len(text)
224060

On enlève les caractères indésirables :

message = text.replace ("\n", "").replace ("\r", "").replace ("\t", "").replace (" ", "").replace (",", "")
message = message.replace (";", "").replace (":", "").replace (".", "").replace ("'", "").replace ("\"", "")
message = message.replace ("-", "").replace ("!", "").replace ("?", "").replace ("(", "").replace (")", "")
message = message.upper ()

On le code une clé :

message = message [5000:7000]  # on réduit la taille du message
code = CodeVigenere (message, "VIGENERES")

Puis on essaye de retrouver la clé :

cle_code = DecodeVigenereCle (code, DecodeVigenereLongueurCle (code))
cle_code
'VIGENERES'