写在前面
即使通信全程都被窃听，你依然可以和对方安全地协商出密钥来进行加密通讯。
D-H 密钥交换流程
- 通信双方甲和乙事先约定好两个精心挑选的数，一个是质数 $p$，另一个是 $g$。这两个数是可以公开的。我们假设 $p=23,g=5$。
- 甲随机选择一个整数 $a$，计算 $A=g^a \mod p$，并将 $A$ 发送给乙。其中 $A$ 是可以公开的，但是 $a$ 不能泄露。我们假设 $a=6$，那么 $A=5^6 \mod 23 =8$。
- 乙随机选择一个整数 $b$，计算 $B=g^b \mod p$，并将 $B$ 发送给甲。其中 $B$ 是可以公开的，但是 $b$ 不能泄露。我们假设 $b=15$，那么 $B=5^{15} \mod 23 =19$。
- 此时双方就可以计算出共有的密码 $s$。甲通过计算 $s = B^a \mod p = 19^6 \mod 23 = 2$。乙通过计算 $s = A^b \mod p = 8^6 \mod 23 = 2$。
- 双方得到了相同的密码 $s$。但这个密码并不是一方主动发给另一方的，而是通过双方交换的信息计算而来的。此时可以使用 $s$ 生成对称密钥来加密通信。
根据模运算法则 $g^a \mod p = [{(g \mod p)}^a] \mod p$，同理 $g^b \mod p = [{(g \mod p)}^b] \mod p$，显然 $s={(g^a \mod p)}^b \mod p = {(g^b \mod p)}^a \mod p$。
可以发现公开的信息只有 $p,g,A,B$，而只需要在草稿纸上试一试就感觉这些信息逆向算出$a,b$是很难的事情，貌似只能去穷举，事实也确实如此。由于计算出密码 $s$ 除了 $p,g,A,B$ 以外还需要 $a$ 或 $b$，所以这种密钥交换方式即使在被窃听的情况下也能保证安全（前提是不会受到中间人攻击）。
离散对数问题
上文说到逆向计算 $a,b$ 是很难的，这其实就是著名的离散对数问题。相关的数学表述本文不会涉及，首先是因为本文的初衷是了解即可，没必要钻那么深，其次就是笔者不是搞数学的，水平有限，查了半天资料还是一知半解的，就不瞎说了。就举一个比较直观的例子吧。
我们设 $g=3,p=10$，依次计算 $g^i \mod p$，其中 $i = 0,1,2,···,99$。
$$
\begin{aligned}
3^{0} \mod 10 = 1 \\
3^{1} \mod 10 = 3 \\
3^{2} \mod 10 = 9 \\
3^{3} \mod 10 = 7 \\
3^{4} \mod 10 = 1 \\
3^{5} \mod 10 = 3 \\
3^{6} \mod 10 = 9 \\
3^{7} \mod 10 = 7 \\
3^{8} \mod 10 = 1 \\
3^{9} \mod 10 = 3 \\
3^{10} \mod 10 = 9 \\
3^{11} \mod 10 = 7 \\
3^{12} \mod 10 = 1 \\
3^{13} \mod 10 = 3 \\
3^{14} \mod 10 = 9 \\
3^{15} \mod 10 = 7 \\
3^{16} \mod 10 = 1 \\
3^{17} \mod 10 = 3 \\
3^{18} \mod 10 = 9 \\
3^{19} \mod 10 = 7 \\
3^{20} \mod 10 = 1 \\
3^{21} \mod 10 = 3 \\
3^{22} \mod 10 = 9 \\
3^{23} \mod 10 = 7 \\
3^{24} \mod 10 = 1 \\
3^{25} \mod 10 = 3 \\
3^{26} \mod 10 = 9 \\
3^{27} \mod 10 = 7 \\
3^{28} \mod 10 = 1 \\
3^{29} \mod 10 = 3 \\
3^{30} \mod 10 = 9 \\
3^{31} \mod 10 = 7 \\
3^{32} \mod 10 = 1 \\
3^{33} \mod 10 = 3 \\
3^{34} \mod 10 = 8 \\
3^{35} \mod 10 = 2 \\
3^{36} \mod 10 = 6 \\
3^{37} \mod 10 = 6 \\
3^{38} \mod 10 = 0 \\
3^{39} \mod 10 = 6 \\
3^{40} \mod 10 = 8 \\
3^{41} \mod 10 = 2 \\
3^{42} \mod 10 = 2 \\
3^{43} \mod 10 = 6 \\
3^{44} \mod 10 = 4 \\
3^{45} \mod 10 = 2 \\
3^{46} \mod 10 = 4 \\
3^{47} \mod 10 = 0 \\
3^{48} \mod 10 = 8 \\
3^{49} \mod 10 = 8 \\
3^{50} \mod 10 = 4 \\
3^{51} \mod 10 = 2 \\
3^{52} \mod 10 = 4 \\
3^{53} \mod 10 = 4 \\
3^{54} \mod 10 = 6 \\
3^{55} \mod 10 = 8 \\
3^{56} \mod 10 = 0 \\
3^{57} \mod 10 = 4 \\
3^{58} \mod 10 = 2 \\
3^{59} \mod 10 = 2 \\
3^{60} \mod 10 = 0 \\
3^{61} \mod 10 = 8 \\
3^{62} \mod 10 = 4 \\
3^{63} \mod 10 = 4 \\
3^{64} \mod 10 = 0 \\
3^{65} \mod 10 = 2 \\
3^{66} \mod 10 = 8 \\
3^{67} \mod 10 = 4 \\
3^{68} \mod 10 = 6 \\
3^{69} \mod 10 = 4 \\
3^{70} \mod 10 = 8 \\
3^{71} \mod 10 = 4 \\
3^{72} \mod 10 = 0 \\
3^{73} \mod 10 = 0 \\
3^{74} \mod 10 = 6 \\
3^{75} \mod 10 = 0 \\
3^{76} \mod 10 = 0 \\
3^{77} \mod 10 = 4 \\
3^{78} \mod 10 = 6 \\
3^{79} \mod 10 = 2 \\
3^{80} \mod 10 = 4 \\
3^{81} \mod 10 = 2 \\
3^{82} \mod 10 = 8 \\
3^{83} \mod 10 = 0 \\
3^{84} \mod 10 = 6 \\
3^{85} \mod 10 = 4 \\
3^{86} \mod 10 = 2 \\
3^{87} \mod 10 = 8 \\
3^{88} \mod 10 = 4 \\
3^{89} \mod 10 = 0 \\
3^{90} \mod 10 = 6 \\
3^{91} \mod 10 = 2 \\
3^{92} \mod 10 = 6 \\
3^{93} \mod 10 = 0 \\
3^{94} \mod 10 = 0 \\
3^{95} \mod 10 = 0 \\
3^{96} \mod 10 = 2 \\
3^{97} \mod 10 = 6 \\
3^{98} \mod 10 = 2 \\
3^{99} \mod 10 = 6 \\
\end{aligned}
$$$$
\begin{aligned}
& 3^{0} \mod 17 = 1 \\
& 3^{1} \mod 17 = 3 \\
& 3^{2} \mod 17 = 9 \\
& 3^{3} \mod 17 = 10 \\
& 3^{4} \mod 17 = 13 \\
& 3^{5} \mod 17 = 5 \\
& 3^{6} \mod 17 = 15 \\
& 3^{7} \mod 17 = 11 \\
& 3^{8} \mod 17 = 16 \\
& 3^{9} \mod 17 = 14 \\
& 3^{10} \mod 17 = 8 \\
& 3^{11} \mod 17 = 7 \\
& 3^{12} \mod 17 = 4 \\
& 3^{13} \mod 17 = 12 \\
& 3^{14} \mod 17 = 2 \\
& 3^{15} \mod 17 = 6 \\
& 3^{16} \mod 17 = 1 \\
& 3^{17} \mod 17 = 3 \\
& 3^{18} \mod 17 = 9 \\
& 3^{19} \mod 17 = 10 \\
& 3^{20} \mod 17 = 13 \\
& 3^{21} \mod 17 = 5 \\
& 3^{22} \mod 17 = 15 \\
& 3^{23} \mod 17 = 11 \\
& 3^{24} \mod 17 = 16 \\
& 3^{25} \mod 17 = 14 \\
& 3^{26} \mod 17 = 8 \\
& 3^{27} \mod 17 = 7 \\
& 3^{28} \mod 17 = 4 \\
& 3^{29} \mod 17 = 12 \\
& 3^{30} \mod 17 = 2 \\
& 3^{31} \mod 17 = 6 \\
& 3^{32} \mod 17 = 1 \\
& 3^{33} \mod 17 = 3 \\
& 3^{34} \mod 17 = 8 \\
& 3^{35} \mod 17 = 15 \\
& 3^{36} \mod 17 = 11 \\
& 3^{37} \mod 17 = 1 \\
& 3^{38} \mod 17 = 11 \\
& 3^{39} \mod 17 = 0 \\
& 3^{40} \mod 17 = 0 \\
& 3^{41} \mod 17 = 8 \\
& 3^{42} \mod 17 = 11 \\
& 3^{43} \mod 17 = 16 \\
& 3^{44} \mod 17 = 15 \\
& 3^{45} \mod 17 = 11 \\
& 3^{46} \mod 17 = 7 \\
& 3^{47} \mod 17 = 6 \\
& 3^{48} \mod 17 = 10 \\
& 3^{49} \mod 17 = 12 \\
& 3^{50} \mod 17 = 2 \\
& 3^{51} \mod 17 = 6 \\
& 3^{52} \mod 17 = 15 \\
& 3^{53} \mod 17 = 2 \\
& 3^{54} \mod 17 = 5 \\
& 3^{55} \mod 17 = 15 \\
& 3^{56} \mod 17 = 10 \\
& 3^{57} \mod 17 = 14 \\
& 3^{58} \mod 17 = 8 \\
& 3^{59} \mod 17 = 14 \\
& 3^{60} \mod 17 = 12 \\
& 3^{61} \mod 17 = 10 \\
& 3^{62} \mod 17 = 13 \\
& 3^{63} \mod 17 = 13 \\
& 3^{64} \mod 17 = 14 \\
& 3^{65} \mod 17 = 10 \\
& 3^{66} \mod 17 = 5 \\
& 3^{67} \mod 17 = 15 \\
& 3^{68} \mod 17 = 7 \\
& 3^{69} \mod 17 = 5 \\
& 3^{70} \mod 17 = 11 \\
& 3^{71} \mod 17 = 16 \\
& 3^{72} \mod 17 = 16 \\
& 3^{73} \mod 17 = 14 \\
& 3^{74} \mod 17 = 9 \\
& 3^{75} \mod 17 = 12 \\
& 3^{76} \mod 17 = 2 \\
& 3^{77} \mod 17 = 7 \\
& 3^{78} \mod 17 = 0 \\
& 3^{79} \mod 17 = 16 \\
& 3^{80} \mod 17 = 12 \\
& 3^{81} \mod 17 = 2 \\
& 3^{82} \mod 17 = 4 \\
& 3^{83} \mod 17 = 16 \\
& 3^{84} \mod 17 = 15 \\
& 3^{85} \mod 17 = 7 \\
& 3^{86} \mod 17 = 4 \\
& 3^{87} \mod 17 = 10 \\
& 3^{88} \mod 17 = 13 \\
& 3^{89} \mod 17 = 14 \\
& 3^{90} \mod 17 = 4 \\
& 3^{91} \mod 17 = 16 \\
& 3^{92} \mod 17 = 14 \\
& 3^{93} \mod 17 = 6 \\
& 3^{94} \mod 17 = 1 \\
& 3^{95} \mod 17 = 3 \\
& 3^{96} \mod 17 = 1 \\
& 3^{97} \mod 17 = 3 \\
& 3^{98} \mod 17 = 5 \\
& 3^{99} \mod 17 = 15 \\
\end{aligned}
$$那么如果我问求一个 $k$ 使得 $3^k \mod 10 = 6$。在没有快捷算法的情况下我们只能一个一个地试，此时可以视为随机取 $i$ 的值去试。可以注意到在上面列出的 100 个计算结果中 6 出现了 13 次，出现的概率是 $13\%$，这意味着我在穷举过程中每次计算都有 $13\%$ 的概率的都正确答案。
那么当我们让$p=17$，即一个素数时，情况就变了。
点击查看计算结果
此时 6 只出现了 5 次，而且呈现出了明显的周期现象，这个周期就是 $p-1$ 即 16。这时我们穷举的时候每次计算只有 $5\%$ 的概率是正确答案了。在这种情况下我们提高了穷举的难度。
目前的数学研究结果让我们可以精心选择一个素数 $p$ 和另一个精心选择的 $g$ 来通过这样的方式来提高穷举的难度，比如我们选择一个长度为 $1024 bit$ 的素数，那么它的周期和 $2^{1024} \approx 1.798 \times 10^{308}$ 是同一个数量级的，那么暴力穷举算法的时间复杂度就是指数级的。那么如果素数的长度是 $2048 bit$ 呢？$4096 bit$ 呢？
上面的例子并不严谨，但可以直观地感受一下离散对数问题的难度。稍微专业点的描述一下离散对数的难度就是暂时没有多项式时间或更快的算法能够求解离散对数问题。
身份验证
D-H 密钥交换没有提供身份验证的机制，所以我们需要公钥基础设施来保证不会受到中间人攻击。
前向安全性
前向安全性即通讯的主密钥泄露不会导致会话密钥的泄露，它可以保证之前的通讯不会因为在未来的某一时刻主密钥泄露而被解密。
目前常见的身份认证方式之一就是基于非对称加密的证书验证。在这种方式下为了实现身份认证服务端会使用私钥给一些必要的信息签名发送给客户端，客户端确认服务端的身份后双方协商出会话密钥，协商过程中的信息会用公钥加密，只有私钥才能解密。此时客户端可以直接将会话密钥通过公钥加密后发送给服务端，然后开始加密通讯。这在正常情况下没有任何问题。但是一旦服务端的私钥泄露，那么之前的会话密钥就会被解密，之前的通讯信息也就暴露了。
回忆一下，D-H 密钥交换过程中 $p,g,A,B$ 是可以公开的，只有$a,b$ 是秘密的，我们假设 $a,b$ 是随机选取的，并且在通讯结束后会被销毁。如果客户端在确认了服务端身份的之后采用 D-H 密钥交换的方式，而不是直接发送公钥加密后的会话密钥，那么即使未来的某一时刻服务端私钥泄露了，也不会泄露会话密钥，也就无法解密之前的通讯信息。
目前这种机制已经被引入 TLS 中。
写在最后
搞密码的这群人是何等的怪物（褒义）。
参考资料
- 迪菲-赫尔曼密钥交换_百度百科
- 前向安全性_百度百科
- RFC 8446 – The Transport Layer Security (TLS) Protocol Version 1.3
ESWINK , 版权所有丨如未注明 , 均为原创
原文标题:「其他分享」D-H 密钥交换—即使被窃听也能安全地交换密钥
📮评论