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

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

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

1 引言

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

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

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

2 經典密鑰交換協議

2.1 DH密鑰交換協議

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

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

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

2.2 可認證的密鑰交換協議

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

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

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

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

3.1 特征值簡介

特征值定義如下。

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

式(1)也可寫成

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

3.2 三方密鑰交換協議

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

設密鑰交換的三方分別為Alice、Bob和Carol。選擇一個秘密n階矩陣A。設A的特征值λi(1≤i≤n)所對應的特征向量為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根據式(1)由pa、pb、pc計算λa、λb、λc，得出會話密鑰λa+λb+λc。

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

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

3.3 可驗證的三方密鑰交換協議

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

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

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

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

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

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

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

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

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

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

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

4 安全性分析

4.1 矩陣構造與合法性認證

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

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

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

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

4.2 密鑰量計算

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

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

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

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

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

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

4.3 復雜性分析

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

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

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

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

5 協議性能比較

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

表1 各類密鑰交換協議性能比較

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

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

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

6 三方密鑰交換協議舉例

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

設通信三方為Alice、Bob和Carol。在有限域Z11上構造秘密矩陣，可計算得到A的3個特征值為λ1=2，λ2=8，λ3=10，其對應的特征向量依次為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都根據式(1)，由pa、pb、pc計算得到λa=2，λb=10，λc=8，得出會話密鑰Kab=λa+λb+λc=20。

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

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

按照3.3節所述的矩陣構造要求，在有限域Z11上構造秘密矩陣為

因為存在可逆矩陣P，使

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

7 結束語

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