- Prenons p=5 et q=11 donc n=pq=55 et (p-1)(q-1)=40
- Prenons e=7, on s’assure (Euclide) que e est premier avec
40
40=5*7+5 7=1*5+2 5=2*2+1
|
On détermine alors l’inverse mod (p-1)(q-1)
(Euclide étendu)
|
5-2*2=1
5-2*(7-1*5)=3*5-2*7=1
3*(40-5*7)-2*7=3*40-17*7=1
7-1 mod 40 = -17 mod 40 = 23 |
- La clé publique vaut (e=7, n=55), la clé privée
vaut d=23, les nombres p=5 et q=11 sont détruits
- Soit à coder un fragment de message représenté
par la valeur m=2, le calcul de c est simplement
c=27 mod 55 = 128 mod 55 = 18
|
 |
Déchiffrement : le destinataire calcule de cd
mod n=1823 mod 55 (on utilise ici l’exponentiation
rapide qui permet de ne manipuler que des nombres relativement petits
alors que 1823 est de l’ordre de 1029)
NB : 232=10111
| 181 mod 55 = 18 |
1 |
18 |
| 182 mod 55 = 324 mod 55 = 49 |
1 |
18*49 mod 55=2 |
| 184 mod 55 = 492 mod 55
= 2401 mod 55 = 36 |
1 |
2*36 mod 55=17 |
| 188 mod 55 = 362 mod 55
= 1296 mod 55 = 31 |
0 |
17 |
| 1816 mod 55 = 312 mod 55
= 961 mod 55 = 26 |
1 |
17*26 mod 55=2 |
1823 mod 55 = 2
|