本章涉及知识点
1、对称加密的概念
2、非对称加密的概念
3、RSA安全性的奥秘
4、RSA秘钥的生成算法
5、RSA明文的加密算法
6、RSA密文的解密算法
7、窃听者破解秘钥的可能性
8、python编程模拟信息发送者的行为
9、 python编程模拟信息接收者的行为
10、python编程模拟窃听者破解秘钥的行为
11、结果分析
12、后记
一、对称加密的概念
对称加密又称单秘钥加密，它的定义是：通信双方通过同一把秘钥对信息进行加密和解密
其工作流程如下
其中m表示要传递的信息明文，c表示对m加密后的密文，e表示秘钥，f(e)函数表示对m加密的运算法则，g(e)函数表示对c解密的运算法则（g(e)是f(e)的逆运算函数）
对称加密的优点为
（1）加密解密都用同一把秘钥，算法是公开的，计算量较单一，加密速度快，加密效率高
（2）适合需要加密大量数据的场景
对称加密的缺点为
（1）虽然f(e)和g(e)函数可以设计的非常复杂，但是通信之前双方需要同步保存秘钥e，而同步过程发生在共有环境
（2）如果窃听者在同步e的过程中，在共有环境劫持到e，就可以通过大量数据穷举出f(e)的法则从而破解密文c得到明文m
（3）通信双方都保存着e，如果任意一方的e泄露，那么二者的通信将不再安全
在1976年之前几乎所有的加密方法都是对称加密
二、非对称加密的概念
非对称加密又称双秘钥加密，它的定义是：通信双方通过两个秘钥来对信息进行加密和解密，这两个秘钥分别是公开秘钥（公钥）和私有秘钥（私钥），且二者的算法存在某种数学关系，但是这种数学关系无法被传统计算机破解
其工作流程如下
其中public_key表示公钥，private_key表示私钥
非对称加密的优点为：
（1）秘钥分为公钥和私钥，公钥公开传递，而私钥只保存在接收方，安全性更高
（2）通信之前二者无需同比私钥，只需要同步公钥即可
（3）如果窃听者在共有环境劫持到密文c和公钥，但是以传统计算机的能力无法通过已知公钥来破解出私钥（数学上可以证明）
非对称加密的缺点为：
（1）加密解密时间花费较长，速度慢
（2）适合对少量重要数据通信的场景
1977年，麻省理工(MIT)大学的三位数学家根据非对称加密的思想，设计出以他们三个人名字命名的RSA算法，该算法也是至今使用最广泛的非对称加密算法，如军事、银行等
三、RSA安全性的奥秘
RSA算法基于一个非常简单的数论事实：
如果将两个大素数相乘，则乘积计算十分容易；但是如果对这个乘积进行质因式分解，却非常困难！
由于全世界的数学家至今无法用一个多项式来精准的表示素数，也无法证明素数的分布规律，所以RSA算法的安全性就是利用了这个数学事实来设计的
四、RSA秘钥的生成算法
RSA秘钥的生成包括了公钥和私钥的生成，涉及到的数学知识有欧拉函数、互质、模反元素、欧几里得扩展算法、大整数的幂运算取模算法等，这些数学算法我在《RSA加密解密算法—数论基础》文中已经说明
下面我们列出RSA秘钥的生成算法步骤
（1）随机选择两个不相等的素数p和q
（2）计算两个素数的乘积
（3）计算n的欧拉函数φ(n)
（4）随机选择一个正整数e，e满足
其中我们用欧拉定理表示e和φ(n)互质
（5）计算e对于φ(n)的模反元素d
（6）封装公钥和私钥
其中公钥可以在公共网络环境里传递，而私钥由消息接收者私人保存
五、RSA明文的加密算法
假设Sender要发送给Receiver的消息为m，m未加密是明文，而Sender拥有从Receiver生成的公钥(n, e)，则Sender使用该公钥对m进行加密
其中，m必须是整数，且m<n
经过公钥(n, e)加密的密文c，就是Sender要传送给Receiver的消息，且c将暴露在网络公共环境中，可以被第三方窃听
六、RSA密文的解密算法
Receiver接受到从Sender发送到的密文c后，需要对密文c进行解密还原为明文m，而Receiver仅自己拥有生成的私钥(n, d)，则Receiver使用自己的秘钥对c进行解密
至此，Receiver就将密文c还原为明文m
七、窃听者破解秘钥的可能性
下面分析窃听者破解秘钥的可能性，我们知道窃听者可以在共用网络环境里窃听到的数据有
（1）加密后的密文c
（2）公开传递的公钥(n, e)
则问题可以描述为：已知n, e, c，求m?
我们通过逆向过程来推导
（1）由于m需要私钥(n, d)来解密，d未知，问题即转化为求d？
（2）而d又是e和φ(n)的模反元素，φ(n)未知，问题即转化为求φ(n)？
（3）而φ(n)=φ(p) * φ(q) = (p - 1) * (q - 1)，p和q未知，问题即转化为求p和q？
（4）而n = p*q，n是已知的，则问题即转化为求n的质因数分解？
综上所述，只要窃听者能够将n质因数分解为p和q，那么它就可以求出φ(n)，从而求出d，最后用(n, d)来破解出密文c得到明文m
但是，人类目前对于大数的质因式分解非常的困难，其本质就是人类无法用一个精确的多项式来描述素数，导致计算机只能通过穷举筛选法来尝试质因数分解，而当分解的数字n非常大的时候（1024位或者2048位长度），计算机穷举分解的时间可能需要几百年或千年，因此，基于这个数论知识和对素数理论的匮乏，窃听者破解密文c的可能性，从有限的时间上无限接近于0
八、python编程模拟信息发送者的行为
Sender有如下行为：
（1）获取公钥
（2）用公钥对信息明文m加密为密文c，将c公开发送给Receiver
九、python编程模拟信息接收者的行为
Receiver有如下行为：
（1）生成秘钥：公钥+私钥
（2）公开公钥，保存私钥
（3）用自己的私钥对Sender发送的密文c解密
十、python编程模拟窃听者破解秘钥的行为
第三方窃听者有如下行为：
（1）从公共网络上获取公钥和密文
（2）尝试对n进行质因数分解
（3）如果质因数分解成功，则成功解密密文
十一、结果分析
我们来做以下实验：
（1）Receiver生成公钥和私钥
（2）Sender要传送的明文m=123456，用公钥加密后传递密文c
（3）Receiver用私钥解密c，得到m=123456
（4）Hacker尝试破解c
实验结果为：
从结果中可以看到：
（1）Receiver用自己的私钥正确的从密文c解密出了明文m，并且时间效率非常高
（2）Hacker虽然成功的破解了密文c，但在这个实验里我们选取的两个素数p=8887，q=13163非常小，质因数分解n=p*q=116979581都花费了大约43秒，那么在真实环境里p和q的长度都是1024位，在有限的时间内，大数的质因数分解根本不可能
十二、后记
RSA算法的安全性，建立在如下两个方面
（1）从数学的角度：人类没有证明出精准的素数表达式和分布规律
（2）从计算机的角度：传统计算机无法突破其并行计算能力的瓶颈
基于这两个角度，要想破解RSA算法，可以依赖于
（1）证明：哥德巴赫猜想(1+1=2)
（2）量子计算机
但是未来无论人类基于什么理论完全破解RSA算法，银行、军事的加密解密体系算法一定都会提前进行更换
案例代码见：RSA加密解密算法—编程实战
