Exemple de chiffrement/déchiffrement code RSA.
On choisit un alphabet de 40 lettres :
A= 0, B= 1, C= 2, D= 3, E= 4, F= 5, G=6, H=7, I=8, J=9, K+10, L=11, M=12, N=13,. . .
V=21, W=22 , X= 23, Y= 24, Z= 25,
_=26, .= 27, ?= 28, €= 29, 0= 30, 1= 31, . . . , 8= 38, 9= 39,
On choisit comme clé publique le couple
p = 23, q = 89, donc n = p . q = 2047,
ϕ(n) = ϕ(2047) = (p-1)(q-1) = 22 × 88 = 1936
il faut trouver e tel qu’il soit premier et e * d = 1 [1936]
si on choisit e = 179, il faut trouver d tel que e * d = 1 [1936]
En utilisant l’algorithme d’Euclide étendu on trouve d = 411.
On a e * d = 73569=38 * 1936 +1=1 [1936]
Clé publique (n, e) = (2047,179), Clé privée (n, d) = (2047,411)
On a 402 ≤ 2047 ≤ 403
On choisit donc de découper le message en clair en blocs de deux lettres et
les messages chiffrés seront en blocs de trois lettres.
On écrit chaque bloc de deux symboles clairs ( X1 , X2 ) sous la forme 40x1 +x2
ou xi est le nombre compris entre 1 et 39 correspondant a Xi.
Le message clair est :
ENVOYEZ_€2500.
Pour le chiffrer on considère des blocs de 2 caractères
EN = 4 × 40 + 13 = 173, VO = 21 × 40 + 14 = 854,
YE = 24 × 40 + 4 = 964, Z_ = 25 × 40 + 26 = 1026,
€2 = 29 x 40 + 32 = 1192, 50 = ..=1430
0. = ..=1227
Chiffrement du message (..)e [2047] avec e= 179
EN → (173)179 [2047] = 854 = 0 × 402 + 21 × 40 + 14 = AVO
VO → (854)179 [2047] = 1315 = 0 × 402 2 + 32 × 40 + 35 = A25
YE → (964)179 [2047] = 452 = 0 × 402 + 11 × 40 + 12 = ALM
Z_ → (1026)179 [2047] = 1295 = 0 × 402 + 32 × 40 + 15 = A2P
€2 → (1192)179 [2047] = 511 = 0 × 40 2 + 12 × 40 + 31 = AM1
50 → (1430)179 [2047] = 1996 = 1 × 40 2 + 9 × 40 + 36 = BJ6
0. → (1227)179 [2047] = 88 = 0 × 402 + 2 × 40 + 8 = ACI
Le message chiffré est donc
AVOA25ALMA2PAM1BJ6ACI
Pour déchiffrer on factorise, on prend des blocs de 3 caractères (..)d [2047] avec d= 411
On écrit chaque bloc de trois symboles codés (Y1 , Y2 ,Y3 ) sous la forme
402 y1 + 40 y2 + y3 ou yi est le nombre entre 0 et 39 correspondant à Yi.
AVO = 0 * 40 + 21*40 + 14 = 854
(854)411 [2047] = 173 [2047] = 4 * 40 + 13 = (4 -13) = EN
A25 = 0 + 32 * 40 + 35 =1315
(1315)411 = 854 [2047] = 21 * 40 + 14 = (21 - 14) = VO
…….
Le texte déchiffré est ENVO …..
Primes numbers
Sous Matlab l’instruction ‘ primes (n)’ vous donne tous les nombres premiers inférieurs à n
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89
97 101 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 211 223
227 229 233 239 241 251 257 …….
Algorithme d’Euclide étendu pour l’exemple
r0 = 1936, r1 179
1936 = 10 * 179 + 146 146 = r0 - 10 r1
179 = 146 + 33 33 = r1 –( r0 - 10 r1 ) = 11 r1 - r0
146 = 4 * 33 + 14 14 =….. = 5 r0 – 54 r1
33 = 2 * 14 + 5 5 = …..= 119 r1 - 11 r0
14 = 2 * 5 + 4 4 = …= 27 r0 - 292 r1
5=4+1 1 = …= 411 r1 -47 r0
4=4*1+0
Donc : PGCD(1936,179) = 1 [1976]
411 r1 -47 r0 =1 [r0] donc 411 r1 =1[1936] et 411 = r0 -1 [1936]
411 = (179)-1 [1936]
