Paper 2007/099
Inferring sequences produced by a linear congruential generator on elliptic curves missing highorder 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 (ECLCG) is a sequence $(U_n)$ of pseudorandom numbers defined by the relation $$ U_n=U_{n1}\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 ECLCG 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 ECLCG should be used with great care. Our results are somewhat similar to those known for the linear and nonlinear pseudorandom number congruential generator.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. pseudorandom numbers, elliptic curves
 Contact author(s)
 jaime gutierrez @ unican es
 History
 20070322: received
 Short URL
 https://ia.cr/2007/099
 License

CC BY
BibTeX
@misc{cryptoeprint:2007/099, author = {Jaime Gutierrez and Alvar Ibeas}, title = {Inferring sequences produced by a linear congruential generator on elliptic curves missing highorder bits}, howpublished = {Cryptology ePrint Archive, Paper 2007/099}, year = {2007}, note = {\url{https://eprint.iacr.org/2007/099}}, url = {https://eprint.iacr.org/2007/099} }