RSA算法和RSA数字签名算法的实现.doc

基于verilog的RSA实现和RSA数字签名题 目：基于verilog的RSA实现和RSA数字签名学 院： 专 业： 姓 名： 学 号： 摘要: RSA算法是一种公钥密码算法.实现RSA算法包括生成RSA密钥,用RSA加密规则和解密规则处理数据.RSA数字签名算法利用RSA算法实现数字签名.本文详述了RSA算法的基本原理, RSA加密算法的实现以及如何利用RSA实现数字签名.关键字: RSA算法, 数字签名, 公开密钥, 私人密钥, 加密, 解密一、引言 随着网络技术的飞速发展,信息安全性已成为亟待解决的问题.公钥密码体制中,解密和加密密钥不同,解密和加密可分离,通信双方无须事先交换密钥就可建立起保密通信,较好地解决了传统密码体制在网络通信中出现的问题.另外,随着电子商务的发展,网络上资金的电子交换日益频繁,如何防止信息的伪造和欺骗也成为非常重要的问题.数字签名可以起到身份认证,核准数据完整性的作用.目前关于数字签名的研究主要集中基于公钥密码体制的数字签名. 公钥密码体制的特点是:为每个用户产生一对密钥(PK和SK);PK公开,SK保密;从PK推出SK是很困难的;A,B双方通信时,A通过任何途径取得B的公钥,用B的公钥加密信息.加密后的信息可通过任何不安全信道发送.B收到密文信息后,用自己私钥解密恢复出明文. 公钥密码体制已成为确保信息的安全性的关键技术.RSA公钥密码体制到目前为止还是一种认可为安全的体制.本文详述了RSA算法和用RSA算法实现数字签名的理论,以及它们在实际应用中的实现.二、RSA算法和RSA数字签名算法的理论描述1 RSA算法 RSA算法的理论基础是一种特殊的可逆模幂运算. 设n是两个不同奇素数p和q的积,即:n=pq, (n)=(p-1)(q-1).定义密钥空间 k=(n,p,q,d,e)|n=pq,p和q是素数,de1 mod (n),e为随机整数,对每一个k=(n,p,q,d,e),定义加密变换为 Ek(x)=xb mod n,xZn;解密变换为 Dk(x)=ya mod n,yZn,Zn为整数集合.公开n和b,保密p,q和a. 为证明加密变换Ek和解密变换 Dk满足Dk(Ek(x)=x,这里不加证明的引用下面两个定理: 定理1(Euler)对任意的a(Zn*,有a(n)(1 mod n,其中Zn*=x(Zn|gcd(x,n)=1,()表示Euler函数. 定理2 设p和q是两个不同的素数,n=pq, (n)=(p-1)(q-1),对任意的x(Zn及任意的非负整数k,有 xk(n)+1(x mod n. 现在来证明RSA算法的加密变换和解密变换的正确性. 证明: 对于加密变换Ek和解密变换Dk.因为ab1 mod (n),所以可设ab=t(n)+1,t是整数且t1.对于任意的xZn,有Dk(Ek(x)Dk(xb) (xb)axt(n)+1x mod n.因此解密过程是正确的.2 RSA数字签名算法 RSA数字签名算法的过程为:A对明文m用解密变换作: s Dk (m)=md mod n,其中d,n为A的私人密钥,只有A才知道它;B收到A的签名后,用A的公钥和加密变换得到明文,因: Ek(s)= Ek(Dk (m)= (md)e mod n,又 de1 mod (n)即de=l(n)+1,根据欧拉定理m(n)=1 mod n,所以Ek(s)=ml(n)+1=m(n)em=m mod n.若明文m和签名s一起送给用户B,B可以确信信息确实是A发送的.同时A也不能否认送给这个信息,因为除了A本人外,其他任何人都无法由明文m产生s.因此RSA数字签名方案是可行的. 但是RSA数字签名算法存在着因计算方法本身同构造成签名易被伪造和计算时间长的弱点,因此实际对文件签名前,需要对消息做MD5变换. MD5函数是一种单向散列函数,它将任意长度的消息压缩成128位的消息摘要.应用MD5的单向性(即给定散列值,计算消息很难)和抗碰撞性(即给定消息M,要找到另一消息M 并满足两者的散列值很难),可以实现信息的完整性检验.另外该函数的设计不基于任何假设和密码体制而直接构造,执行的速度快,是一种被广泛认可的单向散列算法.三、RSA算法的实现 RSA算法的实现分为:生成密钥,加密,解密1 密钥的生成：私钥的产生：本实验鉴于运算速度，和存储器的选择。采用由小到大选择一与(P-1)*(Q-1)互质的e值。公钥的产生：通过e*d=1mod(n)算出d的值，d即为公钥的值。2 生成RSA密钥需完成下列步骤:(1) 选择e的值为3至65536;(2) 随机生成大素数p,直到gcd (e,p-1)=1;其中gcd(a,b)表示a,b取最大公约数(3) 随机生成不同于p的大素数q,直到gcd (e,q-1)=1;(4) 计算n=pq , (n)=(p-1)(q-1);(5) 计算d,满足de1 (mod (n);(6) 计算d mod (p-1), d mod (q-1);(7) 计算q-1 mod p;(8) 将n,e放入RSA公钥;将n,e,d mod (p-1),d mod (q-1) q-1 mod p放入RSA私钥.2.1 随机数的产生 随机数不仅用于密钥生成,也用作公钥加密时的填充字符.它必须具有足够的随机性,以防止破译者掌握随机数的规律性后重现密钥的配制过程或者探测到加密块中的明文.因为在计算机上不可能产生真正的随机数,实际采用周期大于2256位的伪随机序列发生器. 实现过程为:通过PRBS算法，实现PRBS随机码。通过一定时间随机选出一个素数。2.2 素数的产生 对随机数作素性检测,若通过则为素数;否则增加一个步长后再做素性检测,直到找出素数.素性检测采用Fermat测试.这个算法的理论依据是费尔马小定理:如果m是一个素数,且a不是m的倍数,那么根据费尔马小定理有:a m-1=1 ( mod m). 实际应用时:a m-1 = 1 ( mod m) a m = a ( mod m) a= a m ( mod m), 因此对于整数m,只需计算a m ( mod m),再将结果与a比较,如果两者相同,则m为素数.选取a=2,则a一定不会是任何素数的倍数.3 加密过程 加密规则为:Ek(x)=xb mod n,xZn 加密过程的输入为:明文数据D,模数n, 加密指数e(公钥加密)或解密指数d(私钥加密).输出为密文.D的长度不超过log2n-11,以确保转换为PKCS格式时,填充串的数目不为0. 格式化明文. 采用PKCS格式: EB = 00 | BT | PS | 00 | D 其中BT表示块的类型,PS为填充串,D为明文数据.开头为0确保EB长度大于k.对公钥加密BT=02,对私钥解密BT=01.当BT=02时,PS为非0随机数;当BT=01,PS值为FF. 明文由字符型数据转换成整型数据. RSA计算. 为整数加密块x作模幂运算:y = xc mod n,0 = y 为密文,公钥加密时,c为公钥加密指数e;私钥加密时,c为私钥加密指数d. 密文由整型数据转换成字符型数据.4 解密过程 解密规则为 Dk(x)=yc mod n,yZn,Zn为整数集合,x为密文. 解密过程的输入为:密文ED;模数n;加密指数e(公钥解密)或解密指数d(私钥解密),结果为明文.(1) 密文整型化.(2) RSA计算. 对密文做模幂运算:x = yc mod n, 0 = x ruslt_nub2)|ruslt_nub1%ruslt_nub2!=0)beginP=ruslt_nub1;Q=ruslt_nub2;endelsebeginP=b0;Q=b0;endendalwaysbeginbeginn_tem=(P-1)*(Q-1);n=P*Q;in_dec15:0=input_number3:0+10*input_number7:4+100*input_number11:8+1000*input_number15:12;if(ie)begini=0;out_dec=in_dec*out_dec;output_code=out_dec%n;endelsei=i+1;endif(jn_tem)int_nub=(e*x-1)%n_tem;elsex=x+1;if(int_nub%1=0)begind=int_nub;x=1;endelseint_nub=0;endendmodule八、通过Quartus II仿真的底层电路图：九、结束语： 本文讨论了RSA算法的基本原理和RSA的verilog实现