Les nombres premiers sont les entiers naturels p n’ayant pour diviseurs que 1 et p,

                                                 ou les entiers relatifs p n’ayant pour diviseurs que 1, - 1, p et - p.

Tout nombre entier se décompose sous la forme unique d’un produit de facteurs premiers.

Encyclopédie Microsoft® Encarta® 2002. © 1993-2001 Microsoft Corporation. Tous droits réservés.

Nous allons tenter de démontrer que le système RSA permet de retrouver le message original, après chiffrement et déchiffrement, c'est-à-dire x^ed = x [n] avec x le message sous forme de chiffres et n = pq.

Méthode utilisant une conjecture personnelle venue en premier :

Soit x un entier naturel quelconque

Soient p et q deux entiers naturels distincts quelconques très grands

On a x < p et x < q car p et q sont très grands

Si p est premier,

d'après le petit théorème de Fermat, x^(p-1) = 1 [p]

Si q est premier,

d'après le petit théorème de Fermat, x^(q-1) = 1 [q]

On a ainsi (x^(p-1))^(q-1) = 1 [q]

              et (x^(q-1))^(p-1) = 1 [p]

<=> x^(p-1)(q-1) = 1 [q] = 1 [p]

Nous pouvons en déduire que x^(p-1)(q-1) = 1 [pq]

car p et q sont premiers et que l'on utilise (p-1)(q-1) en exposant de x

(aucun contre-exemple n'a été trouvé à ce jour)

Soit e et d  des entiers naturels tels que ed = 1 [(p-1)(q-1)]

On a x*x^k(p-1)(q-1) = x^ed avec k un entier relatif tel que ed = k (p-1)(q-1) + 1

Par produit, x^ed = x*1 = x [pq]

CQFD

Méthode utilisant le théorème d'Euler venue par la suite :

Si n est un entier supérieur ou égal à 2, phy(n) représente le nombre d'entiers compris entre 1 et n inclus, et premiers avec n.

Ainsi si n est premier, phy(n)  = n-1

Si n = pq avec p et q premiers, alors phy(n) = (p-1)(q-1)

Soit x, un entier naturel et n un entier naturel supérieur ou égal à 2,

le théorème d'Euler affirme que x^phy(n) = 1 [n]

Dans le cas du RSA, ed = 1 [phy(n)]

donc x^ed = x*x^phy(n) [n] = x*1 [n] = x [n]

Après chiffrement, x devient x^e.

Après déchiffrement, x^e devient x^ed.

On retrouve bien x, puisque x^ed = x [n]