基于橢圓曲線的加密密鑰交換協(xié)議

張曉敏

陜西省行政學(xué)院 陜西 710068

0 前言

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

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

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

1 預(yù)備知識(shí)

p是有限域Fp的元素個(gè)數(shù)，其中p是大素?cái)?shù)(長度大于160，或p=2m，m為正整數(shù)) 。定義Fp上的橢圓曲線E： y2= x3+ ax+b ，當(dāng)p＞3；或y2+ xy = x3+ ax2+ b，當(dāng)p=2。P是 E( Fp)中階為q的一個(gè)基點(diǎn)，q為大素?cái)?shù)。

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

G是由點(diǎn)P生成的循環(huán)加群，給定Q，找到正整數(shù)n，使得Q=nP。

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

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

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

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

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

如果v=r，則驗(yàn)證者接受簽名。

2 協(xié)議描述

2.1 公開參數(shù)

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

2.2 初始化過程

2.3 協(xié)議過程

假設(shè)是A需要和B建立會(huì)話密鑰。

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

Round 3：

（3）A對eA簽名：隨機(jī)選取kA計(jì)算最后將發(fā)送給S。

（4）B對eB簽名：隨機(jī)選取kB計(jì)算最后將發(fā)送給S。

密鑰計(jì)算：

完成。誠實(shí)執(zhí)行協(xié)議后，各用戶能夠計(jì)算獲得相同的會(huì)話密鑰。

3 效率和安全性分析

3.1 效率分析

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

表1 效率比較

3.2 安全性分析

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

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

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

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

（5）已知密鑰安全。攻擊者攻破一次通信的會(huì)話密鑰，無助于攻破另一次通信的會(huì)話密鑰。這是因?yàn)橥ㄐ烹p方最終得到的會(huì)話密鑰是由隨機(jī)數(shù)構(gòu)成，由于兩次通信使用的是不同的隨機(jī)數(shù)，這種隨機(jī)數(shù)的不相關(guān)性使得攻擊者即使攻破了一個(gè)會(huì)話密鑰也無法利用該信息攻破另一次通信的會(huì)話密鑰，以此實(shí)現(xiàn)已知密鑰安全。

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

[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.