Démonstration RSA

Génération du bi-clé
  1. Choix de deux premiers : p = 673 & q = 677 => pgcd(673,677) = 1
  2. Calcul du module : n = p x q = 673 x 677 = 455621
  3. Indicatrice d'Euler : φ(n) = (p - 1) x (q - 1) = 454272
  4. Exposant chiffrement : e = 5 => pgcd(e,φ(n)) = 1
  5. Exposant déchiffrement : d x e = 1 mod φ(n) & d < φ(n)
    181709 x 5 = 908544 + 1 => d = 181709
  6. Clé publique : KPub = { 000005, 455621 }
  7. Clé privée : KPrv = { 181709, 455621 }
Exemple d'utilisation
  1. Algorithme : Enc = Dec5 mod 455621 <=> Dec = Enc181709 mod 455621
  2. Message secret : texte clair = Cédric CLEMENT (taille = 19 octets en UTF-8)
  3. Représentation : hexadécimale = 43:26:23:32:33:33:3b:64:72:69:63:20:43:4c:45:4d:45:4e:54
  4. Chiffrement : cryptogramme = 1d514:64c3f:1ea14:618ff:1d55a:1d55a:d6a6:7654:e281:65832:2bb2b:47cd3:1d514:6de54:5306d:60899:5306d:57d20:68f3e
  5. Déchiffrement : texte clair = Cédric CLEMENT
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 = 677 & q = 673
  4. Factorisation module 2 : p = 677 & q = 673
  5. Obtention clé publique : KPub = { 000005, 455621 }
  6. Déduction clé privée 1 : KPrv = { 181709, 455621 }
  7. Déduction clé privée 2 : KPrv = { 181709, 455621 }
  8. Temps crackage racine : 0.000023 secondes
  9. Temps crackage Fermat : 0.000018 secondes
Article Wikipedia