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 $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 [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

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

(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
(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
(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
(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
(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
(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)
(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)
(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
(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)

Portail de la cryptologie
Portail des mathématiques

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

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

[2] (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

[3] (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

[4] (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

[5] (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

[6] (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

[:0-7] (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)

[8] (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)

[9] (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

[10] (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)