Increment of insecure RSA private exponent bound through perfect square RSA diophantine parameters cryptanalysis
The public parameters of the RSA cryptosystem are represented by the pair of integers N and e. In this work, first we show that if e satisfies the Diophantine equation of the form ex2−ϕ(N)y2=z for appropriate values of x,y and z under certain specified conditions, then one is able to factor N. That...
| Главные авторы: | , , , , |
|---|---|
| Формат: | Статья |
| Опубликовано: |
Elsevier
2022
|
| _version_ | 1825938597686018048 |
|---|---|
| author | Wan Mohd Ruzai, Wan Nur Aqlili Nitaj, Abderrahmane Kamel Ariffin, Muhammad Rezal Mahad, Zahari Asbullah, Muhammad Asyraf |
| author_facet | Wan Mohd Ruzai, Wan Nur Aqlili Nitaj, Abderrahmane Kamel Ariffin, Muhammad Rezal Mahad, Zahari Asbullah, Muhammad Asyraf |
| author_sort | Wan Mohd Ruzai, Wan Nur Aqlili |
| collection | UPM |
| description | The public parameters of the RSA cryptosystem are represented by the pair of integers N and e. In this work, first we show that if e satisfies the Diophantine equation of the form ex2−ϕ(N)y2=z for appropriate values of x,y and z under certain specified conditions, then one is able to factor N. That is, the unknown [Formula presented] can be found amongst the convergents of [Formula presented] via continued fractions algorithm. Consequently, Coppersmith's theorem is applied to solve for prime factors p and q in polynomial time. We also report a second weakness that enabled us to factor k instances of RSA moduli simultaneously from the given (Ni,ei) for i=1,2,⋯,k and a fixed x that fulfills the Diophantine equation eix2−yi2ϕ(Ni)=zi. This weakness was identified by solving the simultaneous Diophantine approximations using the lattice basis reduction technique. We note that this work extends the bound of insecure RSA decryption exponents. |
| first_indexed | 2024-03-06T11:15:59Z |
| format | Article |
| id | upm.eprints-101837 |
| institution | Universiti Putra Malaysia |
| last_indexed | 2024-03-06T11:15:59Z |
| publishDate | 2022 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | upm.eprints-1018372023-07-12T01:55:18Z http://psasir.upm.edu.my/id/eprint/101837/ Increment of insecure RSA private exponent bound through perfect square RSA diophantine parameters cryptanalysis Wan Mohd Ruzai, Wan Nur Aqlili Nitaj, Abderrahmane Kamel Ariffin, Muhammad Rezal Mahad, Zahari Asbullah, Muhammad Asyraf The public parameters of the RSA cryptosystem are represented by the pair of integers N and e. In this work, first we show that if e satisfies the Diophantine equation of the form ex2−ϕ(N)y2=z for appropriate values of x,y and z under certain specified conditions, then one is able to factor N. That is, the unknown [Formula presented] can be found amongst the convergents of [Formula presented] via continued fractions algorithm. Consequently, Coppersmith's theorem is applied to solve for prime factors p and q in polynomial time. We also report a second weakness that enabled us to factor k instances of RSA moduli simultaneously from the given (Ni,ei) for i=1,2,⋯,k and a fixed x that fulfills the Diophantine equation eix2−yi2ϕ(Ni)=zi. This weakness was identified by solving the simultaneous Diophantine approximations using the lattice basis reduction technique. We note that this work extends the bound of insecure RSA decryption exponents. Elsevier 2022 Article PeerReviewed Wan Mohd Ruzai, Wan Nur Aqlili and Nitaj, Abderrahmane and Kamel Ariffin, Muhammad Rezal and Mahad, Zahari and Asbullah, Muhammad Asyraf (2022) Increment of insecure RSA private exponent bound through perfect square RSA diophantine parameters cryptanalysis. Computer Standards & Interfaces, 80. pp. 1-10. ISSN 0920-5489; ESSN: 1872-7018 https://www.sciencedirect.com/science/article/pii/S0920548921000799 10.1016/j.csi.2021.103584 |
| spellingShingle | Wan Mohd Ruzai, Wan Nur Aqlili Nitaj, Abderrahmane Kamel Ariffin, Muhammad Rezal Mahad, Zahari Asbullah, Muhammad Asyraf Increment of insecure RSA private exponent bound through perfect square RSA diophantine parameters cryptanalysis |
| title | Increment of insecure RSA private exponent bound through perfect square RSA diophantine parameters cryptanalysis |
| title_full | Increment of insecure RSA private exponent bound through perfect square RSA diophantine parameters cryptanalysis |
| title_fullStr | Increment of insecure RSA private exponent bound through perfect square RSA diophantine parameters cryptanalysis |
| title_full_unstemmed | Increment of insecure RSA private exponent bound through perfect square RSA diophantine parameters cryptanalysis |
| title_short | Increment of insecure RSA private exponent bound through perfect square RSA diophantine parameters cryptanalysis |
| title_sort | increment of insecure rsa private exponent bound through perfect square rsa diophantine parameters cryptanalysis |
| work_keys_str_mv | AT wanmohdruzaiwannuraqlili incrementofinsecurersaprivateexponentboundthroughperfectsquarersadiophantineparameterscryptanalysis AT nitajabderrahmane incrementofinsecurersaprivateexponentboundthroughperfectsquarersadiophantineparameterscryptanalysis AT kamelariffinmuhammadrezal incrementofinsecurersaprivateexponentboundthroughperfectsquarersadiophantineparameterscryptanalysis AT mahadzahari incrementofinsecurersaprivateexponentboundthroughperfectsquarersadiophantineparameterscryptanalysis AT asbullahmuhammadasyraf incrementofinsecurersaprivateexponentboundthroughperfectsquarersadiophantineparameterscryptanalysis |