Anzeige
Erschienen in:
03.09.2016 | Original Paper
Predicting the elliptic curve congruential generator
Erschienen in: Applicable Algebra in Engineering, Communication and Computing | Ausgabe 3/2017
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Let p be a prime and let \(\mathbf {E}\) be an elliptic curve defined over the finite field \(\mathbb {F}_p\) of p elements. For a point \(G\in \mathbf {E}(\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}\oplus G)=x(nG\oplus W_0)\), \(n=1,2,\ldots \), where \(\oplus \) denotes the group operation in \(\mathbf {E}\) 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.