Cryptanalysis of RSA with smooth prime sum
Meryem Cherkaoui Semmouni, Abderrahmane Nitaj, Mostafa Belkasmi · Journal of Discrete Mathematical Sciences and Cryptography · 2022
Let N = pq be an RSA modulus with balanced prime factors, that is q < p < 2q. There exist infinitely many integers x, y and z such that ex - ϕ (N ) y = ( p + q -1)z. We show that if the prime sum p + q -1 has only small prime factors and e satisfies an equation of the form ex - ϕ (N ) y = ( p + q -1)z with suitably small integers x, y and Z, then one can factor the RSA modulus in polynomial time. In addition we show that the number of such RSA moduli, as well as the number of exponents that are vulnerable to our attack is non-negligible.