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 | modifier le code]

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 | modifier le code]

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 | modifier le code]

Notes[modifier | modifier le code]

↑ 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 | modifier le code]

↑ (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]

v · m Sécurité prouvable en cryptologie
Modèles de sécurité	Modèle standard Modèle de l'oracle aléatoire (ROM) Modèle du groupe générique (GGM) Modèle du groupe algébrique (AGM) Modèle du chiffre idéal (ICM) Modèle de l'action de groupe à sens unique (OWGA) Transfert inconscient (OT) Fonction à perte extrême (ELF) Fonction pseudo-aléatoire (PRF) Permutation pseudo-aléatoire (PRP) Générateur pseudo-aléatoire (PRG) Groupe bilinéaire Application multilinéaire Modèle de la chaîne de référence commune (CRS) Fonction à sens unique (OWF) Fonction à trappe (TDF) Obfuscation indistinguable (iO) Composabilité universelle (UC)
Outils et techniques de preuve	Réduction Séparation Avantage Argument hybride Distance statistique Coefficient H Simulation Forking lemma Leftover hash lemma Lemme de Schwartz-Zippel Théorème de Luby-Rackoff Théorème des anniversaires Heuristique de Fiat-Shamir
Hypothèses calculatoires	Factorisation Problème RSA Problème RSA fort Problème du logarithme discret Problème de Diffie-Hellman (CDH et DDH) Problème de la résiduosité quadratique Problème de la résiduosité supérieure Navigation dans un graphe expanseur Problème LWE Problème NTRU Problèmes de réseau (SVP, CVP, SIS, SIVP)
Propriétés de sécurité	IND (indistingabilité) EF (forge existentielle) NM (non malléabilité) Résistance aux collisions (CR) CPR (résistance aux collisions à préfixe choisi) PIR (résistance aux préimages) SPIR (résistance aux secondes préimages) Divulgation nulle de connaissance (ZK)
Modèles d'attaques	Attaque sans message (NMA) Clairs/messages choisis (CPA/CMA) Chiffrés choisis (CCA) Chiffrés choisis de façon adaptative (CCA2) Attaque par sondes (ISW)