7.3 Le principe du code RSA
221
ci-dessus que k 1 · m et k 2 · m ont le mˆ eme reste lorsqu’on les divise par n et que k 1 ≥ k 2 ,
alors on obtient encore (k 1 − k 2 ) · m = (q 1 − q 2 ) · n. Donc, n doit diviser le produit
(k 1 − k 2 ) · m. Comme n est relativement premier avec m, on doit avoir n | k 1 − k 2 . Mais
0 ≤ k 1 − k 2 ≤ n − 1. Donc, finalement, la seule possibilit´ e est k 1 − k 2 = 0, c’est-` a-dire
k 1 = k 2 .
En multipliant tous ces nombres, on obtient
(k,n)=1
k k ≡ m
φ(n)
·
(k,n)=1
k k (mod n).
Le r´ esultat suit comme pr´ ec´ edemment, par « simplification » de
(k,n)=1,k relativement premier avec n, de par la proposition 7.5(3). En effet, si a =
(k,n)=1,k et b = m
φ(n)
− 1, on a n | ab et (n, a) = 1, ce qui entraˆ ıne n | b, c’est-` a-dire la conclusion
cherch´ ee.
Proposition 7.10 Le cryptage-d´ ecryptage du code RSA fonctionne : si on encode un
message m tel que (m, n) = 1 comme a, o` u m
e
≡ a (mod n), alors le d´ ecryptage redonne
le message m : a
d
≡ m (mod n).
Preuve Si m
e
≡ a (mod n), alors
a
d
≡ (m
e )
d = m
ed = m
kφ(n)+1 = m
kφ(n) .m = (m
φ(n) )
k .m
≡ 1
k .m = 1.m = m (mod n).
Exemple 7.11 Une compagnie veut monter un syst` eme de commandes sur Internet.
Elle instaure donc un cryptage `
a cl´ e publique pour la transmission du num´ ero de carte
de cr´ edit. Le num´ ero de carte de cr´ edit est un nombre de 16 chiffres auquel on ajoute
les 4 chiffres qui correspondent `
a la date d’expiration, pour un total de 20 chiffres. La
compagnie choisit p et q, deux grands nombres premiers. Nous fonctionnerons dans notre
exemple avec des nombres de 25 chiffres, ce qui donne pour n un nombre de 50 chiffres
environ. Prenons
p = 12345679801994567990089459
et
q = 8369567977777368712343087.
Ceci donne
n = pq = 103328006334666582188478564007333624855622630219933
et
φ(n) = (p − 1)(q − 1)
= 103328006334666582188478543292085845083685927787388.