密钥交换算法: 迪菲-赫尔曼算法
概述
迪菲-赫尔曼算法用于通信双方交换密钥. 还记得之前介绍HTTPS协议的时候, 提到需要先通过对方公钥来进行密钥的交换, 然后再通过密钥对通信内容进行加密. 迪菲-赫尔曼算法就是用于交换密钥的. . 此算法与非对称加密算法不同哦.
OK, 一起来看看吧.
引入
在正式介绍迪菲-赫尔曼算法之前, 先简单跟我思考下面场景.
现场有你, 小王和小李三个人, 你和小王之间需要建立一个共享密钥, 但是, 你们不能交头接耳, 你们之间说的话小李都能听到. 那么, 有什么办法能够建立共享密钥而不让小李知道呢? 现在开始, 跟着思路走一下.
我们假设以下的计算只有乘法没有除法, 即乘法是不可逆的(这里为了简单说明, 在后面会出现真正不可逆的函数)
「第一步」
你和小王都在心里默默的选择一个只有自己知道的数字, 比如: 你选了8, 小王选了3.
image-20200503200946928
「第二步」
小王宣布一个公共数字, 当然, 这个数字也是他选的. 这个数字就暂定是5.
image-20200503201030371
「第三步」
你和小王分别用私人数字与公共数字相乘, 得到新的「私人-公共数字」
image-20200503201311917
「第四步」
你和小王分别将对方的 私人-公共数字 与自己的私人数字相乘, 得到的结果就是你们之间的共享密钥: 「120」.
image-20200503201521952
最终来判断一下, 在这个过程中, 小李有没有可能拿到这个共享密钥: 120. 小李知道的所有信息是, 公共数字7以及你们的 私人-公共数字. (别忘了我们的假设, 没有除法). 显然, 仅凭乘法是得不出的.
那么现在问题来了, 这个不可逆的算法在哪?他在哪???
正式应用
他来了, 他来了, 他来了. 这个不可逆的算法来了.
有这样的一种运算, 将一个数字与n取模得出最终的数, 被称为钟运算. 想象一下一个时钟, 13点就是1点. 嗯, 就是这样.
计算一个指数并将结果与钟的大小取模, 这个过程就是下面的计算了. 例如, 如果钟的大小是12, 基数是2, 则计算公式是: 2^8%12=256%12=4.
问题, 只告诉你数字12, 2和4, 你能算出数字8么? 不能, 因为可能性太多了. 简单穷举一下:
- 2^2%12 => 4
- 2^3%12 => 8
- 2^4%12 => 4
- 2^5%12 => 8
- 2^6%12 => 4
能看得出来很多哈. 重复一下上面的交换步骤, 开始尝试建立公共密钥
「第一步」
选择自己的私人数字.
image-20200503204155129
「第二步」
公布公共数字, 这里公共数字需要两个, 一个数字是钟的大小, 一个数字是求幂的基数.
image-20200503205220865
「第三步」
双方公布自己计算后的数字
image-20200503205130588
「第四步」
混合得到共享密钥. 将对方的 公共-私人数字 为基数, 自己的私人数字为指数, 计算并和钟大小取模, 得出最终的共享密钥
image-20200503205038362
OK, 至此, 密钥交换成功. 当然, 通过穷举的方法还是可以得到共享密钥. 例子中的数字为方便计算, 都很小. 但是, 现实使用中, 钟大小如果有几百位的数字呢?
对于数字的选择有个小小的限制:
- 钟大小的选择必须是一个素数(我也不知道为啥).
- 上面选取的基数2, 只能取到钟上的数字4和8. 现实中基数一般选取钟大小的本原根(我也不知道为啥叫这名). 比如2是11的本原根.(2^1%11 ... 2^10%11 的值分别为: 2,4,8,5,10,9,7,3,6,1. 涵盖了11的所有值. )
对了, 这个计算规则叫做「离散对数」, 名字不重要, 知道怎么回事就行了.