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 :
- Bob engendre deux grands nombres premiers p et q (test de primalité).
- Bob calcule n = p q donc ɸ(n) = (p-1)(q-1), ɸ indicateur d’Euler.
- Bob choisit un nombre aléatoire b avec 1≤ b ≤ ɸ(n) tel que pgcd(b, ɸ(n) ) = 1.
- Bob calcule l’inverse de p modulo ɸ(n), noté e, c’est-à-dire : b*e ≡ 1 mod ɸ(n) (Algorithme d’Euclide généralisé).
- 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) :
- Si n est premier, alors ɸ(n) = n-1.
- Si m et n sont premiers entre eux, ɸ(m*n) = ɸ(m)* ɸ(n).
- Si m et n sont premiers, alors ɸ(m*n) = (m-1)*(n-1).
- Si a est inversible de En, alors a^ ɸ(n) ≡ 1 mod n.