Cours complet
Arithmétique pour RSA & Méthode RSA
Votre Nom
11 octobre 2025
Table des matières
1 Rappels d’arithmétique : les bases de RSA 2
1.1 Divisibilité et nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Division euclidienne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 PGCD et algorithme d’Euclide . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 Bézout et inverse modulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.5 Indicatrice d’Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.6 Petit théorème de Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.7 Théorème d’Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 La méthode RSA 3
2.1 Principe général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Génération des clés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3 Chiffrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.4 Déchiffrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.5 Signature numérique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3 Exemple détaillé 3
4 Exercices 4
5 Corrigés 4
6 Conclusion 4
1
1 Rappels d’arithmétique : les bases de RSA
1.1 Divisibilité et nombres premiers
Définition
Un entier p ≥ 2 est premier si ses seuls diviseurs positifs sont 1 et p.
1.2 Division euclidienne
Pour tous a, b ∈ N, b ̸= 0, il existe un unique couple (q, r) tel que
a = bq + r, 0 ≤ r < b.
1.3 PGCD et algorithme d’Euclide
Algorithme d’Euclide
Pour a ≥ b ≥ 1 on pose r0 = a, r1 = b, puis
rk+1 = rk−1 mod rk
jusqu’à rk = 0 ; le pgcd est l’avant-dernier reste non nul.
1.4 Bézout et inverse modulaire
Théorème de Bézout
Pour tous a, b ∈ Z il existe u, v ∈ Z tels que
au + bv = gcd(a, b).
Si gcd(a, n) = 1, l’équation ax ≡ 1 (mod n) possède une unique solution x ∈ 0, n − 1 :
l’inverse modulaire de a modulo n, noté a−1 mod n.
1.5 Indicatrice d’Euler
Définition
ϕ(n) est le nombre d’entiers k ∈ 1, n premiers avec n.
Propriétés :
— Si p premier, ϕ(p) = p − 1.
— Si p, q premiers distincts, ϕ(pq) = (p − 1)(q − 1).
1.6 Petit théorème de Fermat
Fermat
Si p premier et a ̸≡ 0 (mod p), alors
ap−1 ≡ 1 (mod p).
2
1.7 Théorème d’Euler
Euler
Si gcd(a, n) = 1, alors
aϕ(n) ≡ 1 (mod n).
2 La méthode RSA
2.1 Principe général
— Clé publique : (e, n)
— Clé privée : (d, n)
— Relation : ed ≡ 1 (mod ϕ(n))
2.2 Génération des clés
1. Choisir deux grands nombres premiers p et q (secrets).
2. Calculer n = pq (public) et ϕ(n) = (p − 1)(q − 1) (secret).
3. Choisir e tel que 1 < e < ϕ(n) et gcd(e, ϕ(n)) = 1.
4. Calculer d = e−1 mod ϕ(n).
2.3 Chiffrement
Pour un message M ∈ 0, n − 1 :
C = M e mod n.
2.4 Déchiffrement
M = C d mod n.
2.5 Signature numérique
On signe le hash h du message :
— Signature : s = hd mod n
?
— Vérification : h = se mod n
3 Exemple détaillé
Paramètres petits (didactiques) :
— p = 3, q = 11
— n = 33, ϕ(n) = 20
— Choix e = 3 (premier avec 20)
— d = 7 car 3 × 7 = 21 ≡ 1 (mod 20)
Message M = 5 :
— Chiffrement : C = 53 mod 33 = 125 mod 33 = 26
— Déchiffrement : 267 mod 33 = 5 (vérification immédiate)
3
4 Exercices
Exercice 1
Données : p = 5, q = 11, e = 3, message M = 7.
Effectuer toutes les étapes de génération de clés, chiffrement et déchiffrement.
Exercice 2
Données : p = 7, q = 13, e = 5, message M = 10.
Même consigne.
5 Corrigés
Corrigé 1
— n = 55, ϕ(n) = 40, d = 27
— C = 73 mod 55 = 343 mod 55 = 13
— 1327 mod 55 = 7
Corrigé 2
— n = 91, ϕ(n) = 72, d = 29
— C = 105 mod 91 = 82
— 8229 mod 91 = 10
6 Conclusion
RSA est un pilier de la cryptographie moderne ; sa sécurité repose sur la difficulté de factoriser
n = pq. En pratique :
— p, q doivent être grands ( 1024 bits chacun, soit n ≥ 2048 bits).
— Ne jamais réutiliser des exposants faibles.
— Toujours utiliser un padding adapté (OAEP) en chiffrement et (PSS) en signature.