椭圆曲线标量乘快速算法的研究与设计

论文摘要

椭圆曲线密码（ECC, Elliptic Curve Cryptography）是一种杰出的公钥密码体制。它具有众所周知的优势,在智能卡、无线网络和嵌入式系统等资源受限的设备中有广泛的应用。在ECC的快速实现中,关键的运算是标量乘法kP的计算,其中K为一个大整数而P为椭圆曲线上的一个点。因此标量乘法的快速算法研究成为了许多密码学家关心的问题。本文主要从算法的效率及其安全性两方面对标量乘算法进行研究。在效率方面,主要研究思路有两条：一是在底层域变换点的表示形式,得到高效的点加倍点公式；另一个是对标量进行重编码,得到更低的海明重量。而在安全性方面也有两条研究思路,分别为：一是采用随机化方式,具体有密钥随机化,点随机化等手段,使得攻击者难以捕捉到能耗轨迹的规律；另一种思路是均衡化方式,调整标量乘算法,让点加、倍点按特定的步骤序列进行,让能耗轨迹以相对平衡的方式展现。基于以上研究思路,本文主要工作有：（1）对抵抗边信道攻击的标量乘算法进行了研究,根据Jacobi Quartics曲线的点加倍点公式,提出了一种新的原子结构A-M-N-S-N-A-A,接着给出了优化的边信道原子结构的标量乘算法。新的标量乘算法在效率上比以往的边信道原子结构标量乘算法有较大提高。对于采用NAF编码的192bits的标量乘算法而言,当S/M=0.8时,效率提高约6.7%-23%,当S/M=0.6时,提高约12.7%-33.2%。（2）研究Edwards曲线,为了提高标量乘法的效率,提出了只依赖于y坐标的点加倍点公式。为了使算法适用于并行环境,对标量K的二进制表示进行划分,提出了一种抗SPA的并行标量乘算法,此算法与固定窗口算法、带符号滑动窗口算法相比,除无需额外存储开销及预计算外,效率提高了17.3%、33.3%;而在安全性相当且都无需要额外的存储开销及预计算的情况下,较Montgomery方法效率提高了31.1%。（3）在标量重编码研究上,介绍多基数系统及其在标量乘法中的应用,提出了基于多基数系统的多标量乘算法——Sliding MBNS、I-MBNS,然后对算法进行了分析。在二进制域上Sliding MBNS算法在t=192bit时比Shamir算法效率提高11%,比交错NAF方法提高10%；I-MBNS算法计算量分别提升13%及5%。而在素数域上Sliding MBNS算法较之交错NAF方法效率并未得到很大改善,I-MBNS算法效率提高近5%。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 椭圆曲线密码研究背景与意义
• 1.2 标量乘算法研究现状
• 1.3 论文研究内容与组织结构
• 第2章 椭圆曲线标量乘算法
• 2.1 有限域相关概念
• 2.1.1 群与有限域
• 2.1.2 素域
• 2.1.3 二进制有限域
• 2.1.4 扩域
• 2.2 椭圆曲线数学基础
• 2.2.1 椭圆曲线定义
• 2.2.2 椭圆曲线群运算
• 2.2.3 点的表示及若干椭圆曲线介绍
• 2.3 标量乘算法简介
• 2.3.1 平方-乘算法
• 2.3.2 非相邻表示型
• 2.3.3 滑动窗口方法
• 2.4 小结
• 第3章 基于边信道原子的安全快速标量乘算法
• 3.1 边信道攻击技术
• 3.2 快速边信道原子标量乘算法
• 3.2.1 Jacobi Quartics曲线的倍点和点加公式
• 3.2.2 点加倍点原子结构算法
• 3.2.3 边信道原子标量乘算法
• 3.2.4 算法分析
• 3.3 小结
• 第4章 EDWARDS曲线上的并行标量乘算法
• 4.1 EDWARDS曲线的群运算法则的研究
• 4.1.1 y-coordinate-only点加倍点公式
• 4.1.2 y-coordinate-only算法
• 4.2 抵抗SPA的并行标量乘算法
• 4.2.1 标量k的二进制划分
• 4.2.2 并行标量乘算法
• 4.2.3 算法分析
• 4.3 小结
• 第5章 基于多基数系统的多标量乘算法
• 5.1 背景知识
• 5.1.1 五倍点公式
• 5.1.2 多基数系统简介
• 5.2 传统多标量乘算法
• 5.2.1 Shamir算法
• 5.2.2 交错NAF方法
• 5.2.3 Solinas算法
• 5.3 基于多基数系统的多标量乘快速算法
• 5.3.1 MBNS滑动窗口同时多点乘算法
• 5.3.2 交错MBNS滑动窗口同时多点乘算法
• 5.3.3 算法分析
• 5.4 小结
• 第6章 结论与展望
• 参考文献
• 致谢
• 攻读硕士学位期间发表的论文及参加项目
• 攻读硕士学位期间参加学术会议和讨论班