New Results on Solving Linear Equations Modulo Unknown Divisors and its Applications.
Yao Lu, Rui Zhang, Dongdai Lin · 2014
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, – We improve May’s results (PKC’04) on small secret exponent attack on RSA variant with moduli N = prq (r ≥ 2). – We extend Nitaj’s result (Africacrypt’12) on weak encryption exponents of RSA and CRT-RSA.