Chiffrement par blocs à clé publique : RSA

• Pour l’algorithme RSA (Rivest, Shamir, Adleman), le problème posé par la cryptanalyse est supposé de même difficulté que la factorisation

• Dans l’état de l’art de 1999, on parvient à factoriser des nombres de 155 digits en environ 3 mois avec un effort global de quelques milliers de Mips*année :

   109417386415705274218097073220403576120
   037329454492059909138421314763499842889
   347847179972578912673324976257528997818
   33797076537244027146743531593354333897 
=
   102639592829741105772054196573991675900
   716567808038066803341933521790711307779
x
   106603488380168454820927220360012878679
   207958575989291522270608237193062808643

• Un entier a est inversible modulo un autre entier b <=> a et b premiers entre eux.

• Inverse efficacement déterminé par l’algorithme d’Euclide étendu (qui donne pgcd(a,b) et deux entiers u et v tels que au+bv=pgcd). L’inverse de a modulo b et donc u mod b

• (Petit) théorème de Fermat : Si p est premier, alors pour tout entier a non multiple de p : a_p-1 mod p = 1

• Algorithme d’exponentiation rapide : Calcul de ap mod m pour des grands entiers : calculer de proche en proche la suite des a²ⁱmod m, représenter p en binaire, p : c_nc_n-1 ... c₀, calculer enfin de proche en proche :