rsa算法基本流程及签名流程.doc

1、RSA算法及其实现RSA加密算法是目前应用最广泛的公钥加密算法，特别适用于通过Internet传送的数据，常用于数字签名和密钥交换，被国际上的一些标准化组织ISO、ITU、SWIFT作为标准来采用。1.1 RSA算法的基本原理独立地选取两个大素数pq(保密)。计算n=pq(公开)，其中n为欧拉函数值n=p-1q-1(保密)。随机选取一整数e，满足1en，gcde,n=1，e是公开的密钥即公钥。用Euclid算法计算d，d=e-1modn，d是保密的密钥即私钥。加密变换：对明文mZn，密文为c=Ekm=memod n。解密变换：对密文cZn，明文为m=Dkc=cdmod n。其中，加密变换、解密变换两步也可以改为用d加密，e解密，就变成签名和验证过程。1.2 RSA算法的实现步骤1素数的产生对随机数作素性检测,若通过则为素数，否则增加一个步长后再做素性检测，直到找出素数。素性检测采用Fermat测试。这个算法的理论依据是费尔马小定理：如果m是一个素数，且a不是m的倍数，那么根据费尔马小定理am-1=1 modm。实际应用am-1=1 modmam=a modma=am modm，此对于整数m，需计算am modm，再将结果与a比较。如果两者相同，则m为素数。选取a=2,则a一定不会是任何素数的倍数。步骤2随机数的产生随机数不仅用于密钥生成，也用作公钥加密时的填充字符。它必须具有足够的随机性，以防止破译者掌握随机数的规律后重现密钥的配制过程或者探测到加密块中的明文。因为在计算机上不可能产生真正的随机数，实际采用周期大于2256位的伪随机序列发生器。步骤3密钥的生成(1)选择e的值为2623883或者94475891;(2)随机生成大素数p,直到gcd(e, p-1)=1;(3)随机生成不同于p的大素数q,直到gcd(e,q-1)=1;(4)计算n=pq,(n)=(p-1)(q-1);(5)计算d, d=e-1modn;(6)计算dmod(p-1),dmod(q-1);(7)计算(q-1)modp;(8)将(e,n) 放入RSA公钥;将n,e,dmod(p-1),dmod(q-1),(q-1)modp放入RSA私钥。步骤4加密利用RSA加密，第一步需要将明文数字化。假定A、B统一明文编码方式为空格=00，A=01,B=02,C=03,Z=26, 则明文数字化HI为08、09;然后把明文M分成等长数据块m1,m2,m3,mi，块长为s，其中2sn，s尽可能大。加密规则为：Ekx=xemodn，xZn，x为明文。加密过程的输入为：明文M，模数n，公钥e或私钥d，输出为密文。M的长度不超过log2n-11，以确保转换为PKCS格式时，填充串的数目不为0。(1)格式化明文。采用PKCS格式：EB=00BTPS00M。其中，BT表示块的类型，PS为填充串，M为明文数据，开头为0确保EB长度大于k。对公钥加密BT=02，对私钥解密BT=01。当BT=02时，PS为非0随机数；当BT=01，PS值为FF。(2)明文由字符型数据转换成整型数据。(3)RSA计算：为整数加密块x作模幂运算：y=xcmodn，0y n，其中y为密文。公钥加密时，c为公钥e；私钥加密(数字签名)时，c为私钥d。(4)密文由整型数据转换成字符型数据。步骤5解密解密规则为：Dkx=ycmodn，yZn，y为密文。解密过程的输入为：密文C；模数n；公钥e或私钥d，输出为明文。(1)密文由字符型数据转换成整型数据。(2)RSA解密计算，对密文做模幂运算：x=ycmodn，0x n,其中x为明文。(3)此时明文为整型数据，转换为ASCII型数据，得到PKCS格式的明文。(4)从PKCS格式明文中分离出原明文。从PKCS格式分离明文的过程也是检查数据完整性的过程。若出现以下问题则解密失败：不能清楚地分割；填充字符少于64位或与BT所注明的类型不匹配；BT与实际操作类型不符。2、RSA数字签名算法及实现RSA数字签名算法，包括签名算法和验证签名算法。首先用MD5算法对信息作散列计算。签名的过程需要用户的私钥，验证过程需要用户的公钥。A用签名算法将字符串形式的消息处理成签名；B用验证签名算法验证签名是否是A对消息的签名，确认是A发送的消息；消息没有被篡改过；A一定发送过消息。2.1签名算法步骤1消息摘要计算消息在签名前首先通过MD5计算，生成128位的消息摘要digest。步骤2对摘要作RSA计算用加密算法，采用签名者的私钥加密消息摘要，得到加密后的字符串。加密算法中使用的加密块为01类型。2.2验证签名算法验证签名算法包括两步：RSA解密得签名者的消息摘要，验证者对原消息计算摘要，比较两个消息摘要。验证签名的过程输入为消息，签名者的公钥、签名；输出为验证的结果，即是否是正确的签名。步骤1解密签名实际是加密的字符串。用前面所述的解密算法，采用签名者的公钥对这个加密的字符串解密。解密的结果应为128位的消息摘要。在解密过程中，若得到的加密块的类型不是01，则解密失败。签名不