Attaque du chiffrement RSA à petit exposant privé et réalisation d'un algorithme de chiffrement et son application en code C

Algorithme de chiffrement asymétrique RSA :

1. Soit  n = p*q avec p et q deux nombres premiers distinct
2. Soit   φ (n)   = (p-1) (q-1)
3. Choisir un entier aléatoire  e, tel que 1< e <  φ (n) premier avec φ (n)
4. trouver d, tel que 1< d <  φ (n) : ed ≡ 1 [φ (n)]

Publier (e, n), comme clés publiques.

Tenir (d, n), comme clés privées.

C  =  m^e [n]

Déchiffrement :

m  ≡  c^d  [n]

Théorème :

Soit n =p * q et q<p<2q un produit de deux nombres premiers entre eux, et e un entier tel que : 1≤e≤φ (n) premier avec φ (n).
Si l'inverse d de e modulo n (d ≡ e^-1 [φ (n)]) est plus petit que 1/3 n^1/4 , alors il existe un algorithme qui à partir de (n,e) la donnée  on calcule rapidement d et donc aussi p et q.

Exemple :  

Soient n=85067, e=12997 et m=100, Développement en fraction continue :

      Donnera   

C  =  m^e [n]=11607

On commence le test : m  ≡  c^d  [n]

11607⁶  [85067] ≠100

11607⁷  [85067] ≠100

11607¹³  [85067]=100  d’où on a trouvé notre message et donc l’exposant privé : d= 13