Aller au contenu
  1. Articles/

RSA pour les nuls (comme moi)

570 mots·3 mins·
CRYPTO NOOB
Fayred
Auteur
Fayred
Passionné par l’informatique en général et plus particulièrement par la sécurité informatique. Amateur de CTFs et débutant en Bug Bounty, je cherche avant tout à apprendre, m’amuser et partager ce que j’ai appris.
Sommaire

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.\)

Références
#

Articles connexes

Patriot CTF 2024: DogDay
746 mots·4 mins
PATRIOT CTF WEB CRYPTO MEDIUM
Patriot CTF 2024: Secret Door
843 mots·4 mins
PATRIOT CTF WEB MEDIUM
L4ugh CTF 2024: Micro
421 mots·2 mins
L4UGH CTF WEB EZ