OEF上的快速算法研究及其在ECC上的应用实现

论文摘要

椭圆曲线加密体制（ECC）是一种基于椭圆曲线上的离散对数问题而设计的非对称公钥密码体制。本文主要分析研究了最优扩域（OEF）上的快速算法及其在ECC 上的应用实现。椭圆曲线的计算算法可分为高层计算和低层计算两类算法。其中高层计算算法主要处理椭圆曲线上点的操作,而低层算法侧重于处理有限域中的多项式计算算法,本文通过将这两者有机结合来提高椭圆曲线密码系统中的计算速度。本文对理想扩域的结构特点和椭圆曲线上的标量乘（kP）快速算法进行了分析研究,并对这些快速算法加以测试改进。在最优扩域上的快速算法的研究过程中,通过分析子域求模的快速算法、域元素求逆（MAIA 算法、EEA 算法）和多项式相乘（硬乘算法、Karatsuba 算法）等经典算法后,结合我们选择的有限域(Ⅱ型最优扩域GF ((232-46305)5))的特点,本文提出了一种基于Karatsuba 法的改进型域元素多项式乘算法,并通过理论分析证明该改进算法的计算复杂度低于Karatsuba 算法。经测试（CPU/PⅣ1.4GHz,MS Visual C++6.0）,验证改进算法的性能与Karatsuba 算法相当,比硬乘算法提高了大约4%。在椭圆曲线上的标量乘快速算法的研究过程中,通过分析计算标量乘（二进制算法、Montgomery 算法、NAF 算法、2P + Q算法和FBW 算法等）的算法,本文提出了一种改进型3P 算法和一种基于固定基的MFBW 算法。改进型3P 算法通过优化正整数k 的表示形式来降低标量乘的计算复杂度,MFBW 算法利用一些预计算来提高标量乘的计算速度,并且将这两种改进算法结合来计算标量乘。经测试,改进算法的性能比常规的二进制算法和Montgomery 算法提高了大约15% ,比NAF 算法提高了大约7%。本文利用VC++内联式汇编和C 语言对算法进行软件实现,并给出了测试结果。与Daniel V.Bailey 仿真的结果相比,我们的测试数据与他的测试数据处于同一数量级或优于他的测试数据。

论文目录

• 第一章 引言
• 1.1 研究背景和意义
• 1.2 本文章节安排
• 第二章 ECC 的数学基础
• 2.1 群、域、环
• 2.1.1 群、域、环的概念
• 2.1.2 有限域
• 2.1.3 素数域GF（ p ） 及其数学结构
• 2.1.4 特征为p 的有限域GF （ pm ）
• 2.2 椭圆曲线
• 2.2.1 椭圆曲线相关概念
• 2.2.2 定义在代数封闭域上的椭圆曲线
• 2.2.3 椭圆曲线群
• 2.2.4 椭圆曲线方程的判别式
• 2.2.5 实数域上的椭圆曲线群
• 2.2.6 有限域GF （p） 上的椭圆曲线群
• 2.2.7 有限域GF （pm） 上的椭圆曲线群
• 2.3 ECC 的原理
• 2.3.1 椭圆曲线群上离散对数问题与公钥加密体制
• 2.3.2 椭圆曲线域参数
• 2.3.3 ECC 的原理
• 2.4 椭圆曲线数字签名（ECDSA）
• 2.4.1 ECDSA 概述
• 2.4.2 ECDSA 域参数
• 2.4.3 椭圆曲线数字签名算法
• 2.5 椭圆曲线加密的性能分析
• 2.5.1 加密算法效率的评价标准
• 2.5.2 计算量与处理速度
• 2.5.3 存储空间占用小
• 2.5.4 带宽要求低
• 2.6 小结
• 第三章 软件实现环境
• 3.1 IA-32 与保护模式汇编程序
• 3.1.1 CPU 内部的寄存器
• 3.1.2 保护模式的内存管理
• 3.1.3 数据寻址方式
• 3.2 VC++内联式汇编
• asm 块'>3.2.1 asm 关键字和_asm 块
• asm 块中访问C/C++变量'>3.2.2_asm 块中访问C/C++变量
• asm 块对寄存器的影响和代码优化'>3.2.3_asm 块对寄存器的影响和代码优化
• asm 块中调用C/C++函数'>3.2.4 从_asm 块中调用C/C++函数
• 3.2.5 标号
• 3.2.6 调试工具
• 3.3 小结
• 第四章 最优扩域
• 4.1 最优扩域的定义
• 4.2 最优扩域中的数学运算
• 4.2.1 快速子域求模
• 4.2.2 加法和减法
• 4.2.3 乘法（多项式相乘）
• 4.2.4 子域求模逆
• 4.2.5 域元素求逆
• 4.2.6 域元素模P （x） 归约
• 4.3 小结
• 第五章 椭圆曲线上的快速算法
• 5.1 椭圆曲线上的点加运算和倍点运算
• 5.1.1 实数域上的点加运算
• 5.1.2 素数域GF （p） 上的点加运算
• 5.1.3 有限域GF （pm） 上的点加运算
• 5.2 仿射坐标和投影坐标下的点加公式
• 5.2 ECC 上的标量乘法
• 5.2.1 二进制法
• 5.2.2 Montgomery 法
• 5.2.3 非临近生成NAF 法
• 5.2.4 固定基窗口FBW 法
• 5.2.5 2P+Q 算法
• 5.2.5 改进型3P 算法
• 5.2.6 改进型MFBW 法
• 5.3 小结
• 第六章 算法的实现和性能测试
• 6.1 子域求模加
• 6.2 子域求模减
• 6.3 子域求模乘
• 6.4 子域求模逆
• 6.5 扩域求模加
• 6.6 扩域求模减
• 6.7 扩域求模乘（硬乘法）
• 6.8 扩域求模乘（Karatsuba 法）
• 6.9 扩域求模乘（改进算法）
• 6.10 域元素求逆（EEA）
• 6.11 域元素求逆（MAIA）
• 6.12 椭圆曲线上的点加
• 6.13 椭圆曲线上的倍加
• 6.14 随机生成160 位二进制形式正整数
• 6.15 随机生成160 位NAF 形式正整数
• 6.16 二进制加减法kP 计算
• 6.17 Montgomery 法kP 计算
• 6.18 非临近NAF 法kP 计算
• 6.19 改进型算法kP 计算
• 6.20 综合分析
• 6.21 小结
• 第七章 总结和展望
• 参考文献
• 致谢
• 个人简历