RSA算法

RSA算法需要以下相关的数学概念：

素数：素数是一个比1大，其因子只有1和它本身，没有其它数可以整除它的数。素数是无限的。例如，2，3，5，7……等。

两个数互为素数：指的是它们除了1之外没有共同的因子。也可以说这两个数的最大公因子是1。例如，4和9，13和27等。

模运算：如A模N运算，它给出了A的余数，余数是从0到N-1的某个整数，这种运算称为模运算。

RSA加密算法的过程如下：

（1）取两个随机大素数p和q（保密）

（2）计算公开的模数r=pq(公开)

（3）计算秘密的欧拉函数j (r) =（p-1）(q-1)（保密），两个素数p和q不再需要，应该丢弃，不要让任何人知道。

（4）随机选取整数e，满足gcd(e, j (r))=1(公开e，加密密钥)

（5）计算d，满足de≡1(mod j (r))(保密d，解密密钥，陷门信息)

（6）将明文x（其值的范围在0到r-1之间）按模为r自乘e次幂以完成加密操作，从而产生密文y（其值也在0到r-1范围内）

y=x^e (mod r)

（7）将密文y按模为r自乘d次幂，完成解密操作

x=y^d (mod r)

下面用一个简单的例子来说明RSA公开密钥密码算法的工作原理。

取两个素数p=11，q=13，p和q的乘积为r=p×q=143，算出秘密的欧拉函数j (r)=(p-1)×(q-1)=120，再选取一个与j (r)=120互质的数，例如e=7，作为公开密钥，e的选择不要求是素数，但不同的e的抗攻击性能力不一样，为安全起见要求选择为素数。对于这个e值，可以算出另一个值d=103，d是私有密钥，满足e×d=1 mod j (r)，其实7×103=721除以120确实余1。欧几里德算法可以迅速地找出给定的两个整数a和b的最大公因数gcd（a，b），并可判断a与b是否互素，因此该算法可用来寻找解密密钥。

120=7×17+1

1=120-7×17 mod 120=120-7×(-120+17) mod 120==120+7×103 mod 120

(n,e) 这组数公开，(n,d)这组数保密。

设想需要发送信息x=85。利用(n,e)=(143,7)计算出加密值：

y= x^e (mod r)=85⁷ mod 143=123

收到密文y=123后，利用 (n,d)=(143,103)计算明文：

x=y^d (mod r) =123¹⁰³mod 143=85

加密信息x（二进制表示）时，首先把x分成等长数据块 x₁ ,x₂,..., x_i ，块长s，其中 2^s ≤ n，s尽可能的大。对应的密文是：

y_i = x_i^e ( mod r )

RSA算法中的难点有以下几点：

（1）大数的运算

上百位大数之间的运算是实现RSA算法的基础，因此程序设计语言本身提供的加减乘除及取模算法都不能使用，否则会产生溢出，必须重新编制算法。在编程中要注意进位和借位，并定义几百位的大数组来存放产生的大数。

（2）素数的产生

Hadamard证明，当X变得很大时，从2到X区间的素数数目π(X)与X/ln(X)的比值趋近于1，即：

如果在2到X之间随机选取一个整数，其为素数的概率大约为1/ln(X)。对于1024位的模数r=pq，p和q将选取为512位的素数。一个随机选取的512位整数为素数的概率大约为1/ln2^512» 1/355。

目前，适用于RSA算法的最实用的素数生成办法是概率测试法。该法的思想是随机产生一个大奇数，然后测试其是否满足一定的条件，如满足，则该大奇数可能是素数，否则是合数，经过充分多次运行该算法，把合数判断为素数的概率可以降低到任何所期望的值以下。如solovay和strassen的简明素性概率检测法。目前也存在多项式时间的确定性算法来判断一个数是否为素数。

（3）高次幂剩余的运算

要计算x^e mod r，因x、e、r都是大数而不能采用先高次幂再求剩余的方法来处理，而要采用平方取模的算法，即每一次平方或相乘后，立即取模运算。设e可表示为：

e = bk 2k + bk-1 2k-1 + ... + bi 2i + ... + b2 22 + b1 2 + b0

那么有如下的计算x^e算法：

Square-and-Multiply(x,e,r)

RSA的安全性在理论上存在一个空白，即不能确切知道它的安全性能如何。我们能够做出的结论是：对RSA的攻击的困难程度不比大数分解更难，因为一旦分解出r的因子p、q，就可以攻破RSA密码体制。对RSA的攻击是否等同于大数分解一直未能得到理论上的证明，因为没能证明破解RSA就一定需要作大数分解。目前，RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。1977年，《科学美国人》杂志悬赏征求分解一个129位十进数(426比特)，直至1994年3月才由Atkins等人在Internet上动用了1600台计算机，前后花了八个月的时间才找出答案。现在，人们已能分解155位（十进制）的大素数。因此，模数n必须选大一些，因具体适用情况而定。

若r=pq被因子分解，则RSA便被击破。

因为若p，q已知，则j (r) =（p-1）(q-1)便可算出。解密密钥d关于e满足：

de≡1(mod j (r) )

故d便也不难求出。因此RSA的安全依赖于因子分解的困难性。目前因子分解数度最快的方法，其时间复杂度为exp(sqrt(ln(n)lnln(n)))。

RSA实验室认为，512比特的r已不够安全。他们建议，现在的个人应用需要用768比特的r，公司要用1024比特的r，极其重要的场合应该用2048比特的r。

总之，随着硬件资源的迅速发展和因数分解算法的不断改进，为保证RSA公开密钥密码体制的安全性，最实际的做法是不断增加模r的位数。

为了安全起见，对p，q还要求：p，q长度差异不大；p-1和q-1有大素数因子；（p-1，q-1）很小。满足这些条件的素数称作安全素数。

其他的安全问题包括：

（1）公共模数攻击。每个人具有相同的r，但有不同的指数e和d，这是不安全的。

（2）低加密指数攻击。如果选择了较低的e值，虽然可以加快计算速度，但存在不安全性。

（3）低解密指数攻击。如果选择了较低的d值，这是不安全的。

（4）选择密文攻击。如A想让T对一个T不愿意签名的消息m’签名，A首先选择一个任意值x，计算y=x^e（mod r），然后要求T对m=ym’签名，A最后计算(m^d mod r)x^-1 mod r =( ym’) ^d x^-1mod r= m’^d mod r。记住不要对别人提交的随机消息进行签名。

RSA的缺点主要有：

（1）产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。

（2）分组长度太大，为保证安全性，n 至少也要 600 bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(Secure Electronic Transaction)协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。

（3）RSA的速度由于进行的都是大数计算，使得RSA最快的情况也比DES慢上100倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。RSA与DES的优缺点正好互补。RSA的密钥很长，加密速度慢，而采用DES，正好弥补了RSA的缺点。即DES用于明文加密，RSA用于DES密钥的加密。由于DES加密速度快，适合加密较长的报文；而RSA可解决DES密钥分配的问题。美国的保密增强邮件（PEM）就是采用了RSA和DES结合的方法，目前已成为E-MAIL保密通信标准。