New directions in factoring the prime power RSA modulus N = prq

Factoring large integers is a fundamental problem in algebraic number theory and modern cryptography, which many cryptosystem such as RSA are based on. This paper proposes three new attacks on the Prime Power RSA modulus N = prq. In the first attack we consider the class of public key exponents satisfying an equation eX - NY - (apr + bqr + z) = 1 where a, b are suitably small integers with gcd(a, b) = 1. Using the continued fraction algorithm, we show that such exponents yield the factorization of the RSA Prime Power modulus in polynomial time. Further, we show that the number of such weak keys is at least N5/6 - ϵ where ϵ > 0 is arbitrarily small for large N. We furthered our analysis on k Prime Power RSA moduli Ni = prꜟqꜟ satisfying a variant of the above mentioned condition. We utilized the LLL algorithm on k Prime Power RSA public keys (Ni, ei) with Ni = prꜟqꜟ and we were able to factorize the k Prime Power RSA moduli Ni = prꜟqꜟ simultaneously in polynomial time.

Text Cryptology2016-5.pdf Restricted to Repository staff only Download (378kB)

Actions (login required)

View Item