Paper 2021/1629

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

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


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.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.Computer Standards & Interfaces
RSA cryptosystemalgebraic cryptanalysisinteger factorization problemDiophantine approximationlattice basis reductionkleptography
Contact author(s)
abderrahmane nitaj @ unicaen fr
2021-12-17: received
Short URL
Creative Commons Attribution


      author = {Wan Nur Aqlili Ruzai and Abderrahmane Nitaj and Muhammad Rezal Kamel Ariffin and Zahari Mahad and Muhammad Asyraf Asbullah},
      title = {Increment of Insecure RSA Private Exponent Bound Through Perfect Square RSA Diophantine Parameters Cryptanalysis},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1629},
      year = {2021},
      doi = {10.1016/j.csi.2021.103584},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.