**Inferring sequences produced by a linear congruential generator on elliptic curves missing high--order bits**

*Jaime Gutierrez and Alvar Ibeas*

**Abstract: **Let $p$ be a prime and let $E(\F_p)$ be an elliptic curve defined over
the finite field $\F_p$ of $p$ elements. For a given point $G \in
E(\F_p)$ the linear congruential genarator on elliptic curves (EC-LCG)
is a sequence $(U_n)$ of pseudorandom numbers defined by the relation
$$ U_n=U_{n-1}\oplus G=nG\oplus U_0,\quad n=1,2,\ldots,$$ where
$\oplus$ denote the group operation in $E(\F_p)$ and $U_0 \in E(\F_p)$
is the initial value or seed. We show that if $G$ and sufficiently
many of the most significants bits of two consecutive values $U_n,
U_{n+1}$ of the EC-LCG are given, one can recover the seed $U_0$ (even
in the case where the elliptic curve is private) provided that the
former value $U_n$ does not lie in a certain small subset of
exceptional values. We also estimate limits of a heuristic approach
for the case where $G$ is also unknown. This suggests that for
cryptographic applications EC-LCG should be used with great care. Our
results are somewhat similar to those known for the linear and
non-linear pseudorandom number congruential generator.

**Category / Keywords: **foundations /

**Publication Info: **pseudorandom numbers, elliptic curves

**Date: **received 19 Mar 2007

**Contact author: **jaime gutierrez at unican es

**Available format(s): **PDF | BibTeX Citation

**Version: **20070322:142004 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]