椭圆曲线密码体制标量乘快速算法研究

摘要

在网络技术快速发展的驱动下，计算机网络已经逐渐地开始应用于各个领域。随着网络越来越普遍，计算机网络的安全问题也越来越严重。由于公钥加密比较昂贵，其与对称密钥相比较，它仍然是一个开放的挑战。因此，需要进一步减少最耗时公钥加密的计算成本，以保证其采用用于商业安全通信和基于互联网的应用。椭圆曲线密码系统的提出使得代数几何和数论领域中研究了很久时间的椭圆曲线走上了密码学的舞台。
　　椭圆曲线密码体制中的标量乘法和多标量乘法是实现椭圆曲线密码体制的主要的运算，其运算速度的快慢从整体上决定了椭圆曲线密码体制的实现效率的快慢。本文首先分析了一些经典的椭圆曲线的标量乘算法，然后在针对标量乘的有关算法的不足进行了改进，从而提高了算法的运算效率。本文主要的研究内容和研究结果如下:
　　(1)通过研究分析经典的标量乘NAF算法及其算法的运算量，对现有算法中存在的不足有了基本的了解。该算法将标量k表示为NAF形式，由NAF的性质可得，表示为NAF的标量k可能要比二进制的长度要大;并且在标量k的NAF形式中，如果能够把非零元素和零元素更加集中，能够将进行分块来计算，可以用滑动技术来提高算法的效率。针对这些不足的地方，本文提出了一种改进的NAF算法，改进后的算法可以降低标量七的长度和权值，有利于kP运算。数据表明改进后的算法可以大约提高了9％的效率，这说明了改进的算法要优于原来的算法。
　　(2)通过对Dimitrov等人提出的基于的双基和多基表示标量乘算法的分析，该算法中需要多次用到P+Q，2P+Q等底层域的运算，本文提出了一种改进的标量乘算法，该算法是利用求逆的运算转换乘乘法运算的思想，只用到了一次求逆的运算，虽然乘法和平方运算会有增加，但是总的运算效率是有所提高的。然后对改进算法的最优路径进行了分析，并且用到了2kP，3kP等底层域的算法，从而使得改进算法的效率要高于Dimitrov等人的算法。

目录

声明

摘要

第1章 绪论

1．1 论文的研究背景和意义

1．2 国内外研究现状

1．3 本文的研究内容和结构安排

第2章 椭圆曲线密码体制的数学基础

2．1 有限域基础

2．1．1 群

2．1．2 有限域

2．2 椭圆曲线理论基础

2．2．1 椭圆曲线的概念

2．2．2 椭圆曲线密码体制

2．3 本章小结

第3章 椭圆曲线密码体制标量乘的快速算法

3．1 二进制方法

3．2 m进制方法

3．3 非相邻形式方法

3．4 窗口方法

3．5 本章小结

第4章 一个椭圆曲线标量乘快速算法及其改进

4．1 LLECC方法

4．2 直接计算2kP

4．3 标量乘算法的改进

4．4 效率分析

4．4．1 正确性分析

4．4．2 算法的性能分析

4．5 本章小结

第5章 基于多基标量乘算法研究

5．1 基于双基和多基表示的标量乘算法

5．1．1 双基表示的标量乘算法

5．1．2 多基表示的标量乘算法

5．2 底层域的快速算法

5．3 基于多基标量乘算法的改进

5．4 效率分析

5．4．1 正确性分析

5．4．2 算法的性能分析

5．5 本章小结

总结与展望

致谢

参考文献

攻读硕士学位期间发表的论文及科研成果