An Attack on the Generalized RSA Public Key Scheme Using Two-dimension Lattice
Gou Yu · Journal of Sichuan University · 2015
Based on the two-dimension lattice and lower bound of Euler's totient function,a method for breaking the generalized RSA public key scheme was proposed using Lagrange's reduction algorithm.Moreover,the corresponding attack algorithm was also given and it was proved that the RSA modulus N could be factorized in polynomial time.Compared with the original continued fraction attack,this method removed the steps of computing and repeatedly verifying the convergent of continued fraction,obtained the prime factor p directly,so it simplified the whole solving procedures and improved the factoring efficiency.The results showed that this method has lower time complexity,works faster in the experiment,and can be efficiently used to attack the generalized RSA public key scheme.