论文标题:椭圆曲线密码体制中的倍点算法研究
Research on Elliptic Curve Point Multiplication
论文作者
论文导师 周玉洁,论文学位 硕士,论文专业 密码学
论文单位 解放军信息工程大学,点击次数 126,论文页数 68页File Size3298K
2006-04-01论文网 http://www.lw23.com/lunwen_967111422/
elliptic curve cryptosystem; elliptic curve point multiplication; Montgomery modular inverse
本文针对椭圆曲线密码体制实现效率的核心问题，倍点运算，在F_p和F_(2~n)上进行了多角度，分层次的研究，提出了相应的改进算法，并给出了详细的效率改进评估。主要工作和研究成果如下： 1．分三个层次——椭圆曲线所依赖的有限域上的基础运算，椭圆曲线上的点的基本运算，以及更上层的基于对kP运算中k的各种优化，进行了深入的研究分析，在总结现有算法的基础上提出自己的改进算法。 2．提出两种改进的高基Montgomery逆算法，其中4-基算法把迭代次数的上限由2n降低到了平均7/6n，而平均迭代次数也由1.4n降低到了0.82n。软件实现显示，效率提高了大约11％，迭代次数减少了约41.5％。而对于8-基算法，迭代次数的上限被降低到了平均25/24n，而平均迭代次数也降低到了0.73n，但由于其内部实现的复杂性，软件实验表明它只能适用于非常大的整数应用环境，比如对于2048比特以上的数，效率能提高13％～18％。 3．提出在JSF类算法上改进的“三分裂”算法，在多增加9个点的预计算量的基础上，运算速度提升了26％；在此基础上我们又提出了基于并行实现的二叉树并行算法，以较少的并行单元就能达到较高的运算速度，而且这种运算体系非常利于硬件的流水操作，另外由于算法设计的灵活性，硬件实现时可以在速度和成本上达到平衡。 4．研究过程中自行开发了一个F_p上的椭圆曲线运算包，这个运算包的编写和使用加深了作者对椭圆曲线密码体制的理解，它稍加修改就可以作为商业加密软件模块的支撑库。
In this thesis, we research on the multiplication of points in ECC over F_p and F_(2~n) in differentaspects, which is the core operation in ECC implementations. The main work and results obtained are as follows:1. We take the research in three aspects, that is arithmetic over finite fields, the basic operation of points on elliptic curves, and various optimizations over k when calculating kP . Besides summarizing known algorithms, we also present new improved ones.2. Two modified Montgomery modular inverse algorithms are proposed for software applications. The radix-4 algorithm can reduce the upper limit of the number of iterationsfrom 2n to 7/6n on average, and the average number of iterations from 1.4n to 0.82n accordingly. The software experiment shows about 11% speedup, and the iterations are about 41.5% less in experiment. As for the radix-8 one, it can reduce the upper limit of number of25iterations to 25/24n, and the average number of iterations to 0.73n. But there are more complicated branches in the algorithm, which makes it only suitable for very large numbers. For example, for numbers larger than 2048 bits, the speedup can be 13%-18%.3. "Thribble-splited" algorithm is proposed, which is improved from JSF algorithm. At the cost of precomputing 9 more points, the speedup is about 26%. And further we present the binary tree algorithm for parallel implementation, which can achieve higher speed by less parallel units. And the architecture is also suitable for pipelining in hardware implementation. For the flexibility in the algorithm architecture, hardware implementation can get compromised between efficiency and cost.4. During the research we have developed by ourselves an ECC software library over F_p. Thedevelopment and application of the library deepens our understanding of ECC. By a few modifications, the library can be used in business as a support library for software crypto-module.
|
