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
-
Predicting Module-Lattice Reduction
Speaker : Paola de Perthuis - CWI
Is module-lattice reduction better than unstructured lattice reduction? This question was highlighted as `Q8' in the Kyber NIST standardization submission (Avanzi et al., 2021), as potentially affecting the concrete security of Kyber and other module-lattice-based schemes. Foundational works on module-lattice reduction (Lee, Pellet-Mary, Stehlé, and Wallet, ASIACRYPT 2019; Mukherjee and Stephens[…]-
Cryptography
-
-
Attacking the Supersingular Isogeny Problem: From the Delfs–Galbraith algorithm to oriented graphs
Speaker : Arthur Herlédan Le Merdy - COSIC, KU Leuven
The threat of quantum computers motivates the introduction of new hard problems for cryptography.One promising candidate is the Isogeny problem: given two elliptic curves, compute a “nice’’ map between them, called an isogeny.In this talk, we study classical attacks on this problem, specialised to supersingular elliptic curves, on which the security of current isogeny-based cryptography relies. In[…]-
Cryptography
-