RSA算法和RSA数字签名算法的实现
摘要 RSA算法是一种公钥密码算法.实现RSA算法包括生成RSA密钥，用
RSA加密规则和解密规则处理数据。RSA数字签名算法利用RSA算法实现数字签名。本文详述了RSA算法的基本原理, RSA加密算法的实现以及如何利用RSA实现数字签名.
关键字 RSA算法, 数字签名, 公开密钥, 私人密钥, 加密, 解密 中图分类号 TP301
一、引言
随着网络技术的飞速发展，信息安全性已成为亟待解决的问题。公钥密码体制中，解密和加密密钥不同，解密和加密可分离，通信双方无须事先交换密钥就可建立起保密通信，较好地解决了传统密码体制在网络通信中出现的问题。另外，随着电子商务的发展，网络上资金的电子交换日益频繁，如何防止信息的伪造和欺骗也成为非常重要的问题。数字签名可以起到身份认证、核准数据完整性的作用。目前关于数字签名的研究主要集中基于公钥密码体制的数字签名。
公钥密码体制的特点是：为每个用户产生一对密钥（PK和ＳＫ）；ＰＫ公开，ＳＫ保密；从ＰＫ推出ＳＫ是很困难的；Ａ、Ｂ双方通信时，Ａ通过任何途径取得Ｂ的公钥，用Ｂ的公钥加密信息。加密后的信息可通过任何不安全信道发送。Ｂ收到密文信息后，用自己私钥解密恢复出明文。
公钥密码体制已成为确保信息的安全性的关键技术。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是素数，de?1 mod ?(n),e为随机整数},
对每一个k=(n,p,q,d,e),
定义加密变换为 Ek(x)=xb mod n，x?Zn;
解密变换为 Dk(x)=ya mod n,y?Zn，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。因为ab?1 mod ?(n)，所以可设ab=t?(n)+1,t是整数且t?1。对于任意的x?Zn，有Dk(Ek(x))?Dk(xb)
?(xb)a?xt?(n)+1?x mod n.因此解密过程是正确的。
2 RSA数字签名算法
RSA数字签名算法的过程为：A对明文m用解密变换作: s? Dk (m)=md mod n,其中d，n为A的私人密钥，只有A才知道它；B收到Ａ的签名后，用A的公钥和加密变换得到明文，因: Ek(s)= Ek(Dk (m))= (md)e mod n,又 de?1 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 数据结构
RSA密码系统的安全性依赖于大数分解的难度，一般建议用户选择的素数p和q至少为100位，则n=pq是至少为200位的十进制数。因此实现RSA算法有必要定义大数的数据结构如图一所示。
密钥生成，加密和解密涉及到一些大数的基本typedef struct 运算。定义大数的基本运算库，包括加、减、{ 乘、除、取模运算等，其中最重要的模乘运算 unsigned long int 和模幂运算。 bn[MAX_LENGTH]; 模幂算法是加密解密的核心算法。计算模幂的 unsigned int size; 一种有效算法是“平方-乘”方法，通过对指数}BigNum 的二进制化来实现。8 图２ 大过程如图1： 数的数据结构 Procedure modmult begin
Z=1
typedef struct { for i=l-1 downto 0 do:
unsigned int bits; /* 公钥n begin
的位数 */ Z=Z 2 mod n;
char if bi=1 then Z=Z*x mod n; unsigned modulus[MAX_RSA_ LEN] ;/*公钥 end
n*/ end
unsigned char 图一
exponent[MAX_RSA_LEN]; /*公钥2 密钥的生成
e*/ 2.1 RSA公钥和私钥的结构定义
根据文档PKCS#1定义RSA公钥和} RSA_PUBLIC_KEY; 私钥分别如图2和图3。理论上讲，RSA 图３ RSA公私钥只需包括解密模数和解密指数。钥 但是为加快RSA解密计算的效率，采用中国剩余定理算法，因此RSA私钥包含p,q,d mod (p-1),d mod (q-1),q-1 mod p,其中p,q为大素数, d mod (p-1), d mod (q-1),q-1 mod p由计算过程生成。
2.2 生成密钥步骤
生成RSA密钥需完成下列步骤： typedef struct { (1) 选择e的值为3或者25537; unsigned int bits; /*公钥n的长 (2) 随机生成大素数p，直到gcd 度*/ (e,p-1)=1; unsigned char 其中gcd(a,b)表示a,b取最大公modulus[MAX_RSA_LEN]; /*公钥n */ 约数 unsigned char (3) 随机生成不同于p的大素数q，publicExponent[MAX_RSA_ LEN]; /*公直到 钥e */ gcd (e,q-1)=1; unsigned char (4) 计算n=pq , ?(n)=(p-1)(q-1); exponent[MAX_RSA_LEN]; /*私钥d*/ (5) 计算d,满足de?1 (mod ?(n)); unsigned char prime[2][MAX_RSA_ (6) 计算d mod (p-1), d mod (q-1); LEN]; /*两个素数因子*/ (7) 计算q-1 mod p; unsigned char (8) 将n,e放入RSA公钥；将n,e,d primeExponent[2][MAX_RSA_PRIME_LE-1
mod (p-1),d mod (q-1) q mod p放N]; 入RSA私钥。 unsigned char 随机素数的产生可分为两个模块： coefficient[MAX_RSA_PRIME_LEN]; } RSA_PRIVATE_KEY; 2.2.1 随机数的产生 图4 RSA私钥 随机数不仅用于密钥生成,也用
作公钥加密时的填充字符。它必须具有足够的随机性，以防止破译者掌握随机数的规律性后重现密钥的配制过程或者探测到加密块中的明文。因为在计算机上不可能产生真正的随机数，实际采用周期大于2256位的伪随机序列发生器。 实现过程为：
(1) 记录相邻两次敲击键盘的时间间隔，直到不再需要随机事件。 (2) 做MD5计算，直到不再需要伪随机数。
2.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，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^c mod n，0 <= y 为密文，公钥加密时，c为公钥加密指数e；私钥加密时，c为私钥加密指数d。 (4) 密文由整型数据转换成字符型数据。 4 解密过程 解密规则为 Dk(x)=yc mod n,y?Zn，Zn为整数集合,x为密文。 解密过程的输入为：密文ED；模数n；加密指数e（公钥解密）或解密指数d（私钥解密），结果为明文。 (1) 密文整型化。 (2) RSA计算。 对密文做模幂运算：x = y^c mod n, 0 <= x < n .，其中x为明文。 (3) 此时明文为整型数据，转换为ASCII型数据，得到PKCS格式的明文。 (4) 从PKCS格式明文中分离出原明文。 从PKCS格式分离明文的过程也是检查 数据完整性的过程。若出现以下问题则解密失败：不能清楚的分割；填充字符 少于64位或与ＢＴ所注明的类型不匹配;ＢＴ与实际操作类型不符。 四、 RSA数字签名算法的实现 RSA数字签名算法，包括签名算法和验证签名算法。首先用MD5算法对信息作散列计算。签名的过程需用户的私钥，验证过程需用户的公钥。A用签名算法将字符串形式的消息处理成签名；B用验证签名算法验证签名是否是A对消息的签名，确认是A发送的消息；消息没有被攥改过；A一定发送过消息。 1 签名算法 签名算法包括三步：消息摘要计算，RSA加密。 (1) 消息摘要计算。 消息在签名前首先通过MD5计算，生成128位的消