小绿锁背后的RSA算法

如今，我们上网时常能见到一把小绿锁，这便是多数浏览器对于HTTPS连接的标识。即HTTP over SSL，它代表着我们与网站服务器的连接是经过SSL加密的。然而，不论何种加密算法，总是有加密和解密的过程，其中最关键的就是密钥交换过程，如果在交换过程中这个密钥被窃取，之后的加密便毫无意义。那么SSL是如何确保即使我们的网络流量被抓取的情况下也能保证加密信息安全的呢？这就是我们今天要说的非对称加密算法，而最早的非对称加密算法便是从RSA开始。

算法介绍

RSA算法是1977年由麻省理工学院的Ron Rivest、Adi Shamir、Leonard Adleman三人共同提出的，RSA名字便取自他们三人的姓氏。在RSA算法之前，密钥交换主要采用预共享密钥的方式，例如我们生活中连接WPA2-PSK的Wi-Fi便是采用预共享密钥的方式，它的特点是需要通信双方事先共享密钥才能加密，也称为对称加密。而RSA采用的是非对称加密，需要生成两组密钥，称为公钥(Public Key)和私钥(Private Key)，这两组密钥是成对的。使用公钥加密的数据可以被私钥解密，使用私钥加密的数据可以被公钥解密。

在了解这个算法前，你需要了解以下数学知识，我假设读者已经具备初中数学知识。
对于OIer，你如果了解过扩展欧几里得、欧拉函数、费马小定理，你可以跳过这一段，而且你看这个会很轻松。

0. 最大公因数：
   Greatest Common Divisor，即两个数的因数集合的交集中最大的数，通常我们使用gcd表示。
   例如a、b的最大公因数记为gcd(a,b)

1. 互质关系：
   对于两个数a,b，当a与b的公因数仅有1，我们称为互质，即gcd(a,b) = 1

2. 欧拉函数：
   欧拉函数简写为\varphi(x)，即为小于等于x的正整数中与x互质的数的个数，特殊地：\varphi(1) = 1
   特别地：对于一个质数，\varphi(x) = x - 1（显然质数与小于等于它的其它正整数都互质）
   例如x=7，在[1,6]区间中，1、2、3、4、5、6与7互质，因此\varphi(7)=6=7-1

   同时，欧拉函数在数论上属于积函数，积函数的定义是：
   若f(x)是一个积函数x与y互质，则f(x*y) = f(x) * f(y)
   例如x=6，在[1,5]区间中，1、5与6互质，因此\varphi(6)=2，同时也有\varphi(6) = \varphi(2)*\varphi(3) = 1*2 = 2

3. 模运算：
   记为a % b或a \mod b，即a / b之后的余数

   例如：

   5 \mod 2 = 1
5 \mod 10 = 5
9 \mod 8 = 1

4. 乘法逆元：
   对于a * b \equiv 1 \pmod {p}
   我们称为a是b关于p的模逆元
   而同样，b也是a关于p的摸逆元
   若我们求a关于p的逆元，若a与p不互质，则逆元不存在。
   求解方法：扩展欧几里得算法，费马小定理（稍后介绍）

5. 费马小定理
   假如a是一个整数，p是一个质数，那么a^p-a是p的倍数，可以表示为

   a^p \equiv a \pmod{p}

   证明留给读者自己学习

6. 欧拉定理
   当n与a互质时，有：a^{\varphi(n)} \equiv 1 \pmod n

   • 当n为质数时，证明非常显然，费马小定理的式子两边同除a即可。
   • 当n不为质数时证明留给读者自行学习。

好了，我们开始介绍RSA算法的工作过程。

1. 服务器随机产生两个大质数p、q。

2. 计算N = p *q

3. 计算T = \varphi(p) * \varphi(q)
   由于p、q都是质数，根据前文所述的质数的欧拉函数的积函数性质以及质数的性质，得到：
   T= \varphi(N) = \varphi(p) * \varphi(q) = (p-1)*(q-1)

4. 之后，选择一个正整数E作为公钥（Public Key），使gcd(E,T)=1，即E、T互质。

5. 通过乘法逆元算出私钥（Private Key），记为D，使(E * D ) \equiv 1 \pmod{T}。

此时，我们便得到了公钥和私钥，公钥为二元组(E,N)，私钥为二元组(D,N)。

在RSA中，我们需要扔掉p、q、T以确保安全。

我们定义一个明文M，它对应的密文是C。

加密：M^E \equiv C \pmod{N}
解密：C^D \equiv M \pmod{N}

计算过程实践

我们选择两个大质数p=37,q=23，那么N=p*q=851，T=(p-1)*(q-1)=36*22=792。

之后，我们选择E=5，便得到了公钥(5,851)。我们通过欧拉定理计算E关于T的逆元D作为私钥，对于数字较大的情况，推荐使用扩展欧几里得算法计算，过程如下：

\varphi(792) = 240

D = 5^{(\varphi(792)-1)} \equiv 317 \pmod{792}

得到私钥(317,851)。

假设我们有个待加密数据M=7，计算得：

C = 7^5 \equiv 638 \pmod{851}

此时我们便完成了加密过程。

那么，如何解密呢？

如前文所述，我们使用私钥进行解密。

638^{317} \equiv 7 \pmod{851}

此时，便得到了原来的密文M。

这样，只要确保Private Key不被盗取，便只有求N的质因数的方法来求解p、q得到私钥，但当这个N线性增长的时候，求质因数算法的时间是成指数增长的，目前数学上尚未找到多项式时间内求质因数的方法。因此，只要这个生成N的p、q足够大，基本是没有可能被破解出来的。

正确性证明

1. 当M与N互质时：
   由于E * D \equiv 1 \pmod{\varphi(N)}

   则E * D = 1 + k * \varphi(N)，其中k是我们所拟的一个未知数。

   代入M^{E*D} \equiv M \pmod{N}，得到：

   M * {M^{\varphi(N)}}^k \equiv M \pmod{N}

   根据欧拉定理，有：M^{\varphi(N)} \equiv 1 \pmod{N}

   所以得到({M^{\varphi(N)}})^k \equiv 1 \pmod{N}

   代入原式即可得证。

2. 当M与N不互质时：
   显然N = p * q，我们不妨假设他们的公因子是p。
   那么可以令M = k_1 * p。
   那么有M ^ {E*D} = {(k_1 * p)}^{E*D} \equiv 0 \equiv M \pmod{p}
   同时也有M^{E*D} = M^{(E*D-1)} * M
   根据费马小定理，由(E * D ) \equiv 1 \pmod{(p-1)*(q-1)}，有E*D - 1 = k_2 * (q - 1)，代入得：
   M^{(E*D-1)} * M = ({M^{(q-1)}})^{k_2} * M \equiv 1^{k_2} * M \equiv M \pmod{q}
   得证。

非对称加密的应用

看到这里你一定会有一个疑问，RSA算法计算起来如此繁琐，那SSL加密得有多慢啊。并且只保证了客户端向服务器发送的数据是加密的，服务器用Private Key加密的数据有Public Key的人都能获取，那加密还有什么用呢？

其实不然，SSL的建立连接过程是这样的：

1. 客户端随机一个加密密钥K（通常不用RSA了）
2. 客户端连接服务器，获得服务器的Public Key
3. 用服务器的Public Key加密密钥K，发送给服务器
4. 服务器通过自己的Private Key解密得到密钥K，之后便使用这个密钥加密的其它加密算法进行通信。

除了传输密钥交换之外，RSA算法在数字证书上也有广泛的应用。我们可以思考一个问题，尽管这么加密让我们与服务器的连接难以被窃听，但是我们到服务器的连接中间要是流量被重定向，如果与攻击者伪造的服务器进行密钥交换，那么再安全的加密也无济于事了。

其实不然，现在的操作系统和浏览器都会预置一些证书颁发机构(CA)的公钥，而我们访问https网页的时候，服务器在握手阶段也会把它自己的证书以及它与我们操作系统信任的CA之间的中间CA发送给我们，只要确保操作系统内置的CA在签发证书时相对安全，那么我们到服务器的连接也将是相对安全的。

感谢POJ 2447，带我复习了扩展欧几里得顺便了解了多年以来感兴趣的RSA算法原理。