Remarques sur la page (ou le sujet) : contact.
mentions légales
,
,
Dernière révision: le 06-04-2016 à 08:46.
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 :
F5 dans IDLE) ne devra pas provoquer d'erreur.
test et vous servira à tester vos fonctions. En particulier, vous n'utiliserez pas de variables globales...
La manière la plus simple pour crypter un texte de substituer chaque occurrence d'une lettre par une autre. Par exemple :
a est remplacé par t,
b est remplacè par y,
c est remplacè par e,
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é.
En utilisant la page http://lama.univ-savoie.fr/~hyvernat/substitution.php, décryptez le texte suivant.
Xq jzkuxzykqj c'kqjdarkfmzx, cx abffdyykdzx hx vbcdax odj wq ydgqx à hxwi gxqhkzfxy, cxypwxcy yx vckaèzxqj, c'wq à hzbdjx c'kwjzx à gkwarx hx Hkqjèy; bq bwuzdj wqx vbzjx pwd abffwqdpwkdj hx c'kvvkzjxfxqj hw vzbawzxwz hw zbd kw vkckdy hx twyjdax, bq ywdudj pwxcpwx jxfvy wq hx axy gzkqhy abzzdhbzy ybfmzxy pwd obqj ozdyybqqxz axwi-cà pwd s vkyyxqj, pwkqh fêfx dcy q'bqj kwawq fbjdo hx ozdyybqqxz. Hx fêfx pwx c'kvvkzjxfxqj hx Udccxobzj abffwqdpwkdj kw vkckdy hx twyjdax, cx vkckdy hx twyjdax abffwqdpwkdj à ck vzdybq, ybfmzx fbqwfxqj kaabcé kw vkckdy xj pwx zxgkzhx awzdxwyxfxqj, hx jbwjxy yxy bwuxzjwzxy mékqjxy, cx acbarxz hxy Kaabwcxy pwd yx hzxyyx hxukqj cwd. Kvzèy qbfmzx hx héjbwzy hkqy cx abzzdhbz pw'dc ywdukdj, Hkqjèy udj y'bwuzdz wqx vbzjx kuxa wq gwdarxj hx oxz; cx abffdyykdzx hx vbcdax ozkvvk, kuxa wq fkzjxkw hx oxz, jzbdy abwvy pwd zxjxqjdzxqj, vbwz Hkqjèy, abffx y'dcy éjkdxqj ozkvvéy ywz ybq abxwz; ck vbzjx y'bwuzdj, cxy hxwi gxqhkzfxy vbwyyèzxqj cégèzxfxqj cxwz vzdybqqdxz, pwd réydjkdj xqabzx. Hkqjèy ozkqardj cx yxwdc zxhbwjkmcx, xj ck vbzjx yx zxoxzfk mzwskffxqj hxzzdèzx cwd. Dc zxyvdzkdj wq kwjzx kdz, wq kdz févrdjdpwx xj cbwzh: dc éjkdj xq vzdybq.
Copiez le texte décrypté dans le fichier fourni à l'endroit approprié.
Faites la suite du TP avant de faire cette cryptanalyse.
Comme dernier exemple, essayez de décryptez le texte suivant.
WKL,OSbgambUOSUqvCqhbvSbL,qb.aLqb1980mbaShbvLmbviE.qiqSLaLvOSbgambmLatLqh vSbjqUqipqtb1989bpKbTfvhObCaSbAOmmfibaLbGHMbvSbL,qb:qL,qt.aShmbamba mfUUqmmOtbLObL,qbPwGb.aSZfaZqb(vLmq.rbvSmEvtqhbpKbNIul)bUaEap.qbOr qBUqELvOSb,aSh.vSZbaShbvSLqtraUvSZbgvL,bL,qbPiOqpabOEqtaLvSZbmKmLqikbxaS AOmmfibvmbWKL,OS'mbEtvSUvEa.bafL,OtobaShb,vmbUOSLvSfvSZbUqSLta.btO.qbvS hqUvhvSZbL,qbhvtqULvOSbOrbWKL,OSbvmbtqr.qULqhbvSbL,qbLvL.qbZvCqSbLOb,vibpKbL,q WKL,OSbUOiifSvLKobpqSqCO.qSLbhvULaLOtbrOtb.vrqb(wjnl)k PpOfLbL,qbOtvZvSbOrbWKL,OSobxaSbAOmmfibgtOLqbvSb1996z bbbbFCqtbmvBbKqatmbaZOobvSbjqUqipqtb1989obMbgamb.OORvSZbrOtbab",OppK" bbbbEtOZtaiivSZbEtOVqULbL,aLbgOf.hbRqqEbiqbOUUfEvqhbhftvSZbL,qbgqqRbatOfSh bbbbG,tvmLiamkb KbOrrvUqbkkkbgOf.hbpqbU.OmqhobpfLbMb,ahbab,OiqbUOiEfLqtobaSh bbbbSOLbifU,bq.mqbOSbiKb,aShmkbMbhqUvhqhbLObgtvLqbaSbvSLqtEtqLqtbrOtbL,qbSqg bbbbmUtvELvSZb.aSZfaZqbMb,ahbpqqSbL,vSRvSZbapOfLb.aLq.KzbabhqmUqShaSLbOrbPwG bbbbL,aLbgOf.hbaEEqa.bLObcSvB/Gb,aURqtmkbMbU,OmqbWKL,OSbambabgOtRvSZbLvL.qbrOt bbbbL,qbEtOVqULobpqvSZbvSbabm.vZ,L.KbvttqCqtqSLbiOOhb(aShbabpvZbraSbOrb OSLK bbbbWKL,OS'mbn.KvSZbGvtUfm)k WKL,OSb2k0bgambtq.qamqhbOSb16bFULOpqtb2000obaShbvSU.fhqhbiaSKbiaVOtbSqg rqaLftqmbvSU.fhvSZbabrf..bZatpaZqbUO..qULOtbaShbmfEEOtLbrOtbcSvUOhqkbHvL,bL,vm tq.qamqbL,qbhqCq.OEiqSLbEtOUqmmbgambU,aSZqhbaShbpqUaiqbiOtqbLtaSmEatqSLbaSh UOiifSvLK-paURqhk WKL,OSb3k0b(a.mObUa..qhbWKL,OSb3000bOtbEK3R)obabiaVOtobpaURgathm-vSUOiEaLvp.q tq.qamqobgambtq.qamqhbOSb3bjqUqipqtb2008barLqtbab.OSZbEqtvOhbOrbLqmLvSZk aSKbOrbvLmbiaVOtbrqaLftqmb,aCqbpqqSbpaUREOtLqhbLObL,qbpaURgathm-UOiEaLvp.q WKL,OSb2k6baShb2k7k
Copiez le texte décrypté dans le fichier fourni à l'endroit approprié.
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 return resultat # place dans la substitution
É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...
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 :
'B' est la deuxième lettre de l'alphabet)
'O' est la quinzième lettre de l'alphabet)s
'N' est la quatorzième lettre de l'alphabet)
'J' est la dixième lettre de l'alphabet)
'O' est la quinzième lettre de l'alphabet)
'U' est la vingt et unième lettre de l'alphabet)
'R' est la dix-huitième lettre de l'alphabet)
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 de 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 !!!
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.
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 ...
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.
vigenere fournie pour coder un morceau du fichier arsene-lupin.txt avec la clé "LUPIN",
test_friedman que vous avez écrite vous permet de retrouver que la clé avait une 5 lettres,
tranche pour récupérer une lettre sur 5 avec
>>> s = tranche(chaine_cryptee, 5, 0)
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.
devine_cle(chaine, taille_cle) qui automatise la procédure...
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.
Remarques sur la page (ou le sujet) : contact.
mentions légales
,
,
Dernière révision: le 06-04-2016 à 08:46.