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

Improved modular exponentiation and VLSI implementation for RSA cryptosystem

作　　者：谢元斌[1] 史江一[1] 郝跃[1] 

机构地区：[1]西安电子科技大学宽禁带半导体材料与器件教育部重点实验室,陕西西安710071

出　　处：《西安电子科技大学学报》2011年第2期129-134,179,共7页Journal of Xidian University

基　　金：国家重大基础研究资助项目(61398);国家自然科学基金资助项目(60736033)

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

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

分 类 号：TP332.2[自动化与计算机技术—计算机系统结构]