Factoring the Modulus of Type N = p2q by Finding Small Solutions of the Equation er − (Ns + t) = αp2 + βq2

The modulus of type <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>N</mi><mo>=</mo><msup><mi>p</mi><mn>2</mn></msup><mi>q</mi>&l...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Muhammad Asyraf Asbullah, Normahirah Nek Abd Rahman, Muhammad Rezal Kamel Ariffin, Nur Raidah Salim
Formato:	article
Lenguaje:	EN
Publicado:	MDPI AG 2021
Materias:	cryptography IoT security lattice basis reduction Diophantine approximation pre-quantum cryptography Mathematics QA1-939
Acceso en línea:	https://doaj.org/article/5e5ef54cbe1c42108cb03ac6701886d7
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:5e5ef54cbe1c42108cb03ac6701886d7
record_format	dspace
spelling	oai:doaj.org-article:5e5ef54cbe1c42108cb03ac6701886d72021-11-25T18:17:19ZFactoring the Modulus of Type <i>N</i> = <i>p</i><sup>2</sup><i>q</i> by Finding Small Solutions of the Equation <i>e</i><i>r</i> − (<i>N</i><i>s</i> + <i>t</i>) = <i>α</i><i>p</i><sup>2</sup> + <i>β</i><i>q</i><sup>2</sup>10.3390/math92229312227-7390https://doaj.org/article/5e5ef54cbe1c42108cb03ac6701886d72021-11-01T00:00:00Zhttps://www.mdpi.com/2227-7390/9/22/2931https://doaj.org/toc/2227-7390The modulus of type <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>N</mi><mo>=</mo><msup><mi>p</mi><mn>2</mn></msup><mi>q</mi></mrow></semantics></math></inline-formula> 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>N</mi><mo>=</mo><msup><mi>p</mi><mn>2</mn></msup><mi>q</mi></mrow></semantics></math></inline-formula> of the factoring-based cryptosystem. The first cryptanalysis considers a single user with a public key pair <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mi>e</mi><mo>,</mo><mi>N</mi><mo>)</mo></mrow></semantics></math></inline-formula> related via an arbitrary relation to equation <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>e</mi><mi>r</mi><mo>−</mo><mrow><mo>(</mo><mi>N</mi><mi>s</mi><mo>+</mo><mi>t</mi><mo>)</mo></mrow><mo>=</mo><mi>α</mi><msup><mi>p</mi><mn>2</mn></msup><mo>+</mo><mi>β</mi><msup><mi>q</mi><mn>2</mn></msup></mrow></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>r</mi><mo>,</mo><mi>s</mi><mo>,</mo><mi>t</mi></mrow></semantics></math></inline-formula> are unknown parameters. The second cryptanalysis considers two distinct cases in the situation of <i>k</i>-users (i.e., multiple users) for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>≥</mo><mn>2</mn></mrow></semantics></math></inline-formula>, given the instances of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><msub><mi>N</mi><mi>i</mi></msub><mo>,</mo><msub><mi>e</mi><mi>i</mi></msub><mo>)</mo></mrow></semantics></math></inline-formula> where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>i</mi><mo>=</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>k</mi></mrow></semantics></math></inline-formula>. By using the lattice basis reduction algorithm for solving simultaneous Diophantine approximation, the <i>k</i>-instances of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><msub><mi>N</mi><mi>i</mi></msub><mo>,</mo><msub><mi>e</mi><mi>i</mi></msub><mo>)</mo></mrow></semantics></math></inline-formula> can be successfully factored in polynomial time.Muhammad Asyraf AsbullahNormahirah Nek Abd RahmanMuhammad Rezal Kamel AriffinNur Raidah SalimMDPI AGarticlecryptographyIoT securitylattice basis reductionDiophantine approximationpre-quantum cryptographyMathematicsQA1-939ENMathematics, Vol 9, Iss 2931, p 2931 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	cryptography IoT security lattice basis reduction Diophantine approximation pre-quantum cryptography Mathematics QA1-939
spellingShingle	cryptography IoT security lattice basis reduction Diophantine approximation pre-quantum cryptography Mathematics QA1-939 Muhammad Asyraf Asbullah Normahirah Nek Abd Rahman Muhammad Rezal Kamel Ariffin Nur Raidah Salim Factoring the Modulus of Type <i>N</i> = <i>p</i><sup>2</sup><i>q</i> by Finding Small Solutions of the Equation <i>e</i><i>r</i> − (<i>N</i><i>s</i> + <i>t</i>) = <i>α</i><i>p</i><sup>2</sup> + <i>β</i><i>q</i><sup>2</sup>
description	The modulus of type <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>N</mi><mo>=</mo><msup><mi>p</mi><mn>2</mn></msup><mi>q</mi></mrow></semantics></math></inline-formula> 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>N</mi><mo>=</mo><msup><mi>p</mi><mn>2</mn></msup><mi>q</mi></mrow></semantics></math></inline-formula> of the factoring-based cryptosystem. The first cryptanalysis considers a single user with a public key pair <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><mi>e</mi><mo>,</mo><mi>N</mi><mo>)</mo></mrow></semantics></math></inline-formula> related via an arbitrary relation to equation <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>e</mi><mi>r</mi><mo>−</mo><mrow><mo>(</mo><mi>N</mi><mi>s</mi><mo>+</mo><mi>t</mi><mo>)</mo></mrow><mo>=</mo><mi>α</mi><msup><mi>p</mi><mn>2</mn></msup><mo>+</mo><mi>β</mi><msup><mi>q</mi><mn>2</mn></msup></mrow></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>r</mi><mo>,</mo><mi>s</mi><mo>,</mo><mi>t</mi></mrow></semantics></math></inline-formula> are unknown parameters. The second cryptanalysis considers two distinct cases in the situation of <i>k</i>-users (i.e., multiple users) for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>≥</mo><mn>2</mn></mrow></semantics></math></inline-formula>, given the instances of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><msub><mi>N</mi><mi>i</mi></msub><mo>,</mo><msub><mi>e</mi><mi>i</mi></msub><mo>)</mo></mrow></semantics></math></inline-formula> where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>i</mi><mo>=</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>k</mi></mrow></semantics></math></inline-formula>. By using the lattice basis reduction algorithm for solving simultaneous Diophantine approximation, the <i>k</i>-instances of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><msub><mi>N</mi><mi>i</mi></msub><mo>,</mo><msub><mi>e</mi><mi>i</mi></msub><mo>)</mo></mrow></semantics></math></inline-formula> can be successfully factored in polynomial time.
format	article
author	Muhammad Asyraf Asbullah Normahirah Nek Abd Rahman Muhammad Rezal Kamel Ariffin Nur Raidah Salim
author_facet	Muhammad Asyraf Asbullah Normahirah Nek Abd Rahman Muhammad Rezal Kamel Ariffin Nur Raidah Salim
author_sort	Muhammad Asyraf Asbullah
title	Factoring the Modulus of Type <i>N</i> = <i>p</i><sup>2</sup><i>q</i> by Finding Small Solutions of the Equation <i>e</i><i>r</i> − (<i>N</i><i>s</i> + <i>t</i>) = <i>α</i><i>p</i><sup>2</sup> + <i>β</i><i>q</i><sup>2</sup>
title_short	Factoring the Modulus of Type <i>N</i> = <i>p</i><sup>2</sup><i>q</i> by Finding Small Solutions of the Equation <i>e</i><i>r</i> − (<i>N</i><i>s</i> + <i>t</i>) = <i>α</i><i>p</i><sup>2</sup> + <i>β</i><i>q</i><sup>2</sup>
title_full	Factoring the Modulus of Type <i>N</i> = <i>p</i><sup>2</sup><i>q</i> by Finding Small Solutions of the Equation <i>e</i><i>r</i> − (<i>N</i><i>s</i> + <i>t</i>) = <i>α</i><i>p</i><sup>2</sup> + <i>β</i><i>q</i><sup>2</sup>
title_fullStr	Factoring the Modulus of Type <i>N</i> = <i>p</i><sup>2</sup><i>q</i> by Finding Small Solutions of the Equation <i>e</i><i>r</i> − (<i>N</i><i>s</i> + <i>t</i>) = <i>α</i><i>p</i><sup>2</sup> + <i>β</i><i>q</i><sup>2</sup>
title_full_unstemmed	Factoring the Modulus of Type <i>N</i> = <i>p</i><sup>2</sup><i>q</i> by Finding Small Solutions of the Equation <i>e</i><i>r</i> − (<i>N</i><i>s</i> + <i>t</i>) = <i>α</i><i>p</i><sup>2</sup> + <i>β</i><i>q</i><sup>2</sup>
title_sort	factoring the modulus of type <i>n</i> = <i>p</i><sup>2</sup><i>q</i> by finding small solutions of the equation <i>e</i><i>r</i> − (<i>n</i><i>s</i> + <i>t</i>) = <i>α</i><i>p</i><sup>2</sup> + <i>β</i><i>q</i><sup>2</sup>
publisher	MDPI AG
publishDate	2021
url	https://doaj.org/article/5e5ef54cbe1c42108cb03ac6701886d7
work_keys_str_mv	AT muhammadasyrafasbullah factoringthemodulusoftypeiniipisup2supiqibyfindingsmallsolutionsoftheequationieiiriiniisiitiiaiipisup2supibiiqisup2sup AT normahirahnekabdrahman factoringthemodulusoftypeiniipisup2supiqibyfindingsmallsolutionsoftheequationieiiriiniisiitiiaiipisup2supibiiqisup2sup AT muhammadrezalkamelariffin factoringthemodulusoftypeiniipisup2supiqibyfindingsmallsolutionsoftheequationieiiriiniisiitiiaiipisup2supibiiqisup2sup AT nurraidahsalim factoringthemodulusoftypeiniipisup2supiqibyfindingsmallsolutionsoftheequationieiiriiniisiitiiaiipisup2supibiiqisup2sup
_version_	1718411383328997376

Factoring the Modulus of Type <i>N</i> = <i>p</i><sup>2</sup><i>q</i> by Finding Small Solutions of the Equation <i>e</i><i>r</i> − (<i>N</i><i>s</i> + <i>t</i>) = <i>α</i><i>p</i><sup>2</sup> + <i>β</i><i>q</i><sup>2</sup>

Ejemplares similares