Welcome to the resource topic for 2018/609
Title:
Improved Results on Factoring General RSA Moduli with Known Bits
Authors: 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.
ePrint: https://eprint.iacr.org/2018/609
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .