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

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.Computer Standards & Interfaces
DOI
10.1016/j.csi.2021.103584
Keywords
RSA cryptosystemalgebraic cryptanalysisinteger factorization problemDiophantine approximationlattice basis reductionkleptography
Contact author(s)
abderrahmane nitaj @ unicaen fr
History
2021-12-17: received
Short URL
https://ia.cr/2021/1629
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1629,
      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{https://eprint.iacr.org/2021/1629}},
      url = {https://eprint.iacr.org/2021/1629}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.