Factoring the Modulus of Type N = p 2 q by Finding Small Solutions of the Equation e r ? ( N s + t ) = ? p 2 + ? q 2

Muhammad Asyraf Asbullah, Normahirah Nek Abd Rahman, Muhammad Rezal Kamel Ariffin and Nur Raidah Salim
Additional contact information
Muhammad Asyraf Asbullah: Laboratory of Cryptography, Analysis and Structure, Institute for Mathematical Research, University Putra Malaysia, UPM, Serdang 43400, Malaysia
Normahirah Nek Abd Rahman: Pusat GENIUS@Pintar Negara, University Kebangsaan Malaysia, UKM, Bangi 43600, Malaysia
Muhammad Rezal Kamel Ariffin: Laboratory of Cryptography, Analysis and Structure, Institute for Mathematical Research, University Putra Malaysia, UPM, Serdang 43400, Malaysia
Nur Raidah Salim: Laboratory of Cryptography, Analysis and Structure, Institute for Mathematical Research, University Putra Malaysia, UPM, Serdang 43400, Malaysia

Mathematics, 2021, vol. 9, issue 22, 1-16

Abstract: The modulus of type N = p 2 q 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 = p 2 q 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 e r ? ( N s + t ) = ? p 2 + ? q 2 , 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 ( N i , e i ) where i = 1 , … , k . By using the lattice basis reduction algorithm for solving simultaneous Diophantine approximation, the k -instances of ( N i , e i ) can be successfully factored in polynomial time.

Keywords: cryptography; IoT security; lattice basis reduction; Diophantine approximation; pre-quantum cryptography (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/22/2931/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/22/2931/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:22:p:2931-:d:681519

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().