Lattice-based Coppersmith's Method And Partial Key Exposure Attacks On RSA

As the first well-known public key cryptosystem,RSA is proposed by Rivest,Shamir and Adleman in 1978.This cryptosystem is nowadays used in a wide variety of applications,thus cryptanalysis of RSA draws much attention in the field.In 1996,Coppersmith presents several attacks on RSA by means of lattice-based method,which is then developed into Coppersmith's method.This dissertation summarizes Coppersmith's method for finding small roots of modular polynomial equations and integer polynomial equations.The strategies of construction of lattice are also introduced specifically,which include “Basic Strategy” and “Extended Strategy”.Based on Coppersmith's method,this dissertation studies partial key exposure attacks on RSA.The main results of this dissertation are as follows:1.The technique of variable substitution can be used in partial key exposure attacks on RSA.Following this technique,we are able to linearize some special modular equations,and thus obtain a new strategy of construction of lattice,which is superior to“Extended Strategy”.2.For the case when least significant bits of the private key are exposed,we generalize two results of known attacks,and then present a new attack.The result of this new attack not only cares about how many bits are exposed,but also pays attention to what the value of each exposed bit is.Under certain condition for the values of exposed bits,our new result needs fewer exposed bits,and thus improves the results of known attacks.3.For the case when middle bits of the private key are exposed,we also present a new attack similar to the last case.Moreover,from this new attack we obtain a corollary,which shows that RSA is insecure if there are too many continuous 0 bits in the private key.4.Finally,this dissertation generalizes the new results to the partial key exposure attack with any unexposed blocks in the private key.