Factoring the modulus of type n = p2q by finding small solutions of the equation er − (ns + t) = αp2 + βq2
The modulus of type N=p2q is often used in many variants of factoring-based cryptosystems due to its ability to fasten the decryption process. Faster decryption is suitable for securing small devices in the Internet of Things (IoT) environment or securing fast-forwarding encryption services used in...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI
2021
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/97263/1/mathematics-09-02931-v2.pdf |
| _version_ | 1811137523459555328 |
|---|---|
| author | Asbullah, Muhammad Asyraf Abd Rahman, Normahirah Nek Kamel Ariffin, Muhammad Rezal Salim, Nur Raidah |
| author_facet | Asbullah, Muhammad Asyraf Abd Rahman, Normahirah Nek Kamel Ariffin, Muhammad Rezal Salim, Nur Raidah |
| author_sort | Asbullah, Muhammad Asyraf |
| collection | UPM |
| description | The modulus of type N=p2q is often used in many variants of factoring-based cryptosystems due to its ability to fasten the decryption process. Faster decryption is suitable for securing small devices in the Internet of Things (IoT) environment or securing fast-forwarding encryption services used in mobile applications. Taking this into account, the security analysis of such modulus is indeed paramount. This paper presents two cryptanalyses that use new enabling conditions to factor the modulus N=p2q of the factoring-based cryptosystem. The first cryptanalysis considers a single user with a public key pair (e,N) related via an arbitrary relation to equation er−(Ns+t)=αp2+βq2, where r,s,t are unknown parameters. The second cryptanalysis considers two distinct cases in the situation of k-users (i.e., multiple users) for k≥2, given the instances of (Ni,ei) where i=1,…,k. By using the lattice basis reduction algorithm for solving simultaneous Diophantine approximation, the k-instances of (Ni,ei) can be successfully factored in polynomial time. |
| first_indexed | 2024-09-25T03:35:39Z |
| format | Article |
| id | upm.eprints-97263 |
| institution | Universiti Putra Malaysia |
| language | English |
| last_indexed | 2024-09-25T03:35:39Z |
| publishDate | 2021 |
| publisher | MDPI |
| record_format | dspace |
| spelling | upm.eprints-972632024-07-29T06:44:47Z http://psasir.upm.edu.my/id/eprint/97263/ Factoring the modulus of type n = p2q by finding small solutions of the equation er − (ns + t) = αp2 + βq2 Asbullah, Muhammad Asyraf Abd Rahman, Normahirah Nek Kamel Ariffin, Muhammad Rezal Salim, Nur Raidah The modulus of type N=p2q is often used in many variants of factoring-based cryptosystems due to its ability to fasten the decryption process. Faster decryption is suitable for securing small devices in the Internet of Things (IoT) environment or securing fast-forwarding encryption services used in mobile applications. Taking this into account, the security analysis of such modulus is indeed paramount. This paper presents two cryptanalyses that use new enabling conditions to factor the modulus N=p2q of the factoring-based cryptosystem. The first cryptanalysis considers a single user with a public key pair (e,N) related via an arbitrary relation to equation er−(Ns+t)=αp2+βq2, where r,s,t are unknown parameters. The second cryptanalysis considers two distinct cases in the situation of k-users (i.e., multiple users) for k≥2, given the instances of (Ni,ei) where i=1,…,k. By using the lattice basis reduction algorithm for solving simultaneous Diophantine approximation, the k-instances of (Ni,ei) can be successfully factored in polynomial time. MDPI 2021-11-17 Article PeerReviewed text en http://psasir.upm.edu.my/id/eprint/97263/1/mathematics-09-02931-v2.pdf Asbullah, Muhammad Asyraf and Abd Rahman, Normahirah Nek and Kamel Ariffin, Muhammad Rezal and Salim, Nur Raidah (2021) Factoring the modulus of type n = p2q by finding small solutions of the equation er − (ns + t) = αp2 + βq2. Mathematics, 9 (22). art. no. 2931. pp. 1-16. ISSN 2227-7390 https://www.mdpi.com/2227-7390/9/22/2931 10.3390/math9222931 |
| spellingShingle | Asbullah, Muhammad Asyraf Abd Rahman, Normahirah Nek Kamel Ariffin, Muhammad Rezal Salim, Nur Raidah Factoring the modulus of type n = p2q by finding small solutions of the equation er − (ns + t) = αp2 + βq2 |
| title | Factoring the modulus of type n = p2q by finding small solutions of the equation er − (ns + t) = αp2 + βq2 |
| title_full | Factoring the modulus of type n = p2q by finding small solutions of the equation er − (ns + t) = αp2 + βq2 |
| title_fullStr | Factoring the modulus of type n = p2q by finding small solutions of the equation er − (ns + t) = αp2 + βq2 |
| title_full_unstemmed | Factoring the modulus of type n = p2q by finding small solutions of the equation er − (ns + t) = αp2 + βq2 |
| title_short | Factoring the modulus of type n = p2q by finding small solutions of the equation er − (ns + t) = αp2 + βq2 |
| title_sort | factoring the modulus of type n p2q by finding small solutions of the equation er ns t αp2 βq2 |
| url | http://psasir.upm.edu.my/id/eprint/97263/1/mathematics-09-02931-v2.pdf |
| work_keys_str_mv | AT asbullahmuhammadasyraf factoringthemodulusoftypenp2qbyfindingsmallsolutionsoftheequationernstap2bq2 AT abdrahmannormahirahnek factoringthemodulusoftypenp2qbyfindingsmallsolutionsoftheequationernstap2bq2 AT kamelariffinmuhammadrezal factoringthemodulusoftypenp2qbyfindingsmallsolutionsoftheequationernstap2bq2 AT salimnurraidah factoringthemodulusoftypenp2qbyfindingsmallsolutionsoftheequationernstap2bq2 |