基于GF（2m）的椭圆曲线求逆算法的改进研究

郭高峰+崔强强

摘 要： 针对二进制域上现有求逆算法计算量大、并行度小、速度慢的缺点进行改进，基于二元Euclidean算法提出了改进，设计了相应的乘法器硬件结构，并且分析了其运算效能和资源占用情况。将此求逆计算器的并行改进算法使用Verilog语言编程实现，利用Xilinx ISE 12.4对整个求逆算法综合仿真（行为级），在Xilinx Virtex?5 XC5VFX70T的硬件平台上验证求逆算法的运算效率，结果表明对求逆算法的改进有效地提高了求逆运算的速度。

关键词： 椭圆加密； 二进制域； 求逆； 扩展欧几里得算法

中图分类号： TN918?34； TP309.7 文献标识码： A 文章编号： 1004?373X（2014）18?0019?04

Improvement and research of inversion algorithm of elliptic curve based on GF （2m）

GUO Gao?feng1， CUI Qiang?qiang2

（1. Purchasing Center of Navy Equipments， Lianyungang 222000， China； 2. Jiangsu Automation Research Institute， Lianyungang 222000， China）

Abstract： Since the existing inversion operation algorithm based on GF（2m） has the following disadvantages： large amount of calculation， poor degree of parallelism and slow speed， an improved algorithm is proposed in this paper based on Extended Euclidean Algorithm. A corresponding multiplier hardware structure was designed. Its operation performance and the status of resource occupancy are analyzed. This parallel improved algorithm of inversion operation calculator was realized with the program based Verilog. The comprehensive simulation of the whole inversion algorithm was conducted with Xilinx ISE 12.4. The operation efficiency of the inversion algorithm was verified on hardware platform of Xilinx Virtex?5 xc5vfx70t. The experimental result and performance comparison show that the modification of the inversion algorithm has improved its speed.

Keywords： ECC； GF（2m）； inverse operation； expend Euclidean algorithm

0 引 言

椭圆密码算法ECC（Elliptic Curve Cryptography）[1]具有每bit 最高的安全性[2]，ECC算法的主要优点有[3]：安全性能高；计算量小且运算速度快；占用存储空间小；对数据运算带宽要求低。目前常用的定义椭圆曲线的有限域有两种：素数域GF（p） 和二进制域GF（2m）。在二进制域上元素可以直接用二进制位向量表示，这样元素的加、减、乘等操作在计算机中可以并行实现，所以二进制域的椭圆曲线加密通常被用于硬件实现的椭圆曲线加密系统中。GF（2m）上的非奇异椭圆曲线是Weierstrass 公式定义的：y2+xy=x3+ax2+b。其中a，b是GF（2m）中的元素，且b≠0。曲线E同时还包括一个无穷远点，通常用O 表示， 为曲线上点的加法单位元。有限域上的模逆运算是椭圆曲线密码系统中的关键性计算，但是其运算效率却是最低的，据M.Brown， D.Hankerson等人粗略估计[4]，求逆运算与乘法运算（带有快速取模运算）的资源占用比是80∶1，因此通过改进加速求逆运算减少其计算时间可以在很大程度上提高椭圆加密的运算效率和吞吐量。……