Successful cryptanalytic attacks upon RSA moduli N = pq
This paper reports four new cryptanalytic attacks which show that t instances of RSA moduli Ns = psqs for s = 1, . . . , t where t ≥ 2 can be simultaneously factored in polynomial time using simultaneous Diophantine approximations and lattice basis reduction techniques. We construct four system of e...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Institute for Mathematical Research, Universiti Putra Malaysia
2019
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/76378/1/10.pdf |
| _version_ | 1796980051565084672 |
|---|---|
| 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 |
| collection | UPM |
| description | This paper reports four new cryptanalytic attacks which show that t instances of RSA moduli Ns = psqs for s = 1, . . . , t where t ≥ 2 can be simultaneously factored in polynomial time using simultaneous Diophantine approximations and lattice basis reduction techniques. 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 using N – [(a i+1/i + b i+1/i / 2(ab) i+1/2i + a 1/j + b 1/j / 2(ab) 1/2j) √N] + 1 as a good approximations of φ(Ns) for unknown positive integers d, ds, ks, k, and zs . In our attacks, we found an improved short decryption exponent bound of some reported attacks. |
| first_indexed | 2024-03-06T10:17:48Z |
| format | Article |
| id | upm.eprints-76378 |
| institution | Universiti Putra Malaysia |
| language | English |
| last_indexed | 2024-03-06T10:17:48Z |
| publishDate | 2019 |
| publisher | Institute for Mathematical Research, Universiti Putra Malaysia |
| record_format | dspace |
| spelling | upm.eprints-763782020-02-04T04:09:17Z http://psasir.upm.edu.my/id/eprint/76378/ Successful cryptanalytic attacks 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 t instances of RSA moduli Ns = psqs for s = 1, . . . , t where t ≥ 2 can be simultaneously factored in polynomial time using simultaneous Diophantine approximations and lattice basis reduction techniques. 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 using N – [(a i+1/i + b i+1/i / 2(ab) i+1/2i + a 1/j + b 1/j / 2(ab) 1/2j) √N] + 1 as a good approximations of φ(Ns) for unknown positive integers d, ds, ks, k, and zs . In our attacks, we found an improved short decryption exponent bound of some reported attacks. Institute for Mathematical Research, Universiti Putra Malaysia 2019 Article PeerReviewed text en http://psasir.upm.edu.my/id/eprint/76378/1/10.pdf Abubakar, Saidu Isah and Kamel Ariffin, Muhammad Rezal and Asbullah, Muhammad Asyraf (2019) Successful cryptanalytic attacks upon RSA moduli N = pq. Malaysian Journal of Mathematical Sciences, 13 (spec. Aug.). pp. 141-189. ISSN 1823-8343; ESSN: 2289-750X http://einspem.upm.edu.my/journal/fullpaper/vol13saugust/10.pdf |
| spellingShingle | Abubakar, Saidu Isah Kamel Ariffin, Muhammad Rezal Asbullah, Muhammad Asyraf Successful cryptanalytic attacks upon RSA moduli N = pq |
| title | Successful cryptanalytic attacks upon RSA moduli N = pq |
| title_full | Successful cryptanalytic attacks upon RSA moduli N = pq |
| title_fullStr | Successful cryptanalytic attacks upon RSA moduli N = pq |
| title_full_unstemmed | Successful cryptanalytic attacks upon RSA moduli N = pq |
| title_short | Successful cryptanalytic attacks upon RSA moduli N = pq |
| title_sort | successful cryptanalytic attacks upon rsa moduli n pq |
| url | http://psasir.upm.edu.my/id/eprint/76378/1/10.pdf |
| work_keys_str_mv | AT abubakarsaiduisah successfulcryptanalyticattacksuponrsamodulinpq AT kamelariffinmuhammadrezal successfulcryptanalyticattacksuponrsamodulinpq AT asbullahmuhammadasyraf successfulcryptanalyticattacksuponrsamodulinpq |