The Applications Of LLL Algorithm To RSA Cryptosystem

The concept of asymmetric cryptography was first introduced by Diffe and Hellman in1976,which opened the prelude of modern cryptography. Two years later, Ron Rivest, Adi Shamir andLen Adlemen presented the first public-key cryptosystem, the RSA scheme. It is a multipurposepublic key cryptosystem which can be used for both encrypting data and digital signature, andhas remained the most popular public key cryptosystem ever since. Therefore, the attack on theRSA algorithm has become one of the hotest issues in the field of cryptocrapghy.Since the appearance of the celebrated Lenstra-Lenstra-Lovasz lattice reduction algorithmin the eighties of last century, lattice reductions have had been surprisingly applicated both incryptology design and cryptoanalysis. The algorithm can produce a reduced basis in polynomialtime and often works well in practical attacks.In this paper, we studied the application of LLL algorithm to RSA cryptosystem. Threeattacks on RSA scheme are heuristically generalized by using the LLL algorithm. The mainresults are as follows:1. We present another attack algorithm on RSA cryptosystem using small encryptionexponent based on the fast attack algorithm described by Blomer and May in2001.As thegeneralization of the fast attack algorithm, the experimental data show that this method can findnew weak keys of RSA.2. We present an heuristic algorithm that combine the partial key exposure attack givendiscrete bits with the low exponent attack. We show that if the private exponent d used in theRSA public key cryptosystem is less thanN0.5, then the system is insecure with some bits of pknown which located in one consecutive middle block. Moreover, we extend known bits to anarbitrary number n of blocks for unbalanced RSA modulo. Surprisingly, we are able to show that25%of the bits are sufficient for any n in order to find the factorization when d is lessthanN0.306.3. We study the problem of implicit factoring presented by May and Ritzenhofen in2009and apply it to more general settings, where prime factors of both integers only known byimplicit information of middle discrete bits. In the case of tlog2N bits shared in one consecutivemiddle block, we describe a novel lattice-based method that leads to the factorization of twointegers in polynomial time as soon as t>4. Subsequently, we heuristically generalize themethod to an arbitrary number n of shared blocks.