如何在非安全信道进行安全通信？ - 迪菲赫尔曼密钥交换协议基本原理
让我们从一个非常简单的思想实验开始。
假设 A、B、C 三个素不相识的人待在一个房间里进行口头交流，此时 A 想要秘密地“传输”一条消息给 B，但又不能让 C 知道。为方便起见，假设这条消息只是 0 到 9 之间的一个数字。
需要注意的是，A 说的任何话 B 和 C 都能听到，且 A 不能偷偷摸摸地耍小把戏，比如传纸条给 B 。那么 A 要如何才能做到呢？
欢迎来到 科技研究所，我是無糖。
一、如何告诉 B ？
在告诉你如何做到之前，我需要先向你解释两个数学的基本运算。
- 取模运算
- 幂运算
然后我会通过 A 如何告诉 B 这个简单的思想实验来向你解释迪菲-赫尔曼密钥交换协议的大致流程。
之所以是协议 流程而不是算法 流程，是因为这个过程中需要 B 的参与。
- 「协」字，代表的意思是必须有两个以上的参与者；
- 「议」字，代表的意思是对参与者的⼀种行为约定和规范。
好了，那么你现在已经知道这件事单靠 A 一个人努力是不行的了。
1.1、取模运算
取模运算（ mod ）是求两个数相除的余数。x mod y = z，我们将 y 称为模数 ，z 称为余数。
我举几个例子：
- 5 mod 2 = 1 ，因为 5 除以 2 商 2 余1；
- 10 mod 3 = 1 ，因为 10 除以 3 商 3 余1；
1.2、幂运算
幂运算，又称指数运算，表达式为 $ x^{n} $ ，其中 $ x $ 称为底数 ，$ n $ 称为指数。通常指数写成上标，放在底数的右边。
我举几个例子：
- $ 2^{3}=8 $ ，因为 $ 2 * 2 * 2=8 $ ；
- $ 3^{4}=81 $ ，因为 $ 3 * 3 * 3 * 3 =81 $ ；
1.3、协议流程
现在你已经理解取模运算和幂运算这两个基本数学运算了，接下来我来解释一下这件事要怎么做。
1）双方各挑选一个私人数字（不公开）
为保证数学计算上尽可能简单，我们将在这个例子中使用非常小的数字。因此，假设
- A 挑选了 8 作为私人数字
- B 挑选了 9 作为私人数字
私人数字是不对外公开的，自己默默记住就可以。
2）双方约定两个数（公开）
双方需要约定两个数，分别作为取模运算的模数和幂运算的底数。
为保证数学计算上尽可能简单，我也会使用非常小的数字。
因此，假设 A 与 B 约定了 模数＝11，底数＝2。
3）双方计算各自的 PPN（公开）
双方使用自己的私人数字、双方约定好的模数和底数计算各自的 PPN 。
计算公式： $ PPN=约定的底数^{自己的私人数字} mod 约定的模数 $
这个公式用文字写出来可能会显得有点儿诡异，但实际却很简单。
- A 的 PPN = $ 2^{8} mod 11 = 256 mod 11 = 3 $
- B 的 PPN = $ 2^{9} mod 11 = 512 mod 11 = 6 $
4）计算共享密钥（不公开）
双方使用自己的私人数字、对方的 PPN 和约定好的模数计算共享密钥。
计算公式：$ 共享密钥＝对方的PPN^{自己私人数字} mod 约定的模数 $
同样的，这个公式用文字写出来可能会显得有点儿诡异，但实际却很简单。
- A 计算出来的共享密钥 = $ 6^{8} mod 11 = 1679616 mod 11 = 4 $
- B 计算出来的共享密钥 = $ 3^{9} mod 11 = 19 683 mod 11 = 4 $
现在你发现，A 与 B 都算出来了同样一个数字 4 了，这就回答了文章开头的思想实验。
此处 A 与 B 计算出的共享密钥即为 A 要传输给 B 的“信息”。
C 因为不知道 A 与 B 的私人数字，即使 C 知道了 A 与 B 公开约定的两个数（取模运算的模数和幂运算的底数）和 PPN ，也是无法计算出与相同的共享密钥的。
整个协议过程中，除了 A、B（通信双方）的私人数字（私人密钥）不对外公开，其他都是透明可见的。共享密钥的保密性不依赖此协议流程的保密性，即使协议的计算流程公开，共享密钥也是安全的。
二、关于迪菲-赫尔曼密钥交换协议
通过上面的思想实验，我们知道运用幂运算和取模运算就可以让通信双方在完全没有对方任何预先信息的条件下，通过不安全信道共同建立起一个安全的共享密钥，而一旦建立了共享密钥，这两台电脑就能使用对称加密对后续所有的通信进行加密了。
本文描述的协议流程被称为迪菲–赫尔曼密钥交换机制（DH）。这一机制以怀特菲德·迪菲（Whitfield Diffie）和马丁·赫尔曼（MartinHellman）的名字命名，他们俩于 1976 年首次发表了这一算法。每次你访问一个安全网站（以“https:”而非“http:”开头）时，你的计算机和与其通信的网站服务器之间都会建立一个共享密钥，使用的方法是迪菲–赫尔曼机制或工作原理类似的替代方法之一。除了最早的 DH（迪菲-赫尔曼密钥交换协议）之外，现在已经有 DHE / ECDHE 等变种了。
迪菲-赫尔曼密钥交换协议被发明后不久就出现了 RSA （非对称加密算法），现在的 HTTPS 协议就是通过 RSA+ECDHE 来保证确保通信安全的。
虽然迪菲-赫尔曼密钥交换本身是一个匿名（无认证）的密钥交换协议，它却是很多认证协议的基础。
2.1、实践中的公钥加密
在实践中使用数字要远比我们在例子中使用的数字大。我们使用的模数很小（11），因此计算起来就很简单。但如果你选择的模数很小，那么私人数字的取值范围也会很小（因为你只能使用比模数小的私人数字）。而这也意味着有人可以使用计算机试出所有可能的私人数字，直到找到一个数字生成你的 PPN 。在上面的例子中，只有 11 个可能的私人数字，因此这个系统非常轻易就能被破解。相反，迪菲–赫尔曼机制在现实中运用时通常会使用几百个数位长的钟大小，这让可能的私人数字多得不可想象（比一万亿的一万亿次方还多得多）。即便如此，我们也需要小心地选取公开数字，以确保它们具有正确的数学性质。
最重要的是，模数必须是一个素数——只有1和其自身两个除数。另一个有趣的要求是，约定的底数必须是约定的模数的本原根（primitive root）。这也意味着底数的幂最终将循环遍 [0, 模数) 区间上每个可能的值。在前文使用的例子中， 2 和 6 都是 11 的本原根，但 3 却不是—— 3 的幂循环的值有 3、9、5、4 和 1，却没有 2、6、7、8 和 10 。
2.2、为什么知道了 PPN 也无法反推出私人数字
在上面的思想实验中，我们知道：
- A 的 PPN = $ 2^{8} mod 11 = 256 mod 11 = 3 $
对于 C 来说，假设 $ A 的私人数字=x $，则有：
- A 的 PPN = $ 2^{x} mod 11 = 3 $
那么 C 为什么无法通过 A 的 PPN 反推出他的私人数字？
因为当模数 11 是一个很大的质数时，由于还没有一种方法能让计算机高效地计算离散对数，即使知道了底数（2） 和 A 的 PPN（3），也几乎算不出来 $ x $ 的值。
离散对数求解难就是 DH 的数学基础理论。