Abstract: Modular inversion algorithm on GF(2m) is one of the most crucial algorithms in Elliptic Curve Cryptosystem(ECC). Under the analysis of a universal modular inversion algorithm, an improved algorithm is given in this paper. It can reduce many flaws of the universal algorithm, and has many good improvements for fast implementation. FPGA implementations for the improved algorithm on GF(283) and GF(2233) are presented and compared with two existing implementations respectively. The result indicates that the improved algorithm has about 72.9% higher efficiency on GF(283) and about 59.5% higher efficiency on GF(2233).

Key words: elliptic curve, finite field, modular inversion algorithm, fast implementation

摘要： 在椭圆曲线密码体制中，有限域GF(2m)中模逆运算是最重要的运算之一。在分析一种通用有限域GF(2m)模逆算法的基础上，提出改进算法。改进算法减少了原算法快速实现时的缺点，能够有效地提高算法效率。基于FPGA分别实现了GF(283)和GF(2233)中模逆算法模块，并与2种已有实现结果进行了对比。结果表明，选取有限域GF(283)和GF(2233)时，改进算法效率提高率分别约为72.9%和59.5%。

关键词: 椭圆曲线, 有限域, 模逆算法, 快速实现

CLC Number: 

• TP309.7