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; Muhammad Asyraf Asbullah

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 $e x^{2} - ϕ (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, \dots, k$ and a fixed $x$ that fulfills the Diophantine equation $e_{i} x^{2} - y_{i}^{2} ϕ (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 cryptosystem algebraic cryptanalysis integer factorization problem Diophantine approximation lattice basis reduction kleptography
Contact author(s): abderrahmane nitaj @ unicaen fr
History: 2021-12-17: received
Short URL: https://ia.cr/2021/1629
License: 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},
      url = {https://eprint.iacr.org/2021/1629}
}