1. Introduction — Pourquoi le Chiffrement Asymétrique ?
En chiffrement symétrique, Alice et Bob doivent se mettre d'accord sur une clé secrète avant de communiquer. Mais comment échanger cette clé de façon sécurisée si leur canal de communication n'est pas encore sécurisé ? C'est le problème de la distribution des clés.
Si Alice envoie la clé à Bob via Internet et qu'un attaquant (Eve) l'intercepte, toutes les communications futures sont compromises.
┌─────────────────────────────────────────────────────────┐ │ BOB │ │ Génère une PAIRE de clés : │ │ ┌──────────────────┐ ┌──────────────────┐ │ │ │ Clé PUBLIQUE Kp │ │ Clé PRIVÉE Ks │ │ │ │ (diffusée à │ │ (gardée SECRET │ │ │ │ tout le monde) │ │ uniquement par │ │ │ └──────────────────┘ │ Bob) │ │ │ └──────────────────┘ │ └─────────────────────────────────────────────────────────┘ ALICE veut envoyer M à Bob : ① Alice récupère la clé publique Kp de Bob (publique → pas de risque) ② Alice chiffre : C = E(M, Kp) ③ Alice envoie C à Bob ④ Bob déchiffre : M = D(C, Ks) ← seul Bob peut faire ça ! Eve intercepte C mais ne peut pas déchiffrer sans Ks. ✓ MODE SIGNATURE (inversé) : ① Bob signe avec sa clé PRIVÉE : S = Sign(M, Ks) ② Alice vérifie avec la clé PUBLIQUE de Bob : Verify(S, Kp) ③ Garantie : seul Bob a pu créer S (non-répudiation).
On chiffre avec la clé publique du destinataire, il déchiffre avec sa clé privée.
→ Garantit que seul le destinataire peut lire le message.
→ Alice chiffre avec Kp(Bob), Bob déchiffre avec Ks(Bob).
On signe avec sa propre clé privée, tout le monde vérifie avec la clé publique.
→ Garantit l'authenticité et la non-répudiation.
→ Bob signe avec Ks(Bob), Alice vérifie avec Kp(Bob).
Le chiffrement asymétrique repose sur des problèmes mathématiques faciles dans un sens et computationnellement infaisables dans l'autre :
RSA : Factoriser un grand nombre en ses facteurs premiers (ex: n = p × q) est très difficile si p et q sont grands.
Diffie-Hellman / El Gamal : Calcul du logarithme discret — facile de calculer g^a mod n, mais très difficile de retrouver a connaissant g^a mod n.
2. L'Algorithme RSA — Principe
RSA a été inventé en 1977 par Ron Rivest, Adi Shamir et Leonard Adleman au MIT. C'est le premier algorithme de chiffrement à clé publique pratique. Sa sécurité repose sur la difficulté de factoriser de grands entiers. RSA est toujours utilisé aujourd'hui (TLS, SSH, signatures numériques).
C'est grâce au théorème d'Euler : si pgcd(M, n) = 1, alors M^φ(n) ≡ 1 (mod n).
Puisque e·d ≡ 1 mod φ(n), on a e·d = k·φ(n) + 1 pour un certain entier k.
Donc C^d = (M^e)^d = M^(e·d) = M^(k·φ(n)+1) = (M^φ(n))^k · M ≡ 1^k · M = M (mod n) ✓
3. Génération des Clés RSA — Étapes Détaillées
La génération de clés RSA suit un algorithme précis en 4 étapes. Chaque étape est cruciale et peut faire l'objet d'une question d'examen.
ÉTAPE 1 — Choisir deux grands nombres premiers p et q → p et q doivent être distincts et suffisamment grands (≥ 512 bits en pratique) → Calculer n = p × q (le modulus, public) ÉTAPE 2 — Calculer φ(n) (indicatrice d'Euler) → φ(n) = (p − 1) × (q − 1) [formule fondamentale pour n=pq] → φ(n) est le nombre d'entiers entre 1 et n qui sont premiers avec n ÉTAPE 3 — Choisir e (exposant de chiffrement) → e doit vérifier : 1 < e < φ(n) et pgcd(e, φ(n)) = 1 → e doit être premier avec φ(n) (pour qu'un inverse modulaire existe) → En pratique, e = 65537 = 2^16 + 1 (valeur standard) ÉTAPE 4 — Calculer d (exposant de déchiffrement) → d est l'inverse modulaire de e modulo φ(n) → d tel que : e × d ≡ 1 (mod φ(n)) → Autrement dit, il existe un entier k : d = (1 + k×φ(n)) / e RÉSULTAT : Clé publique KA = (e, n) ← diffusée à tous Clé privée KB = (d, n) ← gardée secrète
Pour calculer a^n mod m avec un grand n, on décompose n en binaire :
Ex : 65 en binaire = 1000001₂
a^65 = a^(2^6 + 2^0) = a^64 × a^1
On calcule en répétant : au carré → mod m → au carré → mod m...
Cette technique réduit considérablement le nombre d'opérations.
Sur l'examen : Si les exposants sont petits, calcul direct. Si grands, on peut appliquer les propriétés des congruences ou utiliser les valeurs intermédiaires.
4. Conditions de Validité et Propriétés RSA
① p et q doivent être premiers — sinon φ(n) = (p-1)(q-1) n'est plus valide.
② e doit véifier pgcd(e, φ(n)) = 1 — pour que l'inverse d existe.
③ M doit vérifier M < n — le message doit être plus petit que le modulus n.
④ pgcd(M, n) = 1 — le message doit être premier avec n (toujours vrai si M < p,q).
⑤ Le couple (e,d) doit vérifier e×d ≡ 1 (mod φ(n)) — condition de déchiffrement correct.
Un couple (e, d) est valide pour RSA si et seulement si : e × d ≡ 1 (mod φ(n)). On vérifie en calculant (e × d) mod φ(n) — le résultat doit être 1.
Pour n = 159 = 3 × 53 → φ(n) = (3-1)(53-1) = 2 × 52 = 104
Un couple (kc, kd) est valide si : kc × kd ≡ 1 (mod 104)
On vérifie : (kc × kd) mod 104 = 1 ?
→ Si oui : couple valide ✓
→ Si non : couple invalide ✗
Autre vérification : kc doit vérifier pgcd(kc, 104) = 1 (sinon pas d'inverse → invalide).
mais ne peut
pas déchiffrer
5. Protocole Diffie-Hellman
Diffie-Hellman n'est pas un algorithme de chiffrement à proprement parler — c'est un protocole d'échange de clés. Il permet à Alice et Bob de générer un secret commun via un canal non sécurisé, sans jamais s'être rencontrés auparavant. Ce secret commun peut ensuite être utilisé comme clé pour un chiffrement symétrique.
Alice et Bob se mettent d'accord publiquement sur :
- n (ou p dans certaines notations) : un grand nombre premier
- g : un entier (générateur, base) avec 1 < g < n
PARAMÈTRES PUBLICS : (n, g)
(connus d'Alice, Bob et Eve)
ALICE BOB
│ │
Choisit a secret Choisit b secret
(1 ≤ a ≤ n-1) (1 ≤ b ≤ n-1)
│ │
Calcule A = g^a mod n Calcule B = g^b mod n
│ │
│──────────────── A ──────────────────────►│
│◄─────────────── B ────────────────────── │
│ │
Calcule K = B^a mod n Calcule K = A^b mod n
│ │
K = (g^b)^a mod n = g^(ab) mod n K = (g^a)^b mod n = g^(ab) mod n
│ │
└───────────── MÊME CLÉ K ! ───────────────┘
EVE voit : n, g, A = g^a mod n, B = g^b mod n
Pour trouver K, Eve doit résoudre le LOGARITHME DISCRET
(trouver a tel que g^a ≡ A mod n) → computationnellement infaisable !
DH est vulnérable à une attaque de l'homme du milieu : Eve peut intercepter A et B, et établir un secret différent avec Alice et un autre avec Bob. Ni Alice ni Bob ne savent qu'Eve est au milieu.
Solution : Combiner DH avec une authentification (certificats numériques, RSA pour signer A et B) → Protocole Authenticated Diffie-Hellman.
6. Chiffrement El Gamal (1985)
El Gamal, inventé par Taher ElGamal en 1985, est un algorithme de chiffrement asymétrique basé sur le problème du logarithme discret (comme Diffie-Hellman). Contrairement à RSA, El Gamal produit un chiffré deux fois plus long que le message original.
- Choisir p premier, et deux entiers s et a tels que : 2 ≤ s ≤ p-2 et 0 ≤ a ≤ p-1
- Calculer P = a^s mod p
- Clé publique = (p, a, P)
- Clé privée = s (l'entier secret)
Alice veut envoyer M à Bob (M < p). Elle choisit un entier aléatoire k et calcule :
Le message chiffré est la paire (C₁, C₂).
Bob reçoit (C₁, C₂). Il calcule :
RSA : Sécurité basée sur la difficulté de factoriser n. Chiffré de même taille que M.
El Gamal : Sécurité basée sur la difficulté du logarithme discret. Chiffré de taille double (paire C₁, C₂).
Diffie-Hellman : Échange de clés uniquement (pas de chiffrement direct), basé sur le logarithme discret.
7. Comparatif : Symétrique vs Asymétrique
| Critère | Chiffrement Symétrique (AES) | Chiffrement Asymétrique (RSA) |
|---|---|---|
| Nombre de clés | 1 clé partagée | 2 clés : publique + privée |
| Distribution des clés | ⚠️ Problème difficile | ✅ La clé publique peut être partagée librement |
| Vitesse | ⚡ Très rapide (100-1000x) | 🐢 Lent (opérations modulo sur grands nombres) |
| Taille de clé typique | 128, 256 bits | 2048, 4096 bits |
| Non-répudiation | ❌ Non (les deux parties ont la même clé) | ✅ Oui (seul le propriétaire a la clé privée) |
| Usage typique | Chiffrement de données volumineuses | Échange de clés, signatures, certificats |
| Sécurité repose sur | Propriétés des algorithmes (confusion/diffusion) | Problèmes mathématiques difficiles (factorisation, log discret) |
| Algorithmes | DES, 3DES, AES, RC4 | RSA, El Gamal, ECC, Diffie-Hellman |
En pratique, on combine les deux approches pour bénéficier des avantages de chacune :
① Alice génère une clé symétrique aléatoire K (clé de session)
② Alice chiffre K avec la clé publique RSA de Bob → envoie à Bob
③ Bob déchiffre K avec sa clé privée RSA → obtient la clé de session
④ Alice et Bob chiffrent leurs messages avec K (AES) → rapide et sécurisé
C'est exactement ce que font TLS/HTTPS, SSH, etc.
Si n = p (premier) : φ(n) = p - 1
Si n = p^k : φ(n) = p^(k-1) × (p-1)
Si n = p × q (p,q premiers distincts) : φ(n) = (p-1)(q-1) ← cas RSA
Propriété multiplicative : Si pgcd(m,n)=1 alors φ(mn) = φ(m)φ(n)
Exemple : n = 159 = 3 × 53
→ φ(159) = (3-1)(53-1) = 2 × 52 = 104
Entrez deux nombres premiers p et q pour générer vos clés RSA, puis chiffrez/déchiffrez un message. Attention : p et q doivent être premiers et distincts.
- Calculer le nombre d'Euler φ(n) et donner les facteurs premiers de n.
- Dans la liste des couples de clés (kc, kd) ci-dessous, trouver les couples ne vérifiant PAS le principe du RSA en justifiant : (7, 15), (9, 81), (5, 125), (33, 43), (3, 139), (23, 95)
Partie 1 : Factorisation de n = 159 et calcul de φ(n)
Partie 2 : Vérification des couples (kc, kd)
Un couple est valide RSA si et seulement si : kc × kd ≡ 1 (mod 104), c'est-à-dire (kc × kd) mod 104 = 1.
De plus, kc doit vérifier pgcd(kc, 104) = 1.
Conclusion : Le couple (33, 43) ne vérifie pas le principe RSA car 33 × 43 mod 104 = 67 ≠ 1. Pour que le déchiffrement fonctionne, il faut absolument que kc × kd ≡ 1 (mod φ(n)).
- Quel est le chiffrement avec cette clé du message m = 100 ?
- Calculer la clé privée d correspondant à e = 11
- Déchiffrer le message c = 133
- Le message codé 625 peut-il résulter d'un codage avec la clé publique ? Même question avec la clé privée.
QCM — Chapitre 3 : Chiffrement Asymétrique
15 questions techniques — Correction immédiate avec explication détaillée.