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>
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...
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | article |
| Lenguaje: | EN |
| Publicado: |
MDPI AG
2021
|
| Materias: | |
| Acceso en línea: | https://doaj.org/article/5e5ef54cbe1c42108cb03ac6701886d7 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| Sumario: | 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. |
|---|