Finding small solutions of the equation \(Bx-Ay=z\) and its applications to cryptanalysis of the RSA cryptosystem (Q2025379)

In this paper it is shown that some important cryptanalytic issues of the RSA cryptosystem can be summarized under the framework of finding small solutions \((x, y, z) = (x_0, y_0, z_0)\) of the equation \(Bx - Ay = z\), where \(A\), \( B\), \(x_0\), \(y_0\), \(z_0\) are positive integers, \(Bx_0\), \(Ay_0\) have the same bit size, and \(\gcd(A, B) = 1\), \(\gcd(x_0, y_0) = 1\). It is proved that a generalization of Wiener's small private exponent attack on RSA, a generalization of May-Ritzenhofen's investigation about the implicit factorization problem, and Coppersmith's method are equivalent for solving the equation \(Bx - Ay = z\) in the general case. Furthermore, two improvements based on Coppersmith's method for solving the equation \(Bx - Ay = z\) in some special cases are obtained which yield interesting applications to cryptanalysis of RSA. Several experiments are implemented to examine the justification of this approach and verify the correctness of the results.