[计算机]超椭圆曲线密码体制论文：超椭圆曲线群快速算法研究.doc

超椭圆曲线密码体制论文：超椭圆曲线群快速算法研究【中文摘要】随着互联网的日益普及,人们的生活生产方式、管理方式也在发生着变化,对于网络的依赖也日益加深,随之而来的网络安全问题越来越受到人们的广泛关注。计算机网络安全是目前研究的重点,因为它为网络电子商务、政府电子公务、军事等重要领域在互联网上的应用提供了保障。随着公钥密码技术PKI的发展,RSA、椭圆曲线密码体制(ECC)等成为了人们研究的热点。自从1989年N.Kobiltz提出了超椭圆曲线密码体制(HECC)理论以来,因为与ECC以及其他密码体制相比具有以下优点：一,在同等安全水平条件下,所用基域更小；二、可以模拟基于乘法群上的如RSA、ElGamal等几乎所有协议;三、在同样的定义域上,亏格大,曲线多,选取用于密码中的安全曲线就多。HECC成为近年来的一个新研究热点。目前超椭圆曲线密码体制主要还处于理论研究阶段,最主要的原因是,超椭圆曲线密码的实现速度要比椭圆曲线密码实现速度慢,因为超椭圆曲线的Jacobian商群上的基本运算比椭圆曲线复杂的多。本文主要的研究工作是如何减少超椭圆曲线的除子加和标量乘法的计算量,从而提高超椭圆曲线密码的实现速度,具体工作有以下两点：(1)对文献中已经给出的亏格为3的超椭圆曲线退化除子算法确定性公式进行改进,从多种方向对于公式进行优化。首先利用几种不同的求逆技巧,针对不同情况的公式进行优化,从而将求逆的过程化简,甚至变换成乘法等运算量较低的运算。再利用公式的性质与结构,将多个乘法运算合并为1个乘法运算,从而减少无谓的运算。最后,利用其他文献中提及的一些乘法化简公式,以及公式变形来减少乘法运算量。各个方法都具有其局限性,但针对适应的公式进行改进,能取得不错的效果。(2)进一步就退化除子算法进行了扩展与改进。给出了亏格为2的确定性公式,并对其计算量进行估计。估计结果表明,在达到最低的安全水平条件下,d取160比特的大整数,此时标准除子标量乘法的运算量为318I+12044M,比标准除子标量乘法大约快30%。然后结合二分法、并行算法等其他算法思想进一步改进退化除子算法,分别得到两个运算量更小的优化算法。其中二分法改进后效果明显,明显减少了求逆与乘法的计算次数。而并行算法主要是将运算合并在同一个运算轮中,运算量降低不明显,但是将乘法处理器与运算轮数降到最低,从而使总体的运算时间能进一步缩短。【英文摘要】With the increasing popularity of the Internet, peoples lives and production methods, management is changing; the network has acquired a deeper dependence, followed by the network security problem more and more peoples attention. Computer network security is the focus of the study, because it for the network e-commerce, electronic government official, military and other important areas ofapplication of the Internet has provided a guarantee.With the development of PKI public key cryptography,RSA,Elliptic curve cryptography (ECC) have become a hot research people. Since 1989, N.Koblitz proposed hyperelliptic curve cryptosystem (HECC) theory since, as with the ECC, and other than the password system has obvious advantages:First, at the same level of security conditions, the use of the base domain smaller; Second, can be simulated based on the multiplicative group on, such as RSA, ElGamal, etc. Almost all the agreements; Third, in the same domain, the genus of a large, curvedand more, select Curve for the security of the password the more. HECC become a newhotspot in recent years.Hyperelliptic curve cryptography key is still in the stage of theoretical research, the main reason is the realization rate of HECC is slower than ECC, because the Jacobian of hyperelliptic curve quotient than the basic operations on theelliptic curve more complicated. In this paper, the research is how to reduce the divisor of hyperelliptic curves and scalar multiplication plus the computation, thereby enhancing the realization of ultra-speed elliptic curve cryptography, the following two specific work:(1) the literature has given genus 3 hyperelliptic curves degenerate divisor deterministic algorithm to improve, the formula from a variety of directions for optimization.First, the inverse using several different techniques for different situations to optimize the formula, which will simplify the process of inversion, and even transform into a low multiplication operations such as computation. Reuse of the nature and structure of the formula, the number of multiplication into a multiplication operation, thus reducing unnecessary operations. Finally, some of the other documents mentioned in the simplified formula for multiplication, and multiplication formula to reduce the amount of deformation. Each method has its limitations, but to improve the formula for adaptation can achieve good results.(2) In addition to the further degradation of sub-algorithm for the extended and improved.the deterministic genus 2 formula and its computation is estimated. Estimation results show that the minimum level of security conditions, d take the big 160-bit integer, then the standard divisor scalar multiplication capacity of 318I+12044 M, than the standard divisor scalar multiplication about 30% faster.Then combined with the dichotomy, parallel algorithms and other algorithms to further improve the degradation of ideological divisor algorithm, respectively, are two smaller computational algorithm. Dichotomy which results improved significantly, a significant reduction in the calculation of the inverse and the multiplication number. The parallel algorithm is computing the major merger in the same round operation, the computation reduction is not obvious, but the processor and the multiplication operation to minimize the number of rounds, so that the overall computation time can be further reduced.【关键词】超椭圆曲线密码体制 Jacobian商群 除子标量乘法【英文关键词】Hyperelliptic curve crypto systems Jacobian quotient group Divisor scalar multiplication【目录】超椭圆曲线群快速算法研究摘要6-7Abstract7第1章 绪论11-161.1 计算机网络安全与公钥密码发展11-121.2 超椭圆曲线密码体制的研究背景意义和研究现状12-141.3 本论文的研究内容及章节安排14-16第2章 超椭圆曲线密码体制概述16-422.1 超椭圆曲线的定义16-212.2 超椭圆曲线Jacobian群的运算法则21-262.2.1 除子有关概念及性质21-242.2.2 Jacobian商群24-262.3 超椭圆曲线密码体制26-392.3.1 有限域的算法约定27-352.3.2 Jacobian商群的算法约定35-372.3.3 超椭圆曲线密码体制相关约定37-392.4 超椭圆曲线密码体制的应用39-402.5 小结40-42第3章 超椭圆曲线密码体制的关键技术42-533.1 超椭圆曲线除子算法的概述42-463.1.1 主要的数据结构42-433.1.2 参数的表示形式43-453.1.3 标量乘法的基本算法研究45-463.2 标量乘法的一些快速算法46-523.2.1 SWNAF算法47-503.2.2 二分算法50-523.2.3 退化除子算法523.3 小结52-53第4章 亏格为3的退化除子快速算法研究53-614.1 退化除子标量乘法53-544.2 退化除子的加法和倍点算法确定性公式54-584.3 公式优化中的技巧与改进58-604.3.1 求逆的技巧584.3.2 利用公式性质简化运算58-594.3.3 其他的技巧59-604.3.4 改进性能分析604.4 小结60-61第5章 退化除子算法的推广与改进61-675.1 亏格为2的退化除子算法研究61-635.2 退化除子算法与多种算法结合改进63-665.2.1 利用二分法的改进63-645.2.2 利用并行算法的改进64-665.3 小结66-67总结与展望67-68致谢68-69参考文献69-73攻读硕士学位期间发表的论文及科研成果73