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

作者:杨润炜
日期:2022/1/10 09:27

公钥加密(密钥交换)

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

因为网络上的数据在传播时会经过很多设备,这些设备基本是不可控的,如:你在广州想把数据通过公共网络发到北京,你没办法控制数据会经过哪些运营商、哪些交换机甚至是服务器。(富二代有钱拉专线,然后雇佣保镖沿路保护设备,这种当我没说。。)
这里的“暗号”指的就是公钥。
公钥加密的基本流程
暗号类似这样一种思想:比如小明和小红的暗号是9,小明想加密发送数字3给小红但,这时小明可以发送“我发送的数字比暗号小6”,小红拿到消息后,通过暗号9减去6得到真正的数字3。这就完成了一次公钥加密传输。

2. 怎样沟通公钥(暗号)?(或者说:如何公开建立暗号?)

还是通过讲段子来说明比较合适,一下子摆公式不道德。
如图所示,这里讲述了一个如何秘制属于小明和小红的专属颜料。
颜料混合大法
颜料混合大法固然有理,但计算机不懂呀,它只懂加减乘除(准确地说是加法),对于颜料一窍不通。而且,这里首要解决的是,如何用计算机实现这样的秘方:颜料混合后无法提纯。

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

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

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

X % A = B — C

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

为什么要用幂函数?
这个算法最有意思的地方,期待下面见证奇迹的时刻吧。
简约版公钥
如图所示,钟算+幂函数 就这样奇妙地化解了单向运算的难题。

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

数字签名

书中的这块知识是与公钥加密分开的,但我觉得两者联系比较紧密,可以放一起总结。
欠条版数字签名
假设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,它前期的加密流程如下:
https加密过程
这里的公钥A和私钥a,指的就是上述的算法中的钥匙(别忘记还有:钟)和锁。

最后说一下

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

敬请期待下篇 纠错码

感谢您的阅读!
如果看完后有任何疑问,欢迎拍砖。
欢迎转载,转载请注明出处:http://www.yangrunwei.com/a/123.html
邮箱:glowrypauky@gmail.com
QQ: 892413924