Paper 2014/343

Solving Linear Equations Modulo Unknown Divisors: Revisited

Yao Lu, Rui Zhang, Liqiang Peng, and Dongdai Lin


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 CaLC 2001, Howgrave-Graham introduced an efficient algorithm for solving univariate linear equations; since then, two forms of multivariate generalizations have been considered in the context of cryptanalysis: modular multivariate linear equations by Herrmann and May (Asiacrypt'08) and simultaneous modular univariate linear equations by Cohn and Heninger (ANTS'12). Their algorithms have many important applications in cryptanalysis, such as factoring with known bits problem, fault attacks on RSA signatures, analysis of approximate GCD problem, etc. 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}

Available format(s)
Publication info
Published by the IACR in ASIACRYPT 2015
Lattice-based analysisLinear modular equationsRSA
Contact author(s)
lywhhit @ gmail com
2015-09-07: revised
2014-05-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yao Lu and Rui Zhang and Liqiang Peng and Dongdai Lin},
      title = {Solving Linear Equations Modulo Unknown Divisors: Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2014/343},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.