学位论文 > 优秀研究生学位论文题录展示

超椭圆曲线密码体制中标量乘法的快速算法研究

作　者: 郝艳华
导　师: 王育民
学　校: 西安电子科技大学
专　业: 密码学
关键词: 超椭圆曲线密码体制标量乘双基链退化除子并行算法
分类号: TN918.1
类　型: 博士论文
年　份: 2007年
下　载: 177次
引　用: 2次
阅　读: 论文下载

内容摘要

作为一类特殊的代数曲线,超椭圆曲线是椭圆曲线的一种推广。与其他公钥密码体制相比,超椭圆曲线密码体制具有更短的操作长度,特别适合在受限系统中使用。由于结构复杂,所以超椭圆曲线密码体制实现速度较慢,目前对它的研究仍处于理论阶段。如何提高超椭圆曲线除子标量乘的计算速度是提高该密码体制实现速度,并使它早日走向实用的一个亟待解决的问题,本文对超椭圆曲线除子标量乘的快速算法作了深入的研究,主要工作如下:1.讨论了使用双基链计算超椭圆曲线除子标量乘的方法,给出了亏格为2的超椭圆曲线上2D₁+D₂,3D₁,3D₁+D₂,4D₁,4D₁+D₂的除子计算公式、他们的变体公式以及他们与变体公式之间联系的临界点,分析了公式的运算量。将2D₁+D₂公式用于非邻接形（NAF）和标准倍点加（double-and-add）标量乘算法中,比使用Lange的公式在平均单比特运算量上分别减少6.8%和9.2%,比使用Fan的改进公式则分别减少2.7%和2%。2.通过分析所给出的除子运算公式的运算量,结合大素数域上常见的实现环境,提出了适合我们应用的高效的超椭圆曲线双基链标量乘算法,并对该算法进行了复杂度分析。经过测算,我们的双基链标量乘算法与标准倍点加和NAF标量乘算法相比,效率分别提高25%和15.8%。该除子标量乘算法能够抵抗某些边信道攻击而且不需要任何预计算。3.给出了亏格为2的超椭圆曲线除子5D₁公式、它的变体公式以及它与变体公式之间联系的临界点,并分析了它们的运算量。给出了椭圆曲线有理点的5倍点公式以及多基链标量乘算法。4.给出了快速有效的亏格为3的超椭圆曲线退化除子运算的运算公式。将它用于总是倍点加（double-and-add-always）标量乘算法中,一次和二次退化除子标量乘分别比标准除子标量乘快25.4%和13%。该算法能够抗击简单能量分析攻击（SPA）和时间攻击（TA）,主要用于使用固定基点进行标量乘的运行环境中,如ElGamal型加密算法、Diffie-Hellman协议的发送方以及数字签名算法HECDSA中。由于退化除子特殊的结构,一次和二次除子的表示长度分别仅为标准除子的三分之一和三分之二。5.给出了求超椭圆曲线除子加法和倍点并行算法的一个易于实现的一般性方法,使用这个方法得到的并行算法的特点是:①需要运行的轮数最少;②在满足①的情况下,所需的并行运算乘法处理器的个数最少;③在满足①和②的情况下,一次需要存储的变量的最大个数最少。利用这个方法给出了亏格为3的超椭圆曲线除子加法和倍点运算的并行算法,分析结果表明,加法运算使用9个乘法处理器至少需要进行15轮运算（其中包含一个求逆轮）,倍点运算使用7个乘法处理器也至少需要进行15轮运算（其中包含一个求逆轮）。6.给出了一个有效的同时求多个域元素逆的求逆算法。将其应用到Mishra的亏格为2的超椭圆曲线除子标量乘算法中,得到了一个高效的抗简单能量分析攻击的标量乘算法。该算法比总是倍点加标量乘算法快24%～26%,比Mishra的两种标量乘算法分别快33%～35%和6%～7%。我们给出的这个求逆算法可以在任何需要求多个元素逆的应用环境中使用。

全文目录

摘要  5-7
Abstract  7-11
第一章绪论  11-21
  1.1 椭圆曲线密码体制  11-13
  1.2 超椭圆曲线密码体制  13-15
  1.3 超椭圆曲线除子标量乘  15-17
  1.4 几点说明  17
  1.5 内容安排及主要工作  17-21
第二章数学背景知识  21-33
  2.1 群和域  21-23
  2.2 超椭圆曲线  23-25
  2.3 除子  25-26
  2.4 JACOBIAN群中的运算  26-29
  2.5 双基链表示  29-31
  2.6 本章小结  31-33
第三章利用双基链计算除子标量乘  33-69
  3.1 2D_1+D_2的计算公式  33-41
  3.2 3D_1的计算公式  41-47
  3.3 3D_1+D_2的计算公式  47-53
  3.4 4D_1的计算公式  53-58
  3.5 4D_1+D_2的计算公式  58-65
  3.6 双基链除子标量乘算法  65-68
  3.7 本章小结  68-69
第四章利用退化除子计算除子标量乘  69-77
  4.1 退化除子标量乘算法  69-71
  4.2 退化除子的加法和倍点公式  71-75
  4.3 退化除子标量乘的运算量分析  75-76
  4.4 本章小结  76-77
第五章利用并行算法计算除子标量乘  77-87
  5.1 公式并行的一般方法  77-79
  5.2 亏格为3的超椭圆曲线除子加法和倍点运算的并行公式  79-86
  5.3 本章小结  86-87
第六章利用同时求逆算法计算除子标量乘  87-93
  6.1 同时求多个逆运算的标量乘算法  87-88
  6.2 同时求多个元素逆的高效算法  88-90
  6.3 各标量乘算法的运算量比较  90-92
  6.4 本章小结  92-93
附录A 多基链除子标量乘算法  93-97
附录B 5D_1的计算公式  97-105
附录C 椭圆曲线五倍点公式  105-109
结束语  109-113
致谢  113-115
参考文献  115-121
研究成果  121-122

超椭圆曲线密码体制中标量乘法的快速算法研究

内容摘要

全文目录

相似论文