RSA加密

因为机房电脑感染病毒的缘故，在访问很多使用HTTPS的网站时浏览器都会提示证书错误。然而大多数人都选择忽略这样的安全警告，甚至认为某些可以在传输不加密的情况下访问使用HSTS的网站的浏览器“好用”。于是在算导上对RSA的介绍的基础上，我又了解了一下基于RSA的证书系统和SSL/TLS协议，写了这么一篇东西。
先不要去管RSA和证书系统的原理，直接来看具体通信时的情况。

Scene Ⅰ

某年某月某日，jyt想要对rxd说“Orz528！”。
由于jyt和rxd在教室里上课，而且他们的位置隔了很远，所以需要hzq来转达。

jyt对hzq说：Orz528！
hzq对rxd说：Orz528！

看起来完全没有问题！那么再来一次。

Scene Ⅱ
某年某月某日，jyt又想对rxd说“Orz528！”，这次同样需要hzq来转达，然而这天hzq吃了ff的西瓜，于是……

jyt对hzq说：Orz528！
hzq对rxd说：Orz528！

下课后，hzq对wyx说：jyt对rxd说“Orz528！”。

这就不对了。。。为了解决通信被中间人窃听的问题，一种方法是使用对称加密算法。
也就是说，能使用一把密钥，把明文变成看起来没有意义的密文，且仅能使用同一把密钥，把密文变成原来的明文。

Scene Ⅲ

jyt发现wyx很不开心，但他还是想和rxd说话。

jyt通过hzq对rxd说：我现在告诉你xxx算法加密的信息，密码是aaa，信息是bbb（使用aaa加密）。

然而由于现在hzq已经恢复了一点神智。
于是他细细品味了jyt的话，用jyt说的密码和加密算法解密了jyt说的话，发现他说的是“Orz528！”。
结果wyx更加不高兴了。

显然，对称加密算法由于需要明文提供密钥，只要中间人知道你的加密算法和提供密钥的方式，就可以轻松解密信息。
那么现在就需要引入一个神奇的东西——非对称加密算法。它使用一对而不是一把密钥，由其中一把密钥加密的信息仅能使用对应的另一把密钥解密。一般情况下，一把密钥公开，称为“公钥”，另一把保密，称为“私钥”。它的具体实现在最后介绍。

Scene Ⅳ

jyt坚持认为Orz528有助于加RP。

rxd使用神犇的力量生成了公钥aaa和私钥bbb。
rxd通过hzq对jyt说：我使用xxx算法，公钥是aaa。
jyt通过hzq对rxd说：ccc。（使用公钥aaa加密）
rxd用私钥bbb解密，发现jyt说的是“Orz528！”。

hzq记下了他们说的所有话，然而他发现并不能使用公钥aaa去解密信息ccc。

这样看起来就非常对了，然而这样的机制并不够完善。

Scene Ⅴ

rxd通过hzq对jyt说：我使用xxx算法，公钥是aaa。
hzq由于又吃了一次西瓜，于是他直接对rxd说：ddd。（使用公钥aaa加密）
rxd用私钥bbb解密，发现信息是“我求阿”。

于是jyt被阿掉了。

由于没有验证信息的机制，中间人很容易伪装成信息的发送方。
这看起来很麻烦，但实际上利用非对称加密很容易解决。只要信息的发送方把消息$M$
用他的私钥加密得到密文$M^{\prime }$，把二元组$\left(M,M^{\prime }\right)$用接收方的公钥加密并发送。这样接收方用自己的密钥解密后信息后，再用发送方的公钥解密附加的密文$M^{\prime }$，与明文$M$比较，就可以确定发送方的身份是否真实。
对于大量信息，这么做会明显增大运算量及传输内容的大小，所以一般使用某种散列（哈希）算法得到信息的一个散列值（这个值的长度一般是固定且较短的），然后再用发送方的私钥加密散列值，代替上面说的密文$M^{\prime }$
随明文一起发送。
这个随明文一起发送的用私钥加密的散列值称为“签名”。

Scene Ⅵ

rxd通过hzq对jyt说：我使用xxx加密算法，公钥是aaa。
jyt使用神犇的力量生成了公钥ccc和私钥ddd。
jyt通过hzq对rxd说：我使用xxx加密算法，yyy散列算法，公钥是ccc。
jyt又通过hzq对rxd说：eee。（使用私钥ddd加密散列值，使用公钥aaa加密整个信息）

rxd用私钥bbb解密，发现信息是“Orz528，fff”。
rxd用yyy算法得到“Orz528”的散列值，用公钥ccc解密信息fff，发现结果一致，所以确认了发送方是jyt。

然而，其实我们一致忽略了一个很严重的问题。由于在交换公钥前不能进行加密或验证，所以公钥的交换过程没有验证机制，通信双方得到的对方公钥其实是不可靠的。

Scene Ⅶ

rxd通过hzq对jyt说：我使用xxx加密算法，公钥是aaa。
hzq使用比利的力量生成了公钥eee和私钥fff。
hzq对rxd说：我使用xxx加密算法，yyy散列算法，公钥是eee。
hzq又对rxd说：ggg。（使用私钥fff加密散列值，使用公钥aaa加密整个信息）

rxd用私钥bbb解密，发现信息是“我求阿，hhh”。
rxd用yyy算法得到“我求阿”的散列值，用公钥eee解密信息hhh，发现结果一致。
rxd以为验证了发送方的身份，于是，jyt又被阿掉了。

现在就需要使用证书系统了。
证书是由某个“权威”的证书颁发机构（CA，Certificate Authority）颁发，用于保证信息发送方的公钥及相关信息可信的东西。
证书包含的信息大概是这样的：我是aaa，我保证公钥bbb是属于ccc的，我给这个证书的签名是ddd，我签名使用的非对称加密算法是eee，散列算法是fff，此证书在ggg时过期。
eee是对证书包含的信息的签名。这样，只要知道证书颁发者的公钥，就可以确认证书使用者的公钥。
那么问题来了，怎么知道证书颁发者的公钥呢？用证书呀。。。
如果有另一个确认了公钥的机构发布一个证书，证明机构aaa的公钥，就可以确认当前证书使用者的公钥。
也就是说各个证书颁发者的权威性由它的上层颁发者来确认，这样形成一个森林的结构。树的根是根证书，叶子是由真正的信息传输双方使用的终端证书，其余结点是中间证书。其中根证书是自签名的，也就是说它的颁发者（aaa）和使用者（ccc）是相同的，签名（ddd）使用的私钥就是证书中包含的公钥（bbb）对应的私钥。
这样的话只要通过其他方法确认少数根证书的可靠性，就可以确认整个证书系统中所有证书的可靠性。
至于确认根证书的方法，在我看来其实并不是非常可靠。具体做法是，根证书颁发机构向各个操作系统提供商通过交易来证明自己很可靠，然后操作系统提供商就把它的自签名证书集成到系统的根证书存储中。中间证书颁发机构则向根证书颁发机构和操作系统提供商通过交易来证明自己很可靠，让根证书颁发机构给它一份证书证明它的公钥，并把这份证书集成到操作系统的中间证书存储中。（注意这里的XX证书颁发机构的断句应是“XX 证书颁发机构”而不是“XX证书 颁发机构”）。
这里中间证书存在的作用似乎不是很明确，但实际上它意义重大。它的作用是确保根证书颁发机构的私钥不会因为频繁地颁发证书或者交易泄露（泄露了那就真的是出大事了。。。），同时由通过各级中间证书形成的信任链来保证终端证书被根证书信任。
所以现在通信过程是这样的。

Scene Ⅷ

rxd通过hzq对jyt说：我的证书是xxx。
jyt通过hzq对rxd说：我的证书是yyy。
jyt验证了rxd提供的证书，确认了rxd的公钥为aaa。
rxd验证了jyt提供的证书，确认了jyt的公钥ccc。

rxd和jyt开始通过非对称加密提供的加密功能亲切交谈。（比如Orz528）

然而，这对于B/S或C/S结构的通信并不适用，在服务器上部署证书当然没问题，但总不能在每个客户端上都向CA申请证书吧，这样不但及其麻烦，而且花费巨大（申请证书当然是要钱的）。
而且非对称加密算法一般情况下相对于对称加密算法运算量要大得多。
这时对称加密的优势就体现出来了，所以Internet上常见的通信加密机制是先在非对称加密的保护下协商对称加密协议及其密钥，再通过对称加密通信。

Scene Ⅸ

rxd由于太强了，现在作为服务器。

jyt通过hzq对rxd说：我要跟你通信。
rxd通过hzq对jyt说：我的证书是xxx。
jyt验证了rxd提供的证书，确认了rxd的公钥为aaa。
jyt通过hzq对rxd说：我给你一段随机数据ccc，我要验证你的身份。
rxd通过hzq对jyt说：ddd。（用私钥bbb加密后的ccc）
jyt用公钥aaa解密ddd，发现结果为ccc，确认了发送方是rxd。
jyt通过hzq对rxd说：eee。（用公钥aaa加密）
rxd用私钥bbb解密eee，发现结果是“我们接下来用yyy加密算法通信，密码是fff”。（yyy是对称加密算法，fff由jyt随机生成）
rxd和jyt开始通过对称加密算法提供的加密功能亲切交谈。（比如Orz528）

这实际上已经与SSL/TLS协议非常相似了。SSL是一个提供在传输层上的安全机制的协议，它最初由网景公司提出，标准化后的名称为TLS。它的应用及其广泛，如HTTPS（HTTP over SSL，使用SSL的HTTP协议，用于网页浏览），FTPS（使用SSL的FTP协议，用于文件传输）等。几乎所有需要安全的Internet通信的地方都用到了它。

SSL/TLS的关键是可靠的非对称加密算法。目前，最常用的非对称加密算法就是RSA。它的原理非常简单，只要有基础的数论知识就能理解。 设公钥为$P$
，私钥为$S$，它们能进行的加密/解密运算用函数表示，分别为$P\left(\right)$和$S\left(\right)$。
那么一个非对称加密系统要求，对于任意信息$M$
，满足$M=P\left(S\left(M\right)\right)=S\left(P\left(M\right)\right)$，即$P\left(\right)$和$S\left(\right)$互为反函数。同时除了拥有密钥的人以外，没有人可以在可行的时间内进行密钥对应的加密/解密运算。
这里假设$M$
为一个整数，实际上任何信息都可以编码成一个二进制整数。
在RSA加密系统中，密钥对的生成方法为：
随机选取两个满足$p\ne q$
的大质数$p$和$q$。（生成质数可以随机生成整数并用Miller Rabin算法验证，可以证明这样做的期望尝试次数不会很大），令$n=pq$。
选取一个与$\varphi \left(n\right)$
互质的小奇数$e$（易知$\varphi \left(n\right)=pq\left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right)=\left(p-1\right)\left(q-1\right)$）。
令$d\equiv e^{-1}\left(\mathrm{mod}\varphi \left(n\right)\right)$
，即$e$对于模$\varphi \left(n\right)$的乘法逆元。
取公钥$P=\left(e,n\right)$
，私钥$S=\left(d,n\right)$，公钥对应的函数$P\left(M\right)=M^{e}modn$，私钥对应的函数$S\left(M\right)=M^{d}modn$。
显然$P\left(S\left(M\right)\right)=S\left(P\left(M\right)\right)=M^{ed}modn$
。
因为$e$
和$d$是对模$\varphi \left(n\right)=\left(p-1\right)\left(q-1\right)$的乘法逆元，所以对某个整数$k$有$ed=1+k\varphi \left(n\right)=1+k\left(p-1\right)\left(q-1\right)$。
那么根据欧拉定理可以得到，对于$M\equiv ̸0\left(\mathrm{mod}p\right)$
，有$\begin{array}{cc}{M}^{ed}& \equiv M^{\varphi \left(n\right)}\\ & \equiv M^{1+k\left(p-1\right)\left(q-1\right)}\\ & \equiv M\cdot {\left(M^{p-1}\right)}^{k\left(q-1\right)}\\ & \equiv M\cdot 1^{k\left(q-1\right)}\\ & \equiv M\left(\mathrm{mod}n\right)\end{array}$ 对于$M\equiv 0\left(\mathrm{mod}p\right)$
，有$M^{ed}\equiv M\equiv 0\left(\mathrm{mod}n\right)$。
同理，可以得到$M^{ed}\equiv M\left(\mathrm{mod}q\right)$
。
根据中国剩余定理，可以得到$M^{ed}\equiv M\left(\mathrm{mod}n\right)$
。
这样就证明了RSA的正确性。而RSA的安全性则主要来源于对大整数进行因式分解的困难性。
如果能够快速地对作为公钥的一部分的$n$
进行因式分解得到$p$和$q$，就可以用与创建密钥对时相同的方法快速地得到公钥对应的私钥。
也就是说，如果能快速地进行大整数的因式分解，就能打破RSA加密系统。
同时，经过多年的研究，也没有人找到比因式分解更好的破解RSA加密系统的方法，所以可以认为：如果不能快速地进行因式分解，就不能打破RSA加密系统。
然而，以目前的技术来看，对于足够大的整数进行因式分解可以说是不可能的。
实际上，使用512bit和768bit密钥的RSA加密系统已经被破解了。在实践中，一般使用1024bit或2048bit的$n$倍来确保安全性.