Paper 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}