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

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 y x can be found amongst the convergents of e 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 , ⋯ , 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.