Cryptanalysis of some algebraic variants of the RSA cryptosystem (Q6887496)

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.