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 {\displaystyle p,q} deux nombres premiers distincts, n = p q {\displaystyle n=pq} , et considérons l'anneau quotient R = Z / ( n ) {\displaystyle R=\mathbb {Z} /(n)} . Le problème RSA fort consiste à trouver, étant donné n {\displaystyle n} et y ∈ R ∖ { 0 } {\displaystyle y\in R\setminus \{0\}} , deux entiers x ∈ R {\displaystyle x\in R} et e ∈ N ∖ { 0 , 1 } {\displaystyle e\in \mathbb {N} \setminus \{0,1\}} tels que x e = y {\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 n {\displaystyle n} . En effet, étant donné une telle factorisation, il est facile de trouver deux entiers e , d {\displaystyle e,d} tels que e d = 1 mod φ ( n ) {\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 x = y d {\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 n {\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, (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, (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, (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, (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, (ISBN 9780387234731, DOI 10.1007/0-387-23483-7_374, lire en ligne), p. 546–546
  6. ↑ 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,‎ , p. 46–51 (ISBN 1581131488, DOI 10.1145/319709.319716, lire en ligne, consulté le )
  7. ↑ (en) Marc Joye, « How (Not) to design strong-RSA signatures », Designs, Codes and Cryptography, vol. 59, nos 1-3,‎ , p. 169–182 (ISSN 0925-1022 et 1573-7586, DOI 10.1007/s10623-010-9453-1, lire en ligne, consulté le )
  8. ↑ (en) Dennis Hofheinz, Tibor Jager et Eike Kiltz, « Short Signatures from Weaker Assumptions », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, (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,‎ , p. 20–27 (ISBN 1581133855, DOI 10.1145/501983.501987, lire en ligne, consulté le )
v · m
Modèles de sécurité
Outils et techniques de preuve
Hypothèses calculatoires
Propriétés de sécurité
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)
  • icône décorative Portail de la cryptologie
  • icône décorative Portail des mathématiques