• Vigenère, le Chiffre indéchiffrable

    Les chiffres de substitution polyalphabétiques
    Le chiffre de Vigenère et sa cryptanalyse (méthodes de Babbage-Kasiski et de Bazeries)
    Principe des chiffres polyalphabétiques


    Dans un chiffre monoalphabétique, l'ensemble des lettres est crypté à partir du même alphabet. Par exemple, un a clair sera toujours un P crypté, un z clair toujours un Q crypté... Lorsqu'on réalise une analyse de fréquences, le profil de l'alphabet clair finit toujours par émerger, d'où la faiblesse de ces chiffres, César ou autres.

    Au contraire, dans un chiffre polyalphabétique, chaque lettre est chiffrée à l'aide d'un alphabet crypté différent, ce qui a pour résultat de brouiller l'analyse de fréquences et de rendre impossible l'identification d'un profil d'alphabet (la cryptanalyse reste néanmoins possible).
    Cet article s'intéressera uniquement au chiffre de Vigenère, mais d'autres existent, tout en étant moins complets.

    Blaise de Vigenère, un diplomate français, a décrit ce chiffre particulier vers 1560, et celui-ci a longtemps été considéré comme  toute épreuve, jusqu'à ce que Babbage, trois siècles plus tard, trouve la faille cachée.



    Cryptographie


    # le Carré de Vigenère
    C'est sur lui que repose le chiffre. Il s'agit d'un tableau comportant 26x26 cases, où l'alphabet est répété 26 fois :

    A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
    A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
    B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
    C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
    D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
    E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
    F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
    G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
    H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
    I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
    J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
    K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
    L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
    M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
    N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
    O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
    P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
    Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
    R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
    S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
    T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
    U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
    V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
    W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
    X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
    Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
    Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

    En orange figure l'alphabet clair, suivi des 26 répétitions avec décalage d'une lettre à chaque fois.

    Alice va définir un mot-clef, par exemple NUIT, qui lui servira à crypter le message. Voyons comment :


    texte clair  rd
    v
    l
    u
    n
    d
    i
    d
    i
    x
    h
    e
    u
    r
    e
    s
     mot-clef NU
    I
    T
    N
    U
    I
    T
    N
    U
    I
    T
    N
    U
    I
    T
    N
     texte chiffré
    E
    X
    D
    E
    H
    H
    L
    B
    Q
    C
    F
    A
    R
    O
    Z
    X
    F

    Pour chaque lettre claire, on utilisera l'alphabet commençant par la lettre du mot-clef correspondant. Ainsi, le premier r est chiffré à l'aide de l'alphabet du carré commençant par NOPQ... C'est ce qui fait la force du chiffre de Vigenère : une même lettre est chiffrée par plusieurs autres (dans l'exemple, r est chiffré par E et Z), et une même lettre chiffrée correspond à plusieurs lettres claires (le H est à la fois u et n, par exemple). Des mots entiers peuvent être chiffrés de manière différente.


    Cryptanalyse : la méthode Babbage-Kasiski


    Le chiffre de Vigenère est longtemps resté le chiffre indéchiffrable. Deux méthodes principales de cryptanalyse existent, celle de Babbage et Kasiski, et celle du commandant Bazerie.

    # la méthode Babbage-Kasiski
    Elle consiste à chercher les répétitions dans le texte chiffré. En effet, lorsque le message est assez long, il est fatal que la clef va se répéter sur deux séquences de texte identiques - la séquence chiffrée sera donc la même.
    Afin d'éviter d'être parasité par des séquences chiffrées identiques par hasard, il est préférable de rechercher uniquement les séquences de quatre lettres et plus.

    ex : (<source> )

    KQOWE FVJPU JUUNU KGLME KJINM WUXFQ MKJBG WRLFN FGHUD WUUMB SVLPS NCMUE KQCTE SWREE KOYSS IWCTU AXYOT APXPL WPNTC GOJBG FQHTD WXIZA YGFFN SXCSE YNCTS SPNTU JNYTG GWZGR WUUNE JUUQE APYME KQHUI DUXFP GUYTS MTFFS HNUOC ZGMRU WEYTR GKMEE DCTVR ECFBD JQCUS WVBPN LGOYL SKMTE FVJJT WWMFM WPNME MTMHR SPXFS SKFFS TNUOC ZGMDO EOYEE KCPJR GPMUR SKHFR SEIUE VGOYC WXIZA YGOSA ANYDO EOYJL WUNHA MEBFE LXYVL WNOJN SIOFR WUCCE SWKVI DGMUC GOCRU WGNMA AFFVN SIUDE KQHCE UCPFC MPVSU DGAVE MNYMA MVLFM AOYFN TQCUA FVFJN XKLNE IWCWO DCCUL WRIFT WGMUS WOVMA TNYBU HTCOC WFYTN MGYTQ MKBBN LGFBT WOJFT WGNTE JKNEE DCLDH WTVBU VGFBI JG

    Après avoir repéré les séquences de plus que quatre lettres se répétant, il faut compter les intervalles séparant celles-ci. Ensuite, en cherchant les facteurs communs des différents intervalles, on cherche les longueurs possibles de la clef :

        Longueurs de clef possibles
    Séquence répétée Espace de répétition 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  

    Ici, il apparaît que la seule longueur commune à toutes les répétitions est 5. La clef comporte donc 5 caractères.

    # Et pour déterminer le mot-clef ?
    Comme on sait maintenant que la clef comporte cinq caractères, on sait également que, toutes les cinq lettres, c'est le même alphabet qui est utilisé.
    L'analyse de fréquences retrouve alors toute son utilité. En établissant un tableau de fréquences pour chaque alphabet de la clef, il est possible de retrouver au fur et à mesure chaque lettre de la clef et, partant, de reconstituer le message clair.

    Le texte de l'exemple devient donc :
    Souvent pour s'amuser les hommes d'équipage prennent des albatros, vastes oiseaux des mers, qui suivent, indolents compagnons de voyage, le navire glissant sur les gouffres amers. A peine les ont-ils déposés sur les planches que ces rois de l'azur, maladroits et honteux, laissent piteusement leurs grandes ailes blanches, comme des avirons, traîner à côté d'eux. Ce voyageur ailé, comme il est gauche et veule, lui naguère si beau, qu'il est comique et laid. L'un agace son bec avec un brûle-gueule, l'autre mime en boitant l'infirme qui volait. Le poète est semblable au prince des nuées, qui hante la tempête et se rit de l'archer. (Baudelaire, L'Albatros)



    Cryptanalyse : la méthode Bazeries


    Pour ceux qui ont eu le courage de lire jusque là, une méhode plus simple et moins fastidieuse que celle de Babbage et Kasiski.

    Elle se base sur la technique du mot probable. On suppose ainsi que le message intercepté renferme un mot particulier, par exemple "attaque", "météo" ou n'importe quoi d'autre.
    On va donc chercher ce mot, qui n'est pas le mot-clef mais va permettre de le découvrir, en prenant une à une des séquences du nombre de lettres du mot-clef et en soustrayant les lettres entre elles, jusqu'à ce qu'apparaisse un motif de lettres répétées, qui sera le mot-clef.

    Plus de détails <ici>. Je n'aime pas cette méthode, d'une approche très réductive. Elle est sûrement payante en temps de conflits, lorsque les messages envoyés sont très courts, mais empêche une approche plus globale du chiffre de Vigenère.



    Force et faiblesse


    La force du Vigenère réside dans l'utilisation de plusieurs alphabets, et rend la cryptanalyse plus complexe - les exemples choisis utilisent un clef courte avec donc une grande probabilité de répétitions, mais une clef aussi longue que le message rend en théorie le chiffre totalement sécuritaire. Des chiffres dérivés du Vigenère, comme par exemple le Grand Chiffre de Louis XIV, ont tenu les cryptanalyste en échec alors même que l'on savait briser le Vigenère.

    Vigenère reste donc entièrement d'actualité, au contraire des <chiffres monoalphabétiques> et des <chiffres de transposition simples> .
    Et promis, si j'apprends à coder, je ferai un bel applet pour briser le Vigenère - on peut en trouver des tout prêts sur Internet, mais je n'aime pas beaucoup ce qui est tout mâché. C'est tellement plus rigolo de le faire soi-même !

    Tags Tags : , ,
  • Commentaires

    1
    Samedi 9 Février 2008 à 10:04
    Oula ... c'est compliqué, j'ai pas vraiment compris ^^
    Faut connaître les différents alphabets et tout ... c'est impossible à comprendre ... ou presque !!!
    2
    Dimanche 10 Février 2008 à 14:43
    Tu en fais un une fois, et ensuite tu comprends bien comment ça marche
    Suivre le flux RSS des commentaires


    Ajouter un commentaire

    Nom / Pseudo :

    E-mail (facultatif) :

    Site Web (facultatif) :

    Commentaire :