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

论文摘要

椭圆曲线密码体制(?)(Elliptic Curve Cryptology, ECC)由于安全性高、存储空间小、带宽要求低等特点,特别适合应用在Smart卡和短距离无线通信领域中,从而得到了广泛研究。但是,在实现ECC的时候仍有一些关键性的问题有待解决,其中非常重要的一个方面就是ECC的快速实现问题。标量乘法是ECC实现过程中最基本、最耗时的运算, ECC的快速实现问题最终归结为标量乘法的计算。关于标量乘法的快速计算,主要有以下两条研究思路：一是对底层域算法进行研究,包括乘法、平方和求逆运算；二是找到标量的有效表示形式,从而减少点加次数。本文在前人工作的基础之上,主要对以下几点进行了详细的研究：(1)分析了底层域算法中的乘法、平方和求逆运算,并且在已有算法的基础上,提出了一种改进的无移位操作comb乘法算法。相比于原算法,新算法在保证无移位操作的情况下,需要更少的预存储空间。(2)由于在基于多基表示的标量乘算法中,需要多次用到5P的计算,所以本文设计出了一种有限域GF(q)上5P的快速算法。该算法利用转换求逆为乘法运算的思想,只用到了一次求逆运算,虽然乘法和平方运算有所增加,但是总的运算效率得到了提高。(3)通过对Dimitrov等人基于多基表示标量乘算法的分析,结合多基数系统和底层域的快速算法,提出了一种改进的基于多基表示的标量乘算法。由于对最优路径进行了分析,并且用到了2kP、3kP和5P的快速算法,使得新算法的效率要高于Dimitrov等人的算法。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景和意义
• 1.2 标量乘法的研究现状
• 1.3 本论文的研究内容及章节安排
• 第2章 椭圆曲线密码体制概述
• 2.1 椭圆曲线的定义
• 2.2 椭圆曲线群运算法则
• 2.2.1 有限域GF（p）上椭圆曲线的运算法则
• 2^m上椭圆曲线的运算法则'>2.2.2 有限域F₂^m上椭圆曲线的运算法则
• 2.3 椭圆曲线密码体制
• 2.3.1 椭圆曲线离散对数问题
• 2.3.2 安全椭圆曲线的选取
• 2.3.3 椭圆曲线在密码学中的应用
• 2.4 椭圆曲线密码体制的攻击方法
• 2.5 本章小结
• 第3章 椭圆曲线上的标量乘法
• 3.1 椭圆曲线标量乘法的研究思路
• 3.2 经典的标量乘算法
• 3.2.1 二进制标量乘法
• 3.2.2 非相邻表示型
• 3.2.3 窗口方法
• 3.2.4 Modified Jacobian下标量乘法
• 3.3 本章小结
• 第4章 底层域快速算法研究
• 4.1 乘法运算
• 4.1.1 基于窗口技术的comb算法
• 4.1.2 无移位操作的comb乘法算法
• 4.1.3 改进的无移位操作的comb乘法算法
• 4.2 平方运算
• 4.3 求逆运算
• 4.4 GF（q）上椭圆曲线5P的快速算法
• 4.4.1 直接计算5P的快速算法
• 4.4.2 效率分析
• 4.5 小结
• 第5章 基于多基表示的标量乘法研究
• 5.1 基于双基表示的标量乘法
• 5.1.1 双基数系统
• 5.1.2 基于双基表示的标量乘法
• 5.2 基于多基表示的标量乘法
• 5.2.1 多基数系统
• 5.2.2 基于多基表示的标量乘法
• 5.3 改进的基于多基表示的标量乘法
• 5.3.1 几个底层域快速算法
• 5.3.2 改进的SMBR标量乘法
• 5.3.3 改进算法的效率分析
• 5.4 本章小结
• 总结与展望
• 致谢
• 参考文献
• 攻读硕士学位期间发表的论文及科研成果