迪菲-赫尔曼密钥交换

迪菲-赫尔曼密钥交换（英语：Diffie-Hellman key exchange，缩写为D-H）

迪菲-赫尔曼密钥交换是在美国密码学家惠特菲尔德.迪菲和马丁.赫尔曼的合作下发明的，发表于1976年。它是第一个实用的在非保护信道中创建共享密钥（英语：Shared secret）方法。它受到了瑞夫.墨克的关于公钥分配工作的影响。

迪菲－赫尔曼通过公共信道交换一个信息，就可以创建一个可以用于在公共信道上安全通信的共享秘密（shared secret）。

以下解释它的过程（包括算法的数学部分）：

clip_image002

其中g,p,A,B是公开在网络上传输的，a和b是秘密的。

最早提出的这个协议使用一个素数p的整数模n乘法群以及其原根g。下面展示这个算法，绿色表示非秘密信息, 红色粗体表示秘密信息：

clip_image004

clip_image006

算法理论证明

对上面Alice和Bob秘钥交换问题的解释（下面用A与B分别表示两人） 首先A: a^k1 mod b ≡ c （例子中a=5,b=23） B: a^k2 mod b ≡ d 之后二人交换所得c和d，再次进行运算，我们有 A: d^k1 mod b ≡ c^k2 mod b :B 等价于 A:(a^k2 mod b )^k1 mod b ≡ (a^k1 mod b)^k2 mod b :B 下面我们对上式进行证明，先证明一个引理 假设有 a mod b ≡ n ,则 a^k mod b ≡ n^k mod b 因为 a mod b ≡ n ,则必然存在唯一整数q使得 a=qb+n（带余除法基本定理） 则 a^k=(qb+n)^k= ……（二项式定理展开） 两边同时除以b，我们发现等式右边（二项式展开部分）除去项n^k外，b的次数都大于零 所以除以b的余数必然由n^k这一项产生 所以 a^k mod b ≡ n^k mod b 引理证毕 所以(a mod b)^k= n^k 于是(a mod b)^k mod b ≡ n^k mod b ≡ a^k mod b 所以对于任意的k1,k2 都有下式成立 (a^k1 mod b)^k2 mod b ≡ (a^k1)^k2 mod b ≡(a^k2 mod b)^k1 mod b

补充：二项式展开

(qb+n)^k= C(k,0)(qb)^k

+C(k,1)(qb)^(k-1)*n

+C(k,2)(qb)^(k-2)*n^2

+...

+C(k,k-2)(qb)^2*n^(k-2)

+ C(k,k-1)(qb)*n^(k-1)

+C(k,k)n^k

参考资料

wikipedia

https://zh.wikipedia.org/wiki/%E8%BF%AA%E8%8F%B2-%E8%B5%AB%E7%88%BE%E6%9B%BC%E5%AF%86%E9%91%B0%E4%BA%A4%E6%8F%9B

网易公开课

http://open.163.com/movie/2012/10/K/N/M99VIFJA6_M9EDSGQKN.html