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 modifier

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 modifier

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 modifier

Notes modifier

↑ 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 modifier

↑ (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
↑ ^{a et b} (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)

[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] {a et b} (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)

[Note 1]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]