Malaysian Journal of Mathematical Sciences, August 2019, Vol. 13(S)
Special Issue: The 6th International Cryptology and Information Security Conference (CRYPTOLOGY2018)
Successful Cryptanalytic Attacks Upon RSA Moduli \(N=pq\)
Abubakar, S. I., Ariffin, M. R. K., and Asbullah, M. A.
Corresponding Email: [email protected]
Received date: -
Accepted date: -
Abstract:
This paper reports four new cryptanalytic attacks which show that \(t\) instances of RSA moduli \(N_s=p_sq_s\) for \(s=1,..., t\) where \(t\geq 2\) can be simultaneously factored in polynomial time using simultaneous Diophantine approximations and lattice basis reduction techniques. We construct four system of equations of the form \(e_sd-k_s\phi(N_s)=1\), \(e_sd_s-k\phi(N_s)=1\), \(e_sd-k\phi(N_s)=z_s\) and \(e_sd_s-k\phi(N_s)=z_s\) using \(N-\left \lceil \left ( \frac{a^{\frac{i+1}{i}}+b^{\frac{i+1}{i}}}{2(ab)^{\frac{i+1}{2i}}}+\frac{a^{\frac{1}{j}}+b^{\frac{1}{j}}}{2(ab)^{\frac{1}{2j}}} \right )\sqrt{N} \right \rceil +1\) as a good approximations of \(\phi(N_s)\) for unknown positive integers \(d\), \(d_s\), \(k\), \(k_s\), and \(z_s\). In our attacks, we found an improved short decryption exponent bound of some reported attacks.
Keywords: RSA Moduli, Simultaneous, Diophantine, Approximations, Lattice, Basis, Reduction, LLL algorithm
