[For the entire collection see Zbl 0651.00027.]
The security of several signature schemes and cryptosystems, essentially proposed by Okamoto, is based on the difficulty of solving polynomial equations or inequations modulo n. The encryption and the decryption of these schemes are very simple when the factorisation of the modulus, a large composite number, is known.
We show here that we can, for any odd n, solve, in polynomial probabilistic time, quadratic equations modulo n, even if the factorisation of n is hidden, provided we are given a sufficiently good approximation of the solutions. We thus deduce how to break Okamoto’s second degree cryptosystem and we extend, in this way, Brickell’s and Shamir’s previous attacks.
Our main tool is lattices that we use after a linearisation of the problem, and the success of our method depends on the geometrical regularity of a particular kind of lattices.
We mention that these methods can be generalized to higher dimensions [B. Vallée, M. Girault, Ph. Toffin, How to guess \(\ell\)-th roots modulo n by reducing lattice bases, Proc. of ISSAC-AECC, Rome 1988, to appear in Lect. Notes Comput. Sci.]. The same methods can also be refined, in this two-dimensional-case: they allow to obtain new results about the distribution of elements with smaller modular squares and to provide the best rigorously established probabilistic complexity bound for integer factorisation algorithms [B. Vallée, Provably fast integer factoring with quasi-uniform quadratic residues, Proc. 21st STOC’89].