|
Abstract : |
Abstract: We consider the problem of solving systems of equations Pi(x) j 0 (mod ni) i = 1: : : k where Pi are polynomials of degree d and the ni are distinct relatively prime numbers and x! min(ni). We prove that if k? d(d+1)2 we can recover x in polynomial time provided min(ni) ? 2d 2. 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 [4] is insecure if RSA with a small exponent is used., |
