7.3 Le principe du code RSA
219
72 = 29 × 2 + 14,
29 = 14 × 2 + 1.
Maintenant, nous remontons pour ´ ecrire 1 en fonction de 29 et de 72 :
1 = 29 − 14 × 2
= 29 − (72 − 29 × 2) × 2 = 29 × 5 − 72 × 2.
On a donc 29 × 5 ≡ 1 (mod 72), ce qui donne d = 5. Soit m = 59 notre message.
On a bien (59, 91) = 1. Pour encoder, nous devons calculer 59
29 (mod 91). Comme
59
29 est un tr` es grand nombre, il faut ˆ etre astucieux pour faire ce calcul. On va calculer
successivement 59
2 , 59
4 , 59
8 et 59
16 modulo 91, et utiliser que 59
29 = 59
16
× 59
8
× 59
4
×
59. Allons-y !
59
2 = 3481 ≡ 23 (mod 91),
59
4 = (59
2 )
2
≡ 23
2 = 529 ≡ 74 (mod 91),
59
8 = (59
4 )
2
≡ 74
2 = 5476 ≡ 16 (mod 91),
59
16 = (59
8 )
2
≡ 16
2 = 256 ≡ 74 (mod 91).
Donc, finalement,
59
29 = 59
16
× 59
8
× 59
4
× 59 (mod 91)
≡ (74 × 16) × 74 × 59 (mod 91)
≡ 1 × 74 × 59 = 4366 (mod 91)
≡ 89 (mod 91).
La m´ ethode de calcul que nous avons pr´ esent´ ee est celle qu’utilisent les ordinateurs. Le
message encod´ e est a = 89. Nous l’envoyons. Pour le d´ ecoder, le receveur doit calculer
le reste de la division de 89
5 par 91. La mˆ eme m´ ethode permet de faire le calcul et de
r´ ecup´ erer le message initial, soit m = 59. En effet,
89
2 = 7921 ≡ 4 (mod 91),
89
4 = (89
2 )
2
≡ 4
2 = 16 (mod 91),
ce qui permet de calculer
89
5 = 89
4
× 89 ≡ 16 × 89 = 1424 ≡ 59 (mod 91).
On a r´ ecup´ er´ e le message m !
Proposition 7.8 Soient p et q deux nombres premiers distincts. Alors,
φ(pq) = (p − 1)(q − 1).
Preuve On doit compter le nombre d’entiers de E = {1, 2, . . . , pq − 1} qui sont relativement premiers avec pq. Les seuls entiers qui ne sont pas relativement premiers avec
pq sont les multiples de p, soit P = {p, 2p, . . . (q − 1)p} (on en a q − 1) et les multiples de
q, soit Q = {q, 2q, (p − 1)q} (on en a p − 1). Notons que P ∩ Q = ∅ puisque, si np = mq