Paper 2018/568

Finding Small Solutions of the Equation $Bx-Ay=z$ and Its Applications to Cryptanalysis of the RSA Cryptosystem

Shixiong Wang, Longjiang Qu, Chao Li, Shaojing Fu, and Hao Chen

Abstract

In this paper, we study the condition of finding small solutions $(x,y,z)=(x_0, y_0, z_0)$ of the equation $Bx-Ay=z$. The framework is derived from Wiener's small private exponent attack on RSA and May-Ritzenhofen's investigation about the implicit factorization problem, both of which can be generalized to solve the above equation. We show that these two methods, together with Coppersmith's method, are equivalent for solving $Bx-Ay=z$ in the general case. Then based on Coppersmith's method, we present two improvements for solving $Bx-Ay=z$ in some special cases. The first improvement pays attention to the case where either $\gcd(x_0,z_0,A)$ or $\gcd(y_0,z_0,B)$ is large enough. As the applications of this improvement, we propose some new cryptanalysis of RSA, such as new results about the generalized implicit factorization problem, attacks with known bits of the prime factor, and so on. The motivation of these applications comes from oracle based complexity of factorization problems. The second improvement assumes that the value of $C \equiv z_0\ (\mathrm{mod}\ x_0)$ is known. We present two attacks on RSA as its applications. One focuses on the case with known bits of the private exponent together with the prime factor, and the other considers the case with a small difference of the two prime factors. Our new attacks on RSA improve the previous corresponding results respectively, and the correctness of the approach is verified by experiments.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
RSACryptanalysisLatticeCoppersmith's method
Contact author(s)
wsx09 @ foxmail com
History
2019-09-23: last of 2 revisions
2018-06-05: received
See all versions
Short URL
https://ia.cr/2018/568
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/568,
      author = {Shixiong Wang and Longjiang Qu and Chao Li and Shaojing Fu and Hao Chen},
      title = {Finding Small Solutions of the Equation $Bx-Ay=z$ and Its Applications to Cryptanalysis of the {RSA} Cryptosystem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/568},
      year = {2018},
      url = {https://eprint.iacr.org/2018/568}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.