Predicting the elliptic curve congruential generator.

Let p be a prime and let $$\mathbf {E}$$ be an elliptic curve defined over the finite field $$\mathbb {F}_p$$ of p elements. For a point $$G\in \mathbf {E}(\mathbb {F}_p)$$ the elliptic curve congruential generator (with respect to the first coordinate) is a sequence $$(x_n)$$ defined by the relation $$x_n=x(W_n)=x(W_{n-1}\oplus G)=x(nG\oplus W_0)$$ , $$n=1,2,\ldots $$ , where $$\oplus $$ denotes the group operation in $$\mathbf {E}$$ and $$W_0$$ is an initial point. In this paper, we show that if some consecutive elements of the sequence $$(x_n)$$ are given as integers, then one can compute in polynomial time an elliptic curve congruential generator (where the curve possibly defined over the rationals or over a residue ring) such that the generated sequence is identical to $$(x_n)$$ in the revealed segment. It turns out that in practice, all the secret parameters, and thus the whole sequence $$(x_n)$$ , can be computed from eight consecutive elements, even if the prime and the elliptic curve are private. [ABSTRACT FROM AUTHOR]