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

论文摘要

椭圆曲线密码算法（Elliptic Curve Cryptography, ECC）作为公钥密码学中的一个研究重点,在性能、安全方面都被证明有很大的优势。ECC的有效实现依赖于椭圆曲线群上的点乘和点加运算的效率,而这两种运算则直接取决于定义曲线的有限域算术运算的快速实现。有限域包括三种:素域GF（p）,二元扩域GF（2m）,一般扩域GF（pm）（p>2）。目前对有限域算术运算的实现方法主要是根据定义设计的,存在着算法效率不高,资源消耗较多等问题。本文针对上述问题,对ECC所使用的有限域GF（2m）和GF（pm）的算术运算实现进行了深入的研究,并且提出了有效的解决方案。本文的研究内容主要包括以下四个方面:首先,对GF（pm）的乘法快速实现进行了研究。重点研究了基于中国剩余定理（Chinese Remainder Theorem, CRT）对模乘的优化实现。利用二项式剩余算术（Binomial Residue, BR）较为简单的特点,提出了GF（pm）元素一种新的表示方法,即BR表示,给出了对应的BR-Montgomery乘法;针对最优扩域（Optimal Extension Fields, 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）的求逆达到了理论下界。

论文目录

摘要

ABSTRACT

符号说明

缩略语列表

第一章绪论

1.1 研究动机和意义

1.2 研究现状及发展趋势

1.2.1 二元扩域上的算术运算

m）（p > 2）扩域上的算术运算'>1.2.2 域GF（p^m）（p >2）扩域上的算术运算

1.3 论文的主要结果

1.4 论文的内容安排

第二章背景知识

2.1 群和域

2.2 有限域

2.2.1 多项式理论

2.2.2 有限域的性质

2.2.3 有限域的类型

2.3 椭圆曲线

第三章 p 元扩域的快速乘法

3.1 模二项式剩余类表示形式

3.2 基于BR 的快速Montgomery 乘法

3.2.1 Montgomery 算法介绍

3.2.2 Lagrange-Montgomery 乘法概述

3.2.3 BR-Montgomery 乘法

3.3 基于BR 的快速模乘

3.3.1 最优扩域（OEF）介绍

3.3.2 一类特殊的不可约多项式APB

3.3.3 基于BR 表示的模APB 乘法

3.3.4 模APB 乘法的改进

3.3.5 特殊情况

3.4 基于快速傅利叶变换（FFT）的改进算法

3.4.1 离散傅利叶变换（DFT）和快速傅利叶变换（FFT）

3.4.2 扩展FFT 算法

3.4.3 基于 FFT 的 BR 变换

3.4.4 应用实例：NTRU 密码体制的优化实现

3.5 本章小结

第四章 p 元扩域的求逆运算

4.1 广义欧几里德求逆算法

4.2 基于BR 的EEA 求逆算法

4.3 Frobenius 求逆

4.3.1 OEF 的求逆运算

4.3.2 BR 表示下OEF 的求逆

4.4 本章小结

第五章并行乘法器设计

5.1 相关知识

5.2 并行乘法器设计的主要方法

5.2.1 Mastrivito 乘法

5.2.2 经典方法

5.2.3 Karatsuba 算法

5.3 Karatsuba 算法改进

5.4 基于SPB 的并行乘法器

5.4.1 移位多项式基（SPB）

5.4.2 Karatsuba 方法与SPB 结合

5.4.3 Karatsuba 型方法介绍

5.4.4 基于3 项 Karatsuba 公式的并行乘法器

5.4.5 基于4 项 Karatsuba 公式的快速乘法器

5.4.6 进一步讨论

5.5 本章小结

第六章二元扩域的求逆算法

6.1 Itoh-Tsujii 算法的介绍

6.2 基于四次方运算的Itoh-Tsujii 算法

6.2.1 平方运算

6.2.2 快速四次方运算

6.2.3 例子

6.2.4 基于四次方求逆

6.2.5 讨论和比较

6.3 TYT 算法

6.3.1 TYT 算法叙述

6.3.2 基于PB 表示的TYT 算法

6.4 TYT 算法的改进

6.4.1 利用中间变量复用的方法

6.4.2 例子

6.4.3 最优分解的搜索算法

6.4.4 分析和比较

6.5 本章小结

第七章总结与展望

7.1 研究工作总结

7.2 展望

参考文献

致谢

攻读博士学位期间完成的学术论文和科研工作

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

论文摘要

论文目录

相关论文文献

猜你喜欢