Consignes

Pour ce TP, la pièce la plus importante sera un fichier tp2-prenom-nom.py contenant votre programme que vous enverrez à votre encadrant de TP (Pierre.Hyvernat@univ-savoie.fr ou Thomas.Seiller@univ-savoie.fr). Le seul fait que votre programme fonctionne ne suffit pas pour avoir une bonne note. Les points suivants seront pris en compte :

  1. la lisibilité de votre programme (choix pertinent pour les noms de variables etc.),
  2. la présence de commentaires aux endroits appropriés,
  3. ...

Ce n'est pas obligatoire, mais je vous conseille fortement d'utiliser le fichier squelette fourni comme point de départ.

Certaines questions appellent à une réponse que vous pouvez mettre en commentaire dans votre fichier tp2-prenom-nom.py.

Attention : les points suivants ne rapportent rien, mais ne pas les respecter pourra retrancher jusqu'à 10 points sur la note finale :

Liens utiles

1. Le code de Vigenère

1.1. Description

1.2. Préliminaire : substitutions

Le code suivant permet de crypter une chaîne de caractères en utilisant un substitution de lettres : 

import string

def codage_substitution(subst, chaîne, decode=False):
    """Crypte la chaîne en utilisant la substitution "subst".
La chaîne est convertie en majuscule d'abord, et seul l'ascii est traité.
La substitution est donnée par la liste des lettres substituées. Par exemple,
pour un décalage de 3 lettres, il suffit de donner la substitution
'DEFGHIJKLMNOPQRSTUVWXYZABC'.
"""
    alphabet = string.ascii_uppercase
    chaîne = chaîne.upper()
    resultat = ""
    for c in chaîne:
        n = alphabet.find(c)
        if n < 0:   # si le caractère c n'est pas dans l'alphabet
            resultat = resultat + c # on le laisse tels quel
        else:       # si le caractère c est dans l'alphabet, on le remplace
            resultat = resultat + subst[n] # par le caractère qui a la même place dans la substitution 
    return resultat

def subst_decalage(d):
    """génère la substitution des lettres ascii majuscules pour un décalage de lettres."""
    alphabet = string.ascii_uppercase
    return alphabet[d:] + alphabet[:d]

Étudiez ce code pour comprendre comment il fonctionne, et ajouter la possibilité de décrypter (c'est à dire, de crypter à l'envers). Pour ceci, vous devrez utiliser l'argument booléen decode.

Vérifiez bien que codage_substitution( subst , codage_substitution( subst , chaîne , False) , True ) == chaîne.

1.3. Coder / décoder Vigenère

Le code de Vigenère agit comme un code par décalage de caractères, mais tous les caractères ne sont pas décalés de la même valeur. Les décalages utilisés dépendent d'une clé, en générale donnée par un mot ou une phrase.

Par exemple, si la clé est "BONJOUR", les lettres du message seront décalés de :

Pour coder le message "vive les topinambours", on répète la clé autant de fois que nécessaire et procède donc comme suit : 

   VIVE LES TOPINAMBOURS
 + BONJ OUR BONJOURBONJO
------------------------- 
   XXJO AZK VDDSCVEDDIBH

Pour simplifier, nous allons supposer que la clé ne contient que des lettres ascii en majuscule, et que la chaine à coder ne contient que des lettres ascii en majuscules. En particulier, elle ne contient ni espace ni ponctuation. La fonction clean(chaine) contenu dans le fichier fourni permet de transformer une chaîne pour obtenir ceci : 

>>> clean("vive les topinambours")
'VIVELESTOPINAMBOURS'

En vous inspirant de la fonction codage_substitution, écrivez une fonction 

def vigenere(cle, chaîne, decode=False):
    """Code le texte en utilisant la clé."""

Comme la chaine ne contient que des lettres, il suffit de coder la i-ème lettre par (chaine[i] + cle[i%t]) % 26, où t est la taille de la clé.

Pour tester, vous pouvez vérifier que l'exemple de Wikipédia est crypté et décrypté correctement : 

>>> vigenere(clean("j'adore ecouter la radio toute la journee"), "MUSIQUE")
'WVWXIZJPJNCVMQNMTMZJYBPMNCVOBPKWVZ'
>>> vigenere('WVWXIZJPJNCVMQNMTMZJYBPMNCVOBPKWVZ', "MUSIQUE", True)
'JADOREECOUTERLARADIOTOUTELAJOURNEE'

Attention, l'exemple sur Wikipedia la lettre "A" provoque un décalage de 0, la lettre "B" un décalage de 1, etc. L'exemple donné est donc décalé de 1 par rapport à ce que l'on fait dans ce TP...

2. Craquer Vigenère

2.1. Indice de coïncidence

Pour craquer le code de Vigenère, nous allons devoir calculer des indices de coïncidence. Pour deux chaînes s1 et s2 de même taille, l'indice de coïncidence est le pourcentage de positions où les lettres de s1 et s2 sont identiques. Par exemple : pour abracadra et raplapla ont un indice de coïncidence de 12.5% : 

abracadabra
raplapla
       +

Il y a seulement une lettre sur 8 qui coïncide dans les deux chaînes. (Les lettres en trop de abracadabra sont simplement ignorées.)

Écrivez une fonction indice_coincidence(s1, s2) qui calcule l'indice de coïncidence de deux chaînes de caractères.

2.2. Obtenir la taille de la clé

Sur deux chaînes aléatoires, l'indice de coïncidence est d'environ 3.85% (un vingt-sixième). Pour deux textes écrits en langue naturelle, l'indice de coïncidence est plus élevé. Pour le français, il est supérieur à 7%. Ceci vient du fait que les lettres ne sont pas distribuées aléatoirement. Par exemple, comme il y a de nombreux 'e' dans des textes en français, il y a un peu plus de chances que des 'e' se retrouvent en même positions dans s1 et s2.

En particulier, l'indice de coïncidence entre une chaîne s et s[n:] doit être supérieur à 7%.

D'autre part, l'indice de coïncidence entre deux chaînes n'est pas modifié si les caractères des deux chaînes ont subit le même décalage. Par contre, l'indice de coïncidence entre deux chaînes où les caractères ont subit deux décalages différents sera de l'ordre de 3.85%.

Pour découvrir la taille de clé, nous allons utiliser le test Friedman. Si s est une chaîne codée avec le code de Vigenère, il faut calculer les indices de coïncidence entre s et s[1:], s et s[2:], s et s[3:, ... Lorsqu'on calcule l'indice de coïncidence entre s et s[d:] où d est la taille de la clé, les lettres alignées ont subit le même décalage. L'indice de coïncidence doit donc être supérieur à 7% ! Dans les autres cas, l'indice de coïncidence sera nettement plus proche de 3.85%...

Programmez une fonction test_friedman(chaîne, decalage_max) qui calcule les indices de coïncidences successifs jusqu'à decalage_max et les affiche.

Testez votre fonction sur des chaînes cryptées avec votre fonction vigenere pour voir que les indices de coïncidence sont effectivement différents quand le décalage est un multiple de la taille de la clé.

Remarque : pour que cela fonctionne, il faut que la chaîne cryptée soit suffisamment grande. Vous pouvez facilement récupérer des chaînes de taille (presque) arbitraire dans le fichier arsene-lupin.txt : 

f = open("arsene-lupin.txt")
s = f.read()
s = clean(s)		# cette fonction transforme la chaîne en ascii majuscule sans espaces
chaîne = s[1000:3000] 	# on obtient donc une chaîne de taille 2000
...

2.3. Analyse statistique

Une fois que l'on connait la taille de la clé, c'est presque gagné : on peut faire une analyse statistique sur les lettres.

Pour ceci, il faut calculer les fréquences d'apparition des lettres par paquets. Si la taille de la clé est de 5 :

Si le texte original est en français « normal », la lettre la plus fréquente sera le «e», pour tous les paquets de lettres. Ainsi, si sur le premier la lettre la plus courante est « u », c'est que le décalage était de 16 lettres («e»+16 = «u»), et donc que la première lettre de la clé était «p» (seizième lettre de l'alphabet.

Écrivez une fonction devine_cle(chaîne, taille_cle) qui calcule les fréquences des lettres sur les taille_cle paquets de lettres de chaîne et calcule la clé la plus probable comme expliqué ci dessus.

Testez en codant des chaînes suffisamment longues avec des clés connues.

2.4. Une chaîne à décoder

Testez vos fonctions en décodant le fichier suivant : 

WJZTGYQWAFVCQZKAZKSROIFSXFTMWXCVUYIWXVISOZJYKARWTFMDXNMAIWDWYIASVEFLWTXN
USHJISBXVDZYBINLSFEHANGOVMOSNDXUTNQSWYOIBZUHNUSYMZEYNJIWTFEODJZNJLHFLGQH
AAEMBTBVFJNNJFSKPZFITJXKSXNZYTGOYJOYSJZXTQOGVFXIMJNIXGIAOIFQXLWGTJCNQZKO
FJFJDVUYVKZJHNVGGYMWNLQTXODJNJRGHWOXMQVEYJOSDLGNGAAGIQKDFUTOLDWXCZDJGPWW
GJCGAAKAXMBIOXQXFKYKEZSMQXBOYWBYCZSTGBQWBYOORNGEXKSSDKMWLKWLWWCJGXEWKGFR
OKQZLYNWBYSAUVNAIMBOEMASWAQSUWKIPJVKQGFJSGKFXJRABJBVXTZEJTWJXYQXWASGANXV
FNHJXKSRSBDJVMZWGXOHUQTPNFSXNDRKBYNDSXKKDTGKSUSWNZOJLNZVSXKKBJEHFLWTXNCZ
BAHGFHRZDFBASLZJCGAAKAXVISZJAYXFJFSAOPJUTOIAFJNPYFEZJUSYDZEHBASUSQYDZIXI
TAAFSNXTKOVMCSCZFWHQAWSSZMQXXJHWRJCXDNLPFDZNCVFNHJXJVTWWAJWNNIIJCYQXKAXA
BJCMQYBJFKDMKGFJLZJKUMOGQSBPJKRJCOMSZWXAHJCYQXFKQQPIKOQXWAUDCRLYQXMQSYGY
KOQXWARSBLKIAXXAYVSXDDFFGEFLSXNZLNKYTFSNVZEYIAWEWXKGMQTJLMSQKKXZLWIJCNDZ
PJYKZJQMOMAWWWSKZFFDXQXKSUCSXVUXLWNLQJDOQUTNIGBSKWXJBJKAFRSOQIXITFCSMGQJ
MKSWBFLPEFBPJLCSVVFYXJISWYKPJUTOXSUJCYMSZAWWICOOUQLARWHYKDFJGBZJSZBZFQHJ
WAONDXQVNESWGYZVEIXXTFUTEOYJFAUGIWNZEFEHJEOSNNENEUFNONDYASVPTMXTEMELKWSV
SFPAXZXJHWRFEYUYXQWKOZHXAZKOIWZNNZZGKKHCQTWWUJGHJKGZSQMNXJYSGXSYGRXJYIIN
FZZFBASLGZBOAZMLTMFXOYQWBZJJOZHWQQEAXUCQYMQXWQUJCKONEJNNVMCNAPUQXJXGWYWJ
ZTGYQWXJXZEFNNFAGYBJBQXZNJSJDVUYNJAWFNDVNQXOFNOSDWUJGMZAZHKNEFMLFJTTSNEJ
LAHZOSDDXQHJXSZJCZEXTUJJHWYKNWNOVMSROIFNEFTAUSKDFFNCJFWJNPSJHHTYIJVJQNEZ
ZEWSOMMQHCNKHJKQQHLKSEOWDZMZLWUGWSDZPFVEJJGTXVULNEQDSFSHMSMAJKCSMCMQNIJS
IJDNASYHFUCSNVONWASAHWSLGJVAYSWYEITTFIJLFTCAAWMWQSQFCNGWXWQSGUOXFFEWIMFJ
DZMQTBZKWGSGUYXWZKCSKGAIXQWSILYPFINJRABJBVXVNAQUCSAPQNEHJUZFCNMNMOFFGMON
UYXNUSFRSGQXLECUSSDNQXIKHWGVEZXFLYNWBHOXARIPJSIOYPDIAQN

Attention,, des sauts de lignes ont été rajouté sur la page web. N'oubliez pas de les enlever, ou utilisez directement le fichier pour obtenir la chaîne vierge.

2.5. Fonction principale (Bonus)

Intégrez les différentes fonctions que vous avez écrite dans une fonction principale craque_vigenere(chaine) (ou craque_vigenere(fichier)) qui permet de craquer une chaine codée avec le codage de Vigenère sans intervention de l'utilisateur.