Citation
Shehu, Sadiq and Kamel Ariffin, Muhammad Rezal
(2016)
New directions in factoring the prime power RSA modulus N = prq.
In: 5th International Cryptology and Information Security Conference 2016 (CRYPTOLOGY2016), 31 May2 June 2016, Kota Kinabalu, Sabah, Malaysia. (pp. 83100).
Abstract
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.
Download File
Additional Metadata
Actions (login required)

View Item 