scientific article; zbMATH DE number 4035724

From MaRDI portal
Publication:3775466





[For the entire collection see Zbl 0583.00049.] We consider the problem of solving systems of equations \(P_ i(x)\equiv 0 (mod n_ i)\), \(i=1...k\), where \(P_ i\) are polynomials of degree d and the \(n_ i\) are distinct relatively prime numbers and \(x<\min n_ i\). We prove that if \(k>d(d+1)/2\) we can recover x in polynomial time provided \(n_ i>>2^ k\). This shows that RSA with low exponent is not a good alternative to use as a public key cryptosystem in a large network. It also shows that a protocol by Broder and Dolev is insecure if RSA with low exponent is used.




Cited in
(29)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3775466)