介绍
非对称加密技术是当前互联网界采用较多的一种数据加密方式.
通过网络传输机密信息的问题是, 传输的渠道是公开, 透明的, 某种程度上来讲, 这就好比要使用明信片来传递秘密一样.
因此我们需要构建的数据加密方式必须能够做到, 只有接受和发送消息的人才能够得到明信片上所真正表示的内容.
什么是秘钥?
首先, 毋庸置疑的是, 我们需要对公开传送的内容进行修改, 使其成为加密的密文.
一个最简单的方法, 就是 "移位密码". 以英文为例, 我们可以简单的让每个字母向后移动几个距离来实现内容的加密, 比如下面这样:
Mark = 每个字符向后移动 3 个距离 => Pdun
这是一个简单的方法, 更进一步的, 使用凯撒密码 https://baike.baidu.com/item/恺撒密码/4905284?fr=aladdin 等方式, 可以实现进一步的加密.
切换到计算机层面上, 即是说可以对传输的二进制包整体做移位处理, 从而实现加密(当然实际的算法要比这复杂的多).
可以看到, 无论是采用什么样的加密方式, 消息的发送者和接受者都需要提前共享一样东西, 来实现加密和解密: 在移位密码的例子中, 这个东西是字母向后移动的距离, 在凯撒密码中, 则是一串字母或是也该单词.
我们将这个需要双方提前共享的东西称为秘钥, 这是一个很形象的比喻, 我们对信息加密, 就像是要对信息加上一把老式的旋转锁, 而无论是上锁还是解锁, 都需要一把同样的钥匙.
所以在共享秘钥的加密方式里, 传输加密消息的关键在于如何通过公开的信道共享同一把秘钥.
使用混合颜料
现在让我们想象一个场景:
在同一个房间里有 A,B,C 三个人, A 要向 B 传输一段私密消息(比如说他的银行卡密码), 而 C 是一名窃听者.
在不使用小纸条, 悄悄话等方式的前提下, A 和 B 要如何传输消息, 才能避免 C 的窃听呢?
另外需要注意的一点是, A 和 B 是陌生关系, 这也就意味着他们没法使用诸如 "天王盖地虎, 宝塔镇河妖" 之类的暗号进行交流.
乍看之下似乎是一个很无解的问题, 但却有一个很巧妙的方法能够解决 -- 我们需要的只是几桶不同颜色的颜料罢了.
前提
现在我们假设 A,B,C 三个人, 分别位于房间的三个角落里, 而每个角落里都有很多很多不同颜色的颜料, 每种颜色的颜料也是无限多的.
注意, 我们规定, 每个人在自己的角落里所做的事情, 是其他任何人都无法看到的, 如果两个人需要对话或是交换信息, 就必须走到房间中央的公共区域去, 在这里做的事情, 是公开透明的.
第一步: A 和 B 选择各自的私有颜色
A 和 B 在各自的角落里选定一种颜色, 我们将这个称为 A 和 B 的私有颜色, 这意味着只有 A 和 B 自己知道它是什么颜色, 其他人都无法知晓.
第二步: A 和 B 选择各自的公开颜色
现在 A 和 B 需要再各自选定一种颜色, 与之前不同的是, 这次选定的颜色是公开的, 这意味着 A 和 B 需要将这种颜色放到房间中央的公共区域去: 任何人都可以取到他们的公开颜色.
第三步: A 和 B 构建自己的混合颜色
现在 A 和 B 需要在各自的角落里做一些 "调色" 工作, 这非常简单:
A 将自己的私有颜色和自己的公开颜色进行混合, 得到一种新的颜色, 我们称其为 A 的 "公开 - 私有混合颜色".
同样的, B 将自己的私有颜色, 与 A 的公开颜色进行混合, 得到 B 的 "公开 - 私有混合颜色".
注意, 他们各自的混合颜色并不相同.
接下来 A 和 B 将会把各自的混合颜色公开, 放置到房间中央的公共区域去.
第四步: A 和 B 在彼此的混合颜色中, 加入自己的私有颜色
现在我们假设, A 获得了 B 的 "公开 - 私有混合颜色", 并将它搬回了自己的角落; 同样的, B 也将 A 的 "公开 - 私有颜色" 搬回了自己的角落.
那么, 神奇的地方来了, 现在 A 和 B 分别向彼此的混合颜色中, 加入自己的私有颜色, 最终他们将得到相同的颜色, 因为他们使用了同样的成分 (A 的公开颜色 + A 的私有颜色 + B 的私有颜色) 来构建最终的颜色.
接下来, A 和 B 只需要使用这种相同的颜色对要传输的信息进行加密 / 解密操作, 就可以实现消息的秘密传输了(参照移位密码).
整体的过程可以参考下图:
我们可以看到, 对于窃听者 C, 无论如何拼凑信息, 都无法得到真正的共享秘钥.
颜料混合的要点
之所以能够使用混合颜料来达到上述的神奇效果, 关键在于:
颜色的混合是一个不可逆的过程
构建 "公开 - 私有混合颜色" 后, 就没有人能够从中从中抽离出原有的两种颜色究竟是什么了
相同的成分混合最终一定能够得到相同的结果
尽管 A 和 B 不能从 "混合颜色" 中提取出原有的颜色, 但他们只要再向其中加入自己的私有颜色, 就可以使颜色混合的结果达成一致, 最终获得相同的颜色.
实际网络中的公钥加密算法
我们以混合颜料的例子说明了如何实现共享秘钥的构建, 现在是时候思考如何在二进制的网路世界里达到同样的效果了.
首先我们需要一种特殊的数字运算方式, 能够和颜料的混合一样实现不可逆运算, 同时还能够保证相同的数字按照不同的顺序进行运算后, 能够得到同样的结果(即满足交换律).
现在来介绍能够满足上述要求的一种计算方式, 也是网络早期共享秘钥 Diffie Hellman 算法所采用的计算方式: 模运算 + 幂运算
模运算(mod)
这对于熟识计算机常识的人并不是一个陌生的数学知识, 我们假定一个模数 A, 那么任何一个数字 B 对 A 取模的结果就是 B / A 的余数.
以模数 A = 11 为例子:
- 13 mod 11 = 2
- (3 + 6) mod 11 = 9
- (2^4) mod 11 = 5
有了模运算的概念后, 我们就可以开始着手构建可用的共享秘钥算法了, 下面依旧基于 A,B,C 三个人的场景进行说明.
第一步: A 和 B 各自选择一个私人数字
为了方便阅读, 我们假设 A 和 B 选择的都是一个非常小的数字: 比如 A 选择 8,B 选择 9. 注意在实际的应用中, 这个数字要大得多.
第二步: A 和 B 选择两个公开的数字
和颜色混合不同, 现在每个人的公开部分需要包含两个数字, 其中一个是模数, 另一个是基数.
假设 A 的公开数字分别是 11(模数)和 2(基数).
第三步: A 和 B 构建自己的公开 - 私人数字(PPN)
这是关键的一步, 我们要解释一个等同于颜料混合的算数过程, 这个过程构建出的结果将会是不可逆的.
现在, A 和 B 都将使用 A 的两个公开数字, 和自己的私有数字, 利用下面的公式计算自己的公开 - 私有数字(我们称其为 PPN):
PPN = 基数 ^ 私人数字 mod 模数
于是:
A 的 PPN = 2^8 mod 11 = 3
B 的 PPN = 2^9 mod 11 = 6
可以看到这个计算 PPN 的过程是不可逆的, 这主要归功于取模操作.
第四步: A 和 B 向彼此的 PPN 中混合自己的私人数字
混合的计算方式和上面类似, 只是公开基数被替换成了对方的 PPN:
A 计算共享秘钥 = B 的 PPN^8 mod 11 = 6^8 mod 11 = 4
B 计算共享秘钥 = A 的 PPN^9 mod 11 = 3^9 mod 11 = 4
之所以能够得到同样的结果, 是因为幂运算满足交换律, 即:
(a^b)^c = (a^c)^b = a^(bc)
很好, A 和 B 成功混合得到了同样的共享秘钥! 现在他们只需要使用这个共享秘钥进行数字的加密 / 解密就可以实现私密通信了.
而窃听者 C 无论拿到谁的 PPN, 都会因为无法混入另一个人的私钥而不能得到最终的共享秘钥.
我们可以把上面的过程总结为下图:
真实的 Deffie-Hellman 算法
上面的例子中, 为了方便理解, 我们都采用了非常小的数字, 比如模数 11, 对应的结果空间只有 0-10 一共 11 个数字, 那么窃听者完全可以通过暴力尝试的方式遍历整个结果空间, 最终破译得到密码.
所以, Deffie-Hellman 对公开数字有以下几个要求:
模数一般是几百个数位长的数字, 确保无法通过暴力遍历的方式求解
模数必须是一个素数
基数必输是模数的 "本原根": 其幂循环最终可以遍历循环模数对应结果空间上的每一个值
有关本原根, 我们可以参考上面使用到的数字, 对于模数 11 而言, 2 和 6 都是本原根, 而 3 则不是:
3 的幂循环对 11 取模后得到的值只有 3,9,5,4,1, 而无法得到 2,6,7,8,10.
更多
共享秘钥加密, 是不对称加密的一个典型使用范例, 除了 Deffie-Hellman 算法之外, 大名鼎鼎的 RSA 也属于同样的思路.
后续的文章中将会更新更多有关不对称加密的内容.
本文参考:改变未来的九大算法 https://book.douban.com/subject/24529132/ 第四章
来源: https://juejin.im/post/5ac49a7b518825558c47a6e7