---

Introduction :

Généralement, dans un contexte de CTF , il est possible de tomber sur un oracle de déchiffrement RSA , on nous donne accès :

• à un oracle permettant de déchiffrer des messages sauf le flag chiffré
• le flag chiffré

Voici donc plusieurs méthodes pour trouver le flag en clair :

Méthode 1:

La première méthode est de Factoriser le message $c$ . On peut ainsi demander de déchiffrer les facteurs du flag puis re-multiplier les clairs entre eux pour récupérer le message original:

$c_{original} =c_1 * c_2 * c_3$
$\implies m_{original} = [f^{-1}(c_1)* f^{-1}(c_2)* f^{-1}(c_3)] \pmod n$
(Avec $f^{-1}$ la fonction de déchiffrement)

Méthode 2:

Le RSA a des propriétés Homomorphique , ce qui veut dire que:

• $f^{-1}(a*b) = f^{-1}(a)*f^{-1}(b)$

C’est la propriété utilisée dans la méthode 1
Ainsi , on peut demander le déchiffrement d’un produit de $c$

$m_{original} = f^{-1}(2*c) * [({f^{-1}(2)})^{-1}\pmod n] \pmod n$

Méthode 3:

On peut aussi envoyer :

• $c+k*n$
  ($k \in N$)

On utilise ici les propriétés du RSA , en appliquant le modulo n , le serveur va directement déchiffrer c

Méthode 4:

On peut demander le déchiffrement de :

• $-c$
• $-1$

Puis :

• $m_{original} = f^{-1}(-c) * f^{-1}(-1) \pmod n$

Méthode 5:

On sait que :
$c \equiv m^e \pmod n$

On doit envoyer : $c^{e+1}$

• On a:
  $\implies (c^{e+1})^d \equiv (c^{e*d} + c^d ) \pmod n$
  $\implies (c^{e+1})^d \equiv c * c^d \pmod n$
  $\implies (c^{e+1})^d \equiv c * m \pmod n$

• Finalement :
  $m_{original} = (c^{e+1})^d * c^{-1} \pmod n$

Méthode 6:

On sait que :
$c \equiv m^e \pmod n$

• Soit $\lambda \in N$
  $\implies \lambda^ec \equiv (\lambda*m)^e \pmod n$
  $\implies (\lambda^ec)^d \equiv ((\lambda*m)^e)^d \pmod n$
  $\implies (\lambda^ec)^d \equiv \lambda*m \pmod n$
  $\implies \dfrac{(\lambda^ec)^d}{\lambda} \equiv m \pmod n$

On peut donc envoyer : $\lambda^e \pmod n$ et diviser par $\lambda$

Retrouver le module $n$:

Toutes les attaques précédentes requièrent de connaitre $n$. On peut le retrouver de la manière suivante :

On demande le déchiffrement de :

• 2
• 4
• 3
• 9
• 5
• 25

On obtient donc :

$\implies \begin{cases} c_2 = 2 ^ e \pmod n \newline c_4 = 4 ^ e \pmod n \newline c_3 = 3 ^ e \pmod n \newline c_9 = 9 ^ e \pmod n \newline c_5 = 5 ^ e \pmod n \newline c_{25} = {25} ^ e \pmod n \newline \end{cases}$

$\implies \begin{cases} {c_2} ^ 2 = c_4 \pmod n \newline {c_3} ^ 2 = c_9 \pmod n \newline {c_5} ^ 2 = c_{25} \pmod n \newline \end{cases}$

$\implies \begin{cases} k_1 = {c_2} ^ 2 - c_4 \newline k_2 = {c_3} ^ 2 - c_9 \newline k_3 = {c_5} ^ 2 - c_{25} \newline \end{cases}$

$\implies n = GCD(k_1,GCD(k_2,k_3))$

---