RSA : Génération des Clés

• Le destinatire choisit deux grands entiers premiers p et q de même taille, calcule leur produit n=pq ainsi que (p-1)(q-1)
  
  
• Il choisit alors au hasard un entier e premier avec (p-1)(q-1)
  
  
• Il utilise l’algorithme d’Euclide étendu pour calculer l’inverse de e modulo (p-1)(q-1) : ed mod (p-1)(q-1) = 1
  
  
• Il place n et e dans le domaine public (constituent sa clé publique), conserve secrètement d (sa clé privée) et éventuellement détruit toute trace de p et q
  

Chiffrement / Déchiffrement

Chiffrement :

• L'émetteur récupère la clé publique (n,e) du destinataire
  
  
• Le message clair (chaîne de bits) est tronçonné en paquets représentables par des nombres compris entre 0 et n-1
  
  
• Pour chiffrer un paquet m du message, il calcule c=m^e mod n qui est le paquet chiffré

Déchiffrement :

• Le destinataire récupère c et pour déchiffrer calcule simplement c^d mod n qui vaut m (preuve ci-après)
  

Note : les calculs de m^e mod n et c^d mod n nécessitent l'utilisation de l'algorithme d'exponentiation rapide