Cryptology ePrint Archive: Report 2014/343

New Results on Solving Linear Equations Modulo Unknown Divisors and its Applications

Yao Lu and Rui Zhang and Dongdai Lin

Abstract: We revisit the problem of finding small solutions to a collection of linear equations modulo an unknown divisor $p$ for a known composite integer $N$. In Asiacrypt'08, Herrmann and May introduced a heuristic algorithm for this problem, and their algorithm has many interesting applications, such as factoring with known bits problem, fault attacks on RSA signatures, etc. In this paper, we consider two variants of Herrmann-May's equations, and propose some new techniques to solve them. Applying our algorithms, we obtain a few by far the best analytical/experimental results for 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 extend Nitaj's result (Africacrypt'12) on weak encryption exponents of RSA and CRT-RSA. \end{itemize}

Category / Keywords: public-key cryptography / lattice-based attack, RSA

Date: received 15 May 2014

Contact author: lywhhit at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20140519:163416 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]