Paper 2021/1629 Original: eprint.iacr.org/2021/1629 ↗

Increment of Insecure RSA Private Exponent Bound Through Perfect Square RSA Diophantine Parameters Cryptanalysis

Abstract

The public parameters of the RSA cryptosystem are represented by the pair of integers $N$ and $e$. In this work, first we show that if $e$ satisfies the Diophantine equation of the form $ex^2-\phi(N)y^2=z$ for appropriate values of $x, y$ and $z$ under certain specified conditions, then one is able to factor $N$. That is, the unknown $\frac{y}{x}$ can be found amongst the convergents of $\frac{\sqrt{e}}{\sqrt{N}}$ via continued fractions algorithm. Consequently, Coppersmith's theorem is applied to solve for prime factors $p$ and $q$ in polynomial time. We also report a second weakness that enabled us to factor $k$ instances of RSA moduli simultaneously from the given $(N_i,e_i)$ for $i=1,2,\cdots,k$ and a fixed $x$ that fulfills the Diophantine equation $e_{i}x^{2}-y_{i}^{2}\phi(N_{i})=z_{i}$. This weakness was identified by solving the simultaneous Diophantine approximations using the lattice basis reduction technique. We note that this work extends the bound of insecure RSA decryption exponents.