【作者】 孙跃刚；

【导师】 李辉来；

【作者基本信息】 吉林大学 ， 基础数学， 2009， 博士

【摘要】 本文主要研究了椭圆曲线密码体制中几个最重要的算法问题.首先研究素域GF(p)上的三种类型的大整数模乘算法,对其中的Montgomery模乘算法的实现算法CIOS算法进行改进,提出了基于无符号滑动窗口CIOS算法,并给出算法分析,证明该算法的运算效率较高.针对椭圆曲线标量乘法的快速算法中自然数k的表示问题,提出基于半点-多基表示(PH-MBR)的标量乘法快速算法,与已有的算法进行比较,证明本方法的优越性.同时给出Koblitz曲线密码中倍点运算的一种改进算法.之后,基于椭圆曲线及其挠曲线,构造出有限域GF(q)上一类伪随机性很强的交错序列,对其0-1平衡性,周期性,线性复杂度进行分析,证明了该序列的较好实用性.研究和分析椭圆曲线有限群阶#E(F_q)的计算的两种重要算法:SEA算法和Satoh算法.另外,独立于本文的主要内容,我们把应用勒让德小波求非线性微积分方程和常微分方程数值解方面的一些研究放在文章的最后.更多还原

【Abstract】 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.更多还原