RSA pour les nuls
Le RSA c’est quoi ?
Le RSA est un algorithme de chiffrement asymétrique, c’est à dire qu’on a deux clés qui ont chacune un rôle distinct, une clé publique pour chiffrer les données et une clé privée pour déchiffrer les données chiffrées. Il est normalement impossible de retrouver la clé privée à partir de la clé publique.
Formules RSA
Les formules utiles pour créer les clés, chiffrer, déchiffrer, créer une signature et vérifier une signature seront listées ici.
Création des clés
- On choisit des nombres premiers distincts, \(p\) et \(q\)
- On calcule le module de chiffrement \(n\) avec \(n = p*q\)
- On calcule \(\varphi(n) = (p-1)(q-1)\)
- On choisit un entier naturel \(e\) premier avec \(\varphi(n)\) et \(1 < e < \varphi(n)\), appelé exposant de chiffrement
- On calcule \(d\) avec \(d = e^{-1} \pmod {\varphi(n)} \) et \(d < \varphi(n)\) appelé exposant de déchiffrement
Avec ça on obtient la clé publique \(n\) et \(e\), ainsi que la clé privée \(n\) et \(d\).
Chiffrement
Si \(M \in \mathbb{N}\) et \(M < n\) représentant un message, alors le message chiffré sera représenté par:
\[C = M^e \pmod n\]Déchiffrement
Pour déchiffrer \(C\), on utilise \(d = e^{-1} \pmod {\varphi(n)} \), et l’on retrouve le message clair \(M\) par:
\[M = C^d \pmod n\]Générer une signature
Pour créer une signature, on chiffre \(hash(M)\) avec la clé privée \(d\):
\[S = h^d \pmod n\]Vérifier une signature
Pour vérifier une signature, on déchiffre \(S\) avec \(e\):
\[h' = S^e \pmod n\]Ensuite on vérifie que \(h' = h\).
Quelques attaques simples
Les attaques simples qui ne demandent pas un gros bagage en math se trouveront ici. Moi même étant très nul en math et en crypto, il n’y aura ici que très peu d’attaques, qui seront assez simples.
n factorisable
Il est parfois possible de factoriser \(n\) afin de retrouver \(p\) et \(q\). Pour faire cela il a le site factordb. Une fois \(p\) et \(q\) en main, on peut retrouver \(d\) et avoir \(Privkey(n, d)\).
Common factor attack
Dans le cas ou on possède deux clés publiques et que \(n_1\) et \(n_2\) ont un facteur commun, alors il est possible de retrouver \(p\), \(q_1\) ainsi que \(q_2\):
- \(p = gcd(n_1, n_2)\)
- \(q_1 = \frac{n_1}{p}\)
- \(q_2 = \frac{n_2}{p}\)
Ensuite on a juste à calculer \(d_1\) et \(d_2\).
Exemple de script python:
from math import gcd
def common_factor_attack(n1, n2, c1, c2, e):
p = gcd(n1, n2)
q1 = n1//p
q2 = n2//p
phi1 = (p-1)*(q1-1)
d1 = pow(e, -1, phi1)
m1 = pow(c1, d1, n1)
phi2 = (p-1)*(q2-1)
d2 = pow(e, -1, phi2)
m2 = pow(c2, d2, n2)
return (m1, m2)
Low Exponent Attack
Dans le cas ou \(e\) est tellement petit que \(M^e < n\) alors on peut retrouver \(M\) à partir de \(C\) avec :
\[M = \sqrt[e]{C}\]Oracle de déchiffrement
Le RSA possède des propriétés Homomorphe ce qui signifie que:
\[M(x * y) = M(x) * M(y)\]\[C(x * y) = C(x) * C(y)\]Cela signifie qu’on peut retrouver \(M\) avec \(C_1 = \frac{C}{x}\) et \(C_2 = x\), et \(C_1 \in \mathbb{N}\) ainsi que \(C_2 \in \mathbb{N}\). Il suffit ensuite d’envoyer \(C_1\) et \(C_2\) à l’oracle de déchiffrement pour avoir \(M_1\) et \(M_2\). Pour finir on peut retrouver \(M\) car \(M = (M_1 * M_2) \pmod n\).