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

RSA算法和RSA数字签名算法的实现摘要RSA算法是一种公钥密码算法.实现RSA算法包括生成RSA密钥，用RSA加密规则和解密规则处理数据。RSA数字签名算法利用RSA算法实现数字签名。本文详述了RSA算法的基本原理,RSA加密算法的实现以及如何利用RSA实现数字签名.关键字RSA算法,数字签名,公开密钥,私人密钥,加密,解密中图分类号TP301一、引言随着网络技术的飞速发展，信息安全性已成为亟待解决的问题。公钥密码体制中，解密和加密密钥不同，解密和加密可分离，通信双方无须事先交换密钥就可建立起保密通信，较好地解决了传统密码体制在网络通信中出现的问题。另外，随着电子商务的发展，网络上资金的电子交换日益频繁，如何防止信息的伪造和欺骗也成为非常重要的问题。数字签名可以起到身份认证、核准数据完整性的作用。目前关于数字签名的研究主要集中基于公钥密码体制的数字签名。公钥密码体制的特点是：为每个用户产生一对密钥（PK和ＳＫ）；ＰＫ公开，ＳＫ保密；从ＰＫ推出ＳＫ是很困难的；Ａ、Ｂ双方通信时，Ａ通过任何途径取得Ｂ的公钥，用Ｂ的公钥加密信息。加密后的信息可通过任何不安全信道发送。Ｂ收到密文信息后，用自己私钥解密恢复出明文。公钥密码体制已成为确保信息的安全性的关键技术。RSA公钥密码体制到目前为止还是一种认可为安全的体制。本文详述了RSA算法和用RSA算法实现数字签名的理论，以及它们在实际应用中的实现。二、RSA算法和RSA数字签名算法的理论描述1RSA算法RSA算法的理论基础是一种特殊的可逆模幂运算。设n是两个不同奇素数p和q的积，即：n=pq,(n)=(p-1)(q-1)。定义密钥空间k={(n,p,q,d,e)|n=pq,p和q是素数，de1mod(n),e为随机整数},对每一个k=(n,p,q,d,e),定义加密变换为Ek(x)=xbmodn，xZn;解密变换为Dk(x)=yamodn,yZn，Zn为整数集合。公开n和b，保密p,q和a.为证明加密变换Ek和解密变换Dk满足Dk(Ek(x))=x,这里不加证明的引用下面两个定理：定理1（Euler）对任意的aZn*,有a(n)1modn,其中Zn*={xZn|gcd(x,n)=1},(·)表示Euler函数。定理2设p和q是两个不同的素数，n=pq,(n)=(p-1)(q-1)，对任意的xZn及任意的非负整数k,有xk(n)+1xmodn.现在来证明RSA算法的加密变换和解密变换的正确性。证明：对于加密变换Ek和解密变换Dk。因为ab1mod(n)，所以可设ab=t(n)+1,t是整数且t1。对于任意的xZn，有Dk(Ek(x))Dk(xb)(xb)axt(n)+1xmodn.因此解密过程是正确的。2RSA数字签名算法RSA数字签名算法的过程为：A对明文m用解密变换作:sDk(m)=mdmodn,其中d，n为A的私人密钥，只有A才知道它；B收到Ａ的签名后，用A的公钥和加密变换得到明文，因:Ek(s)=Ek(Dk(m))=(md)emodn,又de1mod(n)即de=l(n)+1,根据欧拉定理m(n)=1modn，所以Ek(s)=ml(n)+1=[m(n)]em=mmodn。若明文m和签名s一起送给用户B,B可以确信信息确实是A发送的。同时A也不能否认送给这个信息，因为除了A本人外，其他任何人都无法由明文m产生s.因此RSA数字签名方案是可行的。但是RSA数字签名算法存在着因计算方法本身同构造成签名易被伪造和计算时间长的弱点,因此实际对文件签名前，需要对消息做MD5变换。MD5函数是一种单向散列函数，它将任意长度的消息压缩成128位的消息摘要。应用MD5的单向性（即给定散列值,计算消息很难）和抗碰撞性(即给定消息M，要找到另一消息M’并满足两者的散列值很难)，可以实现信息的完整性检验。另外该函数的设计不基于任何假设和密码体制而直接构造，执行的速度快，是一种被广泛认可的单向散列算法。三、RSA算法的实现RSA算法的实现分为：生成密钥，加密，解密。1数据结构RSA密码系统的安全性依赖于大数分解的难度，一般建议用户选择的素数p和q至少为100位，则n=pq是至少为200位的十进制数。因此实现RSA算法有必要定义大数的数据结构如图一所示。密钥生成，加密和解密涉及到一些大数的基本运算。定义大数的基本运算库，包括加、减、乘、除、取模运算等，其中最重要的模乘运算和模幂运算。模幂算法是加密解密的核心算法。计算模幂的一种有效算法是“平方-乘”方法，通过对指数的二进制化来实现。8过程如图1：Proceduremodmultbegintypedefstruct{unsignedlongintbn[MAX_LENGTH];unsignedintsize;}BigNum图２大数的数据结构Z=1fori=l-1downto0do:beginZ=Z2modn;ifbi=1thenZ=Z*xmodn;endend图一2密钥的生成2.1RSA公钥和私钥的结构定义根据文档PKCS#1定义RSA公钥和私钥分别如图2和图3。理论上讲，RSA私钥只需包括解密模数和解密指数。但是为加快RSA解密计算的效率，采用中国剩余定理算法，因此RSA私钥包含p,q,dmod(p-1),dmod(q-1),q-1modp,其中p,q为大素数,dmod(p-1),dmod(q-1),q-1modp由计算过程生成。2.2生成密钥步骤生成RSA密钥需完成下列步骤：(1)选择e的值为3或者25537;(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,满足de1(mod(n));(6)计算dmod(p-1),dmod(q-1);(7)计算q-1modp;(8)将n,e放入RSA公钥；将n,e,dmod(p-1),dmod(q-1)q-1modp放入RSA私钥。随机素数的产生可分为两个模块：2.2.1随机数的产生随机数不仅用于密钥生成,也用作公钥加密时的填充字符。它必须具有足够的随机性，以防止破译者掌握随机数的规律性后重现密钥的配制过程或者探测到加密块中的明文。因为在计算机上不可能产生真正的随机数，实际采用周期大于2256位的伪随机序列发生器。实现过程为：(1)记录相邻两次敲击键盘的时间间隔，直到不再需要随机事件。(2)做MD5计算，直到不再需要伪随机数。2.2.2素数的产生typedefstruct{unsignedintbits;/*公钥n的位数*/unsignedcharmodulus[MAX_RSA_LEN];/*公钥n*/unsignedcharexponent[MAX_RSA_LEN];/*公钥e*/}RSA_PUBLIC_KEY;图３RSA公钥typedefstruct{unsignedintbits;/*公钥n的长度*/unsignedcharmodulus[MAX_RSA_LEN];/*公钥n*/unsignedcharpublicExponent[MAX_RSA_LEN];/*公钥e*/unsignedcharexponent[MAX_RSA_LEN];/*私钥d*/unsignedcharprime[2][MAX_RSA_LEN];/*两个素数因子*/unsignedcharprimeExponent[2][MAX_RSA_PRIME_LEN];unsignedcharcoefficient[MAX_RSA_PRIME_LEN];}RSA_PRIVATE_KEY;图4RSA私钥对随机数作素性检测，若通过则为素数；否则增加一个步长后再做素性检测，直到找出素数。素性检测采用Fermat测试。这个算法的理论依据是费尔马小定理：如果m是一个素数，且a不是m的倍数，那么根据费尔马小定理有：am-1=1(modm)。实际应用时：am-1=1(modm)am=a(modm)a=am(modm)，因此对于整数m，只需计算am(modm)，再将结果与a比较，如果两者相同，则m为素数。选取a=2，则a一定不会是任何素数的倍数。3加密过程加密规则为：Ek(x)=xbmodn，xZn加密过程的输入为：明文数据D，模数n,加密指数e（公钥加密）或解密指数d（私钥加密）。输出为密文。D的长度不超过[log2n]-11，以确保转换为PKCS格式时，填充串的数目不为0。(1)格式化明文。采用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。(2)明文由字符型数据转换成整型数据。(3)RSA计算。为整数加密块x作模幂运算：y=x^cmodn，0=yn，其中y为密文，公钥加密时，c为公钥加密指数e；私钥加密时，c为私钥加密指数d。(4)密文由整型数据转换成字符型数据。4解密过程解密规则为Dk(x)=ycmodn,yZn，Zn为整数集合,x为密文。解密过程的输入为：密文ED；模数n；加密指数e（公钥解密）或解密指数d（私钥解密），结果为明文。(1)密文整型化。(2)RSA计算。对密文做模幂运算：x=y^cmodn,0=xn.，其中x为明文。(3)此时明文为整型数据，转换为ASCII型数据，得到PKCS格式的明文。(4)从PKCS格式明文中分离出原明文。从PKCS格式分离明文的过程也是检查数据完整性的过程。若出现以下问题则解密失败：不能清楚的分割；填充字符少于64位或与ＢＴ所注明的类型不匹配;ＢＴ与实际操作类型不符。四、RSA数字签名算法的实现RSA数字签名算法，包括签名算法和验证签名算法。首先用MD5算法对信息作散列计算。签名的过程需用户的私钥，验证过程需用户的公钥。A用签名算法将字符串形式的消息处理成签名；B用验证签名算法验证签名是否是A对消息的签名，确认是A发送的消息；消息没有被攥改过；A一定发送过消息。1签名算法签名算法包括三步：消息摘要计算，RSA加密。(1)消息摘要计算。消息在签名前首先通过MD5计算，生成128位的消息摘要digest。(2)对摘要作RSA计算。用加密算法，采用签名者的私钥加密消息摘要，得到加密后的字符串。加密算法中使用的加密块为01类型。2验证签名算法验证签名算法包括两步：RSA解密得签名者的消息摘要，验证者对原消息计算摘要，比较两个消息摘要。验证签名的过程输入为消息，签名者的公钥，签名；输出为验证的结果，即是否是正确的签名。(1)RSA解密。签名实际是加密的字符串。用3.5所述的解密算法，采用签名者的公钥对这个加密的字符串解密。解密的结果应为128位的消息摘要。在解密过程中，若出现得到的加密块的类型不是01，则解密失败。签名不正确。(2)消息摘要计算和比较。验证者对消息用MD5算法重新计算，得到验证者自己的消息摘要。验证者比较解密得到的消息摘要和自己的消息摘要，如果两者相同，则验证成功，可以确认消息的完整性及签名确实为签名者的；否则，验证失败。五、RSA算法的时间复杂性RSA算法的时间复杂性取决于它所设计的几个基本运算的时间复杂性。密钥生成过程时间主要是生成随机素数的时间及计算公钥和私钥的模乘法的时间。生成随机素数的时间在于完成对随机大数的Fermat测试的时间，Fermat测试的时间复杂度为O((log2n)3)，n所测试的整数。模乘法的计算方法采取先计算两个数的乘积，再取模n，时间复杂性为O((log2n)2)。RSA加密解密计算的时间主要是模幂运算的时间，即形式为xcmodn的函数的运算时间。模幂算法采取平方乘算法，设l是c的长度，则计算xcmodn至多需要2l次模乘法，因为l[log2n]+1,所以模幂运算能在时间O((log2n)3)内完成。因此，RSA的加密和解密均可在多项