Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits |
| |
Authors: | Jaime Gutierrez Álvar Ibeas |
| |
Institution: | (1) Applied Mathematics and Computer Science Department, University of Cantabria, Santander, 39071, Spain |
| |
Abstract: | Let p be a prime and let be an elliptic curve defined over the finite field of p elements. For a given point the linear congruential genarator on elliptic curves (EC-LCG) is a sequence (U
n
) of pseudorandom numbers defined by the relation: where denote the group operation in and 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.
|
| |
Keywords: | Pseudorandom congruential generators Cryptography Lattice reduction Elliptic curves |
本文献已被 SpringerLink 等数据库收录! |