Le protocole RSA se fonde sur le théorème suivant :

Soient p et q deux nombres premiers.
On pose n = p q.
Si le nombre e est un entier premier avec le nombre (p – 1) (q – 1), alors il existe un unique entier d positif, tel que
1< d< (p-1)(q-1) et vérifiant e d ≡ 1 [(p-1)(q-1)],
et, pour cet entier d et un entier A quelconque, on a :
A^ed ≡ A [n]

Démonstration :

1) Montrons que si e, tel que 1<e<(p-1)(q-1), est premier avec le produit (q-1)(p-1) alors il existe d unique tel que 1<d<(p-1)(q-1) et vérifiant e d ≡ 1 [(p-1)(q-1)]

Si eÙ(p-1)(q-1)=1, il existe d’après le théorème de Bézout, deux entiers relatifs u et v tels que :
u (p-1)(q-1) + v e = 1
on peut définir 2 autres entiers u' et v' tels que
u (p-1)(q-1) + v e = u' (p-1)(q-1) + v' e = 1
nous avons par conséquent : (u' -u)(p-1)(q-1) = - (v'- v) e
Il existe donc un entier k tel que u'=u+k e et v' = v - k (p-1)(q-1)

D’après la division euclidienne, nous avons donc 0£v<(p-1) (q-1)

D’après Bézout, nous avons u (p-1)(q-1) = 1 – v e (division de u (p-1)(q-1) par –e donc 1<v) soit v e ≡ 1 [(p-1)(q-1)]
Nous avons donc d = v.

Montrons que d est unique
Supposons qu’il en existe un autre, nous avons donc e(d-d')≡0 [(p-1) (q-1)]
Comme e est premier avec (p-1)(q-1) alors (d-d')≡0 [(p-1)(q-1)]. Mais comme on a 1<d'<(p-1)(q-1) et 1<d<(p-1)(q-1) alors d=d'.

2) Montrons que A^ed ≡ A [n]

Par hypothèse e est premier avec (p – 1)(q – 1). D’après l’identité de Bézout, il existe (d, f) dans ℕ ´ ℤ tel que 
d e + f (p –1) (q – 1) = 1 soit f (p – 1) (q – 1 ) = 1 – d e

Donc il existe d Î ℕ tel que d e – 1 soit divisible par (p – 1) (q – 1).

Soit A un entier
Si A n’est divisible ni par p ni par q, alors, d’après le petit théorème de Fermat, p et q divisent respectivement A^{p – 1} – 1 et A^{q – 1} – 1. Donc p et q divisent A^{(p - 1)(q - 1)} – 1 car cet entier est multiple de A^{q - 1} – 1 et A^{p - 1} – 1. ( A^{(p - 1)(q - 1)} – 1= (A^{p – 1} –1 )( 1 + A^{p – 1} + A^{2( p – 1)} +...+ A^{(q – 2)(p – 1)}) )

Or d e – 1 est divisible par (p – 1) (q – 1 ), il existe donc kÎ ℕ^* tel que d e – 1 = k (p – 1) (q – 1).
Ainsi on a A^ed - A = A^{1 + k(p - 1)(q - 1)} – A = A(A^{k(p - 1)(q - 1)} - 1) = A(A^{(p - 1)(q - 1)} – 1 )(A^{(k - 1)(p - 1)(q - 1)} +...+ 1).

Donc A^ed - A est divisible par n = pq.

Accueil