Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (13): 62-65.DOI: 10.3778/j.issn.1002-8331.2010.13.019

• 研发、设计、测试 • Previous Articles     Next Articles

Dual-field modular inversion algorithm and hardware implementation

YANG Tong-jie,DAI Zi-bin,YANG Xiao-hui,ZHANG Jun   

  1. Montgomery modular inversion algorithm;dual field;scalable architecture
  • Received:2009-10-13 Revised:2010-01-05 Online:2010-05-01 Published:2010-05-01
  • Contact: YANG Tong-jie

一种双域Montgomery求逆算法与硬件实现

杨同杰,戴紫彬,杨晓辉,张 军   

  1. Modular inverse arithmetic plays an important role in elliptic curve cryptography.This paper analyzes the Montgomery modular inversion algorithm in finite fields GF(p) and GF(2n) respectively and improves the latter by advancing the comparison of degree of variables.This improvement makes it easy to implement the Modular inverse arithmetic in GF(p) and GF(2n) in a unified hardware design and shortens the delay of comparison of degree.A dual-field modular inversion algorithm is presented and a scalable and unified architecture for Montgomery inverse hardware in finite fields GF(p) and GF(2n) is completed accordingly.Finally this work has been verified by modeling it in Verilog-HDL,implementing it under 0.18 μm CMOS technology.The result indicates that the work has advanced performance better than other works.
  • 通讯作者: 杨同杰

Abstract: Modular inverse arithmetic plays an important role in elliptic curve cryptography.This paper analyzes the Montgomery modular inversion algorithm in finite fields GF(p) and GF(2n) respectively and improves the latter by advancing the comparison of degree of variables.This improvement makes it easy to implement the Modular inverse arithmetic in GF(p) and GF(2n) in a unified hardware design and shortens the delay of comparison of degree.A dual-field modular inversion algorithm is presented and a scalable and unified architecture for Montgomery inverse hardware in finite fields GF(p) and GF(2n) is completed accordingly.Finally this work has been verified by modeling it in Verilog-HDL,implementing it under 0.18 μm CMOS technology.The result indicates that the work has advanced performance better than other works.

Key words: Montgomery modular inversion algorithm, dual field, scalable architecture

摘要: 有限域上的求逆运算是椭圆曲线密码算法的关键运算之一。分别对GF(p)和GF(2n)域上的Montgomery模逆算法进行分析,并将GF(2n)域上的Montgomery模逆算法中对变量阶数的比较进行了改进,这样不仅利于GF(p)和GF(2n)域上的模逆运算在统一的硬件结构上实现,也解决了数据位数较大时进行阶数比较延迟较大的问题,在此基础上提出一种基于GF(p)和GF(2n)双域上统一的模逆算法,并根据算法,采用双域可伸缩运算单元,实现了一种可扩展的统一Montgomery模逆硬件结构。设计采用Verilog-HDL语言进行硬件描述,并基于0.18 μm工艺标准单元库进行了综合,结果表明该设计与其他设计相比具有灵活性好、性能高的特点。

关键词: Montgomery模逆算法, 双域, 可扩展硬件电路

CLC Number: