UPM Institutional Repository

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


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 May-2 June 2016, Kota Kinabalu, Sabah, Malaysia. (pp. 83-100).


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

[img] Text
Restricted to Repository staff only

Download (378kB)

Additional Metadata

Item Type: Conference or Workshop Item (Paper)
Divisions: Faculty of Science
Institute for Mathematical Research
Publisher: Institute for Mathematical Research, Universiti Putra Malaysia
Keywords: Prime power RSA; Cryptanalysis; Factorization; Continued fraction
Depositing User: Nabilah Mustapa
Date Deposited: 03 Mar 2019 23:55
Last Modified: 03 Mar 2019 23:55
URI: http://psasir.upm.edu.my/id/eprint/66517
Statistic Details: View Download Statistic

Actions (login required)

View Item View Item