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$.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint.
Keywords
FactorizationGeneral RSA moduliKnown bitsInteger methodLattice-based technique
Contact author(s)
mengce zheng @ gmail com
History
Short URL
https://ia.cr/2018/609

CC BY

BibTeX

@misc{cryptoeprint:2018/609,
author = {Mengce Zheng},
title = {Improved Results on Factoring General RSA Moduli with Known Bits},
howpublished = {Cryptology ePrint Archive, Paper 2018/609},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/609}},
url = {https://eprint.iacr.org/2018/609}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.