基于特征值的可驗證三方安全密鑰交換協(xié)議

張艷碩，王澤豪，王志強，陳輝焱

（1.北京電子科技學(xué)院密碼科學(xué)與技術(shù)系，北京 100070；2.密碼科學(xué)技術(shù)國家重點實驗室，北京 100878；3.數(shù)據(jù)通信科學(xué)技術(shù)研究所系統(tǒng)安全部，北京 100191）

1 引言

密鑰交換協(xié)議是重要的密碼機制。利用密鑰交換協(xié)議，通信雙方可以通過一個公開的不安全的信道產(chǎn)生一個秘密的會話密鑰，以實現(xiàn)秘密性和數(shù)據(jù)的完整性。密鑰交換協(xié)議有著豐富而廣泛的實際應(yīng)用。如TCP/IP中，IPSec安全協(xié)議套件中的因特網(wǎng)密鑰交換（IKE,Internet key exchange）協(xié)議通過建立安全通道、協(xié)商安全聯(lián)盟的方式，建立經(jīng)過認證的密鑰材料[1]。在Web安全中，針對面向上傳下發(fā)和登錄過程的安全防護，應(yīng)用了以DH（Diffie-Hellman）密鑰交換為基礎(chǔ)的加密，來代替全面部署安全套接層（SSL,secure sockets layer）的方案[2]。

基于三方的口令認證密鑰交換（3PAKE,three-party password authenticated key exchange）允許不安全信道上的2個用戶協(xié)商安全會話密鑰，并通過認證服務(wù)器的幫助建立安全信道，以保護其后續(xù)通信[3]。現(xiàn)階段，已有多種不同思路用于設(shè)計三方密鑰交換協(xié)議，如基于混淆設(shè)計的三方密鑰交換協(xié)議[4-5]、基于格的三方密鑰交換協(xié)議[6]、強三方安全模型下的密鑰交換協(xié)議[7]和基于口令的三方密鑰交換協(xié)議[8]等。但許多已提出的協(xié)議又被證明存在不同的安全隱患，如Yoon等[9]指出，Wang等[5]提出的協(xié)議易受消息修改攻擊。Zhao等[10]證明，使用擴展Chebyshev混沌映射的匿名認證協(xié)議易受特權(quán)攻擊和線下密碼猜測攻擊。模冪運算和對稱密鑰密碼系統(tǒng)的3PAKE協(xié)議[11-12]也被證明存在計算成本高、不實用的缺陷。

因此，本文基于特征值方法，構(gòu)造了一個安全高效的可驗證三方密鑰交換協(xié)議，并給出密鑰規(guī)模和相關(guān)參數(shù)。與經(jīng)典DH協(xié)議以及3個不同構(gòu)造的三方密鑰交換協(xié)議[6-8]對比后發(fā)現(xiàn)，本文所設(shè)計的協(xié)議具有良好的安全性和高效性，并且給出了基于特征值的設(shè)計多方安全密鑰交換協(xié)議的新方法和新思路。

2 經(jīng)典密鑰交換協(xié)議

2.1 DH密鑰交換協(xié)議

DH密鑰交換的思想于1976年在公鑰密碼學(xué)文章《New directions in cryptography》[13]中提出。通信雙方Alice和Bob首先協(xié)商一個大素數(shù)n和g，其中g(shù)為n的本原元。n和g不必是秘密的，即他們可以在不安全的途徑中進行協(xié)商，甚至在一組用戶中公用。n和g的選取對安全性有著極大影響。對n的要求是，n必須是一個大素數(shù)，且也必須為素數(shù)。這是因為系統(tǒng)的安全性依賴于與n長度相同的數(shù)的分解難度。g雖然不必是素數(shù)，且所有模為n的本原元g都可以被選擇，但g必須能產(chǎn)生一個大的模n的乘法組子群。

DH密鑰交換過程，Alice選擇秘密的XA，計算公開的YA，。Bob選擇秘密的XB，計算公開的YB，。Alice把YA發(fā)送給Bob，Bob把YB發(fā)送給Alice。最后，Alice和Bob協(xié)商出的會話密鑰為

DH密鑰交換將離散對數(shù)問題作為困難問題，是最經(jīng)典的密鑰交換協(xié)議，可以抵抗公開信道的抗竊聽攻擊。

2.2 可認證的密鑰交換協(xié)議

傳統(tǒng)的DH密鑰交換協(xié)議無法抵抗中間人攻擊。中間人攻擊的原理在于，通信雙方Alice和Bob都與中間人用DH算法協(xié)商密鑰，然后分別用協(xié)商好的密鑰KA和KB進行通信。中間人在通信雙方之間傳遞信息，這樣，通信雙方就在不知不覺間泄露了通信內(nèi)容。

為了抵抗中間人攻擊的風(fēng)險，發(fā)展出許多可認證的密鑰交換協(xié)議[14]，其中最經(jīng)典的2種為MTI（Matsumoto,Takashima,Imai）密鑰協(xié)商和STS（station to station）密鑰協(xié)商。MTI密鑰協(xié)商[15]能夠在2條消息中產(chǎn)生帶有抵抗中間人攻擊的隱式密鑰認證的共享密鑰。STS密鑰協(xié)商[16]是對DH密鑰協(xié)商的三步交換變體，允許在雙方之間建立一個共享密鑰，并帶有相互實體認證和相互顯示密鑰認證。STS密鑰交換協(xié)議可以起到抵抗中間人攻擊的作用，使通信雙方可以確信在網(wǎng)絡(luò)中只有合法的用戶可以計算出密鑰。

MTI密鑰交換無法提供實體認證，也不能進行密鑰確認，因此，其只能用于被動攻擊情景中。STS密鑰交換用于被動攻擊和主動攻擊的情景中的安全性都沒得到證明。這2種協(xié)議都存在一定的安全缺陷。

3 基于特征值的三方安全密鑰交換協(xié)議

3.1 特征值簡介

特征值定義如下。

定義1[17]設(shè)A是n階矩陣，E為單位矩陣，如果數(shù)λ和n維非零列向量x使式(1)成立，那么，這樣的數(shù)λ稱為矩陣A的特征值，非零向量x稱為A的對應(yīng)于特征值λ的特征向量。

式(1)也可寫成

式(2)是n個未知數(shù)n個方程的齊次線性方程組。

3.2 三方密鑰交換協(xié)議

本節(jié)方案基于矩陣特征值進行構(gòu)造，通信三方可以確保只有合法用戶才能計算出會話密鑰。具體方案如下。

設(shè)密鑰交換的三方分別為Alice、Bob和Carol。選擇一個秘密n階矩陣A。設(shè)A的特征值λi(1≤i≤n)所對應(yīng)的特征向量為pi(1≤i≤n)。具體步驟介紹如下。

Step1用戶Alice隨機選擇A的一個特征向量pa，其中1≤a≤n，將pa傳給Bob和Carol。

Step2用戶Bob隨機選擇A的一個特征向量pb，其中1≤b≤n，將pb傳給Alice和Carol。

Step3用戶Carol隨機選擇A的一個特征向量pc，其中1≤c≤n，將pc傳給Alice和Bob。

Step4用戶Alice、Bob、Carol根據(jù)式(1)由pa、pb、pc計算λa、λb、λc，得出會話密鑰λa+λb+λc。

對于該密鑰交換協(xié)議，由于攻擊方無法掌握秘密矩陣A，故其無法偽造會話密鑰進行常規(guī)的中間人攻擊。

但是可以證明，如果存在攻擊方C，且C掌握秘密矩陣A的所有特征向量pi(1≤i≤n)，那么C就可以從中任選3個特征向量分別發(fā)送給Alice、Bob和Carol。這樣Alice、Bob和Carol等合法用戶便會建立起錯誤的會話密鑰，從而該次密鑰協(xié)商被C所破壞。

3.3 可驗證的三方密鑰交換協(xié)議

針對上述安全漏洞，本文借鑒3.2節(jié)三方用戶交換矩陣特征向量的思路，在其基礎(chǔ)上，利用矩陣特征值的重根特性，對秘密矩陣的構(gòu)造進一步限定，構(gòu)造一個添加了用戶身份驗證功能的密鑰交換協(xié)議。

首先，構(gòu)造一個2n階秘密矩陣A，該矩陣滿足如下要求。

1)所有特征值λi(1≤i≤n)均為二重根，即有n個不同的λ。

2)矩陣A相似于對角陣。

矩陣A為以下方案中3個合法通信方共同保有的信息，即A可被視為密鑰。

合法用戶共享一個滿足上述要求的2n階秘密矩陣A，并設(shè)A的每個特征值λi(1≤i≤n)所對應(yīng)的2個特征向量為和(1≤i≤n)。設(shè)通信三方為Alice、Bob和Carol。方案過程介紹如下。

Step1Alice隨機選擇特征向量對發(fā)送pa給Bob和Carol。

Step2Bob隨機選擇特征向量對發(fā)送pb給Alice和Carol。

Step4用戶Alice收到pb和pc之后，首先進行合法性驗證，即判斷pb、pc包含的特征向量是否成對。驗證通過后，根據(jù)式(1)通過秘密矩陣A由pa計算出λa，由pb計算出λb，由pc計算出λc，計算會話密鑰Kabc=λa+λb+λc。

Step5用戶Bob收到pa和pc后，首先進行合法性驗證，即判斷pa、pc包含的特征向量是否成對。驗證通過后，根據(jù)式(1)通過秘密矩陣A由pa計算出λa，由pb計算出λb，由pc計算出λc，計算會話密鑰Kabc=λa+λb+λc。

Step6用戶Carol收到pa和pb之后，首先進行合法性驗證，即判斷pa、pb包含的特征向量是否成對。驗證通過后，根據(jù)式(1)通過秘密矩陣A由pa計算出λa，由pb計算出λb，由pc計算出λc，計算會話密鑰Kabc=λa+λb+λc。

4 安全性分析

4.1 矩陣構(gòu)造與合法性認證

首先，由于3.3節(jié)的密鑰交換協(xié)議是基于3.2節(jié)所述密鑰交換協(xié)議而構(gòu)造的，故其可以抵御傳統(tǒng)的中間人偽造會話密鑰，竊聽合法用戶通信的攻擊。同時，該協(xié)議還可以抵御3.2節(jié)所述的中間人對密鑰協(xié)商過程的干預(yù)，即避免攻擊方C使3個合法通信方誤以為自己與對方建立起會話密鑰這種安全漏洞。

定理1矩陣A相似于對角陣的充要條件為，A有n個線性無關(guān)的特征向量。

由于選取的2n階秘密矩陣A相似于對角陣，由定理1可知，A有2n個線性無關(guān)的特征向量。又由于所構(gòu)造的A的特征值均為二重，因此A的每個特征值都有2個特征向量。

方案的合法性認證正是基于這種秘密矩陣的特殊構(gòu)造的。通信方在接收到另兩方的特征向量對時，驗證特征向量是否成對是保證通信方身份是否合法的一個關(guān)鍵步驟。如果出現(xiàn)特征向量不成對的情況，便認為對方身份合法性存疑，認證不通過。

4.2 密鑰量計算

為了防止攻擊方對秘密矩陣A的窮舉攻擊，需要對密鑰量進行估計，即計算A有多少種選擇。

設(shè)方案基于有限域Zq，按照3.3節(jié)的矩陣設(shè)計要求，對于同2n階矩陣A相似的對角陣Λ而言，其每個對角元素有q種取值，又因為需保證n個特征值兩兩不同，故Λ所有的特征值組合方案個數(shù)Nc為

其中，q>n。因此，可得出Λ所有的特征值排列方案個數(shù)Np為

又因為P為可逆矩陣，有定理2成立。

定理2若A為可逆矩陣，則矩陣乘法AB=AC或BA=CA滿足消去律。

因為方案中P為可逆矩陣，因此根據(jù)定理2有PΛ1P-1≠PΛ2P-1。這意味著不同的對角陣一定對應(yīng)著不同的秘密矩陣A。即對于固定的一個P，可以生成Np個不同的A，方案密鑰量為Np。

4.3 復(fù)雜性分析

假設(shè)Alice、Bob和Carol為合法的通信用戶，攻擊方C若要對通信進行破壞，要進行兩步攻擊，首先需要得到密鑰，即矩陣A。根據(jù)4.2節(jié)的密鑰量計算，可知C掌握正確密鑰的概率為。

若要偽造其中的一個合法用戶發(fā)送信息，就需要從全部特征向量中選取2個成對的發(fā)送出去。假設(shè)矩陣的階為2n，則C成功的選取到成對特征向量的概率為

當(dāng)q的遠大于n時，C成功對通信進行破壞的概率為

可以看出，攻擊成功的復(fù)雜度非常高，攻擊成功的概率小到幾乎可以忽略不計，攻擊方對通信進行破壞的概率極低，這意味著攻擊方對密鑰協(xié)商過程進行干預(yù)的成功率將非常小，很難通過合法一方的合法性驗證。

5 協(xié)議性能比較

本節(jié)將本文設(shè)計的密鑰交換協(xié)議與傳統(tǒng)的DH協(xié)議、基于格的密鑰交換協(xié)議[6]、強三方安全模型下的密鑰交換協(xié)議[7]、基于口令的密鑰交換協(xié)議[8]進行比較。各類密鑰交換協(xié)議性能比較如表1所示，其中，Type表示協(xié)議類型，Mutu-Auth表示協(xié)議是否提供雙向認證的功能，Round表示協(xié)議所需的輪數(shù)。

表1 各類密鑰交換協(xié)議性能比較

從表1中可以看出，本文提出的三方交換協(xié)議支持雙向認證，具有安全性上的優(yōu)勢。在效率方面，本文在基于秘密矩陣的前提下，實現(xiàn)了只需一輪即可達到可驗證密鑰交換的目的，效率更高。

在本文涉及的密鑰量方面，根據(jù)4.2節(jié)的數(shù)據(jù)和4.3節(jié)對復(fù)雜性的分析可知，密鑰量Np可規(guī)約為階乘運算，密鑰空間足夠大，可以保證協(xié)議的安全性。

在計算復(fù)雜性方面，密鑰交換要保證在基本的多項式時間內(nèi)無法進行有效攻擊。傳統(tǒng)的DH密鑰交換協(xié)議基于離散對數(shù)問題進行設(shè)計，是典型的NP問題。文獻[6]所提的基于格的密鑰交換最終被規(guī)約為SVP（shortest vector problem）問題，是NP完全問題。文獻[7]的密鑰交換被證明為包含密鑰確認的認證密鑰交換協(xié)議（AKC,authenticated key exchange protocol with key confirmation）安全，其復(fù)雜性可闡述為多項式時間內(nèi)，攻擊者成功猜出輸出為會話密鑰還是隨機數(shù)的概率可忽略。文獻[8]所提的3PAKE協(xié)議被證明在隨機預(yù)言機模型下，基于計算DH困難性假設(shè)是安全的。本文所提方案在4.3節(jié)中被證明其計算復(fù)雜性為階乘級，這意味著多項式時間內(nèi)中間人攻擊成功的概率可忽略，滿足了密鑰交換協(xié)議的基本設(shè)計要求。

6 三方密鑰交換協(xié)議舉例

6.1 基于特征值的三方密鑰交換協(xié)議舉例

設(shè)通信三方為Alice、Bob和Carol。在有限域Z11上構(gòu)造秘密矩陣，可計算得到A的3個特征值為λ1=2，λ2=8，λ3=10，其對應(yīng)的特征向量依次為p1=(0,1,0)，p2=(1,1,0)，p3=(1,1,1)。具體步驟介紹如下。

Step1用戶Alice隨機選擇A的一個特征向量pa=(0,1,0)，將其傳給Bob和Carol。

Step2用戶Bob隨機選擇A的一個特征向量pb=(1,1,1)，將其傳給Alice和Carol。

Step3用戶Carol隨機選擇A的一個特征向量pc=(1,1,0)，將其傳給Alice和Bob。

Step4用戶Alice、Bob和Carol都根據(jù)式(1)，由pa、pb、pc計算得到λa=2，λb=10，λc=8，得出會話密鑰Kab=λa+λb+λc=20。

6.2 基于特征值可驗證的三方密鑰交換協(xié)議舉例

為了方便演示且限于篇幅，本文選取秘密矩陣為4階矩陣，但實際應(yīng)用中需要一個遠大于該階數(shù)的矩陣。秘密矩陣的構(gòu)造方法可以通過先設(shè)定特征值和特征向量，再以此倒推出秘密矩陣的方式進行。

按照3.3節(jié)所述的矩陣構(gòu)造要求，在有限域Z11上構(gòu)造秘密矩陣為

因為存在可逆矩陣P，使

設(shè)通信三方為Alice、Bob、Carol，方案過程如下。

1)用戶Alice隨機選取特征向量對pa=((0,1,1,1)T,(0,1,0,1)T)。

2)用戶Bob隨機選取特征向量對pb=((0,1,0,0)T,(1,1,0,1)T)。

3)用戶Carol隨機選取特征向量對pc=((0,1,0,0)T,(1,1,0,1)T)。

4)合法用戶在獲得另兩方發(fā)來的特征向量對之后，首先進行合法性驗證，即判斷特征向量是否成對。驗證通過后，根據(jù)式(1)由秘密矩陣A計算得到λa=1，λb=4，λc=4。計算會話密鑰為

7 結(jié)束語

本文在基于矩陣特征值的思路之上，首先提出一種簡單的三方密鑰交換協(xié)議。該協(xié)議可以抵抗中間人攻擊，但無法抵御中間人對密鑰交換過程的干預(yù)。針對這一問題，本文對秘密矩陣進行限制，基于二重特征值提出了一種既可抵御中間人攻擊，又可以進行用戶合法性認證的三方密鑰交換協(xié)議。對比分析證明，該協(xié)議具有良好的安全性和高效性。同時，該協(xié)議每次都可以重新協(xié)商新的會話密鑰，防止一個密鑰多次使用帶來的安全隱患，具有很好的靈活性，為三方或多方密鑰交換協(xié)議設(shè)計提供了一種新方法和新思路。