Finding small solutions of the equation \(Bx-Ay=z\) and its applications to cryptanalysis of the RSA cryptosystem (Q2025379)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Finding small solutions of the equation \(Bx-Ay=z\) and its applications to cryptanalysis of the RSA cryptosystem |
scientific article |
Statements
Finding small solutions of the equation \(Bx-Ay=z\) and its applications to cryptanalysis of the RSA cryptosystem (English)
0 references
12 May 2021
0 references
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.
0 references
RSA
0 references
cryptanalysis
0 references
lattice
0 references
Coppersmith's method
0 references
0 references
0 references
0 references