Diffie-Hellman密钥交换算法

以前写的一篇文章,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密钥交换算法中运用的单向函数就是模运算:

f = x mod p

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

Diffie-Hellman密钥交换步骤

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

1.Bob和Jim公开一个生成器a和素数模n, 假设分别为3和17(就是公钥), 这个信息是Bob, Jim和Eve(窃听者)都掌握的. 
2.Bob随机选择一个数, 记为s1, 假设为15(就是私钥), 计算单项函数f(s1) = 3 ^ s1 mod 17的值, 记为ret1(此处为6), 然后发送给Jim. 在这个过程中, Jim得到单项函数的值(6), 窃听者Eve也能截获.
3.Jim也选择一个数, 记为s2, 假设为13(就是私钥), 计算单项函数f(s2) = 3 ^ s2 mod 17的值, 记为ret2(此处为12), 然后发送给Bob. 在这个过程中, Bob得到单项函数的值(12), 窃听者Eve也能截获.
4.定义函数 g1(x) = ret2 ^ x mod p, Bob计算g1(s1)的值作为密钥, 此例中为10(g1(15) = 12 ^ 15 mod 17 = 10).
5. 定义函数 g2(x) = ret1 ^ x mod p, Jim计算g2(s2)的值作为密钥, 此例中为10(g2(13) = 6 ^ 13 mod 17 = 10).

                               Eve   a.掌握公钥(3, 17)
                                |    b.获得单项函数的值(6)
                                |    c.获得单项函数的值(12)
                                |    d.由于缺少信息(私钥)无法计算得到密钥
                                |
                                | 
                                | 
 Bob     -------------------------------------------->      Jim
 a.公开公钥(3, 17)                                       a.掌握公钥(3, 17)
 b.随机选择一个数, 计算单项函数(f(x) = 3 ^ x)的值并发送       b.获得单项函数的值(6)
 c.获得单项函数的值(12)                                    c.随机选择一个数, 计算单项函数(f(x) = 3 ^ x)的值并发送
 d.计算得到密钥                                           d.计算得到密钥

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

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

g1(x) = ( 3^12 mod 17 ) ^ 15 mod 17 = ( 3^12 ) ^ 15 mod 17
g2(x) = ( 3^15 mod 17 ) ^ 12 mod 17 = ( 3^12 ) ^ 15 mod 17

下面证明一般情况.

(a ^ b mod p) ^ c mod p = (a ^ b) ^ c mod p                           (1)

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

首先证明:

(x mod p) ^ y mod p = x ^ y mod p
证明:
(x mod p) ^ y mod p = ((x mod p) * (x mod p) ^ (y - 1)) mod p
                    = (x * (x mod p) ^ (y-1)) mod p
                    = (x * x * (x mod p) ^ (y - 2)) mod p
                    = x ^ y mod p                                   (2)

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