Démonstration de la Proposition fondamentale du cryptage RSA.

La compréhension de ce qui suit nécessite des connaissances en théorie des groupes. Commençons par un petit lemme qui se révélera très utile :

Lemme 0.1. Soient G un groupe fini d’ordre n et d,e deux entiers tels que ed ≡ 1 mod (n). Alors les applications

G → G et G → G x ↦→ xe x ↦→ xd

sont inverses l’une de l’autre.

Démonstration : Il s’agit de vérifier que x^ed = x ∀x G. Comme ed ≡ 1 mod (n), il existe k ℕ tel que ed = 1 + kn. Ainsi

xed = x1+kn = x.xkn = x. (xn )k = x,

car d’après le théorème de Lagrange, xⁿ = 1. On a donc le résultat voulu. □

Notations : Nous disposons de deux nombres premiers p et p. On note

m = pq.

Soit G =

(ℤ∕mℤ) le groupe des inversibles de ℤ∕mℤ. On sait que le cardinal de G est ♯G = φ(m) = (p - 1)(q - 1), où φ est l’indicateur d’Euler. On pose donc

n = (p - 1)(q - 1).

On choisit enfin e et d tels que

ed ≡ 1 mod (n ).

Proposition 0.2. Les applications

ℤ ∕m ℤ → ℤ ∕m ℤ ℤ∕m ℤ → ℤ ∕m ℤ x ↦→ xe et x ↦→ xd

sont réciproques l’une de l’autre.

Démonstration : Nous devons vérifier que

xed = x ∀x ∈ ℤ ∕m ℤ (⋆).

Soit donc x

ℤ∕mℤ. Nous allons procéder par étapes :

Si x = dans ℤ∕mℤ. Il faut montrer que ^ed = , c’est à dire que p^ed ≡ p mod (pq).
∙ Il est clair que p^ed ≡ p mod p (car p^ed - p est divisibe par p).
∙ Soit la classe de p dans ℤ∕qℤ. Comme p et q sont premiers entre eux, (ℤ∕qℤ). Or ed ≡ 1 mod ((p - 1)(q - 1)), donc a fortiori ed ≡ 1 mod (q - 1). On peut donc appliquer le lemme à G = (ℤ∕qℤ), ce qui donne que ( )^ed = , c’est à dire que p^ed ≡ p mod q.

On a donc montré que p^ed ≡ p mod p et p^ed ≡ p mod q. Or p et q étant premiers entre eux, cela implique (conséquence du théorème de Gauss) que p^ed ≡ p mod (pq), ce qu’il fallait démontrer.
Si x = dans ℤ∕mℤ, alors q^ed ≡ p mod (pq) par symétrie des rôles de p et q, c’est à dire x^ed = x.
Si x et y vérifient (⋆), alors xy également. En effet, comme x^ed = x et y^ed = y, $(xy)ed = xedyed = xy$ (tout est commutatif).
D’après le lemme, (⋆) est vérifiée pour tout x (ℤ∕mℤ) ⊂ (ℤ∕mℤ) (puisque ce groupe est d’ordre n).

Montrons maintenant que (⋆) est vérifiée pour tout x ℤ∕mℤ. Soient x ℤ∕mℤ et a ℤ tel que x = (dans ℤ∕mℤ). Alors a se décompose sous la forme

a = pαqβb, α,β ∈ ℕ, b ∧ (pq) = 1.

Alors

α β x = a�= (�p) (�q)�b.

On a vu que vérifie (⋆) et donc, d’après ce qui a été dit concernant le produit d’éléments vérifiant (⋆), ( )^α vérifie (⋆).
De même, ( )^β vérifie (⋆).
Enfin, comme b ∧ (pq) = 1, (ℤ∕mℤ), et vérifie (⋆).

Conclusion : x s’écrit comme produit d’éléments vérifiant (⋆), ce qui prouve que x vérifie lui même cette relation, c’est à dire que x^ed = x dans ℤ∕mℤ. □

Version pdf de ce document : cliquez ici

Retour à l'article des Mathématiques