Research On Lattice Based Attacks On Small Private Exponent Of RSA

With the popularity and development of computer,people pay more and more attention to information security.The foundation of information security is cryptography.Diffie and Hellman published "New Directions in Cryptography" in 1976,a paper introduced the concept of public-key cryptography,opened the prelude to modern cryptography.In 1978,Rivest,Shamir and Adleman proposed the famous RSA public key cryptosystem.It is the first public-key cryptosystem based on the integer decomposition problem and the first cryptographic algorithm that can be applied to both data encryption and digital signatures.Once put forward,RSA algorithm has been widely concerned,and applied to various areas of network and information security.The study of RSA public-key cryptosystem’s security has been one of the focuses of cryptography.Since the RSA algorithm was proposed,it has stood the test of a variety of attacks,but no algorithm can threaten the security of standard RSA cryptosystem so far.However,in practice,special RSA cryptosystem is often used to accelerate the speed of encryption/decryption(signature/verification),such as RSA using small public(private)exponent,or RSA based on Chinese remainder theorem and so on.But in this way it sacrificed the security of RSA to some extent.The lattice reduction theory is an important theory in mathematics.Since 1982,A·K·Lenstra,H·K·Lenstra and L·Lovasz proposed the famous LLL algorithm,which successfully decomposed rational coefficient polynomial,the lattice reduction theory has been widely used in cryptanalysis,and become one of the important tools in cryptography research.In this paper,by using LLL algorithm,a series of attacks are introduced on RSA with small private exponent.The main work of this paper is as follows:(1)Review and analyze Wiener,Ernst and others’ attack methods and technology in detail;(2)Research the implement of LLL algorithm and analyze its efficiency;Put forward a fast method to attack small public exponent of RSA by using LLL algorithm;Design the experiment and analyze the result;Under the condition of small decryption exponent,compared with Wiener’s method,attack in this paper has an upper bound of d and much faster.(3)Based on Coppersmith’s theory,combined with the leak of a part bits of private key,introduce an attack method that can raise the upper bound of decription key d;then give the result of experiment.