Démonstration RSA

Génération du bi-clé
  1. Choix de deux premiers : p = 733 & q = 739 => pgcd(733,739) = 1
  2. Calcul du module       : n = p x q = 733 x 739 = 541687
  3. Indicatrice d'Euler    : φ(n) = (p - 1) x  (q - 1) = 540216
  4. Exposant chiffrement   : e = 5 => pgcd(e,φ(n)) = 1
  5. Exposant déchiffrement : d x e = 1 mod φ(n) & d < φ(n)
                             432173 x 5 = 2160864 + 1 => d = 432173
  6. Clé publique           : KPub = { 000005, 541687 }
  7. Clé privée             : KPrv = { 432173, 541687 }
Exemple d'utilisation
  1. Algorithme     : Enc = Dec5 mod 541687 <=> Dec = Enc432173 mod 541687
  2. Message secret : texte clair  = Cédric Clément (taille = 24 octets en UTF-8)
  3. Représentation : hexadécimale = 43:26:23:32:33:33:3b:64:72:69:63:20:43:6c:26:23:32:33:33:3b:6d:65:6e:74
  4. Chiffrement    : cryptogramme = 3adcf:24582:7eef3:77360:7d13f:7d13f:6b36a:6fcfc:674b8:1f4da:aa07:7ce25:3adcf:519d:24582:7eef3:77360:7d13f:7d13f:6b36a:278d1:46a2f:31c1b:af26
  5. Déchiffrement  : texte clair  = Cédric Clément
Cassage par force brute
  1. Méthode #1 via racine  : p < √n & n mod p = 0
  2. Méthode #2 via Fermat  : x² - y² = (x + y)(x - y)
  3. Factorisation module 1 : p = 739 & q = 733
  4. Factorisation module 2 : p = 739 & q = 733
  5. Obtention clé publique : KPub = { 000005, 541687 }
  6. Déduction clé privée 1 : KPrv = { 432173, 541687 }
  7. Déduction clé privée 2 : KPrv = { 432173, 541687 }
  8. Temps crackage racine  : 0.000044 secondes
  9. Temps crackage Fermat  : 0.000040 secondes
Article Wikipedia