Problème RSA fort

En cryptologie en théorie des nombres, le problème RSA fort^{[Note 1]} (strong RSA) consiste à trouver une racine e-ième d'un nombre donné dans un certain anneau^[1],[2]. Il a été introduit indépendamment par Barić et Pfitzmann^[3], et Fujisaki et Okamoto^[4] en 1997 comme hypothèse calculatoire afin de prouver la sécurité de constructions cryptographiques, en particulier les signatures numériques^{[5],[6],[7],[8]}. 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 ${\displaystyle p,q}$ deux nombres premiers distincts, ${\displaystyle n=pq}$, et considérons l'anneau quotient ${\displaystyle R=\mathbb {Z} /(n)}$. Le problème RSA fort consiste à trouver, étant donné ${\displaystyle n}$ et ${\displaystyle y\in R\setminus \{0\}}$, deux entiers ${\displaystyle x\in R}$ et ${\displaystyle e\in \mathbb {N} \setminus \{0,1\}}$ tels que ${\displaystyle 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 ${\displaystyle n}$. En effet, étant donné une telle factorisation, il est facile de trouver deux entiers ${\displaystyle e,d}$ tels que ${\displaystyle ed=1{\bmod {\varphi }}(n)}$où ${\displaystyle \varphi }$ est la fonction d'Euler, au moyen de l'algorithme d'Euclide. On en déduit immédiatement ${\displaystyle 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 ${\displaystyle 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 ^[9].
• La sécurité des signatures de Cramer-Shoup est prouvable dans le modèle standard en s'appuyant sur le problème RSA fort^[6].