RSA核心思想
郝伟 2020/07/23

前言

DH 算法是 Diffie和Hellman两位作者于1976年提出了一种的密钥交换协议。这种加密算法主要用于密钥的交换，能够实现了在非安全网络下通信双方密钥的安全建立，从而使通信双方能够使用这个密钥进行消息的加密解密，从而实现通信的安全。

1 应用场景

Alice想要给Bob传递一些资料，为了保证信息安全，Alice做了以下操作：
1）对资料打包并加密
2）将加密后的压缩包通过邮件发给Bob
3）将解密的密码用短信发给了Bob。
4）Bob在收到压缩包后，用短信收到的密钥解开。
这样一来，无论是邮件还是短信在传输的过程中泄露，别人都无法破解资料的内容（假定加密算法是可靠的）。

表面上看起来这样分开传输的方式很安全，但是实际上无论是邮件还是短信，由于都是通过网络传输，即便Bob的电脑和手机本身是安全的，数据仍然有泄露的风险。也就是说，只要Bob的网络和短信通道同时被别人监听了，那么资料仍然会泄露。

这样的场景在生活中是很常见的，如网银，在线支付软件，网上办公等。在这些场景中，为了保证数据安全，我们通常会对需要传递的数据使用一个密钥进行加密和解密。但是在很多时候，通信双方是第一次通信，并没有一个公共的密钥可以为双方使用，由于数据都会在不安全网络中传输，同时任何传递信息都可能会泄露，即加密的数据和密钥都会泄露了，所以如何让第一次通信的双方在一个不安全的网络中安全地建立一套可供加解密的解密，就是一个必需解决的问题。

这个问题的本质原因是，无论采用任何方式进行沟通，只要信道是不安全的，那么就难以保证数据不泄露。我们当然可以采取一定的手段来保证消息通道的安全，但是在实际的应用中，这是很难做到的，比如我们打电话，发短信，通过网络收发消息，使用的都是公共网络，无法保证通信的安全性。

所以，这时候就需要有一种方式，能够保证在不安全信道的中，能够让双方生即便在没有密钥的情况下，仍然能够建安全的密钥。DH密钥交换算法就是这样的一种方法，它通过一种精巧有效的密钥交换算法，实现了密钥交换的安全。本文本将结合实例，从各个方面介绍DH算法的原理、实现方法和一些实例。

本篇分为三部分，第一部分介绍密钥交换的场景；第二部分介绍一下DH算法的的步骤，以及由该算法引出的一些问题；第三部分开始讲数学原理。数学原理可能涉及到数论、抽象代数，本篇尽量在每个公式后面证明该公式的正确性。

2 DH算法简介

2.1 基本原理

为了让A和B能够生成一把相同的密钥，我们先让AB各自建立自己的密钥，然后使用一个共同的信息（此信息是公开的）对密钥加密，加密后将此信息传输（这个信息可能泄露），然后再基于这个信息此进行计算以完成交换，最终AB用自己的密钥和对方的特征值计算生成最终的公共密钥。

让我们通过以下的示例来了解这个过程。

操作 A B
发布公共因子 p = 7 p = 7
随机生成私钥 kak_a = 3 kak_a = 4
生成特征值 tat_a = 3 * 7 = 21 tbt_b = 4 * 7 = 28
交换特征值 将 21 发给 B 将 28 发给 A
进行二次计算 kabk_{ab} = 3 * 28 = 84 kbak_{ba} = 4 * 21 = 84

经过以上的交换和计算，A和B得到了一个共同的密钥 84，从而完成实现了目标。在这个过程中，ka,kbk_a, k_b 并没有在网上交换，所以是安全，而通过它们最终生成的公共密钥是相同的，所以表面上来看，达到了公共密钥一致的需求。

然而这个算法并不实际，因为计算过程太过简单了。公共信息 7，特征值21和28在没有生成密钥前，会不安全的网络上传输，有可能会暴露。一旦被别人获得，那么很容易就可以反推出A和B的私钥分别是3和4。当然我们可以增加数据的复杂程度来解决，但是问题是即便我们使用了更加复杂的数据，如果只是简单的相乘，利用现在的计算机，仍然可以快速计算出来。

那么以上这种方案中，一旦暴露就会导致密钥泄露的问题的根源是什么？根据研究发现，根本原因并不是数据不够复杂，而是算法过于简单而且可逆。而且研究进一步发现，如果只是简单的使用加减乘除进行多项式计算，基本都是可逆且可以快速计算出来的。所以，如何防止别人利用从 ka 或者 kb 根据 p 分解而得出A或B的密钥，同时又能够让A和B根据这三个信息生成公共的密钥成了关键。

2.2 数学表示

以上数学公式可以表达如下：

  1. 设有函数 y=f(a,b,p)y= f(a, b, p), 其中 aa 和 bb 是待计算的输入值，pp 已知公共因子。
  2. 随机初始化 p,gp, g ，其中 gg 是初始值，pp 是公共因子。这两个值是公开的不安全；
  3. 随机生成A和B的不公开密钥 ka,kbk_a, k_b，这两个值只保留在A和B各自的内部，不在网上公开，所以是安全的；
  4. 随机生成A的特征值 ta=f(ka,g,p)t_a = f(k_a, g, p) 和 B 的特征值 tb=f(kb,g,p)t_b = f(k_b, g, p)，这两个值是公开的不安全；

根据以上信息，现在要求实现以下两点目标：

  1. yba=f(f(q,kb,p),ka,p)=f(f(q,ka,p),kb,p)=yaby_{ba} = f(f(q, k_b, p), k_a, p)= f(f(q, k_a, p), k_b, p)=y_{ab} 注：先计算 aa 再计算 bb 称之为 yaby_{ab}。
  2. 无法通过 p,q,ta,tbp, q, t_a, t_b 在有限的时间内计算出 kak_a 或 kbk_b 的值。

3 算法实现

DH算法的一个例子。
例1：设有二元组 (q,p)=(3,7)(q, p) = (3, 7)，我们可以定义以下运算：

  1. Alice 选择一个范围在 [1,p)[1, p) 的随机数，为 ka=5k_a = 5；
  2. Alice 计算 ta=qkamod p=35mod 7=5t_a = q^{k_a} \mathrm{mod} \ p = 3^5 \mathrm{mod} \ 7 = 5；
  3. Bob选择一个范围在 [1,p)[1, p) 的随机数，为 kb=6k_b = 6；
  4. Bob计算Pb = q^db mod p = 3^6 mod 7 = 1
  5. Alice和Bob交换 tat_a 和 tbt_b；
  6. Alice计算共享密钥 S=Pbdamodp=15mod7=1S = Pb ^{da} mod p = 1^5 mod 7 = 1；
  7. Bob计算共享密钥S = Padbmodp=56m7=1Pa ^{db} mod p = 5^6 m 7 = 1。

至此，Alice和Bob能够共享一个密钥为1。中间人由于只得到了Pa=5和Pb=1，如果也想要得到S，要么获取da然后执行步骤6中的等式计算得到结果、要么获取db然后执行步骤7中的等式得到结果。其实该算法的原理和上一部分中简单乘法及其类似，只是获取da或者db不是简单的方程式了，而是涉及到对数运算。对数运算被认为是“困难”的，这里是困难是指：目前为止既没有找到一个能够在可接受时间内计算出结果的算法，也没有在数学上没有证明这个算法是否存在。

看到这肯定有一个问题，随便一个二元组(q, p)都可以参与运算吗？显然不行。我们来看看如果随便一个(q, p)参与运算，会出现什么情况。

假设(q, p) = (7,15)，我们让Alice和Bob再来协商一遍
（1）Alice 选择一个范围在[1, p-1]的随机数，为da= 3
（2）Alice 计算Pa = q^da mod p =7^3 mod 15 = 13
（3）Bob选择一个范围在[1, p-1]的随机数，为db = 2
（4）Bob计算Pb = q^db mod p = 7^2 mod 15 = 4
（5）Alice和Bob交换Pa和Pb
（6）Alice计算共享密钥S = Pb ^da mod p = 4^3 mod 15 = 4
（7）Bob计算共享密钥S = Pa ^db mod p = 13^2 mod 15 = 4

看起来还是协商成功了，那问题在哪？
7x mod 15 的取值范围为 [1, 15)，最多14种可能，这也就意味着利用中间值 tat_a 或 tbt_b 反推 ka,kbk_a, k_b 是很容易造假的，即中间人不一定需要知道Alice原始的随机值（私钥）是什么，只要在[1 , 15) 中任意选择一个满足7x mod 15 = 13的值进行计算S = 47 mod 15 = 411 mod 15 = 4 都能正确计算共享密钥。也就是说，中间人根本不需要暴力遍历 [1 , 15) 中的所有数就能计算共享密钥。为了解决这个问题，选择(b, p)的最简单的解决办法就是 G = bx mod p, 当x遍历[1, p) 时，G也遍历了一遍[1, p)。当p足够大时，就可以让暴力破解的用时超过可接受时间。

4 数学证明

命题
已有公钥 p,gp, g，私钥 ka,kbk_a, k_b 和加密函数 f(a,b,c)=qbmod  cf(a, b, c) =q^b \mathrm{mod} \; c，证明：f(f(g,kb,p),ka,q)=f(f(g,ka,p),kb,q)f( f(g, k_b, p), k_a, q) =f(f(g, k_a, p), k_b ,q).

分析
令Sba=(gkbmod  p)kamod  pS_{ba}=(g^{k_b} \mathrm{mod} \; p)^{k_a} \mathrm{mod} \; p, Sab=(gkamod  p)kbmod  pS_{ab}=(g^{k_a} \mathrm{mod} \; p)^{k_b} \mathrm{mod} \; p, 现要证明 Sba=SabS_{ba}=S_{ab}，即以相同的加密函数和初始化数值，以不同的加密顺序可以得到相同的结果。

证明
设 ta=f(g,ka,p)=gkamod  pt_a = f(g, k_a, p)=g^{k_a} \mathrm{mod} \; p，可得 qka=kp+taq^{k_a}=kp+t_a，其中 kk 为整数，即 ta=qka−kpt_a = q^{k_a} - kp，那么：
Sab=(gkamod  p)kbmod  pS_{ab}= (g^{k_a} \mathrm{mod} \; p)^{k_b} \mathrm{mod} \; p
　　=takbmod  p=t_a^{k_b} \mathrm{mod} \; p
　　=(qka−kp)kbmod  p=(q^{k_a} - kp)^{k_b} \mathrm{mod} \; p。
　　＝qkakbmod  p＝q^{k_ak_b} \mathrm{mod} \; p 这是因为 kp 可以被 p 整除，所以可以直接省略

同理可证，Sab=qkbkamod  pS_{ab}=q^{k_bk_a} \mathrm{mod} \; p，所以 Sab=SbaS_{ab} = S_{ba}。证毕。

5 Java实现

本代码使用Java实现，基于两个大素数的实现。

5.1 源代码

public class DHTest {

	public static void main(String[] args) throws Exception {
		println("************************ DH算法演示 ************************");
		println("Step1: 生成可公开的公共加密因子p和q");
		int g = 25;
		int p = 131;
		println("       A生成可加密因子g和p分别为", g + "和" + p, ". 再传送给B，此时A和B都有g和p。");

		println("Step2: 生成各自的私钥");
		int x = 18;
		int y = 5;
		println("       A和B分别建立了一个自己的私钥，其中A的私钥 x=", x, ", B的私钥 y=", y);

		println("Step3: 各自特征码计算");
		int p_x = (int) (Math.pow(g, x) % p);
		int p_y = (int) (Math.pow(g, y) % p);
		println("       A使用公式 p^x mod q 计算出自己的特征码 p_x=", p_x);
		println("       B使用公式 p^y mod q 计算出自己的特征码 p_y=", p_y);

		println("Step4: 交换特征码生成公共密钥");
		int p_x_y = (int) ((long) Math.pow(g, p_y) % p);
		int p_y_x = (int) ((long) Math.pow(g, p_x) % p);
		println("       A使用公式 p^p_y mod q 计算出对称密钥： ", p_x_y);
		println("       B使用公式 p^p_x mod q 计算出对称密钥： ", p_y_x);
		println("结论：通过这种方式，双方可以得到相同的对称加密的密钥，而在整个传输过程中，由于x和y是不传输的，\n所以即便其他所有信息都被别人获利，也无法计算出对称密钥（因为目前在数学上还无人可以解开此问题）。");
	}
	
	public static void println(Object... objs) {
		StringBuilder sb = new StringBuilder();
		for (Object obj : objs) {
			sb.append(obj == null ? "" : obj.toString());
			sb.append("");
		}
		sb.append("\n");
		System.out.print(sb.toString());
	}

5.2 执行结果

************************ DH算法演示 ************************
Step1: 生成可公开的公共加密因子p和q
       A生成可加密因子g和p分别为25和131. 再传送给B，此时A和B都有g和p。
Step2: 生成各自的私钥
       A和B分别建立了一个自己的私钥，其中A的私钥 x=18, B的私钥 y=5
Step3: 各自特征码计算
       A使用公式 p^x mod q 计算出自己的特征码 p_x=51
       B使用公式 p^y mod q 计算出自己的特征码 p_y=99
Step4: 交换特征码生成公共密钥
       A使用公式 p^p_y mod q 计算出对称密钥： 97
       B使用公式 p^p_x mod q 计算出对称密钥： 97

结论：通过这种方式，双方可以得到相同的对称加密的密钥，而在整个传输过程中，由于x和y是不传输的，
所以即便其他所有信息都被别人获利，也无法计算出对称密钥（因为目前在数学上还无人可以解开此问题）。

6 小结

本文就DH的算法进行了详细介绍，并进行了相应的数学证明。另外，还有一块涉及到原根的知识，

引自 http://www.voidcn.com/article/p-rgubrwfd-bpg.html

原根 (Original Root)
我们在上一节例二中讲到，我们选择的(q, p)尽可能的使得当x遍历[1, p -1]时，
bx mod p也遍历了一遍[1, p -1]。我们就来介绍一下原根。
定义1：当 m > 1, gcd(a, m) = 1，则使得 ae mod m = 1成立的最小正整数 e 称作整数 a 对模m的阶（或指数、乘法周期），记做ord(a)。若a的阶=1, 则a称作为模m的原根。
例二中，7模15的阶是4。那15有原根吗？ 显然，根据定义，找出所有和15互素的数，然后计算他们的阶，阶无一例外均不是，故15不存在原根。
现在我们来看看原根的另一个定理，这个定理对于我们找打合适的(q, p)很重要。
定理1：设 m>1m>1，gcd(a,m)=1gcd(a,m) = 1，则 a0,a1,a2,...aord(a)−1a^0, a^1, a^2, ... a^ord(a)-1 模 mm 两两不同余。
反证法证明：如若存在K,L(L<K<ord(a)) 使得 aK=aLa^K = a^L mod m, 由于gcd (a , m)=1，即存在a的逆a−1a^-1，故等式两边乘上a(−L)a^(-L) a(k−l)=1a^(k-l) = 1 mod m, 即存在k-l,使得a(k−l)=1a^(k-l) = 1 mod m等式成立，而k-l < ord(a)，与阶的定义矛盾。故假设不成立。定理1中a和m的关系，我们就可以用来当做DH算法中的(q,p)。
注：RFC 3526 中给出了推荐的DH参数。