Consignes

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.

Liens utiles

1. Cryptanalyse : César et substitution de lettres

1.1. Description

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

La fonction suivante permet de chiffrer une chaine 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 chiffrer 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://www.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://www.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é.

Difficile ? (à faire en dernier)

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

Programme Python de codage

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

import string

def codage_substitution(subst, chaine, decode):
    """Chiffre la chaine en utilisant la substitution ``subst``.
    La chaine 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échiffrer (c'est à dire, de chiffrer à 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 chaine "Salut, je m'appelle Bob...", et ensuite de la « désapliquer » pour revenir sur la chaine initiale. 

>>> import random
>>> substitution = list(string.ascii_uppercase)
>>> random.shuffle(substitution)
>>> substitution = "".join(substitution)
>>> print(substitution)
ZVRIENHXJAYOKUFWBPLMCGSQTD
>>> message = "Salut, je m'appelle Bob..."
>>> chiffre = codage_substitution(substitution, message, False)
>>> print(chiffre)
LZOCM, AE K'ZWWEOOE VFV...
>>> resultat = codage_substitution(substitution, chiffre, 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
-------------------------
   WWIN ZYJ UCCRBUDCCHAG

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 chaine pour obtenir ceci : 

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

Utilisez l'exemple de Wikipédia et calculez le code de Vigenère sur la chaine ""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.

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 chaines s1 et s2 de même taille, l'indice de coïncidence est le pourcentage de positions ojù les lettres de s1 et s2 sont identiques. Par exemple : pour abracadabra 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 chaines. (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 chaines de caractères.

3.2. Obtenir la taille de la clé

Sur deux chaines 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 chaine 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 chaines n'est pas modifié si les caractères des deux chaines ont subit le même décalage. Par contre, l'indice de coïncidence entre deux chaines 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 chaine 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 chaines 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 chaine cryptée soit suffisamment grande. Vous pouvez facilement récupérer des chaines 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 chaine en ASCII majuscule sans espaces
chaine = s[10000:12000]		    # on obtient donc une chaine de taille 2000
chiffre = vigenere(chaine, "MACLE")  # on chiffre la chaine 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 «q» (lettre en position 16 dans l'alphabet).

3.4. Une chaine à 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(chiffre, 5, 0)

  4. utilisez le script de la page http://www.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 : 

VIYSFXPVZEUBPYJZYJRQNHERWESLVWBUTXHVWUHRNYIXJZQVSELCWMLZHVCVXHZRUDEKVSWMTRGIHRA
WUCYXAHMKREDGZMFNULNRMCWTSMPRVXNHAYTGMTRXLYDXMIHVSEDNCIYMIKGEKFPGZZDLASAUEIMMIE
RJOYEHSIWJRWMYXSFNXINXRIYWSPNFUEWHLIMHWFHZNHEPWKVFSIBMPYJNEIEICUTXUJYIGMUFFXLVM
KPSWNCIMIQFGVNWLPUDXINRCKFMFZZFHPJCETSNKCVWBYCIFOVVFIBFPZJZWLAHNWPWEJXJDYRLPWAN
XVAXBYRSFAPVAXNNQMFDWJRRCJLVKJVKVVBIFWDVJFEQNJPYKXMVAXRZTUMZHLANDLZRVZPRTVJHOIU
JPVEIRFJEWIQZAIAUWSYDISVIWXPWVZRFZMWUEMGIWJRQRACIULYVFWNGTPSOMERWMCQJAXMCRWJJCS
FJRTRVMYNIKMYURWJJAIDGEKVSWMBYAZGFEGQYCEAZRKYIBFPZJZWUHRYIPXWEIERZNOITSNHZEIMOX
EDYITRXCYDGAZRTRPXCYHWHSZZERMWSJNULBRBYEVGPZVRRYLPWWIGVQIBWCMKOECYMBUEMGIWIUSVV
ZIVMMHHIBXPWJZWZAIBLPXAIEJCLJFEIKYIJTLNFPRAOIJQIBNLRYVWZGIBXPWEJPPOHJNPWVZTCBQK
XPWLPRXFXJNPWVZQRAKJHPWWZXURWCCEEFDEKRWMYKMJXSERMUYDXHZVDVWJFLPSIKLRPJJWYKVHIBM
CYOIXJYIPLNLZVVVRJYEECWPWJRTBRWUTWKVMKPICNPTSMHFARJVWIAIJZEQRNPHWHSEBRLFPILJRVA
EKODEAOIKBRUUEXWIHRVXJOITSNWRTIBXLRYZVVHBNNTPKZQVGXJCEIFAYIRYAYEPGIVZNMCWPUMDRV
FXYUDHWWSETSDNXIEZTFHVMYDEDGIDNRMMDMDTEMNMCXZRUOSLWSDLDKJVRUREOZWYWIGVQEDXTXWPV
JNYGWZYJNHVYMMYYFJJGBPSVVTIFGIJFYRPLMWIXRFWRXFQWIXHHMEYYEAZRKFYANZYLKSLEWNXPVAY
IINYGVPPDZWTBPNLPWVPTIBJNMDIMMULBMZOTPWIWFVXVIYSFXPVWIWYDEMMEZFXAIAPWYMIRICUTXM
IZVEMCUMPWNEMNRCVTIFLYZYGJMDELKEISSRMDIKZGYNRCCWPGIWRYIBYDWSTIIGVXJMVMNULRQNHEM
DESZTRJCEEMBIEVIMORIGGSXHIUIPMDYYDVRNLLPGBMJGIJPPGKJRDNVCYLYKVTFVRCYOEUDIIFSWUT
KMDPCRERGLRLZIJBRLBLPMHIRHICMZRXGETBRMUNMVZRZGVRKFIUZXRVXDHSSEHIKEIBZZVLVPRPEBM
FVWVPRFTNWEEDVHLEICYLPSAYJVFRFTXWVYJBRJFZHWPVRHKXOEHMIQZAIAUWUMZPTBRZOPMDGITYEB
MLMLNEEFLNMTXWMTREQRFPWKDBTRRCMPWHZGVFUDYWEKXMVAGNWZQHOIRHNXOCHZPM

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 chaine 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 chaine codée avec le codage de Vigenère sans intervention de l'utilisateur.