Research On Analysis Of RSA Algorithm Based On Lattice Reduction Theory

The RSA cryptosystem, introduced in 1978 by Ron Rivest,Adi Shamir and Len Adleman, is the first public key cryptosystem that can be used both in encryption and signature. The security of RSA is based on the intractability of the integer factorization problem. The RSA algorithm is simple to understand and easy to implement, for the operations involved are just some elemental modular operation. As a consequent, it is widely used in many areas of information security. Now it is one of the public key cryptosystems supported by many recent popular security protocols such as IPSec, PGP, and SSL. It is also one of the most important candidate algorithms adopted by many public key cryptosystem standards such as PKCS and P1363.Research on the cryptanalysis of RSA is always one of the hot topics in cryptology. Since the advent of the RSA public key cryptosystem thirty years ago, it has been widely studied and thoroughly analyzed. Many years passed, RSA can always keep its promise of security when implemented properly. Up till now, no efficient algorithm can really threaten the security of RSA itself. From the above we can see that the research on the security analysis of RSA cryptosystem is among the most important and difficult work in cryptology.The theory of lattice basis reduction, rising from the arithmetic number theory, has become an important tool widely used in cryptographic research. In 1982, Arjen Lenstra, Hendrik Lenstra and Laszlo Lovasz successfully found the solution to some rational coefficient polynomials by using the lattice basis reduction algorithm, that is,the famous LLL algorithm. Since then, the theory of lattice basis reduction began to be used in cryptology. It was first used by Adleman to present an attack on Merkle and Hellman's knapsack cryptosystem. It is also be used to analyze many public key cryptosystems based on different mathematical problems, such as the famous RSA cryptosystem based on the integer factorization problem and the DSA algorithm based on the discrete logarithm problem over the finite field. Besides,new fast public key cryptosystems, such as NTRU,have also been proposed based on the shortest vector problem, or the closest vector problem etc. Now the lattice basis reduction algorithm has become an important and powerful tool widely used in cryptanalysis.In this dissertation, we first make a comprehensive survey on the security of RSA public key cryptosystem and the application of the lattice basis reduction methods in cryptology. Particularly, a thorough review of the application of the lattice basis reduction methods in the cryptanalysis of RSA and RSA-type cryptosystem is provided. Moreover, the essence of such attack algorithms is analyzed and a comparison of the attack on different objects is presented. Following this, the feasibility, hot topic and difficulties in the application of this method are outlined. Also, the research emphasis of this dissertation and possible research directions in future are pointed out. Based on this, some new attacks on RSA cryptosystem are presented by using the lattice basis reduction methods. The main contents of this dissertation are as follows:1. Based on Boneh et al's small inversion attack on RSA cryptosystem using small decryption exponent, we present another attack algorithm on RSA cryptosystem using small encryption exponent. As a generalization of the small inversion attack on RSA, the experiments show that the method presented in this dissertation do find some new'weak'keys of RSA. Our method is the first try in the application of the small decryption attack to the attack on RSA cryptosystem using small encryption exponent, which can provide a new approach to the security analysis of RSA cryptosystem.2. A general partial secret key exposure attack algorithm on RSA is presented, which makes some improvements on Boneh et al's methods in two aspects:●For one hand, our method works in cases when the prime factors p and q of the RSA modulus share few least significant bits, which can be one or more bits, whereas the method given by Boneh et al can only work in cases when p≠q mod 4, that is, p and q share only one least significant bit.●For the other hand, our attack works provided that (?) is small, whereas Boneh et al's attack works provided that e is small. Our method works in almost all cases when p and q are of the same size, that is, the balenced RSA case. Compared with Boneh et al's method, the assumption given in our method is more reasonable and has much wider real application areas.3. The condition such that a kind of integers N-pκq (whereκ≥1, p and q are large primes of almost the same size) can be factored is analyzed, and the corresponding factorization algorithm is provided. Such kind of integers are usually used as the modulus of the RSA-type scheme, and the security of such scheme is totally depended on the factorization of such kind of integers. Although we have not presented a complete partial secret key exposure attack algorithm on RSA-type scheme, our method can be taken as a theoretical base for the corresponding partial secret key exposure attack algorithm, which could play a role almost the same as Boneh's conditional factorization algorithm to their partial secret key exposure attack on RSA cryptosystem. By some simple analysis it can be shown that our method also implys that the traditional RSA cryptosystem using modulus N=pq is more secure than RSA-type cryptosystem using modulus N= pkq.4. Several more general small decryption exponent attack and partial secret key exposure at-tack algorithms on RSA-type scheme are presented. Let N= pkq be the modulus of a RSA-type cryptosystem, our results show that a RSA-type cryptosystem with larger k is more vulnerable to such attacks.