Cryptanalysis on prime power RSA modulus of the form N=prq
Let \(N = p^r q\) be an RSA prime power modulus for \(r \geq 2\) and \(q < p < 2 q\). This paper propose three new attacks. In the first attack we consider the class of public exponents satisfying an equation \(e X - N Y = u p^r + \frac{q^r}{u} + Z\) for suitably small positive integer \(u\)....
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
2016
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/55401/ http://psasir.upm.edu.my/id/eprint/55401/1/Cryptanalysis%20on%20prime%20power%20RSA%20modulus%20of%20the%20form%20N%3Dprq.pdf |
| _version_ | 1848852792454676480 |
|---|---|
| author | Kamel Ariffin, Muhammad Rezal Shehu, Sadiq |
| author_facet | Kamel Ariffin, Muhammad Rezal Shehu, Sadiq |
| author_sort | Kamel Ariffin, Muhammad Rezal |
| building | UPM Institutional Repository |
| collection | Online Access |
| description | Let \(N = p^r q\) be an RSA prime power modulus for \(r \geq 2\) and \(q < p < 2 q\). This paper propose three new attacks. In the first attack we consider the class of public exponents satisfying an equation \(e X - N Y = u p^r + \frac{q^r}{u} + Z\) for suitably small positive integer \(u\). Using continued fraction we show that \(\frac{Y}{X}\) can be recovered among the convergents of the continued fraction expansion of \(\frac{e}{N}\) and leads to the successful factorization of \(N p^r q\). Moreover we show that the number of such exponents is at least \(N^{\frac{r+3}{2(r+1)}-\varepsilon}\) where \(\varepsilon \geq 0\) is arbitrarily small for large \(N\). The second and third attacks works when \(k\) RSA public keys \((N_i,e_i)\) are such that there exist \(k\) relations of the shape \(e_i x - N_i y_i = p_i^r u + \frac{q_i^r}{u} + z_i\) or of the shape \(e_i x_i - N_i y = p_i^r u + \frac{q_i^r}{u} + z_i\) where the parameters \(x\), \(x_i\), \(y\), \(y_i\), \(z_i\) are suitably small in terms of the prime factors of the moduli. We apply the LLL algorithm, and show that our strategy enable us to simultaneously factor the \(k\) prime power RSA moduli \(N_i\). |
| first_indexed | 2025-11-15T10:43:42Z |
| format | Article |
| id | upm-55401 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-15T10:43:42Z |
| publishDate | 2016 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-554012017-10-02T09:07:14Z http://psasir.upm.edu.my/id/eprint/55401/ Cryptanalysis on prime power RSA modulus of the form N=prq Kamel Ariffin, Muhammad Rezal Shehu, Sadiq Let \(N = p^r q\) be an RSA prime power modulus for \(r \geq 2\) and \(q < p < 2 q\). This paper propose three new attacks. In the first attack we consider the class of public exponents satisfying an equation \(e X - N Y = u p^r + \frac{q^r}{u} + Z\) for suitably small positive integer \(u\). Using continued fraction we show that \(\frac{Y}{X}\) can be recovered among the convergents of the continued fraction expansion of \(\frac{e}{N}\) and leads to the successful factorization of \(N p^r q\). Moreover we show that the number of such exponents is at least \(N^{\frac{r+3}{2(r+1)}-\varepsilon}\) where \(\varepsilon \geq 0\) is arbitrarily small for large \(N\). The second and third attacks works when \(k\) RSA public keys \((N_i,e_i)\) are such that there exist \(k\) relations of the shape \(e_i x - N_i y_i = p_i^r u + \frac{q_i^r}{u} + z_i\) or of the shape \(e_i x_i - N_i y = p_i^r u + \frac{q_i^r}{u} + z_i\) where the parameters \(x\), \(x_i\), \(y\), \(y_i\), \(z_i\) are suitably small in terms of the prime factors of the moduli. We apply the LLL algorithm, and show that our strategy enable us to simultaneously factor the \(k\) prime power RSA moduli \(N_i\). 2016 Article PeerReviewed application/pdf en http://psasir.upm.edu.my/id/eprint/55401/1/Cryptanalysis%20on%20prime%20power%20RSA%20modulus%20of%20the%20form%20N%3Dprq.pdf Kamel Ariffin, Muhammad Rezal and Shehu, Sadiq (2016) Cryptanalysis on prime power RSA modulus of the form N=prq. International Journal of Applied Mathematical Research, 5 (4). pp. 167-175. ISSN 2227-4324 10.14419/ijamr.v5i4.6494 |
| spellingShingle | Kamel Ariffin, Muhammad Rezal Shehu, Sadiq Cryptanalysis on prime power RSA modulus of the form N=prq |
| title | Cryptanalysis on prime power RSA modulus of the form N=prq |
| title_full | Cryptanalysis on prime power RSA modulus of the form N=prq |
| title_fullStr | Cryptanalysis on prime power RSA modulus of the form N=prq |
| title_full_unstemmed | Cryptanalysis on prime power RSA modulus of the form N=prq |
| title_short | Cryptanalysis on prime power RSA modulus of the form N=prq |
| title_sort | cryptanalysis on prime power rsa modulus of the form n=prq |
| url | http://psasir.upm.edu.my/id/eprint/55401/ http://psasir.upm.edu.my/id/eprint/55401/ http://psasir.upm.edu.my/id/eprint/55401/1/Cryptanalysis%20on%20prime%20power%20RSA%20modulus%20of%20the%20form%20N%3Dprq.pdf |