Cryptanalysis of some algebraic variants of the RSA cryptosystem
The paper studies algebraic variants of RSA with the key equation \(ed\equiv1\pmod{\varphi_n(N)}\), where \(\varphi_n(N)=(p^n-1)(q^n-1)\). The authors derive polynomial representations and bounds for \(\varphi_n(N)\) and apply lattice reduction and Coppersmith's method to analyze related modular equations. As an application, lattice-based attacks are obtained that factor the RSA modulus under explicit bounds on the private exponent \(d\), both with and without partial information on the primes. The results generalize and improve earlier cryptanalytic bounds, and are illustrated by a numerical example.\N\NSeveral algebraic variants of the RSA cryptosystem use the key equation \(ed\equiv 1\pmod{\varphi_n(N)}\), where \(N=pq\) and \(\varphi_n(N)=(p^n-1)(q^n-1)\). The authors derive algebraic representations and bounds for \(\varphi_n(N)\) and apply lattice reduction and Coppersmith's method to obtain factorization attacks under explicit bounds on the private exponent \(d\), extending earlier results.\N\NThe paper develops new algebraic representations and bounds for the generalized Euler totient function \(\varphi_n(N)=(p^n-1)(q^n-1)\), expressing it as a polynomial in \(p+q\) or, when partial information is available, in a reduced auxiliary variable. Building on these results, the authors propose a lattice-based method combining Coppersmith's technique and LLL reduction to solve multivariate modular equations arising from the key relation \(ed-k\varphi_n(N)=1\). As a consequence, explicit polynomial-time factorization attacks are obtained for algebraic RSA variants with small private exponent \(d\), both in the general case and when the primes share least significant bits, extending and improving earlier cryptanalytic bounds.\N\NThe proofs use lattice-based cryptanalysis, combining Coppersmith's method for small modular roots with LLL reduction. The key equation \(ed-k\varphi_n(N)=1\) is rewritten using polynomial expressions for \(\varphi_n(N)\), leading to multivariate modular equations. Lattices are constructed so that short vectors correspond to algebraic relations vanishing at the secret parameters; the final extraction of the solutions relies on standard heuristic assumptions on the algebraic independence of the polynomials produced by LLL.
- A method for obtaining digital signatures and public-key cryptosystems
- A new generalization of the KMOV cryptosystem
- A security analysis of two classes of RSA-like cryptosystems
- A Strategy for Finding Roots of Multivariate Polynomials with New Applications in Attacking RSA Variants
- An improved analysis on three variants of the RSA cryptosystem
- Another Generalization of Wiener’s Attack on RSA
- Attack on RSA-type cryptosystems based on singular cubic curves over \(\mathbb{Z}/n\mathbb{Z}\)
- Cryptanalysis of a new variant of the RSA cryptosystem
- Cryptanalysis of RSA with Private Key d Less than N 0.292
- Cryptanalysis of short RSA secret exponents
- Cryptanalysis of the RSA variant based on cubic Pell equation
- scientific article; zbMATH DE number 3750287 (Why is no real title available?)
- scientific article; zbMATH DE number 176555 (Why is no real title available?)
- scientific article; zbMATH DE number 1182510 (Why is no real title available?)
- On optimal bounds of small inverse problems and approximate GCD problems with higher degree
- On the high dimensional RSA algorithm -- a public key cryptosystem based on lattice and algebraic number theory
- RSA cryptosystem for Dedekind rings
- RSA cryptosystem for rings with commuting ideals
- Small solutions to polynomial equations, and low exponent RSA vulnerabilities
This page was built for publication: Cryptanalysis of some algebraic variants of the RSA cryptosystem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6887496)
