Comment ça marche ?
On choisit deux premiers p et q, on calcule n = p q et φ(n) = (p − 1)(q − 1). L’exposant public e doit être premier avec φ(n) ; la clé privée d est son inverse modulo φ(n), obtenu par l’algorithme d’Euclide étendu. Un message m (entier inférieur à n) se chiffre en c = m^e mod n et se déchiffre en c^d mod n.
Démonstration pédagogique uniquement : les nombres sont limités à 100 000 et ne protègent rien. Voyez aussi l’exponentiation modulaire et l’indicatrice d’Euler.
Exemple de calcul
p = 61, q = 53 : n = 3 233, φ(n) = 3 120 ; avec e = 17, d = 2 753. Le message 65 se chiffre en 2 790 et se déchiffre en 65.
Questions fréquentes
Pourquoi e doit-il être premier avec φ(n) ?
Sinon e n’a pas d’inverse modulo φ(n) : aucune clé privée n’existe.
Peut-on utiliser ces clés ?
Non : de si petits nombres se factorisent instantanément. Les vraies clés utilisent des centaines de chiffres et un remplissage aléatoire.
Pourquoi le message doit-il être inférieur à n ?
Le calcul se fait modulo n : un message plus grand ne serait pas retrouvé.
Calculatrices associées
Voir toutes les calculatrices Mathématiques.
Méthodologie
n = pq ; φ = (p − 1)(q − 1) ; d = e⁻¹ mod φ ; c = m^e mod n ; m = c^d mod n.
Résultats indicatifs, fournis sans garantie. Ils ne remplacent pas l’avis d’un professionnel.