RSA算法原理

历史

1976年以前，所有的加密方法都是同一种模式：

（1）甲方选择某一种加密规则，对信息进行加密；（2）乙方使用同一种规则，对信息进行解密。

• 1
• 2

由于加密和解密使用同样规则（简称”密钥”），这被称为”对称加密算法”（Symmetric-key algorithm）。

这种加密模式有一个最大弱点：甲方必须把加密规则告诉乙方，否则无法解密。保存和传递密钥，就成了最头疼的问题。

1976年，两位美国计算机学家Whitfield Diffie 和 Martin Hellman，提出了一种崭新构思，可以在不直接传递密钥的情况下，完成解密。这被称为”Diffie-Hellman密钥交换算法”。这个算法启发了其他科学家。人们认识到，加密和解密可以使用不同的规则，只要这两种规则之间存在某种对应关系即可，这样就避免了直接传递密钥。
这种新的加密模式被称为”非对称加密算法”。

（1）乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。（2）甲方获取乙方的公钥，然后用它对信息加密。（3）乙方得到加密后的信息，用私钥解密。

• 1
• 2
• 3

如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。

1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。从那时直到现在，RSA算法一直是最广为使用的”非对称加密算法”。毫不夸张地说，只要有计算机网络的地方，就有RSA算法。
这种算法非常可靠，密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长RSA密钥是768个二进制位。也就是说，长度超过768位的密钥，还无法破解（至少没人公开宣布）。因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全。

预备知识

互质

如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。比如，15和32没有公因子，所以它们是互质关系。这说明，不是质数也可以构成互质关系。

数和互为素数

任何大于1的整数a能被因式分解为如下唯一形式：
a=p1p2…pl(p1,p2，…，pl为素数）

欧拉函数

在数论中，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler’s totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。

通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数(小于等于1)就是1本身）

欧拉定理

若n,a为正整数，且n,a互质，则:

欧拉定理有一个特殊情况：
假设正整数a与质数p互质，因为质数p的φ(p)等于p-1，则欧拉定理可以写成：
a^(p-1)≡1(mod p)
这就是著名的费马小定理。

模逆元

一整数a对同余n之模逆元是指满足以下公式的整数 b：
ab ≡ 1(mod n)
整数 a 对模数 n 之模逆元存在的充分必要条件是 a 和 n 互素。
（可用欧拉定理证明）
b可通过拓展欧几里得算法算得。

RSA算法原理

我们通过一个例子来理解这个过程：
A 和 B 要通信，他需要生成公钥和私钥，过程如下：

1. 随机选择两个不相等的质数p和q：
   假设A选择了61和53。（实际应用中，这两个质数越大，就越难破解。）

2. 计算p和q的乘积n：
   　　n = 61×53 = 3233
   n的长度就是密钥长度。3233写成二进制是110010100001，一共有12位，所以这个密钥就是12位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。

3. 计算n的欧拉函数φ(n)：
   根据公式：
   　　φ(n) = (p-1)(q-1)
   算出φ(3233)等于60×52，即3120。

4. 随机选择一个整数e，条件是1< e="">< φ(n)，且e与φ(n)="" 互质：="">
   我们在1到3120之间，随机选择了17。（实际应用中，常常选择65537。）

5. 计算e对于φ(n)的模逆元d。
   即需要d满足
   　　ed ≡ 1 (mod φ(n))
   这个式子等价于
   　　ed - 1 = kφ(n)
   于是，求解d，实质上就是对下面这个二元一次方程求解。
   　　ex + φ(n)y = 1
   已知 e=17, φ(n)=3120，
   　　17x + 3120y = 1
   这个方程可以用”扩展欧几里得算法”求解。我们可以算出一组整数解为 (x,y)=(2753,-15)，即 d=2753。

6. 将n和e封装成公钥，n和d封装成私钥：
   在本例中，n=3233，e=17，d=2753，所以公钥就是 (3233,17)，私钥就是（3233, 2753）。

7. 加密和解密
   有了公钥和密钥，就能进行加密和解密了。

（1）加密要用公钥 (n,e)
假设B要向A发送加密信息m，他就要用A的公钥 (n,e) 对m进行加密。这里需要注意，m必须是整数（字符串可以取ascii值或unicode值），且m必须小于n。

所谓”加密”，就是算出下式的c：
　　me ≡ c (mod n)

A的公钥是 (3233, 17)，B的m假设是65，那么可以算出下面的等式：
　　6517 ≡ 2790 (mod 3233)

于是，c等于2790，B就把2790发给了A。

（2）解密要用私钥(n,d)

A拿到B发来的2790以后，就用自己的私钥(3233, 2753) 进行解密。可以证明，下面的等式一定成立：
　　cd ≡ m (mod n)

也就是说，c的d次方除以n的余数为m。现在，c等于2790，私钥是(3233, 2753)，那么，A算出
　　27902753 ≡ 65 (mod 3233)
因此，A知道了B加密前的原文就是65。
至此，”加密–解密”的整个过程全部完成。

运算速度

由于进行的都是大数计算，使得RSA最快的情况也比DES慢上好几倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。RSA的速度比对应同样安全级别的对称密码算法要慢1000倍左右。

比起DES和其它对称算法来说，RSA要慢得多。实际上Bob一般使用一种对称算法来加密他的信息，然后用RSA来加密他的比较短的对称密码，然后将用RSA加密的对称密码和用对称算法加密的消息送给Alice。
这样一来对随机数的要求就更高了，尤其对产生对称密码的要求非常高，因为否则的话可以越过RSA来直接攻击对称密码。

可靠性

回顾上面的密钥生成步骤，一共出现六个数字：

　　p　　q　　n　　φ(n)　　e　　d

• 1
• 2
• 3
• 4
• 5
• 6

这六个数字之中，公钥用到了两个（n和e），其余四个数字都是不公开的。其中最关键的是d，因为n和d组成了私钥，一旦d泄漏，就等于私钥泄漏。

那么，有无可能在已知n和e的情况下，推导出d？
　　（1）ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。
　　（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。
　　（3）n=pq。只有将n因数分解，才能算出p和q。

结论：如果n可以被因数分解，d就可以算出，也就意味着私钥被破解。

可是，大整数的因数分解，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。维基百科这样写道：

　　“对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。
　　
　　假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。

　　只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。”

目前被破解的最长RSA密钥就是768位。

（THE END）