4.5 RSA算法

继Merkle-Hellman背包算法之后，出现了第一个成熟的公开密钥算法RSA。1977年由Ron Rivest，Adi Shamir和Len Adleman发明，并于1978年公布。它是一种分组加密算法，明文和密文在0～n-1之间，n是一个正整数。RSA算法是应用最广泛的公钥密码算法，只在美国申请了专利，且已于2000年9月到期。

4.5.1 RSA算法描述

4.5.1.1 设计RSA算法的思路

大素数相乘和因子分解可以被看成一个单向函数，也就是说根据大素数p和q计算出N=pq，比已知N，把N分解为N=pq容易得多。我们是否能够基于这样一个观察构造一个公钥算法？

设p和q为两个大素数，N = pq，考虑这样的乘法群Z*N =Z*pq，它包含1到pq -1之间所有与p和q都互素的整数，那么这个群的大小为φ（pq）= （p-1）（q-1）= N -（p + q）+1，对于任意x∈ Z* pq，根据Euler定理有x（p-1）（q-1）= 1mod N。

因为有限域GF（p）上的幂运算用软件实现的时候有高效的算法，我们希望用求幂运算来加密。令e是一个整数，1<e<（p-1）（q-1），那么当e满足什么条件时，m→me是乘法群 Z* pq上的一一映射？答案是当e与（p-1）（q-1）互素时，m→me是乘法群 Z* pq上的一一映射。因为gcd（e，（p-1）（q-1））=1，那么e存在一个模（p-1）（q-1）的乘法逆元d，ed=1+k（p-1）（q-1）。令ci=mie

4.5.1.2 对RSA算法的描述

RSA算法对明文以分组为单位进行加密，每个二进制分组的值均小于n，也就是说分组的大小必须小于或等于「log2n」位，实际应用中，分组的大小为k位，2k<n≤2k+1，公开密钥为{e,n}，其中n是两素数p和q的乘积，推荐p和q等长，e为与（p-1）（q-1）互素的数，私有密钥为{d,p,q}，d=e-1mod（p-1）（q-1），对于明文分组m和密文分组c，加解密过程如下。

加密：c=me mod n

解密：m=cd mod n=（m e）d mod n=med mod n=m mod n

RSA算法的实现步骤如下：

（1）用户B产生两个大素数p和q，p≠q；

（2）B计算n=pq，n的Euler函数φ（n）=（p-1）（q-1）；

（3）B选择随机数e，（0<e<φ（n）），使gcd（e，φ（n））=1；

（4）B使用扩展的Euclid算法计算d≡e-1mod φ（n）；

（5）选定算法的公钥：KU={e，n}，私钥：KR={d，p，q}。

选择好公私钥后，RSA算法的加解密步骤如下：

将明文划分成块，使得每个明文报文m的长度k满足0<m<n。

加密m时，计算c=me（mod n）

解密c时，计算m=cd（mod n）

选择好公私钥后，RSA算法的签名步骤如下：

将明文划分成块，使得每个明文报文m的长度k满足0<m<n。

签名m时，计算y=Sig（m）=md（mod n）。

验证签名时，计算m′=y e（mod n），判断其是否与原来的m相同。

下面通过一个例子说明用RSA算法加密与解密的过程。

（1）选取素数p和q，p=47，q=61，p和q是秘密的。

（2）计算n=pq=2867，n是公开的。

（3）φ（n）=（p-1）（q-1）=46×60=2760，φ（n）是秘密的。

（4）选取公开密钥e，使gcd（e，φ（n））=1，e=1223是公开的。

（5）计算秘密密钥d，使ed≡1mod（φ（n）），d=167是秘密的。

这里，明文=“RSA ALGORITHM”，n=2867，e=1223，d=167，把明文用两位十进制数字表示，空白=00，A=01，B=02，…，Z=26，再将要保护的明文信息分成一连串十进制数的数据块，每个数据块的值不超过n-1，结果如下：

1819010001120715180920081300

利用加密变换公式C=me mod n，分别对每一个数据块进行加密产生相应的密文块，如C= 18191223 mod 2867 = 2756。

e=1223=210+27+26+22+21+20=1024+128+64+4+2+1，表示为二进制串就是10011000111。密文C=18191223（mod2867）

= 18191024 · 1819128· 181964· 18194· 18192· 18191（mod 2867）

= 2756

类似地，可以得到整个明文对应的密文序列：

2756200105420669234704081815

4.5.2 RSA实现中的问题

4.5.2.1 如何计算me mod n

RSA的加密和解密都要计算某整数的模n整数次幂，如果先计算出幂再对n取模，中间结果会非常大。利用模算术的下述性质进行模幂运算，可对中间结果取模，避免以上问题。

（a×b）mod n=[（a mod n）×（b mod n）]mod n

此外还应考虑到幂运算的效率，以a16为例，若直接计算，需要进行15次乘法：a16=a×a ×a×a×a×a×a×a×a×a×a×a×a×a×a×a

如果重复计算每个中间结果的平方，a2，a4，a8，a16，那么只需要4=log216次乘法就可以计算出a16。

更一般地，“平方乘”算法是一种计算模幂的有效算法。如果要计算me，将e的二进制表示为ekek-1…e0，则，因此

这样就可以构造一个计算c=me mod n的算法，伪代码如下：

                              c=1；
                              for i=k downto 0 do
                                c=c2 mod n
                                if ei=1 then c=mc mod n
                              return c

4.5.2.2 密钥产生

要实现RSA算法，还存在一个比较难的问题，就是密钥的产生。这包括两个问题：如何找到足够大的素数p和q？如何选择e或d，并计算另外一个？

首先考虑如何挑选大素数p和q。为了防止攻击者通过穷举方法找到p和q，p和q必须是足够大的素数。目前没有产生任意大素数的有用技术，通常的做法是随机选取一个需要数量级的奇数，并检验这个数是否是素数。直接判断一个整数是否为素数是困难的，传统使用试除法判断一个数是否是素数，即依次用比该数平方根小的素数进行除法运算，这种方法只对小数有操作性。还有一种办法是根据所有素数满足的特性进行统计素性检测，但是一些伪素数也满足此特性。

素性检测有很多种方法，一般是采用概率性的检验方法，即通过检验的奇数将以一定的概率是素数，当设置检验的次数足够多时，得到的“素数”不是真正的素数可能性会相当小。当然检验需要的时间也相应地变长。实际中应用最多的是Miller-Rabin算法。它基于这样一个数学命题：如果p是奇素数，则方程x2≡1mod p只有两个解x≡ ±1mod p。这是因为

x2≡1mod p⇒p|（x2-1）⇒p|（x+1）（x-1）⇒p|（x+1），或者p|（x-1）

⇒x+1=kp，或者x-1=jp，k，j是整数

⇒x=kp-1，或者x=jp+1

⇒x≡1mod p，或者x≡-1mod p

若方程x2≡1mod p存在的解不是x≡ ±1，则p不是素数。

函数WITNESS（a，n）判定n是否为素数，a是某些小于n的整数，当返回值为TRUE表示n一定不是素数，返回值为FALSE表示n可能是素数。随机选择a<n，计算s次，如果每次都返回FALSE，则这时 n 是素数的概率为（1-1/2s）。令 bk bk-1…b0为（n-1）的二进制表示，WITNESS（a，n）的伪代码如下：

      d = 1；
      for i = k downto 0 do
        x = d；
        d = d2mod n
        if d=1 and x≠1 and x≠n-1 then return TRUE；//（x2？≡1mod n）
        if bi=1 then d=ad mod n； //（an-1 mod n）
      if d ≠ 1 then return TRUE；
      return FALSE；

选取素数的一般过程如下：

（1）随机选取一个奇素数n。

（2）随机选取一个整数a<n。

（3）执行概率素数判定测试[如：用WITNESS（a,n）]。如果n没有通过检验，舍弃n并转到步骤1。

（4）如果n通过了足够多次的检验，接受n，转到步骤2。

Miller-Rabin算法又称为“强伪素数检测”（Strong Pseudo-Prime test），和其他大部分素性检测算法一样，它检验一个给定整数是否素数的过程，是涉及一个挑选出来的整数 n 和一个随机选取的整数a的计算过程，如果n没有通过这一次检验，那么n肯定不是素数，如果n通过了多次检验，那么有相当大的信心相信n是一个素数。随机选取大约需要用ln n/2的次数，如要找一个2200数量级的素数，需要测试ln2200/2=70次。因为只是在生成密钥对时才用到，慢一点还可忍受。

确定素数p和q以后，只需选取e，满足gcd（e,φ（n））=1，使用扩展Euclid算法计算d= e-1 mod φ（n）。

4.5.3 RSA的安全性

RSA的安全性基于加密函数ek（x）= xe（mod n）是一个单向函数，如图4.4所示，所以对攻击的人来说求逆计算不可行。而Bob能解密的陷门是分解n = pq，求得φ （n）= （p-1）（q-1），从而用欧几里得算法解出解密私钥d。攻破RSA与分解n是多项式等价的。然而，这个猜想至今没有给出可信的证明。

对RSA的攻击可能有如下三种形式：

● 强力攻击（穷举法）：尝试所有可能的私有密钥。

● 数学分析攻击：有多种数学方法，实质都是试图分解两个素数的乘积。

● 对RSA实现的攻击。

若要使RSA安全，p与q必为足够大的素数，使分析者没有办法在多项式时间内将n分解出来。建议选择p和q大约是100位的十进制素数。国际数字签名标准ISO/IEC9796中规定n的长度为512比特。至1996年，建议使用768bit的模n。现在建议模n为是一个1024比特或更高比特的数。为了抵抗现有的整数分解算法，对RSA模n的素因子p和q还有如下要求：

（1）|p-q|很大，通常p和q的长度相同。

（2）p-1和q-1分别含有大素因子p1和q1。

（3）p1-1和q1-1分别含有大素因子p2和q2。

（4）p+1和q+1分别含有大素因子p3和q3。

满足以上条件的素数被称为强素数。

表4.3给出了因子分解的最新进展。开始人们使用十进制位数描述被分解的数，如表4.3（a）中的RSA-129表示129位的十进制数，后来使用二进制位数描述被分解的数，如表4.3（b）中的RSA-640表示二进制长度为640比特的数。

4.5.4 对RSA实现的攻击方法

对RSA的具体实现存在一些攻击方法，但不是针对基本算法的，而是针对协议的。主要有以下几种方式：对RSA的选择密文攻击、对RSA的公共模攻击、对RSA的小加密指数攻击、对RSA的小解密指数攻击和计时攻击。

4.5.4.1 对RSA的选择密文攻击

这里给出对RSA的选择密文攻击的三个例子。

例1，E监听A的通信，收集由A的公开密钥加密的密文c，E想知道消息的明文m，使m=cd mod n。

它首先选择随机数r，使r<n，然后用A的公开密钥e计算：

x=r e mod n y = xc mod n

t = r-1 mod n

如果x=r e mod n，则r=xd mod n。现在E让A对y签名，即解密y，A向E发送u=y d mod n，而E计算：

tu mod n=r-1yd mod n=r-1xdcd mod n=cd mod n=m

则E得到了m。

例2，Mallory选取任意一个数值x，计算y=xe mod n。然后，他计算m=ym′mod n，并将m发给Trent，并让Trent对它签名。Trent回送md mod n，现在Mallory计算

（md mod n）·（x-1mod n）=（（ym′）d mod n）·（x-1mod n）=（xe m′）d mod n·（x-1mod n）

=（xed（m′）d）mod n ·（x-1mod n）=x（m′）d x-1mod n=（m′）d mod n

它等于对m′的签名。

例3，E想产生A对m3签名。他产生两个消息m1和m2，满足m3=m1m2（mod n），如果E能让A分别对m1和m2签名，则可以计算：

注意，不要用RSA对陌生人的随机文件签名，签名前先使用一个散列函数，就可以防止这种攻击。

4.5.4.2 对RSA的公共模攻击

一种可能的RSA实现方法是给每个人相同的n，但指数d和e不同。这导致的问题是，如果相同的消息曾用两个不同的指数加密，而这两个指数是互素的，则明文可以不用任何一个解密密钥来恢复。

令m为明文消息，两个加密密钥为e1，e2，两个密文消息为c1，c2

c1= 1me mod n

c2= 2me mod n

由于e1和e2互素，所以可以用扩展Euclid算法找到r，s使re1 + se2 = 1，这样，。

为了防止这种攻击，注意，不要让一群用户共享一个模n。

4.5.4.3 对RSA的小加/解密指数攻击

为了提高加密速度，通常取e为特定的小整数，如EDI国际标准中规定e = 216 +1，ISO/IEC9796中甚至允许取e=3。这时加密速度一般比解密速度快10倍以上。e=216+1优于e=3之处在于它能够抵抗对RSA的小加密指数攻击。

使用一个较小的e值，进行RSA加密会很快，但也不安全。如果用相同e值的不同公开密钥加密e(e +1)/2个线性相关的消息，则系统是可破的。如果有少于这些的消息或消息不相关，则无问题。比如，消息为mj，使用同样的指数e，模数分别为q1，q2，…，qs（两两互素），则密文为，，…，，根据中国剩余定理，可以计算出来，对于较小的e，可以解出mj。

例如，对同一消息m，使用相同的小加密指数e=3加密，同时发给三个的不同的人，这三个人的模数分别为q1，q2，q3，则有：

c1=m3mod q1

c2 = m3 mod q2

c3 = m3 mod q3

利用中国剩余定理可以解下列方程组：

x≡c1 mod q1

x≡c2 mod q2

x≡c3 mod q3

得到x=m3，再通过求x的三次方根可得到m。

对于这一攻击的解决办法是加密前将消息与随机值混合，并保证m与n有相同的长度。

此外，使用较小的d会产生穷尽解密攻击的可能，注意，应选择一个大的d值。

4.5.4.4 计时攻击

计时攻击是一种全新的攻击手段，属于选择密文的攻击，也适用于攻击其他公钥算法，发明于20世纪90年代，是基于加密程序运行时间的攻击。在RSA的加解密过程中涉及到计算m=cd，d=dkdk-1…d0（二进制表示）。

                                m = 1；
                                for i = k downto 0 do
                                  m = m2 mod n
                                  if di=1 then  m=cm mod n
                                return m

观察到若di=1，执行m=cm mod n，否则不执行，有少数的c和m值，上述模乘速度很慢，若攻击者观察到解密算法的执行速度很慢，则可以认为该位是1，否则是0，从左到右逐个确定di。

对抗计时攻击的对策有三种，第一种是使用恒定的幂运算时间，虽然简单，但会降低算法性能。第二种是加一个随机延迟，但是仍然可被攻击者攻击成功。第三种办法称为盲化，在执行幂运算之前先将密文乘上一个随机数。

盲化的m=cd mod n 的实现如下：

（1）产生一个0到n-1之间的随机数r。

（2）计算c′=c（re）mod n，其中e是公开指数。

（3）用通常的RSA实现计算m′=（c′）d mod n。

（4）计算m=m′r-1mod n。

可以证明结果是正确的，盲化操作增加的开销是2% ～10%。