Research On Several Problems Of Pseudorandom Sequences From Elliptic Curves

With widespread application and further research of elliptic curve cryptography, theefficiency of elliptic curve operations on various software and hardware platforms has beencontinually improved. In the systems or equipments adopting elliptic curve cryptography, we canuse the existing elliptic curve arithmetic unit to construct pseudorandom sequence generator,which can save hardware resources.At present, the research of pseudorandom sequences from elliptic curves concentrates onthe following two aspects: one is to find new ways to construct sequences with goodpseudorandom properties, the other is to build more powerful tools to analyze the property of theexisting sequences. The main research contents of this paper are composed of two sections:The first section studies properties of pseudorandom binary sequences from elliptic curvesincluding the well-distribution measure and the correlation measure of order k. Thewell-distribution measure and the correlation measure of order k introduced by Mauduit andSárk zy are two important pseudorandom measures for a finite binary sequence. We constructtwo kinds of pseudorandom binary sequences from elliptic curves: one kind uses rationalfunctions, the other kind uses multiplicative character and its argument. With the help ofexponential sums along elliptic curves, the well-distribution measure and the correlation measureof order k are computed. The results show that both of them are small.The second section studies the properties of linear congruential generator on prime fieldsand we make an attack on the EC-LCG based on the algorithm for solving the closest vectorproblem. For the EC-LCG on prime fields, when the elliptic curve parameters are unknown andthe additive factor G is offered, it is shown that the sequence can be recovered in polynomialtime if sufficiently many bits of three consecutive points’ x-coordinates and the second point’y-coordinate are given, or sufficiently many bits of two consecutive points’ x-coordinates andy-coordinates are given. And the immunity conditions of this attack on the generator are offered.The results are beneficial to the selection of sequences in practice.