Predicting the elliptic curve congruential generator

DOI10.1007/S00200-016-0303-XMaRDI QIDQ2363380zbMATH OpenOpenAlexFDO

Authors László Mérai

Publication date 19 July 2017

Published in Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.03305

zbMATH Keywords

cryptographyelliptic curvepseudorandom sequencecongruential generator

Mathematics Subject Classification ID

Cryptography (94A60) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Pseudo-random numbers; Monte Carlo methods (11K45) Computer solution of Diophantine equations (11Y50) Elliptic curves (14H52) Calculation of integer sequences (11Y55)

Abstract: Let $p$ be a prime and let $mathbfE$ be an elliptic curve defined over the finite field $mathbb{F}_p$ of $p$ elements. For a point $GinmathbfE(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}oplusG)=x(nGoplus{W}_0)$, $n=1,2,dots$, where $oplus$ denotes the group operation in $mathbfE$ 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.

Recommendations

• Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits
• Inferring Sequences Produced by a Linear Congruential Generator on Elliptic Curves Using Coppersmith’s Methods
• Attacking the linear congruential generator on elliptic curves via lattice techniques
• Inferring sequences produced by elliptic curve generators using Coppersmith's methods
• scientific article; zbMATH DE number 1972846

Cites work

• scientific article; zbMATH DE number 1972846 (Why is no real title available?)
• scientific article; zbMATH DE number 1866860 (Why is no real title available?)
• scientific article; zbMATH DE number 1440879 (Why is no real title available?)
• A family of elliptic curve pseudorandom binary sequences
• Construction of Pseudo-random Binary Sequences from Elliptic Curves by Using Discrete Logarithm
• Construction of pseudorandom binary sequences over elliptic curves using multiplicative characters
• Elliptic curve analogue of Legendre sequences
• Elliptic curves. Number theory and cryptography
• Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits
• Large families of elliptic curve pseudorandom binary sequences
• On a Class of Pseudorandom Sequences From Elliptic Curves Over Finite Fields
• On lattice profile of the elliptic curve linear congruential generators
• On the linear complexity and multidimensional distribution of congruential generators over elliptic curves
• Pseudorandom Points on Elliptic Curves over Finite Fields
• Pseudorandom sequences
• Remarks on pseudorandom binary sequences over elliptic curves

Cited in

(5)

• Pseudorandom vector generation using elliptic curves and applications to Wiener processes
• Inferring Sequences Produced by a Linear Congruential Generator on Elliptic Curves Using Coppersmith’s Methods
• Inferring sequences produced by elliptic curve generators using Coppersmith's methods
• Attacking the linear congruential generator on elliptic curves via lattice techniques
• An improved method for predicting truncated multiple recursive generators with unknown parameters

This page was built for publication: Predicting the elliptic curve congruential generator

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2363380)