以前寫(xiě)的一篇文章,copy過(guò)來(lái).
前言
根據(jù)百度百科的解釋: Diffie-Hellman密鑰交換算法是一種確保共享KEY安全穿越不安全網(wǎng)絡(luò)的方法, 它是OAKLEY的一個(gè)組成部分. Whitefield與Martin Hellman在1976年提出了一個(gè)奇妙的密鑰交換協(xié)議, 稱為Diffie-Hellman密鑰交換協(xié)議/算法(Diffie-Hellman Key Exchange/Agreement Algorithm). 這個(gè)機(jī)制的巧妙在于需要安全通信的雙方可以用這個(gè)方法確定對(duì)稱密鑰. 然后可以用這個(gè)密鑰進(jìn)行加密和解密. 但是注意, 這個(gè)密鑰交換協(xié)議/算法只能用于密鑰的交換, 而不能進(jìn)行消息的加密和解密, 雙方確定要用的密鑰后, 要使用其他對(duì)稱密鑰操作加密算法實(shí)際加密和解密消息.
該算法的基本原理是: 在有限域上計(jì)算離散對(duì)數(shù)非常困難.
單向函數(shù)
單向函數(shù)(one-way function)的概念是公開(kāi)密鑰密碼的中心. 單向函數(shù)的基本思想就是單向函數(shù)計(jì)算起來(lái)相對(duì)容易, 但求逆卻非常困難. 也就是說(shuō), 已知x, 我們很容易計(jì)算f(x), 但已知f(x), 卻難于計(jì)算出x.
在Diffie-Hellman密鑰交換算法中運(yùn)用的單向函數(shù)就是模運(yùn)算:
f = x mod p
例如, 設(shè)p ＝ 7, 已知x = 9, 則f(x) = 2, 非常容易計(jì)算. 但是若已知f(x) = 2, 要逆向計(jì)算出x, 幾乎是不可能的, 因?yàn)閤的可能性非常多.
Diffie-Hellman密鑰交換步驟
假設(shè)Bob和Jim需要交換密鑰, 而中間有一個(gè)Eve在竊聽(tīng), 其基本步驟如下(下文中'^'表示多少次方):
1.Bob和Jim公開(kāi)一個(gè)生成器a和素?cái)?shù)模n, 假設(shè)分別為3和17(就是公鑰), 這個(gè)信息是Bob, Jim和Eve(竊聽(tīng)者)都掌握的.
2.Bob隨機(jī)選擇一個(gè)數(shù), 記為s1, 假設(shè)為15(就是私鑰), 計(jì)算單項(xiàng)函數(shù)f(s1) = 3 ^ s1 mod 17的值, 記為ret1(此處為6), 然后發(fā)送給Jim. 在這個(gè)過(guò)程中, Jim得到單項(xiàng)函數(shù)的值(6), 竊聽(tīng)者Eve也能截獲.
3.Jim也選擇一個(gè)數(shù), 記為s2, 假設(shè)為13(就是私鑰), 計(jì)算單項(xiàng)函數(shù)f(s2) = 3 ^ s2 mod 17的值, 記為ret2(此處為12), 然后發(fā)送給Bob. 在這個(gè)過(guò)程中, Bob得到單項(xiàng)函數(shù)的值(12), 竊聽(tīng)者Eve也能截獲.
4.定義函數(shù) g1(x) = ret2 ^ x mod p, Bob計(jì)算g1(s1)的值作為密鑰, 此例中為10(g1(15) = 12 ^ 15 mod 17 = 10).
5. 定義函數(shù) g2(x) = ret1 ^ x mod p, Jim計(jì)算g2(s2)的值作為密鑰, 此例中為10(g2(13) = 6 ^ 13 mod 17 = 10).
Eve a.掌握公鑰(3, 17)
| b.獲得單項(xiàng)函數(shù)的值(6)
| c.獲得單項(xiàng)函數(shù)的值(12)
| d.由于缺少信息(私鑰)無(wú)法計(jì)算得到密鑰
|
|
|
Bob --------------------------------------------> Jim
a.公開(kāi)公鑰(3, 17) a.掌握公鑰(3, 17)
b.隨機(jī)選擇一個(gè)數(shù), 計(jì)算單項(xiàng)函數(shù)(f(x) = 3 ^ x)的值并發(fā)送 b.獲得單項(xiàng)函數(shù)的值(6)
c.獲得單項(xiàng)函數(shù)的值(12) c.隨機(jī)選擇一個(gè)數(shù), 計(jì)算單項(xiàng)函數(shù)(f(x) = 3 ^ x)的值并發(fā)送
d.計(jì)算得到密鑰 d.計(jì)算得到密鑰
在整個(gè)過(guò)程中, Bob和Jim得出的密鑰是一致的, 因此雙方可以用共享的密鑰來(lái)加密. 而竊聽(tīng)者Eve由于沒(méi)有私鑰信息, 無(wú)法計(jì)算出密鑰. 其中較為關(guān)鍵的一點(diǎn)是:
第四步Bob計(jì)算的密鑰和第五步Jim計(jì)算的密鑰一定是一致的. 在此例中:
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是公開(kāi)的公鑰, b是Bob生成的隨機(jī)數(shù)(私鑰), c是Jim生成的隨機(jī)數(shù)(私鑰).
首先證明:
(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).
