概述

两个人在互联网上去传递机密信息，需要双方共用一个相同的密钥，而互联网是一个不安全的环境，所以双方如何安全的互换秘钥就成了大问题。Diffie–Hellman 密钥交换方法就是一套解决方案，可以让大家在不安全的通道内安全的互换密钥。

离散对数问题

我们经常会听见求解离散对数是很困难的事情，但是什么是离散对数？

先看一下对数是什么：

$a^i=b$，i就是以a为底的b的对数，记做 $i=log_ab$

而在模运算中也有类似的函数，是$ind_{a,p}(b)$。

设p是一个素数，a是p的一个本原根(即生成元)，则 $a^1,a^2,a^3...a^{p-1}$在模p后产生出1到p-1的数，每个值仅出现一次。因此对任意的1<=b<=p-1，都存在唯一的i，使得 $b=a^i$%p，我们称i就是模p下以a为底b的指标，记做 $i = ind_{a,p}(b)$，这就是离散对数

举个例子，p = 11, a = 2;

则 $a^i$%p的序列为：2 4 8 5 10 9 7 3 6 1

总的来说：

$a^i$%p = b

当给定大素数 p, 本原根 a，以及一个 b时求解 i 是非常困难的

Diffie-Hellman密钥交换

Diffie-Hellman密钥交换就是利用求解离散对数的困难性来设计的

Diffie-Hellman密钥交换的原理

• 通信双方A和B约定一个大素数p,和一个本原根(即生成元)g，这都是可以公开的，被别人知道了也没关系
• A自己随便取一个a，B也自己随便取一个b，a和b是不可以泄漏的，只有本人知道
• 然后A计算 $aa = g^a$%p,B计算 $bb = g^b$%p，并进行交换，交换的结果也可以公开
• A再求 ${bb}^a$,B再求 $aa^b$，会发现 $bb^a=aa^b$ ，记做K，这个K就可以作为两个人独享的共享密钥

安全性问题

我们从外人的角度来看看如何获取他们的密钥

已知的是p,g,aa,bb，想得K，就需要知道a或者b，但是我们上面解释了，求a,b的问题是一个求解离散对数的问题，可以认为在大素数的情况下是不可解的，所以就不能侦破K,所以是安全的