代换密码算法的模拟实现 RSA密码算法的可重构设计与实现

　　摘要:本文对RSA密码算法的实现和可重构性进行了分析,在对模幂模块和模乘模块进行了可重构设计的基础上,提出一种可重构RSA硬件架构,使其能够适配256bit、512bit、1024bit、2048bit四种不同密钥长度的应用。RSA可重构设计在FPGA上进行了实现与测试,结果表明,工作在200MHz时钟时,2048bit密钥长度RSA在最坏情况下数据吞吐量可达46 kb/s,能够满足高性能的信息安全系统对RSA算法的加密速度要求。
　　关键词: RSA;模乘运算;模幂运算;可重构设计
　　中图分类号:TP339 文献标识码:A
　　
　　Reconfigurable Design and Implementation of RSA Algorithm
　　
　　WU Bin-shan,WANG Yun-feng,LIU Zhi-chao,LIU Tian-xiang
　　(Department of Electronic Engineering,Xiamen University,Xiamen 361005,China)
　　
　　Abstract: In this paper, the implementation and reconfigurable feature of RSA cryptographic algorithm are analyzed. On the basis of the Reconfigurable design of the Modular Multiplication and Modular Exponentiation, we propose the reconfigurable RSA hardware architecture, which is able to fit 256bit, 512bit, 1024bit, 2048bit four applications of different key length. The RSA reconfigurable design and testing were carried out to achieve results, which show that in the worst case, 2048bit RSA get the data throughput achieved 46 kb/s when work in the 200MHz clock. It is able to meet the high-performance information security systems RSA encryption algorithm on the speed requirement.
　　Keywords: RSA; Modular Multiplication; Modular Exponentiation; Reconfigurable Design
　　
　　1引言
　　
　　 随着计算机网络的普及与发展,信息安全问题显得格外重要。以RSA密码算法[1]为代表的公钥密码体制[2]在保证数据的机密性、完整性以及签名和认可等方面的突出优点己经使其成为当今网络安全中最重要的解决方法,相应的密码芯片在网络中得到了广泛的应用。
　　 目前,大多数密码芯片是实现一种固定密码算法的专用芯片,不能满足用户们的不同层次的安全性能和预留密码算法升级空间的要求。因此,近年来国内外许多机构和个人都致力于可重构密码芯片设计的研究[3~6]。可重构密码芯片是采用可重构体系结构设计而成的用于对数据进行加/解密处理的集成电路芯片。其内部逻辑电路可以根据不同密码算法的需求重新组织,构成不同的电路结构,实现不同的功能,从而能够灵活、快速地实现多种不同密码算法[3]。
　　 本文在设计RSA算法实现时,综合考虑密钥长度、安全性、性能、面积等因素,在对模幂和模乘运算模块进行了可重构设计的基础上,提出了一种可重构RSA算法结构,在增加很少逻辑单元的情况下,使其能够适配256bit,512bit,1024bit和2048bit四种密钥长度的RSA算法应用,满足不同层次安全性的信息系统的需要。FPGA的原型实现和验证结果表明,该设计能够满足高性能信息安全系统对于公钥密码加密速度的要求,可以作为可重用IP,用于信息安全SoC设计。
　　
　　2RSA算法
　　
　　 RSA密码算法的明文空间M与密文空间C相等,为Zn(表示mod n所组成的整数空间,取值范围为0~n-1)。
　　 RSA算法描述如下[1]:
　　 (1)选择两个互异的大素数p和q(保密),计算n=p・q(公开),φ(n)=(p-1)・(q-1)(保密),选择一个随机数e(0 本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文 　　
　　 3.3 由Montgomery算法构造的从左到右二进制扫描位扫描法
　　 由于Montgomery算法的结果并不是(A×B)modN,而是(A・B・2-(K+3))mod N。所以必须对从左到右二进制位扫描法进行修改,首先,必须先进行一次预处理步骤,分别计算C =Monprod(1,R,N)和M2=Monprod(M,R,N),其中R为与N相关的常数,R =22(n +3)mod N。其次,算法结束后再进行一次后处理步骤,计算C =Monprod(1,C,N),这样就可以消除模乘运算结果中多余的参数。具体算法如下:
　　 输入:M,e,N,R
　　 输出:C =Me mod N
　　 {
　　 M 2=Monprod(M,R,N)
　　 C =Monprod(1,R,N)
　　 for i=n-1to 0 do
　　 {
　　 C =Monprod(C,C,N);
　　 If (ei=1) C =Monprod(C,M 2,N) ;
　　 }
　　 C =Monprod(1,C,N)
　　 return C;
　　 }
　　
　　 3.4 可重构性分析
　　 可重构设计以软件编程的方式快速灵活的实现不同硬件电路,克服了软件和硬件实现各自的不足,可以比软件实现有着更好的性能,同时比硬件实现更具有灵活性。可重构模块包含许多可由外部编程控制的计算单元,这些单元由一些可配置连线资源连接着,可以通过对连线资源的改变来形成需要的不同电路。
　　 通过对模幂和模乘运算算法分析可知,不同密钥长度的RSA算法的主要部件大数加法运算模块是可重用部件,而差别主要是在模幂运算的循环次数n、ei的起始位ex和模乘算法的循环次数(K+3)。因此可以以大数加法运算模块为重构元素进行可重构设计,设置n、K+3和ex为可控节点,通过输入信号对可控节点进行可编程控制。例如:当密钥长度为1024的时候,选择n为1024、 ex为e[1023]、K+3为1027; 而当密钥长度为2048的时候,选择n为2048、ex为e[2047]、K+3为2051。
　　
　　4RSA算法可重构设计
　　
　　基于模幂、模乘模块的可重构性,本文提出了一种可以根据密钥长度的不同进行可重构的RSA算法实现结构,结构框图如图1所示,分为模乘模块(包括模乘控制器和模乘运算单元)、模幂模块、存储模块三个部分。
　　 图1中各个信号的定义如表1所示。
　　
　　 4.1 模乘模块
　　模乘模块包括模乘运算单元和模乘控制单元。实现模乘的主要运算是大数的加法。可重构RSA算法的最长密钥长度是2048bit,所以模乘运算模块为2048位。由于2048位的加法是循环进行的,使用进位保留加法器CSA(carry saved adder)是很好的解决方案[10]。CSA将加法结果的和数和进位分别用S和C表示,即进位用C保留下来,作为下一次加法的进位输入。一个一位全加器中,输入 A、B是被加数,输入C是上次加法保留的进位。一个k位的CSA是由k个1位全加器并行组成的,如图2所示。
　　 第i位的结果Si和Ci +1同输入之间的关系为:
　　 Si =Ai ?茌Bi ?茌Ci ;
　　 Ci+1=Ai Bi +Ai Ci +Bi Ci 。
　　 CSA加法器的特点是不会随着位数的增加而产生冗长的进位链,这样既能提高速度,又简化了硬件结构。
　　 由CSA构造的模乘运算单元如图3所示。用两个CSA加法器来实现模乘运算中的两次加法。
　　在模乘算法循环结束后需要将两个2048bit的数相加得到结果。使用一个32位的CPA(carry propagation adder)将2048bit位的加法分成64个时钟周期完成,CPA的运算结果就是模乘运算的最终结果。CPA加法器的结构如图4所示。
　　模乘控制单元主要由计数器来实现,不同密钥长度的RSA算法的模乘循环次数不一样,完成一次循环需要一个运算周期,所以计数器的初始载入值也不一样。可重构RSA算法实现由外部输入信号keysize对初始载入值的选择进行控制。初始载入值为密钥长度加上67(3次增加的循环次数和64个CPA加法周期)。例如,当keysize为“00”时,初始载入值为323;当keysize为“01”时,初始载入值为579。每完成一次循环,计数器减一。当计数器为零的时候,表示模乘运算完成。
　　
　　 4.2 模幂模块
　　 模幂模块主要功能是控制模乘模块的循环运算。对模幂模块的可重构设计主要包括对模乘运算循环次数和密钥的控制。由Montgomery构造的从左到右二进制扫描位扫描法硬件结构图如图5所示。
　　 每个输入都有经过相应位数的寄存器。第一次模乘运算(预运算M 2=Monprod(M ,R ,N))结束后,结果存在M-reg中,以备下次使用。第二次模乘运算(预运算 C =Monprod(1 ,R ,N)))结束后,结果存在rrmodn-reg中。接下来每次循环模乘运算的结果都存入rrmodn-reg中。后处理结束后,rrmodn-reg中就是模幂运算的结果。
　　e_reg用来存储密钥。当load有效时,将外部密钥载入e_reg中。当shift_en有效时,e_reg开始由低位向高位进行位移。具体结构图如图6所示。
　　 e_reg的输出有4位,分别为e_reg的第256、512、1024、2048位,这四位输入一个四选一选择器,由key_seze来选择哪位做为输出。
　　模幂运算控制模块主要是由计数器来实现。不同密钥长度的RSA算法的模幂循环次数不一样,所以计数器的初始载入值也不一样。初始值为密钥长度加上3(2次预处理和1次后处理模乘运算)。每执行完一次模乘运算,计数器就减一,e_reg也进行一次移位,当计数器的值为零时,就表示所有模乘运算都完成,rrmodn-reg中就是模幂运算的结果了。
　　对于n位的输入,这种设计要对输入密钥进行n次扫描,每次扫描需要做一次或者两次模乘,同时,在扫描之前要进行预处理,需要做两次模乘,扫描之后要进行后处理,需要做一次模乘,每做一次模乘需要n+3+64个时钟周期。所以,在最坏情况下,加密需要(2n+3)*(n+3+64)个时钟周期,当n为2048时,需要8.67M个时钟周期。
　　
　　5性能分析
　　
　　两种设计方法可以实现采用固定密钥长度的RSA算法结构所设计的电路同时适配256bit、512bit、1024bit、2048bit四种不同密钥长度的应用。第一种方法是电路包含256bit、512bit、1024bit、2048bit四种不同密钥长度的固定密钥长度RSA密码算法结构;第二种方法是采用2048bit的固定密钥长度RSA算法结构。前一种方法浪费资源,后一种方法处理数据速度慢。
　　 论文采用FPGA对可重构RSA算法结构进行了原型实现与验证,与采用类似结构实现的固定密钥RSA算法所占资源、最高时钟频率如表2所示。
　　采用第一种设计方法所占资源为四种固定密钥长度RSA结构之和,即逻辑单元为43308,存储单元为48348;而可重构RSA使用了22897个逻辑单元和24807比特存储单元,节约了47%的逻辑单元和48%的存储单元。
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文 　　采用可重构RSA与采用第二种设计方法(即使用2048bit固定密钥长度)分别应用于256bit、512bit、1024bit、2048bit密钥长度系统时的数据吞吐量如表3所示,当应用于256bit、512bit、1024bit密钥长度应用时,采用可重构RSA结构性能更优。
　　
　　6小结
　　
　　 本文提出并实现了一种使用较少硬件资源的能够适配256bit,512bit,1024bit和2048bit四种密钥长度的可重构RSA算法结构,适配不同密钥长度RSA算法应用,能够更好的满足不同层次安全性的信息系统的需要。
　　
　　参考文献
　　[1] Rivest R , Shamir A , Adleman L. A method for obtaining digital signature and public-key crypto- systems [J].Communications of the ACM, 1978, 21(2):120-126.
　　[2] Diffie W, Hellman M E. New directions in crypto- graph [J]. IEEE Transactions on Information Theory , 1976 , 6 (22) :644-654.
　　[3] 曲英杰. 可重构密码协处理器的组成与结构.[J] 计算机工程与应用, 2003;23:32-34
　　[4] R Reed Taylor. A high-performance flexible architecture for cryptography [A]. Seth Copen Goldstein Proceeding of the Workshop on Cryptographic Hardware and Embedded Systems [C]. London: Springer-Verlag Press, 1999. 231 - 245.
　　[5] Rainer Bcuchy. A programmable crypto processor architecture for high-bandwidth applications [D]. Germany: Technische University Mü nchen, 2002.
　　[6] T W Arnold, L P Van Doorn. The IBM PC IXCC: A new cryptographic coprocessor for the IBM Server [J]. I BM Journal of Research and Development, 2004, 48 (3) : 475 -487.
　　[7] A.Mazzeo, L.Romano, G. P. Saggese FPGA-based Implementation of a serial RSA processor. [C]. Design,Automation and Test in Europe Conference and Exhibition,2003 : 582-587.
　　[8] Montgomery P L. Modular multiplication without trial division [J].Mathematics of computation, 1985, 44(170): 519- 521
　　[9] 王超,沈海斌,孟庆.RSA密码算法的硬件实现.[J] 计算机工程与应用,2004.14:127~128,147
　　[10] T-W Kwon , et al . Two implementation methods of a 1024 bit RSA cryptoprocesor based on modified Montgomery algorithm[A] . Proceed-ings of the 2001 IEEE International Symposium on Circuits and Systems (ISCAS 2001) [C].New York: IEEE press,2001,4 :650-653.
　　
　　作者简介
　　伍彬山,厦门大学电子工程系在读硕士研究生,研究方向:集成电路设计与应用;
　　王云峰,讲师,厦门大学电子工程系硕士研究生导师;
　　刘智超,厦门大学电子工程系在读硕士研究生,研究方向:集成电路设计与应用;
　　刘天翔,厦门大学电子工程系在读硕士研究生,研究方向:集成电路设计与应用。
　　
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文