Partial Exposure Attacks Against a Family of RSA-like Cryptosystems
An RSA generalization using complex integers was introduced by Elkamchouchi, Elshenawy and Shaban in 2002. This scheme was further extended by Cotan and Teșeleanu to Galois fields of order <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"&...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-12-01
|
| Series: | Cryptography |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2410-387X/9/1/2 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | An RSA generalization using complex integers was introduced by Elkamchouchi, Elshenawy and Shaban in 2002. This scheme was further extended by Cotan and Teșeleanu to Galois fields of order <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>≥</mo><mn>1</mn></mrow></semantics></math></inline-formula>. In this generalized framework, the key equation is <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>e</mi><mi>d</mi><mo>−</mo><mi>k</mi><mrow><mo>(</mo><msup><mi>p</mi><mi>n</mi></msup><mo>−</mo><mn>1</mn><mo>)</mo></mrow><mrow><mo>(</mo><msup><mi>q</mi><mi>n</mi></msup><mo>−</mo><mn>1</mn><mo>)</mo></mrow><mo>=</mo><mn>1</mn></mrow></semantics></math></inline-formula>, where <i>p</i> and <i>q</i> are prime numbers. Note that the classical RSA and Elkamchouchi et al.’s key equations are special cases, namely, when <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>=</mo><mn>2</mn></mrow></semantics></math></inline-formula>. In addition to introducing this generic family, Cotan and Teșeleanu described a continued fractions attack capable of recovering the secret key <i>d</i> if <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>d</mi><mo><</mo><msup><mi>N</mi><mrow><mn>0.25</mn><mi>n</mi></mrow></msup></mrow></semantics></math></inline-formula>. This bound was later improved by Teșeleanu using a lattice-based method. In this paper, we explore other lattice attacks that could lead to factoring the modulus <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>N</mi><mo>=</mo><mi>p</mi><mi>q</mi></mrow></semantics></math></inline-formula>, namely, we propose a series of partial exposure attacks that can aid an adversary in breaking this family of cryptosystems if certain conditions hold. |
|---|---|
| ISSN: | 2410-387X |