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 |
| Summary: | 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. |
|---|