Partial Exposure Attacks on a New RSA Variant
In 2022, Cotan and Teşeleanu presented a variant of the RSA cryptosystem where the modulus is of the form <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>N</mi><mo>=</mo><mi&...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-10-01
|
| Series: | Cryptography |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2410-387X/8/4/44 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850241943778361344 |
|---|---|
| author | Mohammed Rahmani Abderrahmane Nitaj Mhammed Ziane |
| author_facet | Mohammed Rahmani Abderrahmane Nitaj Mhammed Ziane |
| author_sort | Mohammed Rahmani |
| collection | DOAJ |
| description | In 2022, Cotan and Teşeleanu presented a variant of the RSA cryptosystem where the modulus is of the form <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>, and the private and the public exponents satisfy <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>e</mi><mi>d</mi><mo>≡</mo><mn>1</mn><mspace width="4.44443pt"></mspace><mo>(</mo><mo mathvariant="normal">mod</mo><mspace width="0.277778em"></mspace><msub><mi>ψ</mi><mi>n</mi></msub><mrow><mo>(</mo><mi>N</mi><mo>)</mo></mrow><mo>)</mo></mrow></semantics></math></inline-formula> with <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>, and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>ψ</mi><mi>n</mi></msub><mrow><mo>(</mo><mi>N</mi><mo>)</mo></mrow><mo>=</mo><mfrac><mrow><mfenced separators="" open="(" close=")"><msup><mi>p</mi><mi>n</mi></msup><mo>−</mo><mn>1</mn></mfenced><mfenced separators="" open="(" close=")"><msup><mi>q</mi><mi>n</mi></msup><mo>−</mo><mn>1</mn></mfenced></mrow><mrow><mo>(</mo><mi>p</mi><mo>−</mo><mn>1</mn><mo>)</mo><mo>(</mo><mi>q</mi><mo>−</mo><mn>1</mn><mo>)</mo></mrow></mfrac></mrow></semantics></math></inline-formula>. This variant of RSA was recently cryptanalyzed by Nitaj, Adenan, and Ariffin at Africacrypt 2024. In this paper, we push further the cryptanalysis of the scheme of Cotan and Teşeleanu by presenting a method to solve the equation <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>x</mi><mi>H</mi><mo>(</mo><mi>y</mi><mo>)</mo><mo>+</mo><mi>c</mi><mo>≡</mo><mn>0</mn><mspace width="4.44443pt"></mspace><mo>(</mo><mo mathvariant="normal">mod</mo><mspace width="0.277778em"></mspace><mi>e</mi><mo>)</mo></mrow></semantics></math></inline-formula> where <i>c</i> is a constant that is independent of <i>x</i> and <i>y</i>. This enables us to propose more attacks on the scheme, including a partial key exposure attack, an attack when the most significant bits of one of the prime factors are known, and an attack when the least significant bits of one of the prime factors are known. |
| format | Article |
| id | doaj-art-2c95b304ca404e8aaf840bb3398fd29e |
| institution | OA Journals |
| issn | 2410-387X |
| language | English |
| publishDate | 2024-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Cryptography |
| spelling | doaj-art-2c95b304ca404e8aaf840bb3398fd29e2025-08-20T02:00:26ZengMDPI AGCryptography2410-387X2024-10-01844410.3390/cryptography8040044Partial Exposure Attacks on a New RSA VariantMohammed Rahmani0Abderrahmane Nitaj1Mhammed Ziane2ACSA Laboratory, Department of Mathematics and Computer Science, Sciences Faculty, Mohammed First University, Oujda 60000, MoroccoLMNO, CNRS, UNICAEN, Caen Normandie University, 14000 Caen, FranceACSA Laboratory, Department of Mathematics and Computer Science, Sciences Faculty, Mohammed First University, Oujda 60000, MoroccoIn 2022, Cotan and Teşeleanu presented a variant of the RSA cryptosystem where the modulus is of the form <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>, and the private and the public exponents satisfy <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>e</mi><mi>d</mi><mo>≡</mo><mn>1</mn><mspace width="4.44443pt"></mspace><mo>(</mo><mo mathvariant="normal">mod</mo><mspace width="0.277778em"></mspace><msub><mi>ψ</mi><mi>n</mi></msub><mrow><mo>(</mo><mi>N</mi><mo>)</mo></mrow><mo>)</mo></mrow></semantics></math></inline-formula> with <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>, and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>ψ</mi><mi>n</mi></msub><mrow><mo>(</mo><mi>N</mi><mo>)</mo></mrow><mo>=</mo><mfrac><mrow><mfenced separators="" open="(" close=")"><msup><mi>p</mi><mi>n</mi></msup><mo>−</mo><mn>1</mn></mfenced><mfenced separators="" open="(" close=")"><msup><mi>q</mi><mi>n</mi></msup><mo>−</mo><mn>1</mn></mfenced></mrow><mrow><mo>(</mo><mi>p</mi><mo>−</mo><mn>1</mn><mo>)</mo><mo>(</mo><mi>q</mi><mo>−</mo><mn>1</mn><mo>)</mo></mrow></mfrac></mrow></semantics></math></inline-formula>. This variant of RSA was recently cryptanalyzed by Nitaj, Adenan, and Ariffin at Africacrypt 2024. In this paper, we push further the cryptanalysis of the scheme of Cotan and Teşeleanu by presenting a method to solve the equation <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>x</mi><mi>H</mi><mo>(</mo><mi>y</mi><mo>)</mo><mo>+</mo><mi>c</mi><mo>≡</mo><mn>0</mn><mspace width="4.44443pt"></mspace><mo>(</mo><mo mathvariant="normal">mod</mo><mspace width="0.277778em"></mspace><mi>e</mi><mo>)</mo></mrow></semantics></math></inline-formula> where <i>c</i> is a constant that is independent of <i>x</i> and <i>y</i>. This enables us to propose more attacks on the scheme, including a partial key exposure attack, an attack when the most significant bits of one of the prime factors are known, and an attack when the least significant bits of one of the prime factors are known.https://www.mdpi.com/2410-387X/8/4/44RSAfactorizationCoppersmith’s methodlattice basis reductionRSA variants |
| spellingShingle | Mohammed Rahmani Abderrahmane Nitaj Mhammed Ziane Partial Exposure Attacks on a New RSA Variant Cryptography RSA factorization Coppersmith’s method lattice basis reduction RSA variants |
| title | Partial Exposure Attacks on a New RSA Variant |
| title_full | Partial Exposure Attacks on a New RSA Variant |
| title_fullStr | Partial Exposure Attacks on a New RSA Variant |
| title_full_unstemmed | Partial Exposure Attacks on a New RSA Variant |
| title_short | Partial Exposure Attacks on a New RSA Variant |
| title_sort | partial exposure attacks on a new rsa variant |
| topic | RSA factorization Coppersmith’s method lattice basis reduction RSA variants |
| url | https://www.mdpi.com/2410-387X/8/4/44 |
| work_keys_str_mv | AT mohammedrahmani partialexposureattacksonanewrsavariant AT abderrahmanenitaj partialexposureattacksonanewrsavariant AT mhammedziane partialexposureattacksonanewrsavariant |