RSA Cryptanalyses with the LLL Reduction
敦 高安 · Institutional Repositories DataBase (IRDB) · 2017
RSA is one of the most famous cryptosystems and the security has been studied in numerous papers.One main approach for the research is due to Coppersmith's lattice based methods that enable us to solve modular/integer equations with small solutions in polynomial time.Indeed, several RSA vulnerabilities have been reported by using the methods.Thus far, a number of attacks on RSA and its variants with some special hints have been proposed, however, some of these attacks have obvious room to be improved.The facts come from the technical hardness to apply Coppersmith's methods to RSA cryptanalyses.More concretely,• how to formulate attack scenarios appropriately and • how to construct appropriate lattices to solve equations are technically hard problems.In this paper, we propose several improved polynomial time attacks on RSA variants by resolving the above difficulties.Our first result is an improved algorithm for solving the small inverse problem that relates to the security evaluation of the small secret exponent (multi-prime) RSA.Our proposed algorithm offers improved attacks on multi-prime RSA with small prime differences.Our second results are improved partial key exposure attacks on CRT-RSA where the attacks utilize partial exposed bits of CRT-exponents.We study attacks with the most/least significant bits of d p or/and d q .For all the cases, we propose improved attacks.Our third results are improved partial key exposure attacks on RSA for general exposure scenarios.Our claimed scenarios contain several ones which have been studied as special cases.We construct attacks that contain all the currently known best attacks as special cases.Furthermore, we obtain improved attacks in several specific scenarios.Our last results are improved small secret exponent attacks and partial key exposure attacks on Takagi's RSA and the prime power RSA both of that have moduli N = p r q.We propose simple lattice constructions to attack the variants and obtain improved attacks.