New Cryptanalysis of Prime Power RSA with Two Private Exponents
Prime Power RSA is a variant of the RSA scheme due to Takagi with 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><m...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-10-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/12/21/3411 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1846173341327556608 |
|---|---|
| author | Shixiong Wang Minghao Sun |
| author_facet | Shixiong Wang Minghao Sun |
| author_sort | Shixiong Wang |
| collection | DOAJ |
| description | Prime Power RSA is a variant of the RSA scheme due to Takagi with 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><mi>r</mi></msup><mi>q</mi></mrow></semantics></math></inline-formula> for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>r</mi><mo>⩾</mo><mn>2</mn></mrow></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>p</mi><mo>,</mo><mi>q</mi></mrow></semantics></math></inline-formula> are of the same bit-size. In this paper, we concentrate on one type of Prime Power RSA which assumes <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>e</mi><mo>·</mo><mi>d</mi><mo>≡</mo><mn>1</mn><mspace width="4pt"></mspace><mi>mod</mi><mspace width="4pt"></mspace><msup><mi>p</mi><mrow><mi>r</mi><mo>−</mo><mn>1</mn></mrow></msup><mrow><mo>(</mo><mi>p</mi><mo>−</mo><mn>1</mn><mo>)</mo></mrow><mrow><mo>(</mo><mi>q</mi><mo>−</mo><mn>1</mn><mo>)</mo></mrow></mrow></semantics></math></inline-formula>. Two new attacks on this type of Prime Power RSA are presented when given two pairs of public and private exponents, namely, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><msub><mi>e</mi><mn>1</mn></msub><mo>,</mo><msub><mi>d</mi><mn>1</mn></msub><mo>)</mo></mrow></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><msub><mi>e</mi><mn>2</mn></msub><mo>,</mo><msub><mi>d</mi><mn>2</mn></msub><mo>)</mo></mrow></semantics></math></inline-formula> with the same modulus <i>N</i>. Suppose that <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>d</mi><mn>1</mn></msub><mo><</mo><msup><mi>N</mi><msub><mi>β</mi><mn>1</mn></msub></msup><mo>,</mo><msub><mi>d</mi><mn>2</mn></msub><mo><</mo><msup><mi>N</mi><msub><mi>β</mi><mn>2</mn></msub></msup></mrow></semantics></math></inline-formula>. In 2015, Zheng and Hu showed that when <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>β</mi><mn>1</mn></msub><msub><mi>β</mi><mn>2</mn></msub><mo><</mo><msup><mrow><mo>(</mo><mi>r</mi><mo>−</mo><mn>1</mn><mo>)</mo></mrow><mn>3</mn></msup><mo>/</mo><msup><mrow><mo>(</mo><mi>r</mi><mo>+</mo><mn>1</mn><mo>)</mo></mrow><mn>3</mn></msup></mrow></semantics></math></inline-formula>, <i>N</i> may be factored in probabilistic polynomial time. The first attack of this paper shows that one can obtain the factorization of <i>N</i> in probabilistic polynomial time, provided that <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>β</mi><mn>1</mn></msub><msub><mi>β</mi><mn>2</mn></msub><mo><</mo><mi>r</mi><mo>/</mo><msup><mrow><mo>(</mo><mi>r</mi><mo>+</mo><mn>1</mn><mo>)</mo></mrow><mn>3</mn></msup></mrow></semantics></math></inline-formula>. Later, in the second attack, we improve both the first attack and the attack of Zheng and Hu, and show that the condition <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>β</mi><mn>1</mn></msub><msub><mi>β</mi><mn>2</mn></msub><mo><</mo><mi>r</mi><msup><mrow><mo>(</mo><mi>r</mi><mo>−</mo><mn>1</mn><mo>)</mo></mrow><mn>2</mn></msup><mo>/</mo><msup><mrow><mo>(</mo><mi>r</mi><mo>+</mo><mn>1</mn><mo>)</mo></mrow><mn>3</mn></msup></mrow></semantics></math></inline-formula> already suffices to break the Prime Power RSA. By introducing multiple parameters, our lattice constructions take full advantage of known information, and obtain the best known attack. Specifically, we make full use of the information that <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mi>p</mi><mi>r</mi></msup></semantics></math></inline-formula> is a divisor of <i>N</i>, while the attack of Zheng and Hu only assumes that <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mi>p</mi><mrow><mi>r</mi><mo>−</mo><mn>1</mn></mrow></msup></semantics></math></inline-formula> is a divisor of <i>N</i>. As a consequence, this method implies a better lattice construction, and thus improves the previous attack. The experiments which reach a better upper bound than before also verify it. Our approaches are based on Coppersmith’s method for finding small roots of bivariate modular polynomial equations. |
| format | Article |
| id | doaj-art-c55e9d01ed5c4c3d9ce05ab0cd7e749b |
| institution | Kabale University |
| issn | 2227-7390 |
| language | English |
| publishDate | 2024-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj-art-c55e9d01ed5c4c3d9ce05ab0cd7e749b2024-11-08T14:37:51ZengMDPI AGMathematics2227-73902024-10-011221341110.3390/math12213411New Cryptanalysis of Prime Power RSA with Two Private ExponentsShixiong Wang0Minghao Sun1Academy of Military Sciences, Beijing 100091, ChinaThe PAP Command College, Tianjin 300100, ChinaPrime Power RSA is a variant of the RSA scheme due to Takagi with 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><mi>r</mi></msup><mi>q</mi></mrow></semantics></math></inline-formula> for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>r</mi><mo>⩾</mo><mn>2</mn></mrow></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>p</mi><mo>,</mo><mi>q</mi></mrow></semantics></math></inline-formula> are of the same bit-size. In this paper, we concentrate on one type of Prime Power RSA which assumes <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>e</mi><mo>·</mo><mi>d</mi><mo>≡</mo><mn>1</mn><mspace width="4pt"></mspace><mi>mod</mi><mspace width="4pt"></mspace><msup><mi>p</mi><mrow><mi>r</mi><mo>−</mo><mn>1</mn></mrow></msup><mrow><mo>(</mo><mi>p</mi><mo>−</mo><mn>1</mn><mo>)</mo></mrow><mrow><mo>(</mo><mi>q</mi><mo>−</mo><mn>1</mn><mo>)</mo></mrow></mrow></semantics></math></inline-formula>. Two new attacks on this type of Prime Power RSA are presented when given two pairs of public and private exponents, namely, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><msub><mi>e</mi><mn>1</mn></msub><mo>,</mo><msub><mi>d</mi><mn>1</mn></msub><mo>)</mo></mrow></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>(</mo><msub><mi>e</mi><mn>2</mn></msub><mo>,</mo><msub><mi>d</mi><mn>2</mn></msub><mo>)</mo></mrow></semantics></math></inline-formula> with the same modulus <i>N</i>. Suppose that <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>d</mi><mn>1</mn></msub><mo><</mo><msup><mi>N</mi><msub><mi>β</mi><mn>1</mn></msub></msup><mo>,</mo><msub><mi>d</mi><mn>2</mn></msub><mo><</mo><msup><mi>N</mi><msub><mi>β</mi><mn>2</mn></msub></msup></mrow></semantics></math></inline-formula>. In 2015, Zheng and Hu showed that when <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>β</mi><mn>1</mn></msub><msub><mi>β</mi><mn>2</mn></msub><mo><</mo><msup><mrow><mo>(</mo><mi>r</mi><mo>−</mo><mn>1</mn><mo>)</mo></mrow><mn>3</mn></msup><mo>/</mo><msup><mrow><mo>(</mo><mi>r</mi><mo>+</mo><mn>1</mn><mo>)</mo></mrow><mn>3</mn></msup></mrow></semantics></math></inline-formula>, <i>N</i> may be factored in probabilistic polynomial time. The first attack of this paper shows that one can obtain the factorization of <i>N</i> in probabilistic polynomial time, provided that <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>β</mi><mn>1</mn></msub><msub><mi>β</mi><mn>2</mn></msub><mo><</mo><mi>r</mi><mo>/</mo><msup><mrow><mo>(</mo><mi>r</mi><mo>+</mo><mn>1</mn><mo>)</mo></mrow><mn>3</mn></msup></mrow></semantics></math></inline-formula>. Later, in the second attack, we improve both the first attack and the attack of Zheng and Hu, and show that the condition <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>β</mi><mn>1</mn></msub><msub><mi>β</mi><mn>2</mn></msub><mo><</mo><mi>r</mi><msup><mrow><mo>(</mo><mi>r</mi><mo>−</mo><mn>1</mn><mo>)</mo></mrow><mn>2</mn></msup><mo>/</mo><msup><mrow><mo>(</mo><mi>r</mi><mo>+</mo><mn>1</mn><mo>)</mo></mrow><mn>3</mn></msup></mrow></semantics></math></inline-formula> already suffices to break the Prime Power RSA. By introducing multiple parameters, our lattice constructions take full advantage of known information, and obtain the best known attack. Specifically, we make full use of the information that <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mi>p</mi><mi>r</mi></msup></semantics></math></inline-formula> is a divisor of <i>N</i>, while the attack of Zheng and Hu only assumes that <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mi>p</mi><mrow><mi>r</mi><mo>−</mo><mn>1</mn></mrow></msup></semantics></math></inline-formula> is a divisor of <i>N</i>. As a consequence, this method implies a better lattice construction, and thus improves the previous attack. The experiments which reach a better upper bound than before also verify it. Our approaches are based on Coppersmith’s method for finding small roots of bivariate modular polynomial equations.https://www.mdpi.com/2227-7390/12/21/3411prime power RSAtwo private exponentslatticeCoppersmith’s methodLLL algorithm |
| spellingShingle | Shixiong Wang Minghao Sun New Cryptanalysis of Prime Power RSA with Two Private Exponents Mathematics prime power RSA two private exponents lattice Coppersmith’s method LLL algorithm |
| title | New Cryptanalysis of Prime Power RSA with Two Private Exponents |
| title_full | New Cryptanalysis of Prime Power RSA with Two Private Exponents |
| title_fullStr | New Cryptanalysis of Prime Power RSA with Two Private Exponents |
| title_full_unstemmed | New Cryptanalysis of Prime Power RSA with Two Private Exponents |
| title_short | New Cryptanalysis of Prime Power RSA with Two Private Exponents |
| title_sort | new cryptanalysis of prime power rsa with two private exponents |
| topic | prime power RSA two private exponents lattice Coppersmith’s method LLL algorithm |
| url | https://www.mdpi.com/2227-7390/12/21/3411 |
| work_keys_str_mv | AT shixiongwang newcryptanalysisofprimepowerrsawithtwoprivateexponents AT minghaosun newcryptanalysisofprimepowerrsawithtwoprivateexponents |