Consignes

Vous devrez utiliser l'interface TPLab pour envoyer vos TP aux encadrants de TP.

La note ne valide pas seulement le résultat de votre programme, mais également son style :

Vérifiez ces points avant de demander à votre intervenant de valider votre code.

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

Liens utiles

1. Cryptographie : César et substitution de lettres

1.1. Description

La manière la plus simple pour crypter un texte de substituer chaque occurrence d'une lettre par une autre. Par exemple :

La fonction suivante permet de crypter une chaîne de caractères en utilisant une telle substitution de lettres. On représente la substitution par la liste des lettres substituées, dans l'ordre. Pour l'exemple précédent, la substitution commencerait donc par "tye...".

Le code de ce type le plus connu est le « code de César » où chaque lettre est remplacé par celle qui vient 3 lettres plus loin dans l'alphabet. De manière similaire, on peut faire un décalage arbitraire (entre 1 et 25) pour crypter un texte...

Le texte ci dessous a été crypté en utilisant un décalage de lettres (« code de César »). En vous aidant de la page http://lama.univ-savoie.fr/~hyvernat/substitution.php, décryptez le...

(Vous pouvez générer une substitution par décalage avec l'option « codage de César »...) 

R'thi jc vpgh, xa gtcigt spch jc rpué,
ti eadju...

Copiez le texte décrypté dans le fichier fourni à l'endroit approprié.

1.2. Cryptanalyse

Facile ?

En utilisant la page http://lama.univ-savoie.fr/~hyvernat/substitution.php, décryptez le texte suivant. 

Zp ! lml ! i'rev ql brq imqkv, srqlr pmaar !
Ml bmqozxv jxkr...Mp ! Jxrq !...txrl jre ipmere rl emaar...
Rl ozkxzlv nr vml, -bzk rfrabnr, vrlrw :   
Zdkreexh: "Amx, amlexrqk, ex s'zozxe ql vrn lrw
Xn hzqjkzxv eqk-nr-ipzab yqr sr ar n'zabqvzeer !"
Zaxizn: "Azxe xn jmxv vkrabrk jzle omvkr vzeer !
Bmqk tmxkr, hzxvre-omqe hztkxyqrk ql pzlzb !"
Jreikxbvxh: "I'rev ql kmi !...i'rev ql bxi !. . .i'rev ql izb !
Yqr jxe-sr, i'rev ql izb ?...I'rev qlr bélxleqnr !"
Iqkxrqf: "Jr yqmx erkv irvvr mtnmldqr izbeqnr ?
J'éikxvmxkr, amlexrqk, mq jr tmîvr à ixerzqf ?"
Dkzixrqf: "Zxarw-omqe à ir bmxlv nre mxerzqf
Yqr bzvrklrnnrarlv omqe omqe bkémiiqbâvre  
Jr vrljkr ir brkipmxk à nrqk brvxvre bzvvre ?"

Copiez le texte décrypté dans le fichier fourni à l'endroit approprié.

Difficile ? (à faire en dernier)

Faites la suite du TP avant de faire cette cryptanalyse.

Comme dernier exemple, essayez de décryptez le texte suivant. 

inb HqgnwMpf QMwighI JqM Juh thtuwwb Wgnb wugg dF gqg iMnFdFkhI huWg taMF
gqMhg FMg dFongstgFg MppuhdMFh JqgF qg Juh ta uww FdkqgI Juh hguggl ug gqg
cngufouhg gucwgb d hgMMl taMF gqg qgungq-ntk uFl adpfgl ta gqg hgdpf Jqdpq Mtn
WdhdgMn qul wgog cgqdFl qdi gqg Fdkqg cgoMngb dg Juh u odFgI gqdpf adgpg Mo
JMMlI ctwcMth-qgulglI Mo gqg hMng Jqdpq dh fFMJF uh u xAgFuFk wuJbgnbx Lthg
tFlgn gqg qgul Juh u cnMul hdwWgn cuFl Fgunwb uF dFpq upnMhhb xGM Luigh
iMngdignI ibnbPbHbI onMi qdh ondgFlh Mo gqg PbPbQbIx Juh gFknuWgl taMF dgI
Jdgq gqg lugg x1884bx dg Juh lthg htpq u hgdpf uh gqg Mwl-ouhqdMFgl ouidwb
anupgdgdMFgn thgl gM punnb-ldkFdodglI hMwdlI uFl nguhhtndFkb

Copiez le texte décrypté dans le fichier fourni à l'endroit approprié.

Programme Python de codage

Le code Python suivant est une fonction qui permet d'appliquer une substitution donnée sur une chaîne de caractères : 

import string

def codage_substitution(subst, chaine, 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	# liste de toutes les lettres ASCII en majuscules
    chaine = chaine.upper()
    resultat = ""
    for c in chaine:
        n = alphabet.find(c)  	# on cherche l'indice de l'occurrence de c dans l'alphabet
        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

É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.

Il suffit de modifier cette fonction dans le fichier fourni à l'endroit approprié.

Vérifiez bien que la fonction permet de décoder, par exemple avec les instructions suivantes qui permettent de générer une substitution aléatoire, de l'appliquer à la chaîne "Salut, je m'appelle Bob...", et ensuite de la « désapliquer » pour revenir sur la chaîne initiale. 

>>> import random
>>> substitution = list(string.ascii_uppercase)
>>> random.shuffle(substitution)
>>> substitution = "".join(substitution)
>>> print(substitution)
ZVRIENHXJAYOKUFWBPLMCGSQTD
>>> message = "Salut, je m'appelle Bob..."
>>> crypte = codage_substitution(substitution, message, decode=False)
>>> print(crypte)
LZOCM, AE K'ZWWEOOE VFV...
>>> resultat = codage_substitution(substitution, crypte, decode=True)
>>> print(resultat)
SALUT, JE M'APPELLE BOB...

2. Le code de Vigenère

Comme le montrent les exemples précédents, les substitutions de lettres sont facilement analysable (càd, « craquables »).

Le code de Vigenère agit comme un code de César, 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 chaîne à 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'

Utilisez l'exemple du Wikipédia et calculez le code de Vigenère sur la chaîne ""j'adore ecouter la radio toute la journee" en utilisant la clé "MUSIQUE".

Vérifiez que vous obtenez bien le bon résultat en utilisant la fonction vigenere définie dans le fichier fourni.

Attention, dans l'exemple sur Wikipedia la lettre "A" provoque un décalage de 0, la lettre "B" un décalage de 1, etc. Nous travaillons avec la lettre "A" qui provoque un décalage de 1, la lettre "B" qui provoque un décalage de "2", etc.

Une fois que vous arrivez à obtenir le même résultat « à la main » et avec la fonction fournie, ajouter le texte suivant dans le fichier fourni : (bien entendu, les ... sont à remplacer par votre nom et prénom !) 

Je soussigné ... atteste sur l'honneur que j'ai compris comment le code de Vigenère fonctionnait.

Une fois que ce message est dans votre fichier, votre encadrant de TP peut vous demander une démonstration de votre aptitude à utiliser le code de Vigenère à la main !!!

3. Craquer Vigenère

3.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.

3.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, si s est une chaîne en français, l'indice de coïncidence entre 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 procédure test_friedman(chaine, decalage_max) qui affiche les indices de coïncidences successifs jusqu'à decalage_max.

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", encoding="UTF-8")
s = f.read()
s = clean(s)			    # cette fonction transforme la chaîne en ASCII majuscule sans espaces
chaine = s[10000:12000]		    # on obtient donc une chaîne de taille 2000
crypte = vigenere(chaine, "MACLE")  # on crypte la chaîne avec le code de Vigenère
...

3.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.

3.4. Une chaîne à décoder

  1. Utilisez la fonction vigenere fournie pour coder un morceau du fichier arsene-lupin.txt avec la clé "LUPIN",
  2. puis vérifiez que la fonction test_friedman que vous avez écrite vous permet de retrouver que la clé avait une 5 lettres,
  3. utilisez la fonction tranche pour récupérer une lettre sur 5 avec 

    >>> s = tranche(chaine_cryptee, 5, 0)
  4. utilisez le script de la page http://lama.univ-savoie.fr/~hyvernat/substitution.php pour compter les occurrences de chaque lettre et en déduire le décalage des lettres 0, 5, 10, 15, ... Ce décalage doit correspondre à la lettre "L",
  5. recommencez pour les lettres 1, 6, 11, 16, ... (lettre "U") jusqu'à retrouver toute la clé...

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.

3.5. Fonction principale (Bonus)

  1. Écrivez une fonction devine_cle(chaine, taille_cle) qui automatise la procédure...
  2. Intégrez les différentes fonctions dans une fonction principale craque_vigenere(chaine) (ou craque_vigenere(fichier)) qui permet de craquer une chaîne codée avec le codage de Vigenère sans intervention de l'utilisateur.