Cryptology ePrint Archive: Report 2018/609

Improved Results on Factoring General RSA Moduli with Known Bits

Mengce Zheng

Abstract: We revisit the factoring with known bits problem on general RSA moduli in the forms of $N=p^r q^s$ for $r,s\ge 1$, where two primes $p$ and $q$ are of the same bit-size. The relevant moduli are inclusive of $pq$, $p^r q$ for $r>1$, and $p^r q^s$ for $r,s>1$, which are used in the standard RSA scheme and other RSA-type variants. Previous works acquired the results mainly by solving univariate modular equations. In contrast, we investigate how to efficiently factor $N=p^r q^s$ with given leakage of the primes by the integer method using the lattice-based technique in this paper. More precisely, factoring general RSA moduli with known most significant bits (MSBs) of the primes can be reduced to solving bivariate integer equations, which was first proposed by Coppersmith to factor $N=pq$ with known high bits. Our results provide a unifying solution to the factoring with known bits problem on general RSA moduli. Furthermore, we reveal that there exists an improved factoring attack via the integer method for particular RSA moduli like $p^3 q^2$ and $p^5 q^3$.

Category / Keywords: public-key cryptography / Factorization, General RSA moduli, Known bits, Integer method, Lattice-based technique

Date: received 12 Jun 2018, last revised 19 Jun 2018

Contact author: mengce zheng at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20180622:144427 (All versions of this report)

Short URL: ia.cr/2018/609


[ Cryptology ePrint archive ]