Researches On Some Problems In Elliptic Curve Cryptography

Researches on some problems in elliptic curve cryptographyElliptic curves were first applied to cryptosystem by Koblitz and Miller independently in 1985, which have been greatly used to encryption and decryption, Key changing, digital signatures and integer factorization etc in recent years. Elliptic Curve Cryptography(ECC) systems are based on discrete logarithm problem which is produced by Abel Group that consists of points on some elliptic curve. Most researches of mathematicians and cryptanalysts think that discrete logarithm problems of elliptic curve are more difficult than those of finite field. Experiments show that ECC algorithm has a faster speed, allows shorter key lengths, requires fewer computational resources for implementation than other traditional public-key algorithms such as RSA in the same safety property. While the computational speed of ECC is much lower than that of symmetry cryptography, and this affects its application in a certain extent. So how to improve the computational efficiency of ECC becomes a hot problem in elliptic curve cryptology.Modular multiplication of long integers or polynomials is a fundamental operation for ECC in finite field GF(q). While q is prime number p, we need integer modular multiplication x×y mod p; While q = p^m, we need polynomial modular multiplication f(x)×h(x) mod f(x). The computation of modular n or modular f(x) wasting more time than multiplication is the key to improve efficiency of modular multiplication.Scalar multiplication computation is the Most important in ECC of all kinds of computation, and the computational efficiency influence the whole implementation efficiency of ECC. So the research of fast computation of scalar multiplication is a hot-spot of ECC all the time.Constructing pseudo-random sequences is an important problem in cryptogramresearch. In public-key cryptosystem, random numbers are a little short random sequences, and used to digital signatures, message authentication, encryption algorithm, identity authentication and large numbers of cryptology protocol. The character of pseudo-random number generator plays an important role in security of those systems. Point counting problem is a pure mathematical problem. It is a fundamental question not only in selecting random curve to construct ECC, but also in the area of cryptography such as primality proof and elliptic curve decomposition. Consequently, it is of great value in modern cryptography to solve this problem.In this dissertation we get some most significant problems in ECC to study and analyze. The main contributions are as follows: ·Study several recently widely used modular multiplication algorithms in prime field GF(p) based on addition, estimating quotient and Montgomery algorithm. Then present a new algorithm based on CIOS which is one of implementation algorithms of Montgomery, analyzing the improved algorithm. Here we mostly make use of the USW_2,h algorithm to coding one of the multipliers in the multiplication. Then we can compute the MonPro(α, b, r, n). The analysis show that the multiplication times in new algorithm reduce from 2s² + s to 3hs, and the temporary memory units only increased 3.·Study the scalar multiplication on elliptic curve. We first summarize the expression method of the scalar k such as binary system method, windows method, DBNS and SDBNS etc, then we get a new fast method for scalar multiplication based on PH-MBR. last we produce an improved method on computing of multiplying points on Koblitz curve cryptography. A half point multi-based present of integer k is called when it is presented asFrom the analysis we can conclude that the inverse computing times are reduced by 23% when compared to algorithm in paper[57], 12% to that in paper[59]. The square times are reduced by 31% than that in paper[57], 10% in[59]. The multiplication times are reduced by 15% than the other three kinds of algorithm.·A kind of binary sequences from an elliptic curve and its twisted curves over a field F_q. Studying of the period, hamming weight and the linear complexity of the sequence shows that the sequence are a kind of good pseudo random sequences.Theorem 0.1 the lengths of interleaved sequence S and R are both 4kq, and(1) hamming weight of S is W_H(S) = kp^k-1(2p - 1);(2) hamming weight of R is W_H(R) = kp^k-1(2p - 1) - k; here q = p^k, p is a prime number and p > 3.Theorem 0.2 When the interleaved sequence S or R is looked as periodic sequence S^∞or R^∞with the period S or R, then(1) the period of S^∞is per{S^∞) = 4kq;(2) the period of R^∞is per(R^∞) = 4kq.Theorem 0.3 if 2 is original unit of F_q, then(1) the linear complexity of S^∞is L(S^∞)∈{4k + s(q - 1), s = 1,2,…, 4k};(2) the linear complexity of R^∞is L(R^∞)≥3(p - 1).From these theorems we can get the conclusion that the interleaved sequence we construct has a better kind of pseudo random character.·Introduce the new trends of algorithms in computing the order of elliptic curves at present, SEA and Satoh algorithm. An improvement project is brought forward.·Making use of Legendre wavelet expression, we get a new numerical method to solve a kind of nonlinear differential integral equation and a kind of ODE. Examples show that this method is effective.