在《Hello，密码学：第二部分，对称密码算法》中讲述了对称密码的概念，以及DES和AES两种经典的对称密码算法原理。既然有对称密码的说法，自然也就有非对称密码，也叫做公钥密码算法。对称密码和非对称密码两种算法的本质区别在于，加密密钥和解密密钥是否相同：
- 对称密码的加解密密钥相同，用密钥A加密，也用密钥B解密。
- 公钥密码的加解密密钥不同，用密钥A加密，而用密钥B解密。
非对称密码的爱心小锁
一、公钥密码产生的初衷
公钥密码产生的初衷就是为了解决 密钥配送 的问题。
Alice 给远方的 Bob 写了一封情意慢慢的信，并使用强悍的 AES-256 进行了加密，但她很快就意识到，光加密内容不行，必须要想一个安全的方法将加密密钥告诉 Bob，如果将密钥也通过网络发送，很可能被技术高手+偷窥癖的 Eve 窃听到。
既要发送密钥，又不能发送密钥，这就是对称密码算法下的“密钥配送问题”。
解决密钥配送问题可能有这样几种方法：
- 通过事先约定的共享密钥解决
- 通过密钥分配中心解决
- 通过公钥密码解决
方法一： 事先约定的共享密钥
这种方法比较高效，但有局限性：
- 只适用于较近的距离。也就是不必通过不信任的网络就能通信的情况，比如办公室内的同事之间，完全可以面对面传递一下密钥。一旦距离较远，无法面对面交互，就出现了问题。
- 只适用于小规模使用。即使距离较近，但如果通信人数众多，比如一个公司有 1000 人，每个员工都可以和另外 999 个人进行加密通信，每个人都需要 999 个密钥，整个公司需要的密钥数量为 1000 × 999 ÷ 2 = 499500 个密钥，这显然不现实。
方法二：密钥分配中心
与方法一不同，密钥不再由通信个体来保存，而由密钥分配中心（KDC）负责统一的管理和分配。双方需要加密通信时，由 KDC 生成一个用于本次通信的通信密钥交由双方，通信双方只要与 KDC 事先共享密钥即可。这样就大大减少密钥的存储和管理问题。
因此，KDC 涉及两类密钥：
- 身份密钥：代表通信个体身份的密钥，好比工卡。企业有 1000 个员工，KDC 中就保存 1000 个身份密钥，人来人往，身份密钥也随之发生变化。
- 通信密钥：也叫做会话密钥，仅在一个通信会话过程中有效。
领略下 KDC 的过程：
- KDC 事先保存了 Alice 和 Bob 的身份密钥，分别记为 iKey-Alice 和 iKey-Bob，i 是 identity 的意思；
- Alice 向 KDC 发出要与 Bob 通信的请求；
- KDC 生成一个通信密钥，记为 cKey，c 是 communication 的意思；
- KDC 从数据库中调取 Alice 和 Bob 的身份密钥，用 iKey-Alice 对 cKey 进行加密后发送给Alice，用iKey-Bob 对 cKey 加密后发送给 Bob；
- Alice 使用 iKey-Alice 解密出 cKey 后，并使用 cKey 对信息进行加密后发送给 Bob；
- Bob 使用 iKey-Bob 解密出 cKey 后，并使用 cKey 对来自 Alice 的加密信息进行解密；
- 本次会话结束后，Alice 和 Bob 按照公司要求，在本地删除本次使用通信密钥 cKey。
KDC 通过中心化的手段，确实能够有效的解决方法一的密钥管理和分配问题，安全性也还不错。但也存在两个显著的问题：
- 性能问题：由于所有的加密通信，都要和 KDC 发生交互，KDC 的负荷会随着通信会话的增加而陡增，一旦瘫痪，整个组织的加密通信都将瘫痪。
- 安全问题：KDC 也是软件，也存在漏洞，黑客 Mallory 可能直接对 KDC 下手。一旦 KDC 的密钥数据库被破解，整个组织的加密通信都将被破译。
方法三：公钥密码
使用公钥密码，加密密钥和解密密钥不同，只要拥有加密密钥，所有人都能进行加密，但只有拥有解密密钥的人才能进行解密。于是就出现了这个过程：
- 信息接收者事先将加密密钥通过普通途径发送给信息发送者即可，不必担心加密密钥被窃听；
- 信息发送者使用加密密钥对信息进行加密并发送给信息接收者；
- 信息接收者使用解密密钥对加密信息进行解密。
密钥配送的问题天然被解决了。当然，解密密钥丢失而导致信息泄密，这不属于密钥配送的问题。
下面，再详细看下这个过程。
二、公钥密码的基本流程
公钥密码流程的核心，可以用如下四句话来概述：
- 发送者只需要加密密钥
- 接收者只需要解密密钥
- 解密密钥须妥善保管，不能被窃听者获取
- 加密密钥无所谓，被窃听者获取也没关系
既然加密密钥是公开的，因此也叫做 “公钥（Public Key）”。
既然解密密钥是私有的，因此也叫做 “私钥（Private Key）。
公钥和私钥是一一对应的，称为 “密钥对”，他们好比相互纠缠的量子对，彼此之间通过严密的数学计算关系进行关联，不能分别单独生成。
在公钥密码体系下，再看看 Alice 如何同 Bob 进行通信。
公钥密码体系的通信
在公钥密码体系下，通信过程是由 Bob 开始启动的：
- Bob 生成公私钥对，妥善保管私钥；
- Bob 将公钥发送给 Alice，公钥被 Eve 窃听也没关系；
- Alice 使用 Bob 的公钥对消息进行加密；
- Alice 将加密后的消息发送给 Bob，密文被 Eve 截取也没关系；
- Bob 使用私钥对密文进行解密。
过程看起来非常简单，但为什么即使公钥被窃取也没有关系？这就涉及了上文提到的严密的数学计算关系了。如果上一篇文章对称密钥的 DES 和 AES 算法进行概述，下面一节也会对公钥体系的数学原理进行简要说明。
三、RSA算法背后的数学原理
自从 Diffie 和 Hellman 在1976年提出公钥密码的设计思想后，1978年，Ron Rivest、Adi Shamir 和 Reonard Adleman 共同发表了一种公钥密码算法，就是大名鼎鼎的 RSA，这也是当今公钥密码算法事实上的标准。其实，公钥密码算法还包括ElGamal、Rabin、椭圆曲线等多种算法，这一节主要讲述 RSA 算法的基本数学原理。
- RSA 加密公式：密文 = 明文 ^ E mod N
- RSA 解密公式：明文 = 密文 ^ D mod N
- RSA 公钥：{E, N}
- RSA 私钥：{D, N}
一堆符号，解释下，E 代表 Encryption，D 代表 Decryption，N 代表 Number。
从公式种能够看出来，RSA的加解密数学公式非常简单（即非常美妙）。RSA 最复杂的并非加解密运算，而是如何生成密钥对，这和对称密钥算法是不太一样的。而所谓的严密的数学计算关系，就是指 E 和 D 不是随便选择的。
RSA加密和解密
RSA的核心问题：生成密钥对
密钥对的生成，是 RSA 最核心的问题，RSA 的美妙与奥秘也藏在这里面。
- 求 N
- 求 L（L是生成密钥对过程种一个关键的中间变量）
- 求 E
- 求 D
接下来是一点点数学介绍了！
1. 求N
求 N 公式：N = p × q
其中，p 和 q 是两个质数，而且应该是很大又不是极大的质数。如果太小的话，密码就容易被破解；如果极大的话，计算时间就会很长。比如 512 比特的长度（155 位的十进制数字）就比较合适。
这样的质数是如何找出来的呢？需要通过 “伪随机数生成器（PRNG）” 进行生成，然后再判断其是否为质数。如果不是，就需要重新生成，重新判断。
判断一个数是否为质数，并不是看其能不能分解质因数，而是通过数学的判断方法来完成，比如费马测试和米勒·拉宾测试等。（描述复杂数学算法的念头还是算了吧）
2. 求L
求 L 公式：L = lcm(p-1, q-1)
lcm 代表 “最小公倍数（least common multiple）” 。注意，L 在加解密时都不需要，仅出现在生成密钥对的过程中。
3. 求E
E 要满足两个条件：
1）1 < E < L
2）gcd(E,L) = 1
gcd 代表 “最大公约数（greatest common divisor）”。gcd(E,L) = 1 就代表 “E 和 L 的最大公约数为1，也就是说，E 和 L 互质”。
L 在第二步已经计算出来，而为了找到满足条件的 E，第二次用到 “伪随机数生成器（PRNG）”，在 1 和 L 之间生成 E 的候选，判断其是否满足 “gcd(E,L) = 1” 的条件。
可以使用“欧几里得辗转相除法”计算最大公约数。（描述复杂数学算法的念头还是算了吧）
经过前三步，已经能够得到密钥对种的 “公钥：{E, N}” 了。
4. 求D
D 要满足两个条件：
1）1 < D < L
2）E × D mod L = 1
只要 D 满足上面的两个条件，使用 {E, N} 进行加密的报文，就能够使用 {D, N} 进行解密。
"E × D mod L = 1" 在数学上的表述方式为：在以 L 为模的世界中，E 和 D 互为倒数。我们平时说的乘法中的倒数（比如 3 和 1/3），只是 L 为 1 的特殊情况。
至此，N、L、E、D 都已经计算出来，再整理一下
| 求解目标 | 计算公式 |
|---|---|
| 求 N | N = p × q （p 和 q 都是用 “伪随机数生成器（PRNG）” 生成的大质数） |
| 求 L | L = lcm(p-1, q-1)（lcm 代表计算最小公倍数） |
| 求 E | E 要满足两个条件： 1 < E < L，以及 gcd(E,L) = 1（gcd 代表计算最大公约数），即 E 和 L互质 |
| 求 D | D 要满足两个条件：1 < D < L，以及 E × D mod L = 1 |
RSA密钥对
RSA 模拟实践
模拟实践的过程包括两部分，第一部分是生成密钥对，第二部分是对数据进行加解密。为了方便计算，都使用了较小的数字。
第一部分：生成密钥对
1. 求N
准备两个质数，p = 5，q = 7，N = 5 × 7 = 35
2. 求L
L = lcm(p-1, q-1) = lcm (4, 6) = 12
3. 求E
gcd(E, L) = 1，即 E 和 L 互质，而且 1 < E < L，满足条件的 E 有多个备选：5、7、11，选择最小的 5 即可。于是，公钥 = {E, N} = {5, 35}
4. 求D
E × D mod L = 1，即 5 × D mod 12 = 1，满足条件的 D 也有多个备选：5、17、41，选择 17 作为 D（如果选择 5 恰好公私钥一致了，这样不太直观），于是，私钥 = {D, N} = {17, 35}
至此，我们得到了公私钥对：
- 公钥 = {5, 35}
- 私钥 = {17, 35}
第二部分：模拟加解密
明文我们也使用一个比较小的数字 -- 4，利用 RSA 的加密公式：
密文 = 明文 ^ E mod N = 4 ^ 5 mod 35 = 9
明文 = 密文 ^ D mod N = 9 ^ 17 mod 35 = 4
尼玛，好大啊
从这个模拟的小例子能够看出，即使我们用了很小的数字，计算的中间结果也是超级大。如果再加上伪随机数生成器生成一个数字，判断其是否为质数等，这个过程想想脑仁儿就疼。还好，现代芯片技术，让计算机有了足够的运算速度。然而，相对于普通的逻辑运算，这类数学运算仍然是相当缓慢的。这也是一些非对称密码卡/套件中，很关键的性能规格就是密钥对的生成速度
网上搜索到的某密码卡性能参数
四、针对 RSA 的攻击
公钥密码体系中，用公钥加密，用私钥解密，公钥公开，私钥隐藏。因此：
- 黑客能够拿到的信息：1）密文；2）公钥（即 E 和 N）
- 黑客无法拿到的信息：1）明文；2）私钥（即 D 和 N）；3）中间计算过程的信息（即 p、q、L）。当然，私钥中的 N 其实能够拿到，和明文的 N 是一样的。
攻击方式一：直接破解明文
加密公式为：密文 = 明文 ^ E mod N
破译的过程就是对该公式进行逆运算。由于除了对明文进行幂次运算外，还加上了“模运算”，因此在数学上，该逆运算就不再是简单的对数问题，而是求离散对数问题，目前已经在数学领域达成共识，尚未发现求离散对数的高效算法。
攻击方式二：通过暴力破解求 D
暴力破解的本质就是逐个尝试。当前主流的 RSA 算法中，使用的 p 和 q 都是 1024 位以上，这样 N 的长度就是 2048 位以上。而 E 和 D 的长度和 N 差不多，因此要找出 D，就需要进行 2048 位以上的暴力破解。即使上文那个简单的例子，算出（蒙出） “9 ^ D mod 35 = 4” 中的 D 也要好久吧。
攻击方式三：通过 E 和 N 求出 D
因为 E 和 N 是已知的，而 D 和 E 在数学上又紧密相关（通过中间数 L），能否通过一种反向的算法来求解 D 呢？
- E × D mod L = 1
- L = lcm(p-1, q-1)
从这个地方能够看出，p 和 q 是极为关键的，这两个数字不泄密，几乎无法通过公式反向计算出 D。也就是说，对于 RSA 算法，质数 p 和 q 绝不能被黑客获取，否则等价于交出私钥。
既然不能靠抢，N = p × q，N是已知的，能不能通过 “质因数分解” 来推导 p 和 q 呢？或者说，一旦找到一种高效的 “质因数分解” 算法，就能够破解 RSA 算法了。
幸运的是，这和上述的“离散对数求解”一样，当下在数学上还没有找到这种算法，当然，也无法证明“质因数分解”是否真的是一个困难问题。因此只能靠硬算，只是当前的算力无法在可现实的时间内完成。这也是很多人都提到过的，“量子时代来临，当前的加密体系就会崩溃”，从算力的角度看，或许如此吧。
既不能抢，也不能算，能不能猜呢？也就是通过 “推测 p 和 q 进行破解”。
p 和 q 是通过 PRNG（伪随机数生成器）生成的，于是，又一个关键因素，就是采用的伪随机数生成器算法要足够随机。
随机数对于密码学极为重要，后面会专门写一篇笔记。
攻击方式四：中间人攻击（最常见的 RSA 攻击手段）
前三种攻击方式，都是基于 “硬碰硬” 的思路，而 “中间人攻击” 则换了一种迂回的思路，不去尝试破解密码算法，而是欺骗通信双方，从而获取明文。具体来说，就是：主动攻击者 Mallory 混入发送者和接收者之间，面对发送者伪装成接收者，面对接收者伪装成发送者。
中间人攻击
这个过程可以重复多次。需要注意的是，中间人攻击方式不仅能够针对 RSA，还可以针对任何公钥密码。能够看到，整个过程中，公钥密码并没有被破译，密码体系也在正常运转，但机密性却出现了问题，即 Alice 和 Bob 之间失去了机密性，却在 Alice 和 Mallory 以及 Mallory 和 Bob 之间保持了机密性。即使公钥密码强度再强大 N 倍也无济于事。也就是说，仅仅依靠密码算法本身，无法防御中间人攻击。
而能够抵御中间人攻击的，就需要用到密码工具箱的另一种武器 -- 认证。在下面一篇笔记中，就将涉及这个话题。
好了，以上就是公钥密码的基本知识了。
五、混合密码体系
公钥密码体系能够完美的解决对称密码体系中 “密钥配送” 这个关键问题，但是抛开 “中间人攻击” 问题不谈，公钥密码自己也有个严重的问题：
公钥密码处理速度远远低于对称密码。不仅体现在密钥对的生成上，也体现在加解密运算处理上。
因此，在实际应用场景下，往往会将对称密码和公钥密码的优势相结合，构建一个 “混合密码体系”。简单来说：首先用相对高效的对称密码对消息进行加密，保证消息的机密性；然后用公钥密码加密对称密码的密钥，保证密钥的机密性。
下面是混合密码体系的加解密流程图。整个体系分为左右两个部分：左半部分加密会话密钥的过程，右半部分是加密原始消息的过程。原始消息一般较长，使用对称密码算法会比较高效；会话密钥一般比较短（十几个到几十个字节），即使公钥密码算法运算效率较低，对会话密钥的加解密处理也不会非常耗时。
著名的密码软件 PGP、SSL/TLS、视频监控公共联网安全建设规范（GB35114） 等应用，都运用了混合密码系统。
1. 混合密码体系-加密流程
混合密码体系-加密流程
2. 混合密码体系-解密流程
混合密码体系-解密流程
好了，以上就是公钥密码算法的全部内容了，拖更了很久，以后还要更加勤奋一些。
为了避免被傻啦吧唧的审核机器人处理，后面就不再附漂亮姑娘的照片（也是为了你们的健康），改成我的摄影作品，希望不要对收视率产生影响，虽然很多小伙儿就是冲着姑娘来的。
就从喀纳斯之旅开始吧。
喀纳斯-月亮湾
网友评论