Finding small solutions of the equation \(Bx-Ay=z\) and its applications to cryptanalysis of the RSA cryptosystem
type: Item
instance of: scholarly article
title: Finding small solutions of the equation \(Bx-Ay=z\) and its applications to cryptanalysis of the RSA cryptosystem
zbMATH Open document ID: 1472.11315
author: Shixiong Wang
author: Longjiang Qu
author: Chao Li
author: Shaojing Fu
author: Hao Chen
published in: Advances in Mathematics of Communications
publication date: 2021-05-12T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 11Y05
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 7347785
zbMATH Keywords: RSA
zbMATH Keywords: cryptanalysis
zbMATH Keywords: lattice
zbMATH Keywords: Coppersmith's method
reviewed by: Dimitros Poulakis
MaRDI profile type: Publication
full work available at URL: amc.2020076
OpenAlex ID: W3015954852
cites work: A New Lattice Construction for Partial Key Exposure Attack for RSA
cites work: Advances in Cryptology - CRYPTO 2003
cites work: Cryptanalysis of RSA with Private Key d Less than N 0.292
cites work: Q4249286
cites work: Finding a Small Root of a Univariate Modular Equation
cites work: Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known
cites work: Small solutions to polynomial equations, and low exponent RSA vulnerabilities
cites work: Advances in Cryptology - EUROCRYPT 2004
cites work: Deterministic polynomial-time equivalence of computing the RSA secret key and factoring
cites work: Cryptanalysis of RSA with small prime difference
cites work: Partial Key Exposure Attacks on RSA up to Full Size Exponents
cites work: Implicit Factoring with Shared Most Significant and Middle Bits
cites work: Q3856819
cites work: Maximizing Small Root Bounds by Linearization and Applications to Small Secret Exponent RSA
cites work: Q4400575
cites work: Q4787198
cites work: Algorithmic Cryptanalysis
cites work: Factoring polynomials with rational coefficients
cites work: Towards Optimal Bounds for Implicit Factorization Problem
cites work: Improved bounds for the implicit factorization problem
cites work: Solving Linear Equations Modulo Unknown Divisors: Revisited
cites work: Advances in Cryptology – CRYPTO 2004
cites work: Implicit Factoring: On Polynomial Time Factoring Given Only an Implicit Hint
cites work: Geometry of numbers
cites work: Implicit factorization of unbalanced RSA moduli
cites work: A New Attack on RSA and CRT-RSA
cites work: Partial prime factor exposure attacks on RSA and its Takagi's variant
cites work: Implicit factorization of RSA moduli revisited (short paper)
cites work: Further Improvement of Factoring RSA Moduli with Implicit Hint
cites work: A method for obtaining digital signatures and public-key cryptosystems
cites work: Partial Key Exposure: Generalized Framework to Attack RSA
cites work: Partial Key Exposure Attack on RSA – Improvements for Limited Lattice Dimensions
cites work: Improved Partial Key Exposure Attacks on RSA by Guessing a Few Bits of One of the Prime Factors
cites work: Approximate Integer Common Divisor Problem Relates to Implicit Factorization
cites work: Partial Key Exposure Attacks on RSA: Achieving the Boneh-Durfee Bound
cites work: Cryptanalysis of short RSA secret exponents
DOI: 10.3934/AMC.2020076
description: scientific article; zbMATH DE number 7347785