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 sati...
| Main Authors: | , |
|---|---|
| Format: | Conference or Workshop Item |
| Language: | English |
| Published: |
Institute for Mathematical Research, Universiti Putra Malaysia
2016
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/66517/ http://psasir.upm.edu.my/id/eprint/66517/1/Cryptology2016-5.pdf |
| _version_ | 1848855592429420544 |
|---|---|
| author | Shehu, Sadiq Kamel Ariffin, Muhammad Rezal |
| author_facet | Shehu, Sadiq Kamel Ariffin, Muhammad Rezal |
| author_sort | Shehu, Sadiq |
| building | UPM Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-15T11:28:13Z |
| format | Conference or Workshop Item |
| id | upm-66517 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-15T11:28:13Z |
| publishDate | 2016 |
| publisher | Institute for Mathematical Research, Universiti Putra Malaysia |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-665172019-03-03T23:55:26Z http://psasir.upm.edu.my/id/eprint/66517/ New directions in factoring the prime power RSA modulus N = prq Shehu, Sadiq Kamel Ariffin, Muhammad Rezal 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. Institute for Mathematical Research, Universiti Putra Malaysia 2016 Conference or Workshop Item PeerReviewed text en http://psasir.upm.edu.my/id/eprint/66517/1/Cryptology2016-5.pdf 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). |
| spellingShingle | Shehu, Sadiq Kamel Ariffin, Muhammad Rezal New directions in factoring the prime power RSA modulus N = prq |
| title | New directions in factoring the prime power RSA modulus N = prq |
| title_full | New directions in factoring the prime power RSA modulus N = prq |
| title_fullStr | New directions in factoring the prime power RSA modulus N = prq |
| title_full_unstemmed | New directions in factoring the prime power RSA modulus N = prq |
| title_short | New directions in factoring the prime power RSA modulus N = prq |
| title_sort | new directions in factoring the prime power rsa modulus n = prq |
| url | http://psasir.upm.edu.my/id/eprint/66517/ http://psasir.upm.edu.my/id/eprint/66517/1/Cryptology2016-5.pdf |