Coverage for src/ensae_teaching_cs/td_1a/vigenere.py: 94%

81 statements  

« prev     ^ index     » next       coverage.py v7.1.0, created at 2023-01-27 05:44 +0100

1# -*- coding: utf-8 -*- 

2""" 

3@file 

4@brief Quelques fonctions à propos d'une séance 3. 

5""" 

6 

7 

8def code_vigenere(message, cle, decode=False, binary=False): 

9 """ 

10 Crypte et décrypte le code de Vigenère sachant la clé connue. 

11 

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é 

17 

18 .. exref:: 

19 :title: code de Vigenère 

20 :tag: Algorithme 

21 

22 .. runpython:: 

23 :showcode: 

24 

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 

33 

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") 

44 

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 

61 

62 

63def DecodeVigenere(message, cle): 

64 return code_vigenere(message, cle, True) 

65 

66 

67def CodeVigenere(message, cle): 

68 return code_vigenere(message, cle) 

69 

70 

71def PGCD(m, n): 

72 """ 

73 Détermine le PGCD de deux entiers. 

74 

75 @param m premier entier 

76 @param n second entier 

77 @return PGCD 

78 

79 .. exref:: 

80 :title: calcul du PGCD avec la méthode des soustractions 

81 :tag: Algorithme 

82 

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>`_. 

87 

88 .. runpython:: 

89 :showcode: 

90 

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) 

96 

97 print(PGCD(50, 40)) 

98 """ 

99 if m <= 0 or n <= 0: 

100 raise Exception("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) 

108 

109 

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

117 

118 :: 

119 

120 message : .....DES...........DES...........DES.........DES....DES 

121 cle : ABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCD 

122 code : .....EGV.........................EGV.........EGV.......... 

123 distance : <----------24--------------><----8-----> 

124 

125 La longueur de la clé divise le *PGCD* de 24 et 8. 

126 

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() 

134 

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] 

143 

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]) 

154 

155 # on extrait le PGCD 

156 if len(dis) == 0: 

157 raise Exception("impossible de determiner la clé") 

158 

159 if len(dis) == 1: 

160 return dis[0] 

161 

162 longueur = PGCD(dis[0], dis[1]) 

163 for d in dis: 

164 longueur = PGCD(longueur, d) 

165 

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) 

172 

173 

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 

178 

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

191 

192 # on compte les lettres 

193 for k in sous: 

194 nombre[al.find(k)] += 1 

195 

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 

201 

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] 

206 

207 return cle 

208 

209 

210def CasseVigenere(message): 

211 """ 

212 Appelle les deux fonctions @see fn DecodeVigenereLongueurCle et 

213 @see fn DecodeVigenereCle pour casser le code de Vigenère. 

214 

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