基礎知識:什么是素數(shù)的原根?
原根Primitive Root
g^i mod p ≠ g^j mod p
其中i≠j且i, j介於1至(p-1)之間
則g為p的原根。
mod讀“模”， mod n的意思是除以n的余數(shù)。
如： 10 mod 3 =1 13 mod 5 =3
首次發(fā)表的公開密鑰算法出現(xiàn)在Diffie和Hellman的論文中，這篇影響深遠的論文奠定了公開密鑰密碼編碼學。由于該算法本身限于密鑰交換的用途，被許多商用產(chǎn)品用作密鑰交換技術，因此該算法通常稱之為Diffie-Hellman密鑰交換。這種密鑰交換技術的目的在于使得兩個用戶安全地交換一個秘密密鑰以便用于以后的報文加密。
Diffie-Hellman密鑰交換算法的有效性依賴于計算離散對數(shù)的難度。簡言之，可以如下定義離散對數(shù)：首先定義一個素數(shù)p的原根，為其各次冪產(chǎn)生從1 到p-1的所有整數(shù)根，也就是說，如果a是素數(shù)p的一個原根，那么數(shù)值
a mod p, a2 mod p, ..., ap-1
mod p
是各不相同的整數(shù)，并且以某種排列方式組成了從1到p-1的所有整數(shù)。
對于一個整數(shù)b和素數(shù)p的一個原根a，可以找到惟一的指數(shù)i，使得
b = ai mod p
其中0 ≤ i ≤ (p-1)
指數(shù)i稱為b的以a為基數(shù)的模p的離散對數(shù)或者指數(shù)。該值被記為inda ,p(b)。
基于此背景知識，可以定義Diffie-Hellman密鑰交換算法。該算法描述如下：
1、有兩個全局公開的參數(shù)，一個素數(shù)q和一個整數(shù)a，a是q的一個原根。
2、假設用戶A和B希望交換一個密鑰，用戶A選擇一個作為私有密鑰的隨機數(shù)XA<q，并計算公開密鑰YA=aXA mod q。A對XA的值保密存放而使YA能被B公開獲得。類似地，用戶B選擇一個私有的隨機數(shù)XB<q，并計算公開密鑰YB=aXB mod q。B對XB的值保密存放而使YB能被A公開獲得。
3、用戶A產(chǎn)生共享秘密密鑰的計算方式是K = (YB)XA mod q。同樣，用戶B產(chǎn)生共享秘密密鑰的計算是K = (YA)XB mod q。這兩個計算產(chǎn)生相同的結果：
K = (YB)XA mod q
= (aXB mod q)XA mod q
= (aXB)XA mod q （根據(jù)取模運算規(guī)則得到）
= aXBXA mod q
= (aXA)XB mod q
= (aXA mod q)XB mod q
= (YA)XB mod q
因此相當于雙方已經(jīng)交換了一個相同的秘密密鑰。
4、因為XA和XB是保密的，一個敵對方可以利用的參數(shù)只有q、a、YA和YB。因而敵對方被迫取離散對數(shù)來確定密鑰。例如，要獲取用戶B的秘密密鑰，敵對方必須先計算
XB = inda ,q(YB)
然后再使用用戶B采用的同樣方法計算其秘密密鑰K。
Diffie-Hellman密鑰交換算法的安全性依賴于這樣一個事實：雖然計算以一個素數(shù)為模的指數(shù)相對容易，但計算離散對數(shù)卻很困難。對于大的素數(shù)，計算出離散對數(shù)幾乎是不可能的。
下面給出例子。密鑰交換基于素數(shù)q = 97和97的一個原根a = 5。A和B分別選擇私有密鑰XA
= 36和XB
= 58。每人計算其公開密鑰
YA = 536 = 50 mod 97
YB = 558 = 44 mod 97
在他們相互獲取了公開密鑰之后，各自通過計算得到雙方共享的秘密密鑰如下：
K = (YB)XA mod 97 = 4436 = 75 mod 97
K = (YA)XB mod 97 = 5058 = 75 mod 97
從|50，44|出發(fā)，攻擊者要計算出75很不容易。
假設用戶A希望與用戶B建立一個連接，并用一個共享的秘密密鑰加密在該連接上傳輸?shù)膱笪摹Ｓ脩?/span>A產(chǎn)生一個一次性的私有密鑰XA，并計算出公開密鑰YA并將其發(fā)送給用戶B。用戶B產(chǎn)生一個私有密鑰XB，計算出公開密鑰YB并將它發(fā)送給用戶A作為響應。必要的公開數(shù)值q和a都需要提前知道。另一種方法是用戶A選擇q和a的值，并將這些數(shù)值包含在第一個報文中。
下面再舉一個使用Diffie-Hellman算法的例子。假設有一組用戶（例如一個局域網(wǎng)上的所有用戶），每個人都產(chǎn)生一個長期的私有密鑰XA，并計算一個公開密鑰YA。這些公開密鑰數(shù)值，連同全局公開數(shù)值q和a都存儲在某個中央目錄中。在任何時刻，用戶B都可以訪問用戶A 的公開數(shù)值，計算一個秘密密鑰，并使用這個密鑰發(fā)送一個加密報文給A。如果中央目錄是可信任的，那么這種形式的通信就提供了保密性和一定程度的鑒別功能。因為只有A和B可以確定這個密鑰，其它用戶都無法解讀報文（保密性）。接收方A知道只有用戶B才能使用此密鑰生成這個報文（鑒別）。
Diffie-Hellman算法具有兩個吸引力的特征：
1、僅當需要時才生成密鑰，減小了將密鑰存儲很長一段時間而致使遭受攻擊的機會。
2、除對全局參數(shù)的約定外，密鑰交換不需要事先存在的基礎結構。
然而，該技術也存在許多不足：
1、沒有提供雙方身份的任何信息。
2、它是計算密集性的，因此容易遭受阻塞性攻擊，即對手請求大量的密鑰。受攻擊者花費了相對多的計算資源來求解無用的冪系數(shù)而不是在做真正的工作。
3、沒辦法防止重演攻擊。
4、容易遭受中間人的攻擊。第三方C在和A通信時扮演B；和B通信時扮演A。A和B都與C協(xié)商了一個密鑰，然后C就可以監(jiān)聽和傳遞通信量。中間人的攻擊按如下進行：
（1）B在給A的報文中發(fā)送他的公開密鑰。
（2）C截獲并解析該報文。C將B的公開密鑰保存下來并給A發(fā)送報文，該報文具有B的用戶ID但使用C的公開密鑰YC，仍按照好像是來自B的樣子被發(fā)送出去。A收到C的報文后，將YC和B的用戶ID存儲在一塊。類似地，C使用YC向B發(fā)送好像來自A的報文。
（3）B基于私有密鑰XB和YC計算秘密密鑰K1。A基于私有密鑰XA和YC計算秘密密鑰K2。C使用私有密鑰XC和YB計算K1，并使用XC和YA計算K2。
（4）從現(xiàn)在開始，C就可以轉(zhuǎn)發(fā)A發(fā)給B的報文或轉(zhuǎn)發(fā)B發(fā)給A的報文，在途中根據(jù)需要修改它們的密文。使得A和B都不知道他們在和C共享通信。
Oakley算法是對Diffie-Hellman密鑰交換算法的優(yōu)化，它保留了后者的優(yōu)點，同時克服了其弱點。
Oakley算法具有五個重要特征：
1、它采用稱為cookie程序的機制來對抗阻塞攻擊。
2、它使得雙方能夠協(xié)商一個全局參數(shù)集合。
3、它使用了現(xiàn)時來保證抵抗重演攻擊。
4、它能夠交換Diffie-Hellman公開密鑰。
5、它對Diffie-Hellman交換進行鑒別以對抗中間人的攻擊。
Oakley可以使用三個不同的鑒別方法：
1、數(shù)字簽名：通過簽署一個相互可以獲得的散列代碼來對交換進行鑒別；每一方都使用自己的私鑰對散列代碼加密。散列代碼是在一些重要參數(shù)上生成的，如用戶ID和現(xiàn)時。
2、公開密鑰加密：通過使用發(fā)送者的私鑰對諸如ID和現(xiàn)時等參數(shù)進行加密來鑒別交換。
3、對稱密鑰加密：通過使用某種共享密鑰對交換參數(shù)進行對稱加密，實現(xiàn)交換的鑒別。
（楊獻春 編撰）