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.
Anonyme

Auteur/autrice : Victor

Ingénieur en informatique de formation et de métier, j’administre ce serveur et son domaine et privilégie l'utilisation de logiciels libres au quotidien. Je construis progressivement mon "cloud" personnel service après service pour conserver un certain contrôle sur mes données numériques.

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *