• 主题
高级搜索  >
历史搜索 清空历史
首页> 中文学位 >椭圆曲线密码中的有限域算术运算研究
【6h】

椭圆曲线密码中的有限域算术运算研究

代理获取
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

椭圆曲线密码算法(Elliptie Curve Cryptography，ECC)作为公钥密码学中的一个研究重点，在性能、安全方面都被证明有很大的优势。ECC的有效实现依赖于椭圆曲线群上的点乘和点加运算的效率，而这两种运算则直接取决于定义曲线的有限域算术运算的快速实现。有限域包括三种：素域GF(p)，二元扩域GF-(2m)，一般扩域GF(pm)(p>2)。目前对有限域算术运算的实现方法主要是根据定义设计的，存在着算法效率不高，资源消耗较多等问题。本文针对上述问题，对ECC所使用的有限域GF(2m)和G(pm)的算术运算实现进行了深入的研究，并且提出了有效的解决方案。本文的研究内容主要包括以下四个方面：　　 首先，对GF(pm)的乘法快速实现进行了研究。重点研究了基于中国剩余定理(Chinese Remainder Theorem，CRT)对模乘的优化实现。利用二项式剩余算术(Binomial Residue，BR)较为简单的特点，提出了GF(pm)元素一种新的表示方法，即BR表示，给出了对应的BR-Montgomery乘法；针对最优扩域(Optimal ExtensionFields，OEF)所使用的不可约二项式存在数量较少的问题，利用BR表示构造了一类不可约多项式，并对其存在的数量和分布进行了预测，随后研究了模乘的快速实现；使用快速傅利叶变换(Fast Fourier Transform，FFT)进一步提升了BR-Montgomery乘法的实现速度，并使用相应的技巧优化了NTRU(Number Theory Research Unit)密码算法的实现。　　 其次，研究了BR表示下GF(pm)的求逆运算。提出了一种广义欧几里德算法的变形，进一步完善基于BR表示的算术运算系统；通过对不可约二项式进行变换，提出了一种新的快速模乘算法，并研究了在BR表示下基于Frobenius映射的求逆算法。　　 再次，研究了GF(2m)的并行乘法器设计。重点研究了基于Karatsuba-Offman算法的乘法器：提出了一种Karatsuba算法的变形，在增加少量电路门的前提下，减小了整个乘法器的时延；结合移位多项式基(Shifted Polynomial Basis，SPB)与Karatsuba算法，构造了两类针对特殊三项式的并行乘法器，与已有的乘法器相比，空间和时间复杂度的综合指标要优于已有的结果。　　 最后，提出了三种基于Fermat小定理的GF(2m)的求逆算法：基于四次方的Itoh-Tsujii(IT)算法以及Takagi-Yoshiki-Takagi(TYT)算法的两种改进算法。其中，前一种算法使用快速四次方运算代替平方运算，减少了求逆算法的时延；后两种算法则在不同环境下比原TYT算法使用更少的操作。　　 本文创新性的工作描述如下：　　 1.基于二项式剩余算术，提出了GF(pm)元素的BR表示；据此构造了BR-Montgomery乘法，其计算复杂度为亚平方数量级，最低可达到O(m1.5)；针对BR表示提出了一种广义欧几里德的算法变型，可在该表示下直接进行求逆。　　 2.利用BR表示构造了一类不可约多项式，提出了一种模乘的快速实现算法；这种多项式与OEF通常使用的不可约二项式相比，存在数量更多、分布更广，并且模乘效率在某些情况下更高，有效的扩展了OEF的应用范围。　　 3.在对Karatsuba算法进行扩展的基础上，提出了一种基于不可约三项式的Karatsuba算法变型，主要目的在于减少Karatsuba并行乘法器的时延。该乘法器可达到与Mastrovito并行乘法器相同的时延，且空间复杂度更低。此外，提出了两类关于特殊三项式的Karatsuba乘法器，这两种乘法器在达到目前现有并行乘法器最少时延的前提下，空间复杂度仅为同类乘法器的66％和62％，其空间和时间复杂度综合指标达到了最优。　　 4.提出了一种快速四次方运算，并据此改进了IT算法，减少了IT算法的时延。　　 5.推广和改进了TYT求逆算法：提出了一种多项式基下的TYT算法，证明了该算法实际效率至少相当于原TYT算法。此外，利用中间值复用的方法改进了TYT的分解技巧，并进一步减少了求逆运算所需乘法的数量；实验结果表明，改进算法的计算复杂度对部分GF(2m)的求逆达到了理论下界。

著录项

  • 作者

    李银;

  • 作者单位

    上海交通大学;

  • 授予单位 上海交通大学;
  • 学科 密码学与计算机安全
  • 授予学位 博士
  • 导师姓名 陈恭亮;
  • 年度 2011
  • 页码
  • 总页数
  • 原文格式 PDF
  • 正文语种 chi
  • 中图分类
  • 关键词

    椭圆曲线密码算法,素域,二元扩域,一般扩域;

相似文献

  • 中文文献
  • 外文文献
  • 专利
代理获取

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号