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

*Wan Nur Aqlili Ruzai and Abderrahmane Nitaj and Muhammad Rezal Kamel Ariffin and Zahari Mahad and Muhammad Asyraf Asbullah*

**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.

**Category / Keywords: **public-key cryptography / RSA cryptosystem, algebraic cryptanalysis, integer factorization problem , Diophantine approximation, lattice basis reduction, kleptography

**Original Publication**** (with minor differences): **Computer Standards & Interfaces
**DOI: **10.1016/j.csi.2021.103584

**Date: **received 14 Dec 2021

**Contact author: **abderrahmane nitaj at unicaen fr

**Available format(s): **PDF | BibTeX Citation

**Version: **20211217:142055 (All versions of this report)

**Short URL: **ia.cr/2021/1629

[ Cryptology ePrint archive ]