一种长整数模乘幂的改进算法与实现

doi:10.3969/j.issn.1001-2400.2011.02.023

J4 ›› 2011, Vol. 38 ›› Issue (2): 129-134+179.doi: 10.3969/j.issn.1001-2400.2011.02.023

一种长整数模乘幂的改进算法与实现

谢元斌;史江一;郝跃

(西安电子科技大学宽禁带半导体材料与器件教育部重点实验室，陕西西安 710071)

收稿日期:2010-10-06 出版日期:2011-04-20 发布日期:2011-05-26
通讯作者: 谢元斌
作者简介:谢元斌(1982-)，男，西安电子科技大学博士研究生，E-mail: ybxie@mail.xidian.edu.cn．
基金资助:
国家重大基础研究资助项目(61398);国家自然科学基金资助项目(60736033)

Improved modular exponentiation and VLSI implementation for RSA cryptosystem

XIE Yuanbin;SHI Jiangyi;HAO Yue

(Ministry of Education Key Lab. of Wide Band-Gap Semiconductor Materials and Devices, Xidian Univ., Xi'an 710071， China)

Received:2010-10-06 Online:2011-04-20 Published:2011-05-26
Contact: XIE Yuanbin

摘要/Abstract

摘要：

RSA密码系统性能受到长整数模乘和模幂运算速度的制约．为了提高模乘幂运算器的速度，采用两级进位保留加法器(CSA)结构改进了蒙哥马利模乘算法．通过插入寄存器缩短了电路的关键路径，保证了CSA操作数的同时性，显著提升了模乘运算器速度．另外，通过调整从左到右的二进制模幂运算的模乘运算次序，避免了大部分模乘运算结束后的结果格式转换，大大节省了转换时间．将采用本方法实现的1024位模幂运算器与近年最具代表性的从左到右二进制模幂运算器相比较的结果表明，Xilinx的FPGA综合实现时，吞吐率提高了36%，面积减少了18%; ASIC综合后，吞吐率提高了75%，面积减少了33%．

关键词: 蒙哥马利模乘算法, 模幂算法, RSA密码系统, 硬件结构设计

Abstract:

Modular multiplication and exponentiation severely restrict the RSA performance. The paper displays a modified Montgomery modular multiplication algorithm based on the two-level carry-save addition (CSA) tree. By inserted registers, the algorithm shortens the critical path and guarantees operands arriving at the CSA input ports simultaneously, which significantly improves the speed of modular multiplication. The modular-multiplication sequence is adjusted in modular exponentiation, which avoids most format conversion and reduces the conversion time. The proposed modular exponentiation circuit improves the throughput rate by 36% and saves hardware cost by 18% compared with the most representative design based on FPGA. For ASIC implementation, the throughput rate is improved by 75%, and area is decreased by 33%.

Key words: montgomery modular multiplication, modular exponentiation, RSA cryptosystem, VLSI architecture

谢元斌;史江一;郝跃. 一种长整数模乘幂的改进算法与实现[J]. J4, 2011, 38(2): 129-134+179.

XIE Yuanbin;SHI Jiangyi;HAO Yue. Improved modular exponentiation and VLSI implementation for RSA cryptosystem[J]. J4, 2011, 38(2): 129-134+179.

参考文献

［1］ Diffie W, Hellman M. New Directions in Cryptography［J］. IEEE Trans on Information Theory,1976,22(6):644-654.
［2］ Wang Guilin. An Abuse-Free Fair Contract-Signing Protocol Based on the RSA Signature ［J］. IEEE Trans on information forensics and security,2010, 5(1):158-168.
［3］ Montgomery P L. Modular Multiplication Without Trial Division［J］. Mathematics of Computation,1985, 44(170):519-521.
［4］刘强, 佟冬, 程旭. 一款RSA 模乘幂运算器的设计与实现［J］. 电子学报,2005,33(5):923-927.
Liu Qiang, Tong Dong, Cheng Xu. The Design and Implementation of a RSA Modular Exponentiator［J］. Acta Electronica Sinica,2005, 33(5):923-927.
［5］ Kwon T W, You C S, Heo W S, et al. Two Implementation Methods of a 1024-bit RSA Cryptoprocessor Based on Modified Montgomery Algorithm［C］//The 2001 IEEE International Symposium on Circuits and Systems. Piscataway: IEEE Press, 2001: 650-653.
［6］ McIvor C, McLoone M, McCanny J V. Modified Montgomery Modular Multiplication and RSA Exponentiation Techniques［J］. IEE Proceedings-Computers and Digital Techniques, 2004, 151(6): 402-408.
［7］ Shieh Mingder, Chen Junhong, Wu Haoshuan, et al. A New Modular Exponentiation Architecture for Efficient Design of RSA Cryptosystem［J］. IEEE Trans on VLSI, 2008, 16(9): 1151-1161.
［8］ McIvor C, McLoone M, McCanny J V. Fast Montgomery Modular Multi-plication and RSA Cryptographic Processor Architectures［C］//Conference Record of the 37th Asilomar Conference on Signals, Systems, and Computers: Vol 1. Piscataway: IEEE Press, 2003: 379-384.
［9］ Zimmermann R. Binary Adder Architectures for Cell-Based VLSI and Their Synthesis［D］. Zurich: Swiss Federal Inst of Technology, 1997.
［10］ Omondi A, Premkumar B. Residue Number Systems: Theory and Implementation［M］. First Edition. London: Imperial College Press, 2007: 29.

一种长整数模乘幂的改进算法与实现

Improved modular exponentiation and VLSI implementation for RSA cryptosystem

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

Metrics

本文评价

推荐阅读 0