Predicting the elliptic curve congruential generator
This addresses a security vulnerability in cryptographic systems using ECCG for pseudorandom number generation, potentially impacting cryptographers and security practitioners, but it is incremental as it builds on known attacks on similar generators.
The paper tackles the problem of predicting sequences generated by the elliptic curve congruential generator (ECCG) from partial data, showing that given some consecutive elements as integers, one can compute an ECCG in polynomial time that matches the revealed segment, and in practice, all secret parameters and the entire sequence can be recovered from eight consecutive elements even with private prime and curve.
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,\dots$, 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.