Diffie

以前写的一篇文章,copy过来.

前言

根据百度百科的解释: Diffie-Hellman密钥交换算法是一种确保共享KEY安全穿越不安全网络的方法, 它是OAKLEY的一个组成部分. Whitefield与Martin Hellman在1976年提出了一个奇妙的密钥交换协议, 称为Diffie-Hellman密钥交换协议/算法(Diffie-Hellman Key Exchange/Agreement Algorithm). 这个机制的巧妙在于需要安全通信的双方可以用这个方法确定对称密钥. 然后可以用这个密钥进行加密和解密. 但是注意, 这个密钥交换协议/算法只能用于密钥的交换, 而不能进行消息的加密和解密, 双方确定要用的密钥后, 要使用其他对称密钥操作加密算法实际加密和解密消息.
该算法的基本原理是: 在有限域上计算离散对数非常困难.

单向函数

单向函数(one-way function)的概念是公开密钥密码的中心. 单向函数的基本思想就是单向函数计算起来相对容易, 但求逆却非常困难. 也就是说, 已知x, 我们很容易计算f(x), 但已知f(x), 却难于计算出x.
在Diffie-Hellman密钥交换算法中运用的单向函数就是模运算:

例如, 设p ＝ 7, 已知x = 9, 则f(x) = 2, 非常容易计算. 但是若已知f(x) = 2, 要逆向计算出x, 几乎是不可能的, 因为x的可能性非常多.

Diffie-Hellman密钥交换步骤

假设Bob和Jim需要交换密钥, 而中间有一个Eve在窃听, 其基本步骤如下(下文中'^'表示多少次方):

在整个过程中, Bob和Jim得出的密钥是一致的, 因此双方可以用共享的密钥来加密. 而窃听者Eve由于没有私钥信息, 无法计算出密钥. 其中较为关键的一点是:

第四步Bob计算的密钥和第五步Jim计算的密钥一定是一致的. 在此例中:

下面证明一般情况.

其中, a和p是公开的公钥, b是Bob生成的随机数(私钥), c是Jim生成的随机数(私钥).

首先证明:

利用式(2)可以很容易的证明式(1).