title: Problème RSA fort
text: # 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.
  