New Cryptanalysis of Prime Power RSA with Two Private Exponents

Shixiong Wang and Minghao Sun ()
Additional contact information
Shixiong Wang: Academy of Military Sciences, Beijing 100091, China
Minghao Sun: The PAP Command College, Tianjin 300100, China

Mathematics, 2024, vol. 12, issue 21, 1-12

Abstract: Prime Power RSA is a variant of the RSA scheme due to Takagi with modulus N = p r q for r ⩾ 2 , where p , q are of the same bit-size. In this paper, we concentrate on one type of Prime Power RSA which assumes e · d ≡ 1 mod p r − 1 ( p − 1 ) ( q − 1 ) . Two new attacks on this type of Prime Power RSA are presented when given two pairs of public and private exponents, namely, ( e 1 , d 1 ) and ( e 2 , d 2 ) with the same modulus N . Suppose that d 1 < N β 1 , d 2 < N β 2 . In 2015, Zheng and Hu showed that when β 1 β 2 < ( r − 1 ) 3 / ( r + 1 ) 3 , N may be factored in probabilistic polynomial time. The first attack of this paper shows that one can obtain the factorization of N in probabilistic polynomial time, provided that β 1 β 2 < r / ( r + 1 ) 3 . Later, in the second attack, we improve both the first attack and the attack of Zheng and Hu, and show that the condition β 1 β 2 < r ( r − 1 ) 2 / ( r + 1 ) 3 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 p r is a divisor of N , while the attack of Zheng and Hu only assumes that p r − 1 is a divisor of N . 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.

Keywords: prime power RSA; two private exponents; lattice; Coppersmith’s method; LLL algorithm (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/21/3411/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/21/3411/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:21:p:3411-:d:1511839

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().