Sommaire

  • Cet exposé a été présenté le 14 décembre 2007.

Description

  • Orateur

    Emmanuel Thomé - LORIA

Nous étudions le problème du calcul de racines e-èmes modulaires. Sous l'hypothèse de la disponibilité d'un oracle fournissant des racines e-èmes de la forme particulière $x_i + c$, nous montrons qu'il est plus facile de calculer des racines $e$-èmes que de factoriser le module $n$. Ici $c$ est fixé, et l'attaquant choisit les petits entiers $x_i$. L'attaque se décline en plusieurs variantes, selon les hypothèses exactes sur l'oracle, et selon les buts poursuivis, allant de la falsification sélective à la falsificaction universelle. La complexité obtenue est $L_n(\frac{1}{3}, \sqrt[3]{\frac{32}{9}})$ dans les cas les plus significatifs, ce qui correspond à la complexité du {\sl special} number field sieve ({\sc snfs}).<br/> Ce travail étend les résultats existants sur la malléabilité du schéma de signature RSA, plus particulièrement au sujet des falsificactions affines. Ce problème particulier est polynomial lorsque le {\em padding} $c$ n'excède pas $n^{2/3}$, mais sa résolution dans le cas général était uniquement accessible via la factorisation.

Prochains exposés

  • CryptoVerif: a computationally-sound security protocol verifier

    • 05 septembre 2025 (13:45 - 14:45)

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Orateur : Bruno Blanchet - Inria

    CryptoVerif is a security protocol verifier sound in the computational model of cryptography. It produces proofs by sequences of games, like those done manually by cryptographers. It has an automatic proof strategy and can also be guided by the user. It provides a generic method for specifying security assumptions on many cryptographic primitives, and can prove secrecy, authentication, and[…]
    • Cryptography

Voir les exposés passés