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

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

作　者: 丁勇
导　师: 王育民
学　校: 西安电子科技大学
专　业: 密码学
关键词: 椭圆曲线密码体系标量乘法 NAF 自同态窗口技术辫群
分类号: TN918.1
类　型: 博士论文
年　份: 2005年
下　载: 451次
引　用: 5次
阅　读: 论文下载

内容摘要

自从公钥密码体制被提出以来,它就被广泛用于许多实用密码系统中,比如密钥协商、身份认证、数据完整性保护、数字签名、电子选举、电子商务、电子政务等等。特别以CA和证书为支撑的PKI更是成为构建大型安全网络所必须的基础设施。目前在实际中使用最为广泛的公钥算法是RSA。椭圆曲线密码制(ECC)是1985提出的新公钥体制,由于在保证相同安全强度下其所需的密钥长度较RSA的短,而特别适用于无线系统或者存储受限的设备。在许多安全标准中,如IPsec、WAPI、WPKI等等,都已经将其采用。在不远的将来ECC会成为应用标准中的首选算法。在ECC的快速实现中,最关键的就是标量乘kP的计算,其中k为一个大整数而P为椭圆曲线上的一个点。因此,标量乘的快速算法研究成为了许多密码学家关心的问题,并取得了相当多的不错的成果。在前人成果的基础上,本文主要做了以下的工作: 1.基于NAF分解,我们提出了一种新的方法,以任意的正整数w而不仅仅是2为基来表示整数k。因为它以w为基又近似NAF,我们称这种方法为w-NNAF方法。在所有以w为基的表示中,该方法的汉明重量最轻。使用k的w-NNAF表示,结合现存的一些方法,我们提出了一种计算kP的方法。 2.基于Solinas提出的RTNAF方法,我们提出了一种三比特结合的方法用以快速计算ECC中的标量乘。使用这种方法,可以以两个额外的存储为代价节省m/18个点加法。在有多余的存储的情况下,可将该方法推广到(w+1)比特结合,使得标量乘的计算复杂性可以进一步降低。最后定量分析了该方法所降低的计算复杂性。 3.提出了一种RTSNAF方法,它使用τ~2为基底而不象RTNAF方法那样使用τ来分解标量k。通过数学分析证明了该分解的存在性和唯一性。同时给出了该分解的长度和汉明密度的精确估计。最后,确定了使用该分解来计算kP的计算量为3m/14个点加法,相对RTNAF的m/3次有所改善。 4.为了加速ECC中标量乘法kP的计算,通过使用特征多项式为φ~2+2=0的自同态φ,Ciet将标量k分解为φ-NAF表示。通过对φ-NAF表示使用窗口技术,我们得到了七的φ-NAF_w分解。它能比Ciet的方法更高效的计算kP。最后,我们精确的估计了该分解的长度和汉明密度。 5.基于整数NAF(非相邻形式)表示,Solinas提出了一对整数(a,b)的JSF(联合稀疏形式)表示。由于JSF可以产生更多的双零位置,因此在计算ECC中的

全文目录

摘要  5-7
ABSTRACT  7-12
第1章绪论  12-18
  1.1 信息安全的现实需求  12-13
  1.2 公钥密码体系的发展  13-14
  1.3 椭圆曲线密码的优势  14-16
  1.4 本文的主要成果  16-18
第2章椭圆曲线密码简介  18-25
  2.1 无穷远点  18
  2.2 有限域简介  18-19
  2.3 椭圆曲线简介  19-23
    2.3.1 GF(p)上的椭圆曲线群  21
    2.3.2 GF(2~m)上的椭圆曲线  21-22
    2.3.3 ECC的困难问题  22
    2.3.4 ECDSA算法  22-23
  2.4 小结  23-25
第3章 ECC上的点计算  25-32
  3.1 点计算算法即计算量分析  25-30
  3.2 射影坐标  30
  3.3 小结  30-32
第4章 W-NNAF表示  32-44
  4.1 引言  32
  4.2 NAF以及NAF_w  32-36
  4.3 W-NNAF表示  36-37
  4.4 W-NNAF分析  37-42
  4.5 小结  42-44
第5章 KOBLITZ曲线上的多比特组合方法  44-54
  5.1 引言  44
  5.2 SOLINAS方法  44-48
  5.3 多比特组合方法  48-52
  5.4 总结  52-54
第6章 RTSNAF方法  54-62
  6.1 引言  54
  6.2 RTSNAF方法  54-59
  6.3 总结  59-62
第7章 φ-NAF_w分解  62-70
  7.1 引言  62
  7.2 自同态φ  62-63
  7.3 φ-NAF分解  63-64
  7.4 φ-NAF_w窗口技术  64-68
  7.5 总结  68-70
第8章窗口3NAF的联合稀疏形式  70-78
  8.1 引言  70
  8.2 JSF表示  70-72
  8.3 WT-JSF  72-76
  8.4 结论  76-78
第9章通用的φ-NAF分解方法  78-84
  9.1 引言  78
  9.2 通用φ-NAF分解  78-82
  9.3 结论  82-84
第10章 JSF与FROBENIUS映射的结合  84-92
  10.1 引言  84
  10.2 LEE等的方法  84-87
    10.2.1 FROBENIUS表示  84-85
    10.2.2 方法1  85-86
    10.2.3 方法2  86-87
  10.3 与JSF的结合  87-90
  10.4 结论  90-92
第11章基于辫群的签名方案ECSS  92-96
  11.1 引言  92
  11.2 共轭问题  92-93
  11.3 原有签名方案  93-94
  11.4 改进的ECSS方案  94-95
  11.5 结论  95-96
结束语  96-100
致谢  100-101
参考文献  101-106
研究成果  106-107

相似论文

某水电厂计算机监控系统的设计与实现,TV736
拟AP（AGP）-内射模的自同态环的若干研究,O153.3
椭圆曲线密码点乘算法的并行调度研究,TN918.1
超椭圆曲线群快速算法研究,TN918.1
NAF对映异构体合成工艺优化以及手性苯基哌嗪类化合物的合成、生物活性初步评价,R96
基于DICOM标准的医学图像融合方法研究,TP391.41
非自治动力系统拓扑熵的估计,O19
李Poisson代数分解唯一性与泛中心扩张,O152.5
两类有限群的自同构群,O152.1
关于图的自同态的研究,O157.5
自同态环上的相对凝聚模,O153.3
基于CPM和TOC的单件小批生产计划与调度方法研究,F273
氟化钠对体外培养的人黑素瘤细胞株A375增殖活性影响的研究,R739.5
媒体路径优化中继节点选择算法研究与系统设计,TN925
基于图像分割的立体匹配算法研究,TP391.41
椭圆曲线密码体制及其应用研究,TN918.1
椭圆曲线密码快速算法的标量分解研究,TN918.1
基于辫群的比特承诺协议,TP393.04
超椭圆曲线的密码学应用,TN918.1
椭圆曲线快速标量乘算法研究,TN918.1
关于M-主内射模、拟主内射模、伪主内射模,O153.3