2016/09/12 by Mérai, László
#Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT)
paper · doi:10.48550/arxiv.1609.03305
Let p be a prime and let E be an elliptic curve defined over the finite field \mathbbFp of p elements. For a point G\inE(\mathbbFp) the elliptic curve congruential generator (with respect to the first coordinate) is a sequence (xn) defined by the relation xn=x(Wn)=x(Wn-1⊕ G)=x(nG⊕ W0), n=1,2,…, where ⊕ denotes the group operation in E and W0 is an initial point. In this paper, we show that if some consecutive elements of the sequence (xn) 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 (xn) in the revealed segment. It turns out that in practice, all the secret parameters, and thus the whole sequence (xn), can be computed from eight consecutive elements, even if the prime and the elliptic curve are private.