Welcome to the resource topic for 2021/1629
Title:
Increment of Insecure RSA Private Exponent Bound Through Perfect Square RSA Diophantine Parameters Cryptanalysis
Authors: Wan Nur Aqlili Ruzai, Abderrahmane Nitaj, Muhammad Rezal Kamel Ariffin, Zahari Mahad, 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.
ePrint: https://eprint.iacr.org/2021/1629
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .