Coverage for src/ensae_teaching_cs/td_1a/vigenere.py: 94%
81 statements
« prev ^ index » next coverage.py v7.1.0, created at 2023-04-28 06:23 +0200
« prev ^ index » next coverage.py v7.1.0, created at 2023-04-28 06:23 +0200
1# -*- coding: utf-8 -*-
2"""
3@file
4@brief Quelques fonctions à propos d'une séance 3.
5"""
8def code_vigenere(message, cle, decode=False, binary=False):
9 """
10 Crypte et décrypte le code de Vigenère sachant la clé connue.
12 @param message message à crypter ou décrypter
13 @param cle clé du code
14 @param decode False: crypte, True: décrypte
15 @param binary code et décode en binaire
16 @return le message crypté ou décrypté
18 .. exref::
19 :title: code de Vigenère
20 :tag: Algorithme
22 .. runpython::
23 :showcode:
25 def code_vigenere ( message, cle, decode = False) :
26 message_code = ""
27 for i,c in enumerate(message) :
28 d = cle[ i % len(cle) ]
29 d = ord(d) - 65
30 if decode : d = 26 - d
31 message_code += chr((ord(c)-65+d)%26+65)
32 return message_code
34 m = "JENESUISPASCODE"
35 c = code_vigenere (m, "DOP")
36 d = code_vigenere (c, "DOP", True)
37 print(c, d)
38 """
39 if binary:
40 if not isinstance(message, bytes):
41 raise TypeError("message must be bytes")
42 if not isinstance(cle, bytes):
43 raise TypeError("cle must be bytes")
45 message_code = []
46 for i, c in enumerate(message):
47 d = int(cle[i % len(cle)])
48 if decode:
49 d = 256 - d
50 message_code.append((int(c) + d) % 256)
51 return bytes(message_code)
52 else:
53 message_code = ""
54 for i, c in enumerate(message):
55 d = cle[i % len(cle)]
56 d = ord(d) - 65
57 if decode:
58 d = 26 - d
59 message_code += chr((ord(c) - 65 + d) % 26 + 65)
60 return message_code
63def DecodeVigenere(message, cle):
64 return code_vigenere(message, cle, True)
67def CodeVigenere(message, cle):
68 return code_vigenere(message, cle)
71def PGCD(m, n):
72 """
73 Détermine le PGCD de deux entiers.
75 @param m premier entier
76 @param n second entier
77 @return PGCD
79 .. exref::
80 :title: calcul du PGCD avec la méthode des soustractions
81 :tag: Algorithme
83 La fonction qui suit est l'implémentation en Python de la méthode décrite
84 ici :
85 `Algorithme de calcul du PGCD par soustractions successives
86 <http://www.kartable.fr/terminale-s/mathematiques/1640/exercice/algorithme-de-calcul-du-pgcd-par-soustractions-successives,TS01505>`_.
88 .. runpython::
89 :showcode:
91 def PGCD (m,n) :
92 if m == 1 or n == 1 : return 1
93 if m == n : return m
94 if m < n : return PGCD (m, n-m)
95 return PGCD (n, m-n)
97 print(PGCD(50, 40))
98 """
99 if m <= 0 or n <= 0:
100 raise RuntimeError("impossible de calculer le PGCD")
101 if m == 1 or n == 1:
102 return 1
103 if m == n:
104 return m
105 if m < n:
106 return PGCD(m, n - m)
107 return PGCD(n, m - n)
110def DecodeVigenereLongueurCle(message, mot=3):
111 """
112 Cette fonction determine la longueur de la clé, elle
113 repère les groupes de trois lettres qui se répète dans le message codé
114 et suppose qu'il y a une très forte probabilité qu'un même groupe de trois
115 lettres soit codé avec les mêmes trois lettres du message et les mêmes trois
116 lettres de la clé.
118 ::
120 message : .....DES...........DES...........DES.........DES....DES
121 cle : ABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCD
122 code : .....EGV.........................EGV.........EGV..........
123 distance : <----------24--------------><----8----->
125 La longueur de la clé divise le *PGCD* de 24 et 8.
127 @param message message codé
128 @param mot longueur des séquences de lettres consécutifs dont on étudie la féquence
129 @return longueur probable de la clé
130 """
131 al = "".join([chr(97 + i)
132 for i in range(0, 26)]) # l'alphabet en minuscule
133 al = al.upper()
135 # parcours du message pour recenser toutes les positions
136 dico = {}
137 for i in range(0, len(message) - 2):
138 t = message[i:i + mot]
139 if t in dico:
140 dico[t].append(i)
141 else:
142 dico[t] = [i]
144 # on va garder toutes les distances entre
145 # entre deux occurrences du meme mot de n lettres
146 dis = []
147 for d in dico: # pylint: disable=C0206
148 p = dico[d]
149 if len(p) > 1:
150 for i in range(0, len(p) - 1):
151 # print d, p [i+1] - p [i], " --- ", float (p [i+1] - p [i]) /
152 # 8
153 dis.append(p[i + 1] - p[i])
155 # on extrait le PGCD
156 if len(dis) == 0:
157 raise RuntimeError("impossible de determiner la clé")
159 if len(dis) == 1:
160 return dis[0]
162 longueur = PGCD(dis[0], dis[1])
163 for d in dis:
164 longueur = PGCD(longueur, d)
166 if longueur > 5:
167 # si la longueur est suffisante, le resultat a des chances d'etre bon
168 return longueur
169 else:
170 # sinon, on relance l'algorithme avec des mots plus grand
171 return DecodeVigenereLongueurCle(message, mot + 1)
174def DecodeVigenereCle(code, lc):
175 """
176 Détermine la cle du message code, connaissant sa longueur,
177 on suppose que la lettre E est la lettre la plus fréquente
179 @param code message codé
180 @param lc longueur probable de la clé
181 @return message décodé
182 """
183 al = "".join([chr(97 + i)
184 for i in range(0, 26)]) # l'alphabet en minuscule
185 al = al.upper()
186 cle = ""
187 for i in range(0, lc):
188 nombre = [0 for a in al]
189 sous = code[i:len(code):lc] # on extrait toutes les lettres
190 # i, i+l, i+2l; i+3l, ...
192 # on compte les lettres
193 for k in sous:
194 nombre[al.find(k)] += 1
196 # on cherche le maximum
197 p = 0
198 for k in range(0, len(nombre)):
199 if nombre[k] > nombre[p]:
200 p = k
202 # on suppose que al [p] est la lettre E code,
203 # il ne reste plus qu'a trouver la lettre de la cle
204 # qui a permis de coder E en al [p]
205 cle += al[(p + 26 - al.find("E")) % 26]
207 return cle
210def CasseVigenere(message):
211 """
212 Appelle les deux fonctions @see fn DecodeVigenereLongueurCle et
213 @see fn DecodeVigenereCle pour casser le code de Vigenère.
215 @param message message codé
216 @return message décodé (sans la clé)
217 """
218 ld = DecodeVigenereLongueurCle(message)
219 cle = DecodeVigenereCle(message, ld)
220 decode = DecodeVigenere(message, cle)
221 return decode