基于橢圓曲線的加密密鑰交換協議

張曉敏

陜西省行政學院 陜西 710068

0 前言

為了實現網絡安全，網絡用戶傳送加密和可鑒定的消息。此時，用來加密和鑒定的密鑰就是由網絡中的用戶通過密鑰交換協議得到的。此外，網絡用戶在進行會話時，驗證其它參與方的身份是非常有必要的，這種認證通常是和密鑰交換協議結合在一起的。口令因其容易記憶，易于選取，節省存儲空間，適合實際應用等特點成為最簡單的認證方法。當然，由于口令是從一個相對較小的字典中均勻選取的，攻擊者可能發起窮舉字典攻擊，進而發動會話進行冒充。為了研究如何安全地利用口令進行密鑰協商，并避免窮舉字典攻擊，研究者們提出了加密密鑰交換協議(encrypted key exchange，EKE)的概念，又稱為基于口令的密鑰交換協議。1992年，Bellovin 和Merritt首次提出了一個兩方的EKE協議，通信雙方通過預先共享的低熵的口令構造出高熵的會話密鑰，并且能夠抵抗字典攻擊。在三方的EKE中，通信雙方分別和可信服務器共享一個容易記憶的口令，并通過服務器進行安全密鑰交換，服務器用口令加密信息以實現對用戶的認證，只有合法用戶能夠解密信息從而能夠生成正確的會話密鑰。

加密密鑰交換協議主要分為兩類：對稱模型和非對稱(基于驗證元)模型。對稱模型中，用戶和服務器持有相同的口令。因此，當服務器泄露時，敵手能夠直接獲得全部用戶的真實口令，并且使用口令模仿任何合法用戶。基于驗證元模型中，用戶持有口令，服務器持有的是利用單向函數生成的口令的映像(即驗證元)，而非口令本身。基于驗證元模型降低了服務器泄露攻擊對協議的破壞程度：服務器泄露時，敵手不能直接獲得用戶的口令，但仍允許敵手在服務器泄露攻擊后對獲得的口令文件進行離線字典攻擊。敵手必須進行一些額外計算才有可能發現用戶真正的口令，而進行這些計算給了服務器通知用戶受攻擊的時間。

1994年，Bellovin 和 Merritt提出了首個基于驗證元的加密密鑰交換協議，它采用特殊函數來存儲用戶的口令。自此以后，一些相關研究出現，協議的安全性和效率也得到了提高。基于橢圓曲線上離散對數問題的密碼系統近年來廣泛應用于實際中，與其他密碼系統相比，達到相同的安全性，橢圓曲線密碼系統的密鑰更短。此外，在橢圓曲線上實現數字簽名具有速度快、密鑰和簽名短等優點。因此，本文利用橢圓曲線密碼學的特點，給出了一個基于驗證元的三方加密密鑰交換協議，服務器通過口令實現對用戶的認證，協議能夠抵抗字典攻擊、服務器泄露攻擊和中間人攻擊，提供前向安全性，能夠保證無密鑰控制和已知密鑰安全。此外，協議每運行一次各用戶可以獲得四個安全的會話密鑰，而服務器得不到這些密鑰的準確信息。

1 預備知識

p是有限域Fp的元素個數，其中p是大素數(長度大于160，或p=2m，m為正整數) 。定義Fp上的橢圓曲線E： y2= x3+ ax+b ，當p＞3；或y2+ xy = x3+ ax2+ b，當p=2。P是 E( Fp)中階為q的一個基點，q為大素數。

1.1 橢圓曲線上離散對數問題(DLP)

G是由點P生成的循環加群，給定Q，找到正整數n，使得Q=nP。

1.2 橢圓曲線 Diffie-Hellman 密鑰交換協議(ECDH)

A選擇隨機數 a∈Fq并計算PA=aP發送給B；B選擇隨機數 b∈Fq并計算PB=bP發送給A。A和B分別計算aPB，bPA從而得到共同的會話密鑰 K=(a b) P。

1.3 橢圓曲線數字簽名算法(ECDSA)

密鑰生成：私鑰： da∈ [2 ,n - 2]，公鑰： Qa=daP。

簽名： k∈ [2 ,n - 2]，計算kP和 r =(k P). x mod n ，計算得到簽名(r , s)。

如果v=r，則驗證者接受簽名。

2 協議描述

2.1 公開參數

P是q階循環加群G的生成元， H:{0 ,1}?→ {0 ,1}l是雜湊函數；A,B是用戶，pwA，pwB是用戶相應的口令；S是服務器。

2.2 初始化過程

2.3 協議過程

假設是A需要和B建立會話密鑰。

Round 1發起者A廣播(A ,B,S)。

Round 3：

（3）A對eA簽名：隨機選取kA計算最后將發送給S。

（4）B對eB簽名：隨機選取kB計算最后將發送給S。

密鑰計算：

完成。誠實執行協議后，各用戶能夠計算獲得相同的會話密鑰。

3 效率和安全性分析

3.1 效率分析

我們分析協議的通信、計算和輪復雜度以及存儲開銷和實現成本。協議每執行一次，用戶和服務器之間需要四輪交互。整個協議過程中，用戶要進行2次雜湊函數運算，一次簽名運算；服務器需要進行4次雜湊函數運算，2次簽名驗證。每生成一個會話密鑰，每個用戶平均需要進行2次點乘運算；服務器平均需要進行2.5次點乘運算。對于每個用戶，服務器只需要存儲一個與之相應的校驗元，與其它同性質的協議比較(見表1)，降低了存儲開銷和通信開銷，更適宜于實際應用。

表1 效率比較

3.2 安全性分析

（1）字典攻擊。首先，在離線字典攻擊中，攻擊者利用其截獲的信息驗證猜測的口令是否正確。該協議中，以用戶A為例，攻擊者在各輪中可截獲等信息，由于在通信過程中沒有傳遞eA，敵手沒有辦法驗證猜測的口令是否正確。因此，無法進行離線字典攻擊。其次，本協議可以抵抗可測在線字典攻擊，因為服務器在第四輪里通過驗證用戶對eA的簽名來驗證用戶是否真正知道口令。一旦驗證失敗，服務器就會意識到是誰的口令已經作為在線字典攻擊的目標了。如果失敗的次數超過預定的門限值，服務器就會通知該用戶停止使用該口令并啟用新的口令。最后，如前所述，敵手不能將S作為口令試驗預言機，因此不能進行不可測在線字典攻擊。

（2）服務器泄露。如果攻擊者獲得服務器中存儲的口令文件，即可獲得用戶的驗證信息 VA, VB，由于橢圓曲線上離散對數問題的困難性，攻擊者仍然得不到 vA, vB，因此在第三輪中不能偽造用戶A、B對eA，eB的簽名，則在第四輪中無法通過服務器的驗證，故而不能冒充合法用戶。所以協議抵抗服務器泄露攻擊。

（3）前向安全性。由于最終的會話密鑰是由隨機數構成的，而隨機數是由各參與方隨機選取的，在協議交互過程中，傳遞的信息是隨機數所對應的離散對數形式。由于離散對數問題的困難性，攻擊者即使獲得用戶與服務器的長期密鑰，仍然無法獲得隨機數，因此不能計算出會話密鑰。所以協議提供前向安全性。

（4）無密鑰控制。協議使用Diffie-Hellman密鑰交換協議協商會話密鑰，此外，xAi是由A選取的，xBi是由B選取的，xS是由S選取的。因此，任何一方不能單獨控制會話密鑰的選擇，達到了協議無密鑰控制的目的。

（5）已知密鑰安全。攻擊者攻破一次通信的會話密鑰，無助于攻破另一次通信的會話密鑰。這是因為通信雙方最終得到的會話密鑰是由隨機數構成，由于兩次通信使用的是不同的隨機數，這種隨機數的不相關性使得攻擊者即使攻破了一個會話密鑰也無法利用該信息攻破另一次通信的會話密鑰，以此實現已知密鑰安全。

（6）抗中間人攻擊。服務器和用戶之間通過驗證元 VA, VB實現相互認證來抵抗中間人攻擊。攻擊者無法獲得驗證元信息，因此不能偽裝為合法用戶。此外，由于協議第三輪中的 eA, eB是由用戶和服務器各自利用交互信息生成的，而沒有進行直接傳輸，并且用戶分別利用 vA,vB對 eA, eB分別進行了簽名。因此，協議還能抵抗在線字典攻擊和中間人攻擊的聯合攻擊。

[1]S.M. Bellovin, M. Merrit. Encrypted key exchanged: password-based protocols secure against dictionary attacks, Proceeding of IEEE Computer Society Symposium on Research in Security and Privacy.Oakland.California.1992.

[2]IEEE P1363.2/D15, Standard Specifications for Password-Based Public Key Cryptographic Techniques.2004.

[3]Bellovin, S.M.,Merritt,M.,1994.Augmented encrypted key exchange:a password-based protocol secure against dictionary attacks and password file compromise.Technical report, AT&T Bell Laboratories.