Diffie-Hellman
密钥交换算法及其优化
首次发表的公开密钥算法出现在
Diffie
和
Hellman
的论文中，这篇影响深远的论文奠定了公开密钥密码编码学。由于该算法本身限于密钥交换的用途，被许多商用产品用作密钥交换技术，因此该算法通常称之为
Diffie-Hellman
密钥交换。这种密钥交换技术的目的在于使得两个用户安全地交换一个秘密密钥以便用于以后的报文加密。
Diffie-Hellman
密钥交换算法的有效性依赖于计算离散对数的难度。简言之，可以如下定义离散对数：首先定义一个素数
p
的原根，为其各次幂产生从
1
到
p
-1
的所有整数根，也就是说，如果
a
是素数
p
的一个原根，那么数值
a
mod
p
,
a
2
mod
p
, ...,
a
p-1
mod
p
是各不相同的整数，并且以某种排列方式组成了从
1
到
p
-1
的所有整数。
对于一个整数
b
和素数
p
的一个原根
a
，可以找到惟一的指数
i
，使得
b
=
a
i
mod
p
其中
0 ≤
i
≤ (
p
-1)
指数
i
称为
b
的以
a
为基数的模
p
的离散对数或者指数。该值被记为
ind
a ,p
(b)
。
基于此背景知识，可以定义
Diffie-Hellman
密钥交换算法。该算法描述如下：
1
、有两个全局公开的参数，一个素数
q
和一个整数
a
，
a
是
q
的一个原根。
2
、假设用户
A
和
B
希望交换一个密钥，用户
A
选择一个作为私有密钥的随机数
X
A
<
q
，并计算公开密钥
Y
A
=
a
X
A
mod
q
。
A
对
X
A
的值保密存放而使
Y
A
能被
B
公开获得。类似地，用户
B
选择一个私有的随机数
X
B
<
q
，并计算公开密钥
Y
B
=
a
X
B
mod
q
。
B
对
X
B
的值保密存放而使
Y
B
能被
A
公开获得。
3
、用户
A
产生共享秘密密钥的计算方式是
K = (Y
B
)
X
A
mod
q
。同样，用户
B
产生共享秘密密钥的计算是
K = (Y
A
)
X
B
mod
q
。这两个计算产生相同的结果：
K = (Y
B
)
X
A
mod
q
= (
a
X
B
mod
q
)
X
A
mod
q
= (
a
X
B
)
X
A
mod
q
（根据取模运算规则得到）
=
a
X
B
X
A
mod
q
= (
a
X
A
)
X
B
mod
q
= (
a
X
A
mod
q
)
X
B
mod
q
= (Y
A
)
X
B
mod
q
因此相当于双方已经交换了一个相同的秘密密钥。
4
、因为
X
A
和
X
B
是保密的，一个敌对方可以利用的参数只有
q
、
a
、
Y
A
和
Y
B
。因而敌对方被迫取离散对数来确定密钥。例如，要获取用户
B
的秘密密钥，敌对方必须先计算
X
B
= ind
a
,q
(Y
B
)
然后再使用用户
B
采用的同样方法计算其秘密密钥
K
。
Diffie-Hellman
密钥交换算法的安全性依赖于这样一个事实：虽然计算以一个素数为模的指数相对容易，但计算离散对数却很困难。对于大的素数，计算出离散对数几乎是不可能的。
下面给出例子。密钥交换基于素数
q
= 97
和
97
的一个原根
a
= 5
。
A
和
B
分别选择私有密钥
X
A
= 36
和
X
B
= 58
。每人计算其公开密钥
Y
A
=
5
36
= 50 mod 97
Y
B
=
5
58
= 44 mod 97
在他们相互获取了公开密钥之后，各自通过计算得到双方共享的秘密密钥如下：
K = (Y
B
)
X
A
mod 97 = 44
36
= 75 mod 97
K = (Y
A
)
X
B
mod 97 = 50
58
= 75 mod 97
从
|50
，
44|
出发，攻击者要计算出
75
很不容易。
下图给出了一个利用
Diffie-Hellman
计算的简单协议。
假设用户
A
希望与用户
B
建立一个连接，并用一个共享的秘密密钥加密在该连接上传输的报文。用户
A
产生一个一次性的私有密钥
X
A
，并计算出公开密钥
Y
A
并将其发送给用户
B
。用户
B
产生一个私有密钥
X
B
，计算出公开密钥
Y
B
并将它发送给用户
A
作为响应。必要的公开数值
q
和
a
都需要提前知道。另一种方法是用户
A
选择
q
和
a
的值，并将这些数值包含在第一个报文中。
下面再举一个使用
Diffie-Hellman
算法的例子。假设有一组用户（例如一个局域网上的所有用户），每个人都产生一个长期的私有密钥
X
A
，并计算一个公开密钥
Y
A
。这些公开密钥数值，连同全局公开数值
q
和
a
都存储在某个中央目录中。在任何时刻，用户
B
都可以访问用户
A
的公开数值，计算一个秘密密钥，并使用这个密钥发送一个加密报文给
A
。如果中央目录是可信任的，那么这种形式的通信就提供了保密性和一定程度的鉴别功能。因为只有
A
和
B
可以确定这个密钥，其它用户都无法解读报文（保密性）。接收方
A
知道只有用户
B
才能使用此密钥生成这个报文（鉴别）。
Diffie-Hellman
算法具有两个吸引力的特征：
1、
仅当需要时才生成密钥，减小了将密钥存储很长一段时间而致使遭受攻击的机会。
2、
除对全局参数的约定外，密钥交换不需要事先存在的基础结构。
然而，该技术也存在许多不足：
1、
没有提供双方身份的任何信息。
2、
它是计算密集性的，因此容易遭受阻塞性攻击，即对手请求大量的密钥。受攻击者花费了相对多的计算资源来求解无用的幂系数而不是在做真正的工作。
3、
没办法防止重演攻击。
4、
容易遭受中间人的攻击。第三方
C
在和
A
通信时扮演
B
；和
B
通信时扮演
A
。
A
和
B
都与
C
协商了一个密钥，然后
C
就可以监听和传递通信量。中间人的攻击按如下进行：
（1）
B
在给
A
的报文中发送他的公开密钥。
（2）
C
截获并解析该报文。
C
将
B
的公开密钥保存下来并给
A
发送报文，该报文具有
B
的用户
ID
但使用
C
的公开密钥
Y
C
，仍按照好像是来自
B
的样子被发送出去。
A
收到
C
的报文后，将
Y
C
和
B
的用户
ID
存储在一块。类似地，
C
使用
Y
C
向
B
发送好像来自
A
的报文。
（3）
B
基于私有密钥
X
B
和
Y
C
计算秘密密钥
K
1
。
A
基于私有密钥
X
A
和
Y
C
计算秘密密钥
K
2
。
C
使用私有密钥
X
C
和
Y
B
计算
K
1
，并使用
X
C
和
Y
A
计算
K
2
。
（4）
从现在开始，
C
就可以转发
A
发给
B
的报文或转发
B
发给
A
的报文，在途中根据需要修改它们的密文。使得
A
和
B
都不知道他们在和
C
共享通信。
Oakley
算法是对
Diffie-Hellman
密钥交换算法的优化，它保留了后者的优点，同时克服了其弱点。
Oakley
算法具有五个重要特征：
1、
它采用称为
cookie
程序的机制来对抗阻塞攻击。
2、
它使得双方能够协商一个全局参数集合。
3、
它使用了现时来保证抵抗重演攻击。
4、
它能够交换
Diffie-Hellman
公开密钥。
5、
它对
Diffie-Hellman
交换进行鉴别以对抗中间人的攻击。
Oakley
可以使用三个不同的鉴别方法：
1、
数字签名：通过签署一个相互可以获得的散列代码来对交换进行鉴别；每一方都使用自己的私钥对散列代码加密。散列代码是在一些重要参数上生成的，如用户
ID
和现时。
2、
公开密钥加密：通过使用发送者的私钥对诸如
ID
和现时等参数进行加密来鉴别交换。
3、
对称密钥加密：通过使用某种共享密钥对交换参数进行对称加密，实现交换的鉴别。
（
杨献春
编撰
）
