Elliptic Curves And Constructions Of Pseudo-Random Sequences

Pseudorandom sequences have wide applications in spread-spectrum communication systems, code division multiple-access systems, ranging systems, software testing, radar systems, stream ciphers and public cryptosystems. Especially the security of stream ciphers heavily depends on the randomness and the unpredictability of the key streams. It is a hot-spot to construct pseudo-random sequences for use. This dissertation investigates the construction of pseudo-random sequences (pseudo-random numbers) from elliptic curves and mainly analyzes their cryptographic properties by using exponential sums over rational points along elliptic curves. The main results are as follows:(1) The uniform distribution of the elliptic curve linear congruential generator is discussed and the lower bound of its nonlinear complexity is given.(2) Two large families of binary sequences are constructed from elliptic curves. The well distribution measure and the correlation measure of order k of the resulting sequences are studied. The results indicate that they are "good" binary sequences which give a positive answer to a conjecture proposed by Goubin et al.(3) A kind of binary sequences from an elliptic curve and its twisted curves over a prime field F_p. The length of the sequences is 4p. The '1' and '0' occur almost the same times. The linear complexity is at least one-fourth the period (length).(4) The exponential sums over rational points along elliptic curves over ring Z_pq are estimated and are used to estimate the well distribution measure and the correlation measure of order k of a family of binary sequences from elliptic curves over ring Z_pq.(5) The correlation of the elliptic curve power number generator is given. It is proved that the sequences produced by the elliptic curve quadratic generator are asymptotically uniformly distributed.(6) The uniform distribution of the elliptic curve subset sum generator is considered.(7) We apply the linear feedback shift register over elliptic curves to produce sequences with long periods. The distribution and the linear complexity of the resulting sequences are also considered.