In this paper, by introducing multiple parameters, we propose several generalizations of the above equations. The motivation behind these extensions is that some attacks on RSA variants can be reduced to solving these generalized equations, and previous algorithms do not apply. We present new approaches to solve them, and compared with previous methods, our new algorithms are more flexible and especially suitable for some cases. Applying our algorithms, we obtain the best analytical/experimental results for some attacks on RSA and its variants, specifically,
\begin{itemize} \item We improve May's results (PKC'04) on small secret exponent attack on RSA variant with moduli $N = p^rq$ ($r\geq 2$). \item We experimentally improve Boneh et al.'s algorithm (Crypto'98) on factoring $N=p^rq$ ($r\geq 2$) with known bits problem. \item We significantly improve Jochemsz-May' attack (Asiacrypt'06) on Common Prime RSA. \item We extend Nitaj's result (Africacrypt'12) on weak encryption exponents of RSA and CRT-RSA. \end{itemize}
Category / Keywords: Lattice-based analysis, Linear modular equations, RSA Original Publication (in the same form): IACR-ASIACRYPT-2015 Date: received 15 May 2014, last revised 6 Sep 2015 Contact author: lywhhit at gmail com Available format(s): PDF | BibTeX Citation Version: 20150907:034446 (All versions of this report) Short URL: ia.cr/2014/343 Discussion forum: Show discussion | Start new discussion