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].

Notes et références

Notes

1. On trouve aussi le nom problème RSA flexible (en anglais : flexible RSA problem) qui est toutefois beaucoup moins utilisé dans la littérature.

Références

1. (en) Ronald L. Rivest et Burt Kaliski, « RSA Problem », dans Encyclopedia of Cryptography and Security, Springer US, 2005 (ISBN 9780387234731, DOI 10.1007/0-387-23483-7_363, lire en ligne), p. 532–536
2. (en) Dan Boneh, « Strong RSA Assumption », dans Encyclopedia of Cryptography and Security, Springer US, 2005 (ISBN 9780387234731, DOI 10.1007/0-387-23483-7_414, lire en ligne), p. 597–597
3. (en) Niko Barić et Birgit Pfitzmann, « Collision-Free Accumulators and Fail-Stop Signature Schemes Without Trees », dans Advances in Cryptology — EUROCRYPT ’97, Springer Berlin Heidelberg, 1997 (ISBN 9783540629757, DOI 10.1007/3-540-69053-0_33, lire en ligne), p. 480–494
4. (en) Eiichiro Fujisaki et Tatsuaki Okamoto, « Statistical zero knowledge protocols to prove modular polynomial relations », dans Advances in Cryptology — CRYPTO '97, Springer Berlin Heidelberg, 1997 (ISBN 9783540633846, DOI 10.1007/bfb0052225, lire en ligne), p. 16–30
5. (en) Dan Boneh, « Secure signatures from the “strong RSA” assumption », dans Encyclopedia of Cryptography and Security, Springer US, 2005 (ISBN 9780387234731, DOI 10.1007/0-387-23483-7_374, lire en ligne), p. 546–546
6. (en) Ronald Cramer et Victor Shoup, « Signature schemes based on the strong RSA assumption », CCS '99 Proceedings of the 6th ACM conference on Computer and communications security, ACM,‎ 1^er novembre 1999, p. 46–51 (ISBN 1581131488, DOI 10.1145/319709.319716, lire en ligne, consulté le 22 août 2018)
7. (en) Marc Joye, « How (Not) to design strong-RSA signatures », Designs, Codes and Cryptography, vol. 59, n^os 1-3,‎ 22 décembre 2010, p. 169–182 (ISSN 0925-1022 et 1573-7586, DOI 10.1007/s10623-010-9453-1, lire en ligne, consulté le 22 août 2018)
8. (en) Dennis Hofheinz, Tibor Jager et Eike Kiltz, « Short Signatures from Weaker Assumptions », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2011 (ISBN 9783642253843, DOI 10.1007/978-3-642-25385-0_35, lire en ligne), p. 647–666
9. (en) David Naccache, David Pointcheval et Jacques Stern, « Twin signatures: an alternative to the hash-and-sign paradigm », CCS '01 Proceedings of the 8th ACM conference on Computer and Communications Security, ACM,‎ 5 novembre 2001, p. 20–27 (ISBN 1581133855, DOI 10.1145/501983.501987, lire en ligne, consulté le 22 août 2018)