简单总结《改变未来的九大算法》（二）——公钥与数字签名

公钥加密（密钥交换）

1. 为什么要用公钥加密？

因为网络上的数据在传播时会经过很多设备，这些设备基本是不可控的，如：你在广州想把数据通过公共网络发到北京，你没办法控制数据会经过哪些运营商、哪些交换机甚至是服务器。（富二代有钱拉专线，然后雇佣保镖沿路保护设备，这种当我没说。。）
这里的“暗号”指的就是公钥。

暗号类似这样一种思想：比如小明和小红的暗号是9，小明想加密发送数字3给小红但，这时小明可以发送“我发送的数字比暗号小6”，小红拿到消息后，通过暗号9减去6得到真正的数字3。这就完成了一次公钥加密传输。

2. 怎样沟通公钥（暗号）？（或者说：如何公开建立暗号？）

还是通过讲段子来说明比较合适，一下子摆公式不道德。
如图所示，这里讲述了一个如何秘制属于小明和小红的专属颜料。

颜料混合大法固然有理，但计算机不懂呀，它只懂加减乘除（准确地说是加法），对于颜料一窍不通。而且，这里首要解决的是，如何用计算机实现这样的秘方：颜料混合后无法提纯。

3. 如何解决“混合颜料无法提纯问题”？

因为计算机只会做一件事——计算，所以“混合颜料”得转换为计算，所以这个问题在数学上的描述就是：
让几个数字做一些运算得出结果，其中一些运算的数字是公开的，一些是私有的，但不能根据结果推导出进行所有运算的数字。

这里不得不祭出两个数学工具：钟算（其实就是取余运算）、幂函数。
为什么是钟算？
还是用例子来解释比较形象

X % A = B — C

这里用（私有数字，只有自己知道的数字）对A（公开数字）取余数，得到B（中间结果，不公开）和C（公开数字），这样的话是无法“直接”通过C和A去推算X的，这里说的“直接”指的是比较高效的运算，暴力遍历的方式除外。

为什么要用幂函数？
这个算法最有意思的地方，期待下面见证奇迹的时刻吧。

如图所示，钟算+幂函数 就这样奇妙地化解了单向运算的难题。

以上方法，可以说是一种密钥交换，在实际经常使用的公钥加密场景是将公钥加密后传输，如HTTPS。其中用到的著名算法有RSA和DH，前者是本书提及的，后者是更优方案。

数字签名

书中的这块知识是与公钥加密分开的，但我觉得两者联系比较紧密，可以放一起总结。

假设Pauky和Glowry有一个欠条，在大家的见证下，Glowry用自己的锁将欠条锁在保险箱并由Pauky保管，Glowry和公证人都拥有开锁的钥匙。Pauky需要Glowry还钱时，他会找来公证人和Glowry一块开箱，要求Glowry兑现欠条。

• 锁和钥匙是用来证明箱子里的东西是Glowry确认的（即平时说的签字画押，也是签名的意思）；
• 需要公证人的原因是避免Glowry反悔，不提供钥匙或提供假钥匙；

这个验证欠条真实性的环节用计算机实现，就是数字签名。
它需要实现一种能够将原始数据用锁加密，然后用对应的钥匙解开原始数据的方法。咱们用数字的方法描述一下这个过程。（以下将直接展示这个过程的数学过程，因为只知道存在这样的奇妙数学现象）

如上图所示，只要生成了锁（3）和钥匙（7），并且锁是私有的，钥匙和钟（22）公开给校验者使用，可以让消息（4）经过加密（20），最终用钥匙解出原始消息（4）。这样就解决了上述需要加密和解密消息的问题。现实中，钥匙公开后将交给权威机构保管和分发，避免其被伪造。

安全性

现实中使用数千位的钟来保证算法防止被破解，但不是说完全不能被破解，只是现有条件下无法高效被破解，比如在数千位的钟长度下需要数万亿年的计算时间，这就相当于“无法”破解了！

非对称加密

除了数字签名，这个算法还有另外一个用处，还是继续用上面的例子来直观感受下。

神奇了，这个过程反过来也是可以实现加密的。相当于钥匙（7）加密了消息（4）后，能用锁（3）解出原始消息（4）。

密钥如何生成？

一般常用的方法有RSA、DH，这里先借用大佬的RSA讲解
（这里挖个坑，后面来总结一下生成的原理）

实际应用场景

实际的应用场景有HTTPs，它前期的加密流程如下：

这里的公钥A和私钥a，指的就是上述的算法中的钥匙（别忘记还有：钟）和锁。

最后说一下

公钥加密、数字签名、非对称加密，感觉像是一脉相承。它们也共同承担了许许多多互联网的安全重担，本人觉得是本书里对计算机发展奉献最大的算法了！

敬请期待下篇 纠错码