Solving Simultaneous Modular Equations of Low Degree

We consider the problem of solving systems of equations Pᵢ (x) ≡ 0( nᵢ )i = 1 ⋯ k where Pᵢ are polynomials of degree d and the nᵢ are distinct relatively prime numbers and x < min (nᵢ ). We prove that if k > d(d + 1) / 2 we can recover x in polynomial time provided min (nᵢ ) > 2d². As a consequence the RSA cryptosystem used with a small exponent is not a good choice to use as a public-key cryptosystem in a large network. We also show that a protocol by Broder and Dolev [Proceedings on the 25th Annual IEEE Symposium on the Foundations of Computer Science, 1984] is insecure if RSA with a small exponent is used.