A new simultaneous diophantine attack upon RSA moduli N = pq
This paper reports four new cryptanalytic attacks which show that the t instances of RSA moduli N = pq can be simultaneously factored in polynomial time using simultaneous diophantine approximations and lattice basis reduction techniques. In our technique we utilize the relation given by N−[(a j/i+b...
| Main Authors: | , , |
|---|---|
| Format: | Conference or Workshop Item |
| Language: | English |
| Published: |
Institute for Mathematical Research, Universiti Putra Malaysia
2018
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/66551/ http://psasir.upm.edu.my/id/eprint/66551/1/Cryptology2018-6.pdf |
| _version_ | 1848855601452417024 |
|---|---|
| author | Abubakar, Saidu Isah Kamel Ariffin, Muhammad Rezal Asbullah, Muhammad Asyraf |
| author_facet | Abubakar, Saidu Isah Kamel Ariffin, Muhammad Rezal Asbullah, Muhammad Asyraf |
| author_sort | Abubakar, Saidu Isah |
| building | UPM Institutional Repository |
| collection | Online Access |
| description | This paper reports four new cryptanalytic attacks which show that the t instances of RSA moduli N = pq can be simultaneously factored in polynomial time using simultaneous diophantine approximations and lattice basis reduction techniques. In our technique we utilize the relation given by N−[(a j/i+b j/I / (2ab) j/2i + a 1/j+b 1/j / (2ab) 1/2j) √N] + 1 as a good approximations of Φ (N) for unknown positive integers d, di, ki, k, and zi. We construct four system of equations of the form esd − ksΦ(Ns) = 1, esds − kΦ (Ns) = 1, esd − kΦ (Ns) = zs and esds − kΦ (Ns) = zs where s = 1, 2, ..., t. In our attacks, we improve the short decryption exponent bounds of some reported attacks. |
| first_indexed | 2025-11-15T11:28:21Z |
| format | Conference or Workshop Item |
| id | upm-66551 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-15T11:28:21Z |
| publishDate | 2018 |
| publisher | Institute for Mathematical Research, Universiti Putra Malaysia |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-665512019-03-04T00:04:57Z http://psasir.upm.edu.my/id/eprint/66551/ A new simultaneous diophantine attack upon RSA moduli N = pq Abubakar, Saidu Isah Kamel Ariffin, Muhammad Rezal Asbullah, Muhammad Asyraf This paper reports four new cryptanalytic attacks which show that the t instances of RSA moduli N = pq can be simultaneously factored in polynomial time using simultaneous diophantine approximations and lattice basis reduction techniques. In our technique we utilize the relation given by N−[(a j/i+b j/I / (2ab) j/2i + a 1/j+b 1/j / (2ab) 1/2j) √N] + 1 as a good approximations of Φ (N) for unknown positive integers d, di, ki, k, and zi. We construct four system of equations of the form esd − ksΦ(Ns) = 1, esds − kΦ (Ns) = 1, esd − kΦ (Ns) = zs and esds − kΦ (Ns) = zs where s = 1, 2, ..., t. In our attacks, we improve the short decryption exponent bounds of some reported attacks. Institute for Mathematical Research, Universiti Putra Malaysia 2018 Conference or Workshop Item PeerReviewed text en http://psasir.upm.edu.my/id/eprint/66551/1/Cryptology2018-6.pdf Abubakar, Saidu Isah and Kamel Ariffin, Muhammad Rezal and Asbullah, Muhammad Asyraf (2018) A new simultaneous diophantine attack upon RSA moduli N = pq. In: 6th International Cryptology and Information Security Conference 2018 (CRYPTOLOGY2018), 9-11 July 2018, Port Dickson, Negeri Sembilan, Malaysia. (pp. 119-138). |
| spellingShingle | Abubakar, Saidu Isah Kamel Ariffin, Muhammad Rezal Asbullah, Muhammad Asyraf A new simultaneous diophantine attack upon RSA moduli N = pq |
| title | A new simultaneous diophantine attack upon RSA moduli N = pq |
| title_full | A new simultaneous diophantine attack upon RSA moduli N = pq |
| title_fullStr | A new simultaneous diophantine attack upon RSA moduli N = pq |
| title_full_unstemmed | A new simultaneous diophantine attack upon RSA moduli N = pq |
| title_short | A new simultaneous diophantine attack upon RSA moduli N = pq |
| title_sort | new simultaneous diophantine attack upon rsa moduli n = pq |
| url | http://psasir.upm.edu.my/id/eprint/66551/ http://psasir.upm.edu.my/id/eprint/66551/1/Cryptology2018-6.pdf |