【表哥有话说 第91期】Diffie-Hellman密钥交换算法

Diffie-Hellman

密钥交换算法

 嗨嗨嗨！

表哥又带着他的周分享来啦~

这周我们聊密钥算法  快搬好小板凳听吧

简介

Diffie-Hellman（中文名叫迪菲-赫尔曼密钥交换算法，以下简称为DH算法），这种交换算法由惠特菲尔德·迪菲（Bailey Whitfield Diffie）和马丁·赫尔曼（Martin Edward Hellman）在1976年首次提出，是一种基于离散对数问题的公钥密钥交换算法。它能够使得通信双方在一个所有通信信息都泄露的情况下，安全地完成一次密钥交换过程，使得通信双方获得一段相同的没有被泄露过的信息。是不是感觉不可能，但是先前的数学家确实做到了，很神奇吧，有时候数学就是这么神奇。

安全性

那这个算法的安全性是如何保证的呢，下面就来好好讲一下。讲到DH算法的安全性，就不得不先讲一下公钥密码的安全性。而谈公钥密码的安全性，就避不开一个重要的数学概念——陷门函数。陷门函数（trapdoor function）是指一类特殊的数学函数，特点是再一个方向上容易计算，但逆推这个计算过程却极其复杂。具体来讲，如果设$f(x)$为陷门函数，对于给定$x$值计算$f(x)$的值比较容易，而对于给定$f(x)$的值，计算$x$的值，则相对复杂。而能够设计为公钥密码的陷门函数必须满足：

1. 1. 正向容易求解，且可以被设计为计算机程序

2. 2. 逆向不容易求解，求解过程不能够简化，且在一段较长的时间内一般求解不出来（这个时间一般是几十年） 对于满足上述条件的尤其是求解过程不能简化的陷门函数，其实并没有几个。像大整数分解、离散对数求解、椭圆曲线上的离散对数、奇异椭圆曲线等目前没有行之有效的求解算法的问题才能作为现代密码学的陷门函数。DH算法基于离散对数这个数学难题，目前还没有公布出能够在可接受的时间内求解的算法，所以安全性是可以保障的。值得注意的是，虽然当前离散对数是相对安全的，但是在某些特定的条件下，离散对数是可以被在可接受的时间内求解的，在具体的使用过程一定要实际了解离散对数参数如何选取，保证算法的安全性。

数学基础

密码总是和数学密不可分，当然DH算法也不例外，不过虽然DH算法作为现代密码学的一部分，但其实其中的数学原理并不复杂。保证其安全性的离散对数可以被分为两个部分，一个是“离散”，另一个则是“对数”。“离散”即为不连续的，对应到数学上则是模运算——只在有限个整数上进行的运算。模运算可以简单理解为在每次计算后都进行出$p$求余的运算，并用除$p$求余的结果代替运算的结果。且先代替运算的两个数再计算，和先计算再用模$p$求余的结果去代替，其实两者的结果都是不变的。这个$p$则可以确定有限个整数是多少个，且在模运算进行之前就需要指明。简单的举个例子，在模11的条件下，计算$2 times 3$的结果 $2 times 3 = 12 newline 12 div 11 = 1 cdotcdotcdot 1 $ 由上述的运算可知：$2 times 3 equiv 1 pmod {11}$，其中“$equiv$”是等价开的含义，在模运算中可以理解为“等于”，在模运算中的加法和减法同理。而离散对数的“对数”问题和乘方问题是逆运算，而DH算法的陷门函数正方向的计算就是模运算上的乘方运算。想想一下模运算中的乘方运算，则是多个相同的数进行累乘，但当乘方运算的指数过大时，使用累乘的方法会大大降低算法的运行效率，这样计算正方向计算也会比较缓慢，时间是达不到陷门函数的要求的。那有没有一种办法加速模运算中的成乘方运算呢，答案是有的。给出个例题——求解$a ^ b pmod p$的结果，说明一下乘方运算是如何加速的：先将b转换成一个n位二进制形式，即$b = b_{n} times 2^{n-1} + ··· +b_2 times 2^1 + b_1 times 2^0$。将结果设为0，$a$不断增倍，如果$b_k$等于1，则结果加上$a$第$k$次增倍的结果。当遍历完n个$b_i$时，就得到$a^b pmod p$的结果。反观对数问题，并没有这样的加速算法，求解离散对数问题，只能采用暴力搜索或者类似暴力搜索的方法进行求解。这就满足了陷门函数的特点，可以保证安全性。

算法模型

采用经典的Alice、Bob模型进行解释

1. 1. Alice、Bob两人处在不安全的通信条件下，可以通信，但是通信内容都会被截获。

2. 2. Alice、Bob协商一个整数$p$和一个整数$g$，两者都可以公开。

3. 3. Alice选择一个整数$a$作为私钥，并计算$A = g^apmod p$，并将结果$A$发送给Bob。

4. 4. Bob也选择一个整数$b$作为私钥，也计算$B = g^b pmod p$，并将结果B发送给Alice。

5. 5. Alice收到$B$，计算$ B^a pmod p$得到公共的密钥。

6. 6. Bob收到$A$，计算$A^bpmod p$得到公共的密钥。

算法原理

Alice得到的公共的密钥：$B^apmod p equiv (g^b)^a pmod p equiv g^{ab} pmod p$ Bob得到的公共密钥：$A^bpmod p equiv (g^a)^b pmod p equiv g^{ab} pmod p$ 能够说明算法是Alice和Bob获得了相同的密钥，且截获两者通信的信息$A、B、g、p$，并不能绕开离散对数问题，计算得到$g^{ab}pmod p$。

---

下面用程序简单的实现一下这个过程

from random import randint
from Crypto.Util.number import getPrime

# 协定两个整数
p = getPrime(1024)
g = getPrime(24)
# Alice这边
    # 选取随机私钥
a = randint(1,p)
    # 计算A
A = pow(g,a,p)
# Alice将（g,p,A）发送给Bob

# Bob这边，接收（g,p,A）
    # 选取随机私钥
b = randint(1,p)
shared_key = pow(A,b,p)
B = pow(g,b,p)
# Bob将(B)发送给Alice

# Alice接收B
shared_key = pow(B,a,p)

本期学习分享到此结束

 好好消化哦 

 表哥下期的干货已经在等你啦

          记得长按下方二维码关注我们啊啊啊

原文始发于微信公众号（SKSEC）：【表哥有话说 第91期】Diffie-Hellman密钥交换算法