Problème RSA fort
# Problème RSA fort

En cryptologie en théorie des nombres, le problème RSA fort (strong RSA) consiste à trouver une racine e-ième d'un nombre donné dans un certain $anneau^,.$ Il a été introduit indépendamment par Barić et Pfitzmann, et Fujisaki et Okamoto en 1997 comme hypothèse calculatoire afin de prouver la sécurité de constructions cryptographiques, en particulier les signatures $numériques^,^,^,.$ Cette relaxation du problème RSA donne des signatures plus efficaces et permet de se passer de certains modèles idéalisés tel que l'oracle aléatoire dans la preuve de sécurité.

## Définition

Soit $p,q$ deux nombres premiers distincts, $n=pq$, et considérons l'anneau quotient $R=\mathbb {Z} /(n)$. Le problème RSA fort consiste à trouver, étant donné $n$ et $y\in R\setminus \{0\}$, deux entiers $x\in R$ et $e\in \mathbb {N} \setminus \{0,1\}$ tels que $x^{e}=y$.

Le problème RSA fort est a priori plus facile que le problème RSA standard, puisque l'on peut en principe choisir e librement.

À l'heure actuelle (2018) le meilleur moyen connu pour résoudre le problème RSA fort (comme pour le problème RSA standard) est d'obtenir une factorisation de $n$. En effet, étant donné une telle factorisation, il est facile de trouver deux entiers $e,d$ tels que $ed=1{\bmod {\varphi }}(n)$où $\varphi$ est la fonction d'Euler, au moyen de l'algorithme d'Euclide. On en déduit immédiatement $x=y^{d}$. Toutefois il n'est pas exclu qu'existent des algorithmes spécifiques résolvant le problème RSA fort sans pour autant obtenir une factorisation de $n$.

## Exemples importants

* La sécurité des signatures de Gennaro-Halevi-Rabin face aux contrefaçons existentielles a été réduite dans le modèle standard au problème RSA fort.
* La sécurité des signatures de Cramer-Shoup est prouvable dans le modèle standard en s'appuyant sur le problème RSA fort.
