心有多大舞臺(tái)便有多大

基礎(chǔ)知識(shí):什么是素?cái)?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的論文中，這篇影響深遠(yuǎn)的論文奠定了公開密鑰密碼編碼學(xué)。由于該算法本身限于密鑰交換的用途，被許多商用產(chǎn)品用作密鑰交換技術(shù)，因此該算法通常稱之為Diffie-Hellman密鑰交換。這種密鑰交換技術(shù)的目的在于使得兩個(gè)用戶安全地交換一個(gè)秘密密鑰以便用于以后的報(bào)文加密。

Diffie-Hellman密鑰交換算法的有效性依賴于計(jì)算離散對(duì)數(shù)的難度。簡言之，可以如下定義離散對(duì)數(shù)：首先定義一個(gè)素?cái)?shù)p的原根，為其各次冪產(chǎn)生從1 到p-1的所有整數(shù)根，也就是說，如果a是素?cái)?shù)p的一個(gè)原根，那么數(shù)值

                  a mod p, a² mod p, ..., a^p-1 mod p

是各不相同的整數(shù)，并且以某種排列方式組成了從1到p-1的所有整數(shù)。

對(duì)于一個(gè)整數(shù)b和素?cái)?shù)p的一個(gè)原根a，可以找到惟一的指數(shù)i，使得

                  b = aⁱ mod p     其中0 ≤ i ≤ (p-1)

指數(shù)i稱為b的以a為基數(shù)的模p的離散對(duì)數(shù)或者指數(shù)。該值被記為ind_{a ,p}(b)。

基于此背景知識(shí)，可以定義Diffie-Hellman密鑰交換算法。該算法描述如下：

1、有兩個(gè)全局公開的參數(shù)，一個(gè)素?cái)?shù)q和一個(gè)整數(shù)a，a是q的一個(gè)原根。

2、假設(shè)用戶A和B希望交換一個(gè)密鑰，用戶A選擇一個(gè)作為私有密鑰的隨機(jī)數(shù)X_A<q，并計(jì)算公開密鑰Y_A=a^XA mod q。A對(duì)X_A的值保密存放而使Y_A能被B公開獲得。類似地，用戶B選擇一個(gè)私有的隨機(jī)數(shù)X_B<q，并計(jì)算公開密鑰Y_B=a^XB mod q。B對(duì)X_B的值保密存放而使Y_B能被A公開獲得。

3、用戶A產(chǎn)生共享秘密密鑰的計(jì)算方式是K = (Y_B)^XA mod q。同樣，用戶B產(chǎn)生共享秘密密鑰的計(jì)算是K = (Y_A)^XB mod q。這兩個(gè)計(jì)算產(chǎn)生相同的結(jié)果：

              K = (Y_B)^XA mod q

                = (a^XB mod q)^XA mod q

                = (a^XB)^XA mod q                   （根據(jù)取模運(yùn)算規(guī)則得到）

                = a^XBXA mod q

                = (a^XA)^XB mod q

                = (a^XA mod q)^XB mod q

                = (Y_A)^XB mod q

因此相當(dāng)于雙方已經(jīng)交換了一個(gè)相同的秘密密鑰。

4、因?yàn)?/span>X_A和X_B是保密的，一個(gè)敵對(duì)方可以利用的參數(shù)只有q、a、Y_A和Y_B。因而敵對(duì)方被迫取離散對(duì)數(shù)來確定密鑰。例如，要獲取用戶B的秘密密鑰，敵對(duì)方必須先計(jì)算

               X_B = ind_{a ,q}(Y_B)

然后再使用用戶B采用的同樣方法計(jì)算其秘密密鑰K。

Diffie-Hellman密鑰交換算法的安全性依賴于這樣一個(gè)事實(shí)：雖然計(jì)算以一個(gè)素?cái)?shù)為模的指數(shù)相對(duì)容易，但計(jì)算離散對(duì)數(shù)卻很困難。對(duì)于大的素?cái)?shù)，計(jì)算出離散對(duì)數(shù)幾乎是不可能的。

下面給出例子。密鑰交換基于素?cái)?shù)q = 97和97的一個(gè)原根a = 5。A和B分別選擇私有密鑰X_A = 36和X_B = 58。每人計(jì)算其公開密鑰

                Y_A = 5³⁶ = 50 mod 97

                Y_B = 5⁵⁸ = 44 mod 97

在他們相互獲取了公開密鑰之后，各自通過計(jì)算得到雙方共享的秘密密鑰如下：

                    K = (Y_B)^XA mod 97 = 44³⁶ = 75 mod 97

                    K = (Y_A)^XB mod 97 = 50⁵⁸ = 75 mod 97

從|50，44|出發(fā)，攻擊者要計(jì)算出75很不容易。  

假設(shè)用戶A希望與用戶B建立一個(gè)連接，并用一個(gè)共享的秘密密鑰加密在該連接上傳輸?shù)膱?bào)文。用戶A產(chǎn)生一個(gè)一次性的私有密鑰XA，并計(jì)算出公開密鑰Y_A并將其發(fā)送給用戶B。用戶B產(chǎn)生一個(gè)私有密鑰XB，計(jì)算出公開密鑰Y_B并將它發(fā)送給用戶A作為響應(yīng)。必要的公開數(shù)值q和a都需要提前知道。另一種方法是用戶A選擇q和a的值，并將這些數(shù)值包含在第一個(gè)報(bào)文中。

下面再舉一個(gè)使用Diffie-Hellman算法的例子。假設(shè)有一組用戶（例如一個(gè)局域網(wǎng)上的所有用戶），每個(gè)人都產(chǎn)生一個(gè)長期的私有密鑰XA，并計(jì)算一個(gè)公開密鑰Y_A。這些公開密鑰數(shù)值，連同全局公開數(shù)值q和a都存儲(chǔ)在某個(gè)中央目錄中。在任何時(shí)刻，用戶B都可以訪問用戶A 的公開數(shù)值，計(jì)算一個(gè)秘密密鑰，并使用這個(gè)密鑰發(fā)送一個(gè)加密報(bào)文給A。如果中央目錄是可信任的，那么這種形式的通信就提供了保密性和一定程度的鑒別功能。因?yàn)橹挥?/span>A和B可以確定這個(gè)密鑰，其它用戶都無法解讀報(bào)文（保密性）。接收方A知道只有用戶B才能使用此密鑰生成這個(gè)報(bào)文（鑒別）。

Diffie-Hellman算法具有兩個(gè)吸引力的特征：

1、僅當(dāng)需要時(shí)才生成密鑰，減小了將密鑰存儲(chǔ)很長一段時(shí)間而致使遭受攻擊的機(jī)會(huì)。

2、除對(duì)全局參數(shù)的約定外，密鑰交換不需要事先存在的基礎(chǔ)結(jié)構(gòu)。

然而，該技術(shù)也存在許多不足：

1、沒有提供雙方身份的任何信息。

2、它是計(jì)算密集性的，因此容易遭受阻塞性攻擊，即對(duì)手請(qǐng)求大量的密鑰。受攻擊者花費(fèi)了相對(duì)多的計(jì)算資源來求解無用的冪系數(shù)而不是在做真正的工作。

3、沒辦法防止重演攻擊。

4、容易遭受中間人的攻擊。第三方C在和A通信時(shí)扮演B；和B通信時(shí)扮演A。A和B都與C協(xié)商了一個(gè)密鑰，然后C就可以監(jiān)聽和傳遞通信量。中間人的攻擊按如下進(jìn)行：

（1）B在給A的報(bào)文中發(fā)送他的公開密鑰。

（2）C截獲并解析該報(bào)文。C將B的公開密鑰保存下來并給A發(fā)送報(bào)文，該報(bào)文具有B的用戶ID但使用C的公開密鑰Y_C，仍按照好像是來自B的樣子被發(fā)送出去。A收到C的報(bào)文后，將Y_C和B的用戶ID存儲(chǔ)在一塊。類似地，C使用Y_C向B發(fā)送好像來自A的報(bào)文。

（3）B基于私有密鑰X_B和Y_C計(jì)算秘密密鑰K₁。A基于私有密鑰X_A和Y_C計(jì)算秘密密鑰K₂。C使用私有密鑰X_C和Y_B計(jì)算K₁，并使用X_C和Y_A計(jì)算K₂。

（4）從現(xiàn)在開始，C就可以轉(zhuǎn)發(fā)A發(fā)給B的報(bào)文或轉(zhuǎn)發(fā)B發(fā)給A的報(bào)文，在途中根據(jù)需要修改它們的密文。使得A和B都不知道他們?cè)诤?/span>C共享通信。

Oakley算法是對(duì)Diffie-Hellman密鑰交換算法的優(yōu)化，它保留了后者的優(yōu)點(diǎn)，同時(shí)克服了其弱點(diǎn)。

Oakley算法具有五個(gè)重要特征：

1、它采用稱為cookie程序的機(jī)制來對(duì)抗阻塞攻擊。

2、它使得雙方能夠協(xié)商一個(gè)全局參數(shù)集合。

3、它使用了現(xiàn)時(shí)來保證抵抗重演攻擊。

4、它能夠交換Diffie-Hellman公開密鑰。

5、它對(duì)Diffie-Hellman交換進(jìn)行鑒別以對(duì)抗中間人的攻擊。

Oakley可以使用三個(gè)不同的鑒別方法：

1、數(shù)字簽名：通過簽署一個(gè)相互可以獲得的散列代碼來對(duì)交換進(jìn)行鑒別；每一方都使用自己的私鑰對(duì)散列代碼加密。散列代碼是在一些重要參數(shù)上生成的，如用戶ID和現(xiàn)時(shí)。

2、公開密鑰加密：通過使用發(fā)送者的私鑰對(duì)諸如ID和現(xiàn)時(shí)等參數(shù)進(jìn)行加密來鑒別交換。

3、對(duì)稱密鑰加密：通過使用某種共享密鑰對(duì)交換參數(shù)進(jìn)行對(duì)稱加密，實(shí)現(xiàn)交換的鑒別。