Démonstration RSA
Génération du bi-clé- Choix de deux premiers : p = 487 & q = 491 => pgcd(487,491) = 1
- Calcul du module : n = p x q = 487 x 491 = 239117
- Indicatrice d'Euler : φ(n) = (p - 1) x (q - 1) = 238140
- Exposant chiffrement : e = 11 => pgcd(e,φ(n)) = 1
- Exposant déchiffrement : d x e = 1 mod φ(n) & d < φ(n)
216491 x 11 = 2381400 + 1 => d = 216491 - Clé publique : KPub = { 000011, 239117 }
- Clé privée : KPrv = { 216491, 239117 }
Exemple d'utilisation- Algorithme : Enc = Dec11 mod 239117 <=> Dec = Enc216491 mod 239117
- Message secret : texte clair = Cédric Clément (taille = 24 octets en UTF-8)
- 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
- Chiffrement : cryptogramme = 2e6a0:2f3df:2e811:19c0:30ef7:30ef7:30721:1ad28:17cf3:22bac:b01d:1e303:2e6a0:10381:2f3df:2e811:19c0:30ef7:30ef7:30721:12596:1ef3b:286c9:16e5d
- Déchiffrement : texte clair = Cédric Clément
Cassage par force brute- Méthode #1 via racine : p < √n & n mod p = 0
- Méthode #2 via Fermat : x² - y² = (x + y)(x - y)
- Factorisation module 1 : p = 491 & q = 487
- Factorisation module 2 : p = 491 & q = 487
- Obtention clé publique : KPub = { 000011, 239117 }
- Déduction clé privée 1 : KPrv = { 216491, 239117 }
- Déduction clé privée 2 : KPrv = { 216491, 239117 }
- Temps crackage racine : 0.000022 secondes
- Temps crackage Fermat : 0.000019 secondes
Article Wikipedia