椭圆曲线的选取与双线性对的快速计算研究

论文摘要

椭圆曲线密码体制（ECC）是公钥密码体制中的重要研究领域。其应用中的关键问题是在保证安全的前提下提高系统效率。椭圆曲线密码体制实现中最重要的问题是安全的椭圆曲线参数选取,椭圆曲线的点乘运算以及基于椭圆曲线的双线性对计算。本文从密码系统的快速实现出发,对pairing-friendly椭圆曲线的选取和椭圆曲线点乘的计算以及椭圆曲线Tate Pairing和Ate Pairing的计算进行了研究,并取得以下结果:1.在Duan等人工作的基础上,构造了更多适合双线性对计算的pairing-friendly椭圆曲线,衡量的参数主要有嵌入次数k和ρ。本文扩充了嵌入次数的取值;同时放宽了r（x）的限制。改进的算法适合所有的双线性对,当椭圆曲线的Frobenius迹t达到下界时,更能有效地加速Ate对的运算,从而进一步提高了基于双线对设计的密码方案的效率。2.点乘算法的速度直接决定椭圆曲线密码体制的效率。本文通过对椭圆曲线点乘算法的改进,提高了双线性对的速度,进而提高椭圆曲线密码体制的速度。本文研究了特征为素数的有限域,首先在基域中,乘法计算比平方计算更费时,本文在已有算法基础上对二次求逆重新组合,利用“double-add”技巧,减少乘法运算次数,改进的算法比已有的算法效率提高了2.9%。最后将优化后的倍点加算法直接运用到Miller算法中,并结合NAF的表示形式,减少了倍点加的运算次数,改进的Miller算法相对于Miller算法提高了约47%;相对于文献[55]中算法提高了约4.03%,从而有效的提高了双线性对的效率。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.2 研究现状
• 1.2.1 椭圆曲线的选取
• 1.2.2 基域的选择
• 1.2.3 点乘算法
• 1.2.4 双线性对的计算
• 1.3 椭圆曲线密码的应用现状
• 1.4 本文工作
• 1.5 本文的章节安排
• 第二章 椭圆曲线基本理论知识
• 2.1 有限域的介绍
• 2.1.1 有限域中一些重要的结论
• 2.1.2 有限扩域的具体构造
• 2.2 椭圆曲线的基本介绍
• 2.2.1 有限域上的Weierstrass方程
• 2.2.2 群的运算法则
• 2.2.3 椭圆曲线上点的表示和运算
• 2.2.4 群的阶及扭映射
• 2.2.5 除子
• 2.3 椭圆曲线的条件
• 2.3.1 椭圆曲线的安全性约束
• 2.3.2 椭圆曲线条件的推导
• 2.4 双线性对
• 2.5 一般Pairing-friendly曲线生成方法
• 2.6 椭圆曲线的复乘理论
• 2.7 本章小结
• 第三章 一种新的Pairing-friendly椭圆曲线的构造算法
• 3.1 Pairing-friendly椭圆曲线的选取
• 3.2 构造椭圆曲线的算法
• 3.3 改进的构造椭圆曲线的算法
• 3.3.1 r（x）为分圆多项式的形式
• 3.3.2 r（x）为非分圆多项式的情形
• 3.4 CM判别式D可变
• 3.5 生成适合Ate对的椭圆曲线的算法
• 3.6 本章小结
• 第四章 双线性对快速算法研究及改进
• 4.1 椭圆曲线的点乘运算
• 4.2 计算2P+Q
• 4.2.1 计算2P+Q
• 4.2.2 改进计算2P+Q的算法
• 4.3 Miller算法
• 4.3.1 具体的定义
• 4.3.2 关于Miller算法
• 4.3.3 引入NAF后改进的Miller算法
• 4.4 本章小结
• 第五章 总结与展望
• 5.1 总结
• 5.2 展望
• 致谢
• 参考文献
• 硕士期间论文发表情况及科研工作