New Approach for Efficiently Computing Factors of the RSA Modulus
Muhammad Rezal Kamel Ariffin, Amir Hamzah Abd Ghafar, Wan Nur Aqlili Ruzai, Nurul Nur Hanisah Adenan · 2021
This chapter consists of a compilation of new attacks on the modulus of the RSA cryptosystem. The first attack works when the public exponent e satisfies the modified RSA key equation eX – uY = Z – ϕ b where X , Y , Z are integers and u = ϕ a + ϕ b for ϕ a and ϕ b are the upper and lower bounds of ϕ ( N ). We show that the modulus N can be factored if X , Y , Z satisfy our given condition. The second attack is an extension of first attack, as we alter the equation into e i X – u i Y i = Z i – ϕ b . We show that the modulus N i = p i q i can be factored simultaneously whenever our given condition is satisfied. The third attack is conducted upon the modulus N = pq with the public key e < ϕ ( N ) satisfies the key equation ed – kϕ ( N ) = 1. Applying the continued fraction and continuous midpoint subdivision analysis upon an interval containing ( p – 1) ( q – 1), we show that N can be factored in polynomial time. The last attack is applicable upon the modulus N = p 2 q where the primes share a known amount of Least Significant Bits (LSBs). Utilizing the given information to build a lemma, we substitute it into the equation ed – kϕ ( N ) = 1 where ϕ ( N ) = p ( p – 1) ( q – 1), then we build an integer polynomial. We manage to find the roots of the polynomial by using the Jochemsz-May strategy and thus factor the modulus N .