Cryptographie RSA

Chiffrement RSA

Principe :

Si Bob désire que l’on puisse communiquer avec lui de façon secrète, il procède de la manière suivante :

1. Bob engendre deux grands nombres premiers p et q (test de primalité).
2. Bob calcule n = p q donc ɸ(n) = (p-1)(q-1), ɸ indicateur d’Euler.
3. Bob choisit un nombre aléatoire b avec 1≤ b ≤ ɸ(n) tel que pgcd(b, ɸ(n) ) = 1.
4. Bob calcule l’inverse de p modulo ɸ(n), noté e, c’est-à-dire : b*e ≡ 1 mod ɸ(n) (Algorithme d’Euclide généralisé).
5. Bob publie (n, b) (clef public) et garde e qui forme la clef secrète.

Fantasio veut envoyer un message M (M < n) à Bob, il calcule :

C = M^b mod n et envoi C à Bob.

Bob reçoit C et calcule : C^e mod n =M

 

Notions mathématiques :

Considérons l’ensemble suivant : En = {0, 1, 2, …, n-1}.

Théorème :

Soit a appartient à En, alors a est inversible ssi pgcd(a,n) = 1, c’est-à-dire, a et n sont premiers entre eux. Ainsi, si n est premier, alors chaque élément de En est inversible, sauf 0 .

Définition : Indicateur d’Euler noté ɸ.

Il indique le nombre d’élément inversible de En.

Propriétés de ɸ(n) :

1.  Si n est premier, alors ɸ(n) = n-1.
2. Si m et n sont premiers entre eux, ɸ(m*n) = ɸ(m)* ɸ(n).
3. Si m et n sont premiers, alors ɸ(m*n) = (m-1)*(n-1).
4. Si a est inversible de En, alors a^ ɸ(n) ≡ 1 mod n.