Description
This survey addresses the problems of factoring and inverting the RSA function. We define practically relevant relaxed instances of these problems that can be solved in polynomial time. These problem instances are modelled by polynomial equations with small roots. In order to recover the roots, we make use of a method due to Coppersmith which is in turn based on the famous LLL lattice reduction.<br/> As new applications of the method we present an improved Hastad attack on RSA in the case of several RSA encryptions of the same underlying message, and an algorithm for factoring N=pq given 70% of the bits of p in any positions.
Next sessions
-
CryptoVerif: a computationally-sound security protocol verifier
Speaker : 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
-