双有限域模乘和模逆算法及其硬件实现

陈光化; 朱景明; 刘名; 曾为民

doi:10.3724/SP.J.1146.2009.01258

双有限域模乘和模逆算法及其硬件实现

doi: 10.3724/SP.J.1146.2009.01258

陈光化^{① 朱景明,},
朱景明,
刘名,
曾为民

基金项目:

上海大学十一五211建设项目资助课题

计量
- 文章访问数: 4041
- HTML全文浏览量: 135
- PDF下载量: 1133
- 被引次数: 0
出版历程
- 收稿日期: 2009-09-25
- 修回日期: 2009-12-31
- 刊出日期: 2010-09-19

Dual-field Modular Multiplication Algorithm and Modular Inversion Algorithm with VLSI Implementation

摘要

摘要: 有限域上的模乘和模逆运算是椭圆曲线密码体系的两个核心运算。该文在Blakley算法的基础上提出一种radix-4快速双有限域模乘算法，该算法采用Booth编码技术将原算法的迭代次数减少一半，并利用符号估计技术简化约减操作；在扩展Euclidean求逆算法的基础上提出一种能够同时支持双有限域运算的高效模逆算法，该算法不仅避免了大整数比较操作，而且提高了算法在每次迭代过程中的移位效率。然后针对这两种算法特点设计出一种能够同时完成双有限域上模乘和模逆操作的统一硬件结构。实现结果表明：256位的模乘和模逆统一硬件电路与同类型设计相比较，在电路面积没有增加的情况下，模乘运算速度提高68%，模逆运算的速度也提高了17.4%。
- 椭圆曲线密码体系 /
- 模乘 /
- 模逆 /
- 双有限域 /
- Blakley算法 /
- 扩展Euclidean算法
Abstract: Modular multiplication and modular inversion algorithms are the kernel of elliptic curve cryptography. In this paper, a radix-4 dual-filed modular multiplication algorithm which is based on Blakelys algorithm is proposed. Booths algorithm is used to halve the iteration number of the Blakelys algorithm, and the sign estimation is employed to simplify the modular reduction operation. A dual-field modular inversion algorithm which is derived from extended Euclidean algorithm is presented to avoid magnitude comparison and shift efficiently. Furthermore, a unified hardware structure which can support dual-field modular multiplication and modular inversion operation is designed, and the result of the hardware implementation shows that the circuit can run 68% faster for modular multiplication and 17.4% faster for modular inversion without area increasing than others.
- Elliptic Curve Cryptography (ECC) /
- Modular multiplication /
- Modular inversion /
- Dual-field /
- Blakleys algorithm /
- Extended Euclidean algorithm.

HTML全文

参考文献(1)

Hankerson D, Menezes A, and Vanstone S. Guide to Elliptic Curve Cryptography. New York: Springer Verlag New York Inc, 2004: 25-147.[2]Savas E and Koc C K. A scalable and unified multiplier architecture for finite fields GF(P) and GF(2m). Cryptographic Hardware and Embedded Systems(CHES) 2000, Worcester, MA, USA, Augst 17-18, 2000: 277-292.[3]Chiou C W, Lee C Y, and Lin J M. Unified dual-field multiplier in GF(P) and GF(2k)[J].Information Security.2009, 3(2):45-52[4]Wang Jian and Jiang An-ping. A high-speed dual field arithmetic unit and hardware implementation, ASICON'07, Guilin, China, Oct. 22-25, 2007: 213-216.[5]Ma Shi-wei, Hao Yuan-ling, and Pan Zhong-qiao. Fast implementation for modular inversion and scalar multiplication in the elliptic curve cryptography, IITA '08, Beijing, China, Dec. 20-22, 2008: 488-492.[6]Yan Xiao-dong and Li Shu-guo. Modified modular inversion algorithm for VLSI implementation, ASICON'07, Guilin, China, Oct. 22-25, 2007: 90-93.[7]Shieh M D, Chen J H, and Lin W C. A new algorithm for high-speed modular multiplication design[J].Circuits and Systems.2009, 56(9):2009-2019[8]Hussin R, Shakaff A Y M, and Idris N. An efficient modified Booth multiplier architecture electronic design, ICED'08, Beijing, China, Dec. 1-3, 2008: 1-4.[9]Nibouche O, Nibouche M, and Bouridane A. New iterative algorithm for modular multiplication, ICECS 2001, St. Julians. Malta, Sept. 2-5, 2001: 879-882.[10]王健. 椭圆曲线加密体制的双有限域算法及其硬件实现. [博士论文], 北京大学, 2008.[11]Wang Jian. A dual-field algorithm for elliptic curve cryptosystem and its hardware implementation. [Ph.D. dissertation], Peking University, 2008.

施引文献

资源附件(0)

访问统计