椭圆曲线上快速标量乘算法的研究

论文摘要

椭圆曲线密码制（ECC）是1985提出的新公钥体制,由于在保证相同安全强度下其所需的密钥长度比RSA短,而特别适用于无线系统或存储受限的设备。在许多安全标准中,如IPsec、WAPI、WPKI等,都已经将其采用,在不远的将来ECC会成为应用标准中的首选算法。在ECC的快速实现中,关键的运算是标量乘法kP的计算,其中k为一个大整数而P为椭圆曲线上的一个点。因此标量乘法的快速算法研究成为了许多密码学家关心的问题。本文主要做了以下几方面的工作:（1）在标量重编码方面,采用回溯法设计出一种重编码算法。该算法只须对标量序列进行一次变换、至多四个中间变量及只需基于比特位比较赋值操作,效率更高、利于硬件实现标量乘法,并证明了所得结果具有正则序列的性质。将算法应用到计算数字签名中常用的gP+hQ时,得到g、h的具有最小联合重量序列。（2）在双基数标量乘算法方面,本文做了两个工作:第一引用一个新的数域系统—双基数系统,减少标量乘法中的上层运算。在底层域上直接推导出直接计算3kP快速算法。最后结合直接计算2kP、2P±Q、3P±Q及3kP快速算法,给出基于双基数的快速标量乘新算法,该算法的效率优于Dimitrov算法及传统标量乘算法。第二在改进二元域椭圆曲线上基于双基数标量乘法时,新设计的以1/2和3为基的双基数编码可结合直接计算3kP和折半运算。基于该双基数编码的标量乘算法只涉及到点加运算、折半运算、三倍点和直接计算3kP,底层域运算复杂性得到降低,在NIST推荐的椭圆曲线上比Dimitrov算法效率提高70%以上,比Wong方法提高10%以上。（3）在定点标量乘算法的设计方面,本文主要做了三个工作:第一给出一种标量的串长加法链算法来提高椭圆曲线标量乘法的效率。该标量乘算法结合底层域直接计算2Q+P、2nR+S算法,使用大小窗口法将串长算法和滑动窗口算法结合,加法链长度、存储空间和预计算都减少,其效率比二元法提高53%,比NAF法提高47.5%,比串长算法提高46.2%,比Window法提高42.2%。第二对传统滑动窗口算法进行改进,首先利用预处理栈存储非零窗口值与非零窗口权的指数,然后结合底层域直接计算2kR+S算法和预计算表提出了新的标量乘算法。该算法以牺牲适量的存储空间换取赋值阶段效率的提高,并分析出在混合坐标下,当w=4时新算法比仿射坐标下传统滑动窗口算法效率提高约40.6%左右。第三利用NAF编码,预计算表法和Yen-Laih法分别在三个阶段对Lim-Lee算法进行优化。该定点标量乘算法在赋值阶段动态扫描矩阵宽度为w的非全零列窗口,结合2kP底层域快速算法和扩充过的预计算表来提高计算效率。当位长是160时,新算法效率比Lim-Lee算法提高22.7%,192时提高23%,224时提高23.3%。（4）研究Koblitz曲线上的快速标量乘法,从整数k的TNAF出发,给出了基于Frobenius映射的两种上层运算:Comb算法和窗口算法。算法对一定长度的序列预先计算其对应的椭圆曲线上点保存,累加赋值阶段充分使用该预计算表。算法是基于高效的Frobenius映射,无需倍点运算,且算法所需的点加量是传统算法的1/51/4,当行数任意时,本文算法的效率在任意坐标下比传统Comb算法提高至少67%左右。

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 椭圆曲线密码体制
• 1.2 椭圆曲线定义
• 1.3 椭圆曲线加法公式
• 1.4 标量乘法算法简介
• 1.4.1 平方-乘算法
• 1.4.2 m-ary 算法
• 1.4.3 NAF 方法
• 1.4.4 滑动窗口算法
• 1.4.5 Comb 算法
• 1.5 本文主要工作与结构安排
• 第二章 新的二进制序列重编码算法
• 2.1 常用重编码算法
• 2.2 从右到左重编码算法
• 2.3 从左到右重编码算法
• 2.4 算法性能分析
• 2.5 应用于多标量乘法
• 第三章 基于双基数的标量乘法的设计
• 3.1 基于直接计算的双基数标量乘算法
• 3.1.1 双基数系统
• 3.1.2 底层域快速算法
• kP 算法'>3.1.3 直接计算3^kP 算法
• 3.1.4 新的双基数标量乘算法
• 3.1.5 算法性能分析
• 3.2 基于折半运算的双基数标量乘算法
• 3.2.1 椭圆曲线
• 3.2.2 折半运算
• 3.2.3 双基数编码
• 3.2.4 折半双基数标量乘算法
• 3.2.5 算法性能分析
• 第四章 定点标量乘算法的设计
• 4.1 基于加法链的快速标量乘算法
• 4.1.1 串长加法链
• 4.1.2 基于串长加法链的标量乘算法
• 4.1.3 算法性能分析
• 4.2 改进的滑动窗口标量乘算法
• 4.2.1 算法介绍
• 4.2.2 算法性能分析和结论
• 4.3 一种定点快速标量乘算法的优化
• 4.3.1 Lim-Lee 算法
• 4.3.2 算法优化
• 4.3.3 算法性能分析
• 第五章 基于Frobenius 映射的快速标量乘算法
• 5.1 背景知识
• 5.1.1 Koblitz 曲线
• 5.1.2 Frobenius 映射
• 5.1.3 约简
• 5.2 Frobenius Comb 算法
• 5.2.1 算法过程
• 5.2.2 算法分析
• 5.3 Frobenius 窗口算法
• 5.3.1 算法过程
• 5.3.2 算法分析
• 第六章 结束语
• 参考文献
• 致谢
• 攻读硕士学位期间发表的论文及参加项目
• 攻读硕士学位期间参加学术会议和研讨班