Le RSA, c’est quoi ? #
RSA est un algorithme de cryptographie asymétrique : il utilise deux clés aux rôles distincts. La clé publique peut être diffusée pour chiffrer un message ou vérifier une signature, tandis que la clé privée reste secrète pour déchiffrer ou signer. Cet article part de la création de cette paire de clés, suit le trajet d’un message, puis montre comment certaines configurations ou utilisations incorrectes rendent RSA vulnérable.
La sécurité repose notamment sur la difficulté de factoriser un très grand entier. Avec des paramètres correctement choisis, retrouver la clé privée à partir de la clé publique est considéré comme infaisable en pratique.
Formules RSA #
Commençons par construire les clés. Les mêmes nombres serviront ensuite au chiffrement, au déchiffrement et aux signatures.
Création des clés #
- Choisir deux nombres premiers distincts, \(p\) et \(q\).
- Calculer le module \(n\) avec \(n = p*q\).
- Calculer \(\varphi(n) = (p-1)(q-1)\).
- Choisir un entier \(e\) premier avec \(\varphi(n)\), tel que \(1 < e < \varphi(n)\) : c’est l’exposant de chiffrement.
- Calculer \(d\) avec \(d = e^{-1} \pmod {\varphi(n)} \) et \(d < \varphi(n)\) : c’est l’exposant de déchiffrement.
La condition sur \(e\) garantit que son inverse modulo \(\varphi(n)\) existe. On obtient alors la clé publique \((n, e)\) et la clé privée \((n, d)\). Dans une implémentation réelle, la clé privée conserve généralement aussi \(p\) et \(q\), mais \((n, d)\) suffit pour comprendre les formules suivantes.
Chiffrement #
Une fois la clé publique créée, elle permet de transformer un message en texte chiffré. Si \(M \in \mathbb{N}\) et \(M < n\) représente ce message, le résultat est :
\[C = M^e \pmod n\]
Déchiffrement #
Le destinataire passe ensuite de \(C\) au message clair grâce à la clé privée. Avec \(d = e^{-1} \pmod {\varphi(n)}\), il calcule :
\[M = C^d \pmod n\]
Générer une signature #
La même paire de clés peut aussi prouver l’origine et l’intégrité d’un message. Dans ce modèle simplifié, on note \(h = hash(M)\), représenté par un entier inférieur à \(n\), puis on applique l’exposant privé \(d\) :
\[S = h^d \pmod n\]
Vérifier une signature #
Le vérificateur utilise alors la clé publique et applique \(e\) à \(S\) :
\[h’ = S^e \pmod n\]
Il vérifie ensuite que \(h’ = h\). En pratique, chiffrement et signature utilisent des schémas de remplissage sûrs : les formules ci-dessus décrivent le RSA « brut » afin d’en comprendre le mécanisme.
Quelques attaques simples #
Ces relations mathématiques supposent que les paramètres et l’utilisation de RSA sont corrects. Les exemples suivants montrent, pour chaque faiblesse, ce que l’on observe, la condition qui la rend exploitable et son effet.
\(n\) factorisable #
Constat : la clé publique expose le module \(n\). Condition : si ce module est assez petit ou composé de facteurs trop faciles à trouver, il devient factorisable ; le site factordb peut aider à vérifier des exemples connus. Effet : retrouver \(p\) et \(q\) permet de recalculer \(\varphi(n)\), puis \(d\), et donc d’obtenir \(Privkey(n, d)\).
Attaque par facteur commun #
Constat : deux clés publiques fournissent les modules \(n_1\) et \(n_2\). Condition : s’ils partagent un facteur premier \(p\), ils ne sont pas premiers entre eux. Leur PGCD révèle alors ce facteur :
- \(p = gcd(n_1, n_2)\)
- \(q_1 = \frac{n_1}{p}\)
- \(q_2 = \frac{n_2}{p}\)
Effet : on retrouve \(q_1\) et \(q_2\), puis on calcule \(d_1\) à partir de \(e_1\) et \(d_2\) à partir de \(e_2\). Les deux clés privées sont compromises.
Exemple de script Python :
from math import gcd
def common_factor_attack(n1, n2, c1, c2, e1, e2):
p = gcd(n1, n2)
q1 = n1 // p
q2 = n2 // p
phi1 = (p - 1) * (q1 - 1)
d1 = pow(e1, -1, phi1)
m1 = pow(c1, d1, n1)
phi2 = (p - 1) * (q2 - 1)
d2 = pow(e2, -1, phi2)
m2 = pow(c2, d2, n2)
return (m1, m2)Attaque par petit exposant #
Constat : l’exposant public \(e\) est petit. Condition : avec du RSA brut, sans remplissage, si le message est assez petit pour que \(M^e < n\), la réduction modulo \(n\) ne change pas \(M^e\) et \(C = M^e\) dans les entiers. Effet : on retrouve directement le message \(M\) en calculant la racine entière :
\[M = \sqrt[e]{C}\]
Oracle de déchiffrement #
Constat : le RSA brut possède une propriété homomorphe multiplicative. En notant \(E(m) = m^e \pmod n\) :
\[E(x * y) \equiv E(x) * E(y) \pmod n\]
Condition : supposons qu’un oracle restitue le message en clair d’un texte chiffré RSA brut choisi, mais refuse le texte chiffré cible \(C\). On choisit \(x \in \mathbb{Z}_n^\) tel que \(Cx^e \not\equiv C \pmod n\), puis on lui soumet cet autre texte chiffré :
\[C’ = C * x^e \pmod n\]
Effet : l’oracle renvoie \(M’ = M*x \pmod n\). Comme \(x\) est inversible, on retrouve le message avec :
\[M = M’ * x^{-1} \pmod n\]
Cette attaque vise donc un protocole qui restitue le message en clair RSA brut, ou laisse fuiter une information équivalente exploitable dans un scénario à textes chiffrés choisis ; elle ne concerne pas indistinctement tout mécanisme qualifié d’oracle de déchiffrement.
Conclusion #
RSA relie une construction de clés, deux opérations inverses et un mécanisme de signature à quelques principes arithmétiques. Ces mêmes principes expliquent ses faiblesses : la sécurité dépend autant de bons paramètres que d’un remplissage adapté et de l’absence de fuite exploitable dans un scénario à textes chiffrés choisis.
