一種基于ECDLP有身份認證的ECDH 密鑰協(xié)商方案

曹 陽，郝玉潔，洪 歧

（1.陜西理工學(xué)院計算機系，陜西漢中723000;2.電子科技大學(xué)計算機學(xué)院，四川成都 610051）

0 引言

密鑰協(xié)商方案（key agreement scheme）就是一種能夠讓通信雙方或多個參與方在一個公開的、不安全的信道上，通過通信協(xié)議協(xié)商建立一次會話所用的臨時密鑰的密碼協(xié)議。橢圓曲線密鑰協(xié)商方案（elliptic curve key agreement scheme-diffie-hellman version，ECDH）［1-2］是橢圓曲線密碼體制［3］中常用密鑰協(xié)商方案之一，已被列入IEEE1363-2000和ANSIX9.63等標準之中。它能較好地防止被動攻擊，但無法應(yīng)付所謂的中間人攻擊。M.Aydos等［4］提出采用證書實現(xiàn)可認證的密鑰交換，能防止中間人的攻擊，但此方案需要通過第三方可信認證中心CA來完成，且終端能夠處理證書，系統(tǒng)擴展存在較大的難度，當(dāng)用戶增多時需要增加存儲空間來存儲證書，同時也要增加帶寬來驗證證書。Seo等［5］提出基于共享口令可認證的Diffie-Hellman密鑰協(xié)商協(xié)議，但該方案容易遭到離線口令猜測、服務(wù)器欺騙及字典攻擊。為了解決上述問題，本文提出一種基于橢圓曲線離散對數(shù)問題（elliptic curve discrete logarithm problem，ECDLP）的有身份認證的密鑰協(xié)商方案。

1 橢圓曲線密碼體制

1.1 橢圓曲線

所謂橢圓曲線［6-7］指的是由韋爾斯特拉斯（Weierstrass）方程所確定的平面曲線

（1）式中:系數(shù)ai（i=1，2，…，6）定義在某個域上，可以是有理數(shù)域、實數(shù)域、復(fù)數(shù)域，還可以是有限域GF（q）;x，y是橢圓曲線上的點，橢圓曲線密碼體制中用到的橢圓曲線都定義在有限域上的。

常用的有限域GF（q）上的方程定義為y2=x3+ax+b的橢圓曲線E（GF（q）），其中，a，b∈GF（q）且4a3+27b2≠0（modp），p為大于3的素數(shù)。

1.2 橢圓曲線離散對數(shù)問題及橢圓曲線選取

橢圓曲線公鑰密碼體制的安全性［8-9］與相應(yīng)的ECDLP的求解困難性等價，困難性是所有橢圓曲線密碼方案安全性的基礎(chǔ)。ECDLP定義為給定橢圓曲線E（GF（q））及其上一點P，n為P點的階，對于另一點Q∈E（GF（q）），求整數(shù)l（0≤l≤n－1），使得Q=lP（假設(shè)整數(shù)l存在），其中，l稱為Q的以P為底的離散對數(shù)。橢圓曲線上所有的點，外加一個無窮遠點構(gòu)成的集合連同其上定義的加法運算構(gòu)成一個Abel群。在Abel群E（GF（q））上關(guān)于m（m是明文消息）的方程Q=mP中，已知m和點P求點Q比較容易，反之，已知點Q和點P求m卻是相當(dāng)困難，這個問題稱為橢圓曲線上點群的離散對數(shù)問題，橢圓曲線密碼體制正是利用這個困難問題設(shè)計而來。安全橢圓曲線的選取方法主要有虛數(shù)乘法和隨機選取2種方法，從安全角度考慮，本文采用隨機選取方法選取橢圓曲線。

1.3 明文嵌入

通常加密系統(tǒng)都需要讓原文變?yōu)榭梢赃M行數(shù)學(xué)計算的數(shù)值，在橢圓曲線密碼體制中，需要將明文以一定的方式映射為橢圓曲線上的點，一個點由X坐標和Y坐標組成，因此，一個點實際上是由2個數(shù)組成的數(shù)對，并且這2個數(shù)都在曲線所在的有線域GF（q）上。由于一個點由2個數(shù)組成，而消息可以轉(zhuǎn)換成一個數(shù)，因此必須找到另外一個數(shù)與消息轉(zhuǎn)換后得到的數(shù)組成一個點。這就是所謂的明文消息的嵌入。明文嵌入概率算法描述如下。

1）假設(shè)明文消息是m（0≤m≤M），k是一個足夠大的整數(shù)，使得將明文消息鑲嵌到橢圓曲線上時，錯誤的概率是2－k。

2）計算x={mk+j，j=0，1，2，…}={30m，30m+1，30m+2，…}，直到x3+ax+b（modp）是平方根，即得到橢圓曲線上的點 （x，，其中，k可以在30～50取值，不防取k=30，m是明文消息。

3）從橢圓曲線上的點（x，y）得到明文消息m，只須求m=x/30。

2 ECDH密鑰協(xié)商

ECDH 密鑰協(xié)商［10］是 Diffie-Hellman［11］密鑰協(xié)商協(xié)議在ECC上的實現(xiàn)。假設(shè)需要完成密鑰協(xié)商通信雙方為A和B，ECDH密鑰協(xié)商協(xié)議描述如下。

1）A隨機地選擇一個大整數(shù)kA∈［1，n－1］作為自己的私鑰，并計算公鑰QA=kA P發(fā)送給B;

2）B隨機地選擇一個大整數(shù)kB∈［1，n－1］作為自己的私鑰，計算公鑰QB=kB P發(fā)送給A;

3）A在收到B發(fā)來的QB以后，計算

同樣，B在收到A發(fā)過來的QA后，計算

這樣，A和B完成了ECDH密鑰協(xié)商，協(xié)商后雙方約定的臨時會話密鑰為K=kA kB P。

總之，田面水中各形態(tài)氮濃度在施肥后 1~4 d達到峰值，在施肥后10 d內(nèi)濃度較高，若在此期間遇到強降雨，稻田氮素的流失量會隨著施氮量的增加而增加，故施氮初期是管理氮素流失的關(guān)鍵時期。施用控釋氮肥處理田面水各形態(tài)氮濃度比施用尿素處理有所降低，一定程度上減少了氮素流失的風(fēng)險。

3 基于ECDLP有身份認證的ECDH密鑰協(xié)商方案

從基于ECC Diffie-Hellman密鑰協(xié)商協(xié)議可以看出，通信雙方A或B在向?qū)Ψ桨l(fā)送信息時容易受到中間人的攻擊，在密鑰協(xié)商中，任何人都可以獲得公鑰，中間人E選擇大整數(shù)kM∈［1，n－1］，截取A發(fā)送給B的kAP和B發(fā)送給A的kB P，并將kAP，kB P修改為kM P，協(xié)商結(jié)束后，A與攻擊者生成共享密鑰kA kB P，但A誤認為B共享的，B與攻擊者共享了密鑰kA kB P，而B卻誤認為是與A共享的，真正的用戶A與B并沒有共享一個密鑰。當(dāng)用戶A發(fā)送機密信息給B時A用kA kM P對消息加密，攻擊者截獲進行解密，然后偽造一個消息，用密鑰kA kB P加密后發(fā)送給B，這樣，攻擊者成功的欺騙了用戶A，B，而用戶A，B卻并不知道，這影響了正常的密鑰協(xié)商。

為了使A，B雙方能夠正常通信，完成正常的密鑰協(xié)商，在此建立一個有身份認證機制的密鑰協(xié)商方案，該方案描述如下。

假設(shè)q是大于3的素數(shù)，在有限域GF（q）隨機生成一條橢圓曲線E（GF（q）），使得求解ECDLP在計算上是不可行的。隨機選取一點G，G的階p是一大素數(shù)。通信雙方各自選擇自己的整數(shù)k（1≤k≤p－1），計算k關(guān)于p的k－1，將k和k－1作為自己的秘密密鑰，而將Q=kG作為自己的公開密鑰。設(shè)A和B進行密鑰協(xié)商身份認證過程如下。

1）A隨機選取秘密數(shù)s，并計算s關(guān)于p乘法逆元s－1，保密s和s－1，計算GA=sQA，把自己的身份信息IA和GA一并發(fā)送給B;

2）B收到IA和GA，用自己的秘密密鑰加密GA得到GB=kBGA，并把GB發(fā)送給A;

3）A收到GB后，計算X=s－1kA－1GB=kBGX，并把X與B公開的QB進行比較，如果相等則確定對方就是B，并把（X1，X2）發(fā)送給B，X1=kA－1GB=kBsG，X2=（kA+s）G;否則放棄通信;

4）B收到（X1，X2）后，計算Y1=kB－1X1=sG，Y=X2+（－Y1）=kAG，把Y與A公開的秘密密鑰QA進行比較，如果相等而相信對方就是A，否則放棄通信。身份認證過程如圖1所示。

圖1 身份認證過程Fig.1 Authentication process

1）A隨機選擇整數(shù)nA∈［1，n－1］，利用B的公鑰計算SA，并將SA發(fā)送給B，收到B的SB后計算:

（2）式中:kA是A的私鑰;QA是A的公鑰;G是E（GF（q））上的一點。

2）B隨機選擇整數(shù)nB∈［1，n－1］，利用A的公鑰計算SB并將SB發(fā)送給A，收到A的SA后計算:

（3）式中:kB是B的私鑰;QB是B的公鑰;G是E（GF（q））上的一點。

從上可以看出，在身份認證的條件下A和B進行密鑰協(xié)商，且雙方能得相同的密鑰。

4 安全性分析

可以看到，安全橢圓曲線選取保證了求解ECDLP是計算上不可行的，以下從4方面對本文提出的密鑰協(xié)商方案進行安全性分析。

1）該方案實現(xiàn)了A和B之間的雙向身份認證，攻擊者不能冒充通信雙方中的任何一方，增強了雙方通信的安全性。假設(shè)攻擊者可以冒充A，但由于不知道s和kA，因此無法生成（X1，X2），B也就無法通過計算得到與A相同的公鑰，同樣攻擊者也不能冒充B，進而身份認證失敗。

2）密鑰安全性，通信雙方在進行密鑰協(xié)商之前，都是在雙向身份認證通過的前提下進行的，加上密鑰協(xié)商時nA nB是隨機選取的，也就使得攻擊者法從一個已知的會話密鑰推出將來可能的會話密鑰，因此密鑰是安全的。

3）前向安全性，信道上傳輸?shù)男畔?GA，GB，（X1，X2），基于ECDLP這一難題，攻擊者無法從中恢復(fù)nA，nB，所以nA，nB依然是安全的。

4）防止重放攻擊，因為nA，nB都是隨機選取，可以保證信息的新鮮性，通信雙方在密鑰協(xié)商的時候也就確認了密鑰是本次協(xié)商得到的。

5 總結(jié)

本文給出了一種基于ECDLP有身份認證的ECDH密鑰協(xié)商方案，其安全性是建立在橢圓曲線離散對數(shù)問題困難性的基礎(chǔ)上之上。該方案分為認證和協(xié)商兩個過程，在身份認證中，參數(shù)s，kA，kB都是保密的，因而攻擊者無法冒充A或B，從而保證了身份認證的正確性。在密鑰協(xié)商階段也使用了隨機數(shù)nA，nB，從而保證了密鑰協(xié)商的安全性，同時還可以防止重放攻擊。

［1］ LAW L，MENEZESA，QU M，et al.An efficient protocol for authenticated key agreement［J］.Designs，Codes and Cryptography，2003，（3）28:119-134.

［2］SMART N P.An identity based authenticated key agreement protocolbased on the well pairing［J］.Electronics Letters，2002，38（13）:630-632.

［3］KOBLITZ N.Elliptic Curve Cryptosystem［J］.Mathematics of Compution，1987，48（177）:203-309.

［4］ AYDOSM，SUANR B，KOC C K.An elliptic curve cryptography based authentication and key agreemend protocol forwireless communication［J］.Electronics Letters，1999，35（13）:82-85.

［5］DONG Hwi-seo，SWEENEY P.Simple authenticated key agreement algorithm［J］.Electronics Letters，1999，35（13）:1073-1074.

［6］黃劍櫻.淺析橢圓曲線密碼體制［J］.宜賓學(xué)院學(xué)報，2007，6（6）:88-89.

HUANG Jian-ying.Introduction of Elliptic Curve Cryptography［J］.Journal of Yibin University，2007，6（6）:88-89.

［7］ 曹陽.基于無線局域網(wǎng)認證中ECC密碼體制的應(yīng)用研究［D］.成都:電子科技大學(xué)，2008:16-24.

CAO Yang.Applied Research of Elliptic Curve Cryptography Based on Wireless LAN Certification［D］.Cheng du:University of Electronic Science and Technology，2008:16-24.

［8］劉志猛，趙燕麗，范輝.橢圓曲線密碼體制中安全曲線的選取［J］.淮海工學(xué)院學(xué)報，2008，17（1）:25-28.

LIU Zhi-meng，ZHAO Yan-li，F(xiàn)AN HUI.Selection of Elliptic Curves Based on ECC［J］.Journal of Huaihai Institute of Technology，2008，17（1）:25-28.

［9］ 汪朝暉.橢圓曲線密碼的安全性研究［D］.武漢:武漢大學(xué)，2004:27-28.

WANG Chao-hui.A Research on the Securities of Elliptic Curve Cryptosystems［D］.Wu han:Wuhan University，2004:27-28.

［10］邵曉博.橢圓曲線密碼體制中密鑰協(xié)商方案改進的研究［J］.計算機安全，2010，01:23-25.

SHAO Xiao-bo.Reserach of Improved Key Agreement Scheme Based on Elliptic Curve Cryptography［J］.Computer Security，2010，01:23-25.

［11］隋愛芬，楊義先，鈕心忻，等.基于橢圓曲線密碼的可認證密鑰協(xié)商協(xié)議的研究［J］.北京郵電大學(xué)學(xué)報，2004，27（3）:28-32.

SUI Ai-fen，YANG Yi-xian，NIU Xin-xin etc.Reserach on the Authenticated Key Agreement Protocol Based on Elliptic Curve Cryptography［J］.Journal of Beijing University of Posts and Telecommunications，2004，27（3）:28-32.