🔒 Encyclopédie Cryptographique : Algorithme RSA
Guide technique ultra-densifié : Mathématiques, Génération de Clés, Chiffrement, Signatures & Sécurité.
Concept : Crypto Asymétrique
Principe des clés publiques/privées. Le problème de l'échange de clés symétriques.
PKISens UniqueMathématiques : Arithmétique Modulaire
Nombres premiers, Indicatrice d'Euler (φ), PGCD, Inverse modulaire. La base du chiffrement.
ModuloNombres PremiersLe Mécanisme : Fonction à Trappe
Facile à calculer dans un sens (multiplication), impossible à inverser sans la trappe (factorisation).
FactorisationComplexitéGénération des Clés (Algorithme)
Etape par étape : choix de p,q. Calcul de n, φ(n), e, d. Construction des paires.
e (Publique)d (Privée)Chiffrement & Déchiffrement
Les formules mathématiques fondamentales. Comment M est transformé en C, et inversement.
C = M^e mod nExponentiationAuthenticité : Signatures Numériques
Inversion du processus : chiffrer avec la clé privée pour prouver l'origine et l'intégrité.
Non-RépudiationHachageImplémentation : Le Padding (OAEP)
Pourquoi le RSA "pur" (textbook) est dangereux. Rôle du padding pour introduire de l'aléa.
OAEPSécurité SémantiqueAttaques & Menaces
Factorisation de n, attaques par clé commune, attaques par canal auxiliaire, informatique quantique.
GNFSShorRecommandations : Tailles de Clés
Évolution de la puissance de calcul vs longueur de n. Équivalences de sécurité (NIST).
2048 bits4096 bitsUsage Réel : Cryptographie Hybride
Pourquoi RSA n'est pas utilisé pour chiffrer des fichiers. Combinaison avec AES (SSL/TLS).
Key ExchangePerformanceLe Problème de la Crypto Symétrique
Dans la cryptographie symétrique (ex: AES), la même clé est utilisée pour chiffrer et déchiffrer. Si Alice veut envoyer un message à Bob, ils doivent s'être mis d'accord sur la clé auparavant via un canal sécurisé. C'est le problème majeur de la distribution des clés à grande échelle sur Internet.
La Révolution Asymétrique (Diffie-Hellman, RSA)
Inventée dans les années 70, elle utilise deux clés mathématiquement liées mais différentes :
- Clé Publique (Public Key) : Peut être distribuée ouvertement à n'importe qui (publiée dans un annuaire). Elle sert à Chiffrer les messages ou à Vérifier des signatures.
- Clé Privée (Private Key) : Doit rester absolument secrète par son propriétaire. Elle sert à Déchiffrer les messages reçus ou à Signer des documents.
L'Analogie de la Boîte aux Lettres
- N'importe qui peut glisser une lettre dans la fente d'une boîte aux lettres (la clé publique est la fente accessible à tous).
- Seul le propriétaire de la boîte possède la clé physique pour l'ouvrir et lire les lettres (la clé privée).
Les Fonctions Mathématiques à Trappe
La sécurité repose sur l'existence de fonctions mathématiques faciles à calculer dans un sens, mais très difficiles à inverser sans une information cachée (la "trappe"). Dans RSA, cette trappe est la connaissance de la factorisation d'un grand nombre.
RSA repose sur des concepts d'arithmétique modulaire et de théorie des nombres. Sans ces bases, l'algorithme est incompréhensible.
1. Nombres Premiers
Un nombre entier > 1 qui n'a pour diviseurs que 1 et lui-même (ex: 2, 3, 5, 7, 11, 13, 17...). RSA utilise deux très grands nombres premiers aléatoires, $p$ et $q$.
2. Arithmétique Modulaire (Modulo)
C'est "l'arithmétique de l'horloge". Le résultat de $a \pmod{n}$ est le reste de la division entière de $a$ par $n$.
Exemple: $17 \pmod{5} = 2$.
Toutes les opérations RSA se font à l'intérieur d'un ensemble fini défini par un module $n$.
3. Nombre Premier entre eux (Coprimes)
Deux nombres $a$ et $b$ sont premiers entre eux si leur PGCD (Plus Grand Commun Diviseur) est égal à 1.
Exemple: PGCD(8, 9) = 1, ils sont coprimes.
4. Fonction Indicatrice d'Euler (φ)
Pour un nombre $n$, $\varphi(n)$ est le nombre d'entiers entre 1 et $n$ qui sont premiers avec $n$.
Propriété clé pour RSA : Si $n = p \times q$ (où $p, q$ sont premiers), alors :
φ(n) = (p - 1) * (q - 1)
5. Inverse Modulaire
L'inverse de $e$ modulo $\varphi(n)$ est un nombre $d$ tel que :
(e * d) ≡ 1 mod φ(n)
Cela signifie que $(e \times d)$ divisé par $\varphi(n)$ donne un reste de 1. $d$ se calcule via l'Algorithme d'Euclide Étendu.
Les Étapes de Création
- Choisir deux grands nombres premiers distincts, $p$ et $q$ (aléatoires, secrètes, ex: 1024 bits chacun).
- Calculer le module $n$ : $n = p \times q$. ($n$ est public, sa taille définit la longueur de la clé).
- Calculer l'indicatrice d'Euler $\varphi(n)$ : $\varphi(n) = (p-1) \times (q-1)$. (secrète).
- Choisir l'exposant public $e$ tel que :
- $1 < e < \varphi(n)$
- PGCD($e$, $\varphi(n)$) = 1 (coprime avec $\varphi(n)$).
- (Souvent, $e = 65537$ est utilisé pour des raisons de performance).
- Calculer l'exposant privé $d$ : Il doit être l'inverse modulaire de $e$ modulo $\varphi(n)$. C'est-à-dire trouver $d$ tel que :
d ≡ e⁻¹ mod φ(n)
Les Paires de Clés Finales
| Clé | Composition | Visibilité |
|---|---|---|
| Clé Publique | Paire $(e, n)$ | Publique |
| Clé Privée | Paire $(d, n)$ (ou $(d, p, q)$ pour optimiser) | Secrète |
Exemple Mathématique (Petits Nombres)
Les opérations sont des exponentiations modulaires. Le message $M$ doit être converti en un nombre entier tel que $0 \le M < n$ (grâce au padding).
1. Chiffrement (par Alice)
Alice possède la clé publique de Bob $(e, n)$. Elle veut envoyer $M$.
Elle calcule le message chiffré $C$ :
Alice envoie $C$ à Bob via Internet.
2. Déchiffrement (par Bob)
Bob reçoit $C$. Il utilise sa clé privée secrète $(d, n)$.
Il recalcule le message original $M$ :
$C^d \pmod{n} = (M^e)^d \pmod{n} = M^{e \times d} \pmod{n}$.
Or, par construction, $e \times d \equiv 1 \pmod{\varphi(n)}$. Grâce au Petit Théorème de Fermat (ou Théorème d'Euler), on peut prouver que $M^{e \times d} \equiv M \pmod{n}$.
Exemple (suite de la modale 2.1)
Message $M = 65$ (ASCII 'A'). Clé Publique $(17, 3233)$. Clé Privée $(2753, 3233)$.
- Chiffrement : $C = 65^{17} \pmod{3233} = 2790$.
- Déchiffrement : $M = 2790^{2753} \pmod{3233} = 65$. Le message 'A' est récupéré.
Le processus RSA est réversible : on peut "chiffrer" avec la clé privée. Comme la clé privée est unique et secrète, cela prouve mathématiquement l'origine (authenticité) et garantit que le message n'a pas été modifié (intégrité).
Processus de Signature (Alice signe)
- Alice crée son message $M$.
- Elle applique une fonction de hachage (ex: SHA-256) pour obtenir une empreinte unique : $H = Hash(M)$.
- Elle "chiffre" le hash $H$ avec sa Clé Privée $d$ pour obtenir la signature $S$ :
S = H^d mod n - Alice envoie $(M, S)$ à Bob.
Processus de Vérification (Bob vérifie)
- Bob reçoit le document $M'$ et la signature $S$. (Le prime $M'$ car il ne sait pas s'il a été modifié).
- Il recalcule le hash de $M'$ : $H' = Hash(M')$.
- Il "déchiffre" la signature $S$ avec la Clé Publique d'Alice $e$ pour obtenir le hash original supposé $H_{original}$ :
H_original = S^e mod n - Il compare : SI $(H' == H_{original})$, ALORS la signature est valide.
Authenticité
Seule Alice possédait sa clé privée $d$. Personne d'autre n'aurait pu générer une signature $S$ qui se vérifie correctement avec sa clé publique $e$.
Intégrité
Si un attaquant modifie $M$ en $M_{fake}$, le hash $Hash(M_{fake})$ ne correspondra pas au hash extrait de la signature.
Non-Répudiation
Alice ne peut pas nier avoir signé le message (tant que sa clé privée n'a pas été compromise).
Pourquoi le RSA "Pur" (Textbook) est Dangereux
L'algorithme mathématique de base (Textbook RSA) décrit en 2.2 n'est pas sûr s'il est utilisé tel quel.
- Chiffrement Déterministe : Si vous chiffrez deux fois le même message $M$ (ex: "OUI") avec la même clé publique, vous obtiendrez le même chiffré $C$. Un attaquant peut construire un dictionnaire des messages courants.
- Faible exposant public $e$ : Si $e=3$ et $M$ est petit, $M^3 < n$, le module $n$ ne joue aucun rôle. Une simple racine cubique suffit à déchiffrer.
- Malléabilité : Un attaquant peut manipuler mathématiquement $C$ pour modifier $M$ de manière prévisible (ex: multiplier $M$ par 2) sans savoir déchiffrer.
La Solution : Le Padding (Remplissage)
Avant d'appliquer la formule $M^e \pmod{n}$, on applique une transformation au message $M$ pour le transformer en un bloc encodé $EM$ (Encoded Message).
Le padding moderne pour le chiffrement est **OAEP** (Optimal Asymmetric Encryption Padding).
Fonctionnement de RSA-OAEP
- Aléa (Aléatoire) : Il ajoute une chaîne de bits aléatoires au message original.
- Structure : Il structure le bloc selon un schéma précis.
- Hachage : Il utilise des fonctions de hachage et des XOR pour lier l'aléa au message.
Avantages de OAEP
- Sécurité Sémantique (IND-CCA) : OAEP rend le chiffrement **probabiliste**. Chiffrer deux fois "OUI" donnera deux résultats $C_1$ et $C_2$ totalement différents. Un attaquant ne peut tirer aucune information.
- Résistance aux attaques : Il empêche les attaques par malléabilité et les attaques à texte chiffré choisi.
- Intégrité : Le processus de dé-padding à la réception échouera si le bloc $EM$ a été corrompu d'un seul bit lors du transport.
1. Attaques sur la Factorisation (Mathématiques)
C'est l'attaque la plus directe : factoriser $n$ pour trouver $p$ et $q$, puis calculer la clé privée $d$.
- Algorithme : GNFS (General Number Field Sieve). C'est l'algorithme le plus efficace connu pour factoriser de grands entiers sur des ordinateurs classiques.
- Sa complexité est sous-exponentielle. Cela signifie que doubler la taille de la clé (ex: de 1024 à 2048 bits) augmente la difficulté de factorisation de manière bien plus que double.
- Record actuel (2020) : Factorisation de RSA-250 (un nombre de 829 bits). Il a fallu environ 2700 années-cœur de calcul. }
2. Attaques par Canal Auxiliaire (Side-Channel)
Ces attaques ne visent pas les maths, mais **l'implémentation physique** de l'algorithme sur un processeur.
- Timing Attacks : En mesurant très précisément le temps que met un serveur à déchiffrer, un attaquant peut déduire des bits de la clé privée (car l'exponentiation modulaire prend un temps légèrement différent selon que le bit de $d$ est 0 ou 1).
- Power Analysis : En mesurant la consommation électrique d'une carte à puce lors des calculs. }
Contre-mesures :
Les bibliothèques de crypto modernes utilisent le **Blinding** (aveuglement) : on multiplie temporairement le message par un nombre aléatoire avant de déchiffrer, pour masquer le calcul réel.
3. La Menace de l'Informatique Quantique
Les ordinateurs classiques sont mauvais pour factoriser. Les ordinateurs quantiques, grâce à leurs qubits et au phénomène de superposition, sont théoriquement excellents pour cela.
- L'Algorithme de Shor : C'est un algorithme quantique inventé en 1994 qui permet de factoriser un nombre $n$ en un temps **polynomial** (extrêmement rapide).
- Impact : Si un ordinateur quantique doté de plusieurs milliers de qubits stables (un "Cryptographically Relevant Quantum Computer") est construit un jour, RSA sera instantanément brisé, quelle que soit la taille de la clé (2048, 4096...).
- Solution : Post-Quantum Cryptography (PQC). L'industrie effectue actuellement une transition vers de nouveaux algorithmes (ex: Kyber) basés sur des problèmes mathématiques différents (les réseaux euclidiens) que même l'algorithme de Shor ne peut résoudre rapidement. }
Augmenter la taille du module $n$ renforce la sécurité face à la factorisation, mais augmente considérablement le coût en calcul (la crypto asymétrique est très lente).
| Taille du module n (bits) | Statut de Sécurité | Usage courant |
|---|---|---|
| 512 bits | BRISÉE (en quelques heures en 1999) | Aucun |
| 1024 bits | DÉCONSEILLÉE (Trop risquée face aux gouvernements/grands groupes) | Vieux systèmes Legacy |
| 2048 bits | SÛR (Standard actuel) (Jusqu'à environ 2030+) | SSL/TLS, Certificats Web |
| 4096 bits | TRÈS SÛR (Long terme) | Autorités de Certification, données critiques |
Équivalences de Sécurité NIST (bits de sécurité)
L'attaquant doit effectuer $2^X$ opérations pour briser la clé.
- AES-128 (Symétrique) = 128 bits de sécurité.
- Pour obtenir cette même sécurité avec RSA, il faut une clé de... 3072 bits.
- RSA-2048 n'offre que environ 112 bits de sécurité effective.
Le compromis Performance
- Le déchiffrement (avec $d$) est environ 10x plus lent sur une clé de 4096 bits par rapport à une clé de 2048 bits.
- C'est pourquoi l'industrie préfère RSA-2048 ou passe à la cryptographie sur les Courbes Elliptiques (ECC), qui offre la même sécurité pour des clés bien plus petites (256 bits ECC == 3072 bits RSA) et plus rapides.
Comparaison d'efficacité
RSA est **extrêmement lent** et peut chiffrer très peu de données (sa limite est la taille du module $n$, ex: < 245 octets pour RSA-2048/OAEP). AES est **très rapide** et peut chiffrer des Gigaoctets.
Le protocole Hybride (ex: SSL/TLS pour HTTPS)
On utilise l'asymétrique pour sécuriser l'échange, et le symétrique pour le volume.
- Phase d'Asymétrique (Lente, RSA) :
- Le client se connecte au serveur et récupère sa Clé Publique RSA (via le certificat).
- Le client génère une **"Clé de Session"** symétrique aléatoire (ex: clé AES-256 de 32 octets).
- Le client chiffre cette clé AES avec la Clé Publique RSA du serveur.
- Le client envoie la clé AES chiffrée au serveur. Seul le serveur peut la déchiffrer avec sa clé privée.
- Phase Symétrique (Rapide, AES) :
- Client et Serveur possèdent maintenant la même clé AES.
- Tout le reste de la communication (les pages HTML, images) est chiffré/déchiffré avec AES.
Authentification RSA
Dans HTTPS, la clé RSA du serveur est incluse dans un **Certificat X.509**. Ce certificat est lui-même signé numériquement (avec RSA) par une Autorité de Certification (ex: Let's Encrypt) en laquelle votre navigateur a confiance. Cela prouve que vous êtes sur le vrai site (`facebook.com`) et non un site attaquant.