可證明安全的隨機密鑰協商協議

張小梅+吳福生+彭長根

摘 要： 主要研究隨機密鑰協商問題，針對Diffie?Hellman協議、SAKA協議和改進Lin協議、E?SAKA協議等存在的不具有認證功能和不能抵抗中間人攻擊等缺陷，應用動態雙向認證因子認證方法和非時間同步技術提出一種隨機密鑰協商協議，該協議適用于OTP動態口令系統設計，同時解決密鑰協商過程中的動態認證和時間同步問題。最后，在標準模型下證明了方案的安全性。

關鍵詞： 隨機密鑰協商； Diffie?Hellman密鑰協商； DDH問題； 可證明安全

中圖分類號： TN918?34； TP309 文獻標識碼： A 文章編號： 1004?373X（2017）13?0087?04

Abstract： The random key agreement issue is studied. Since the Diffie?Hellman protocol， SAKA protocol， improved Lin protocol and E?SAKA protocol don′t have the authentication function， and can′t resist the man?in?the?middle attack， a random key agreement protocol is proposed on the basis of the factor authentication method of dynamic bidirectional authentication and non?time synchronization technology， which is suitable for the design of OTP dynamic password system， and can solve the problems of dynamic authentication and time synchronization in the key agreement process. The security of the proposed scheme is proved with the standard model.

Keywords： random key agreement； Diffie?Hellman key agreement； DDH problem； provable security

0 引 言

密鑰協商協議是通信雙方建立安全會話鏈接的主要工具之一，能有效保障通信參與方間的安全通信。早在1976年，Diffie和Hellman在“密碼學的新方向”一文中提出的公玥密碼思想為密鑰協商提供了新的解決途徑[1]。后續有大量學者在密鑰協商方面做了重要的工作[2?4]。文獻[4]在標準模型下提出了一種可證明安全的基于身份的認證密鑰協商協議；最近，文獻[5]提出一種面向無線傳感器網絡的雙因子用戶認證協議?？梢?，密鑰協商協議一如既往地受到廣大研究人員的重視。

Diffie?Hellman[1]算法是一個著名的雙方生成共享密鑰的經典協議算法，但是該協議不具有認證功能，不能抵抗中間人攻擊。針對Diffie?Hellman協議的不足，文獻[2]提出簡單密鑰交換協議（SAKA），但其存在如下三個缺陷：攻擊者雖然不能獲得會話密鑰，但是可以模仿Bob與Alice建立連接；協議不能抵抗密鑰猜測攻擊； 協議不能保證前向的安全性。另外一些學者還提出了針對SAKA協議的一些改進協議，如文獻[6?9]。但是這些研究未能解決安全認證問題和中間人攻擊問題。針對這一不足，本文提出一種改進的新SAKA協議，該協議應用動態雙向認證因子認證方法實現密鑰協商的動態認證，并利用非時間同步技術解決密鑰協商雙方的時間同步問題，最后在標準模型下給出協議的安全性證明。

1 基礎知識和協議原理

1.1 基本知識

Diffie?Hellman的DDH難解問題[11]（又稱Diffie?Hellman的判斷問題）：如果對任何概率多項式時間算法D，都不能區分和其中是一個隨機數。

定義1 偽隨機函數：設是偽隨機函數，如果對于每個概率多項式算法和有足夠大的，滿足：。

其中：是一個均勻分布的函數；是一個可忽略函數。表示對所有攻擊者可能取到的最大值。

定義2 單向函數：設是一個單向函數，則滿足：

任意給一個，求出很容易，即一定存在一個概率多項式算法，在多項式時間內有：。

已知求出不可能的，即：如果對于任意的任何概率多項式算法都不能從得出即：其中是一個可忽略函數。

定理1 如果存在單向函數，則存在加密方案具有選擇密文攻擊下不可區分加密，以及存在消息鑒別碼具有選擇消息攻擊下不可偽造。

引理1 如果存在離散對數的偽隨機單向函數，那么滿足DDH難解問題。

1.2 密鑰交換原理及分析

Lin提出的增強算法是為了克服原始SAKA算法的不足。而根據文獻[10]的分析，Lin的算法仍然會受到密碼猜測攻擊。

通信雙方為A與B預先共享一個密碼系統參數是一個大素數，是有限域的一個本原元，和是公開的，通信雙方用指定方法從密碼得到和具體方法不做規定，要求與互質，并且由不同的生成具有抗碰撞性。協議過程如下：

Step1： A選擇一個隨機整數并且發送給B：；

Step2： B選擇一個隨機整數并且發送給A：；

Step3：A計算共享密鑰，并計算

Step4：B計算共享密鑰并計算發給

Hsieh攻擊分析中，攻擊者可以在第（1）步中得到第（4）步中得到，然后進行如下的離線猜測攻擊：攻擊者首先猜測密碼并且得到和，然后通過驗證等式是否成立來離線猜測出和的正確性，使攻擊成功。

文獻[7]提出了E?SAKA協議，但存在離線猜測等弱點；文獻[8]提出了另一種改進協議，雖然能抵抗Hsieh分析，但不能抵抗E的假冒而進行猜測攻擊。

2 改進的SAKA協議算法

基于Diffie?Hellman算法、SAKA協議思想，通過兩次Diffie?Hellman算法生成一個臨時共享密鑰和一個雙方之間的會話密鑰，并進行雙向認證。生成的第一個共享密鑰稱為臨時輔助共享密鑰，產生的第二個共享密鑰稱為A與B之間的會話密鑰。

本協議共分為三個階段：

（1） 雙向認證因子注冊階段，其中雙向認證因子是實體A與B雙方共同具有的某一特性標識，或者雙方都認可的某一特性標識；

（2） 臨時輔助共享密鑰生成階段；

（3） 會話密鑰生成以及雙向認證與驗證階段。

2.1 雙向認證因子注冊階段

通過安全信道注冊一個雙方認可的雙向認證因子，用表示雙向認證因子，此因子是靜態的，且具有惟一性和認可性。注冊的雙向認證因子明文本身不參與認證與驗證，而是經過一個單向函數[8]轉換成一個隨機數值參與認證與驗證。

2.2 臨時輔助共享密鑰生成階段

基于第一次用Diffie?Hellman協議生成本次臨時輔助共享密鑰，生成過程如下：

Step1： A選擇兩個隨機整數并且發送給；

Step2： B收到A發送的消息后，選擇兩個隨機整數，并且發送給A：

Step3： A收到B發送的消息后，判斷收到的與自己原有的是否相等，相等則計算和發送{}給否則，協議終止；

Step4： B收到Step2中A發來的{}，判斷收到的與自己原有的是否相等，相等則計算和。否則，協議終止。

說明：當協議完成時，本階段臨時輔助共享密鑰生成成功，這時系統消除由于整數都是隨機選取，具有很好的隨機性，因此也具有很好的隨機性，而只是作為一個隨機數值參與到認證與驗證。而協議中的與只是作為保證A與B之間生成的臨時輔助共享密鑰相同而已，不會參與到后續協議的任何階段中。

2.3 會話密鑰生成以及雙向認證與驗證階段

由注冊與臨時輔助共享密鑰生成階段可知，與都已知，且是靜態，是動態隨機。在本階段還要求有一個單向函數，用表示。的主要作用是把靜態的雙向認證因子通過加入動態隨機的轉換為動態隨機的雙向認證因子，用表示動態隨機雙向認證因子，函數輸入值相同時輸出值也相同，輸入值不同時，具有抗碰撞性。這樣保證了A與B的雙向認證因子同步進行。分別表示實體A與B的身份。

協議系統參數是一個大素數，是有限域的一個本原元，和是公開的。具體實施協議過程如下：

Step1： A計算再計算同時計算生成且與互質，并發送，給B；

Step2： B計算再計算同時計算生成且與互質，并發送給

Step3： A計算和并發送給B；

Step4： B計算和并發送給A；

Step5： A計算相等，則A確認對方通信的是B，即A認證B成功，否則失敗；

Step6： B計算相等，則B確認對方通信的是A，即B認證A成功，否則失敗。

當且僅當Step5和Step6同時成立時，則密鑰為雙方共享會話密鑰。

2.4 攻擊分析

由Hsieh分析可知，攻擊者（E）可能在第（1）與第（4）步可以得到與第（2）步與第（3）步得到與不可能得到。所以能抵抗由Hsieh方法分析。

E假冒B與A通信，進行猜測攻擊：

Step1： E得到。

Step2： E選擇自己的一個數計算 發給A。

Step3： A收到E發來的消息后，計算，由于是E自己選取，很容易計算得到然后計算比較等式，這樣E可以進行離線或在線猜測。一旦等式成立，則E攻擊成功。但是由函數動態得到的是一個隨機動態值，E不可能在線猜測成功，即使E能夠攻擊通信A或B得到靜態的但是得不到臨時輔助共享密鑰生成階段生成的（要得到就必須解離散對數），所以E不可能猜測得到故該協議能抵抗在線或離線猜測。

2.5 全安性分析

本文提出改進的SAKA算法的安全性主要依賴于離散對數困難問題，同時還充分利用了隨機性以及單向函數的安全性。其安全性具體分析如下：

（1） 無論是生成的臨時輔助共享密鑰還是后面生成的雙方共享會話密鑰都依賴于離散對數困難問題，攻擊者不可能得到這兩次密鑰。

（2） 雖然攻擊者在臨時輔助共享密鑰生成階段可以冒充A或B，生成一個替換臨時輔助共享密鑰但是攻擊者沒有雙向認證因子以及轉換后的動態隨機雙向認證因子則無法生成與從而有效地防止攻擊者的冒充攻擊和中間人攻擊。

（3） 如果攻擊者攻擊靜態的雙向認證因子即使得到了但也無法得到創新性分析說明了E無法猜測得到。

（4） 由于是動態隨機的，所以生成的都是動態隨機的，這就有效阻止了對在線或離線猜測攻擊。

（5） 由于是動態隨機新鮮的，則都具有動態隨機新鮮性，所以本協議能夠保證前向的安全性。

3 安全性證明

本節給出所提協議的安全性證明，主要從協議的后兩個階段（臨時輔助共享密鑰生成階段、會話密鑰生成及雙向認證與驗證階段）證明其安全性。

首先證明第二階段的安全性：

第二階段：由改進協議第二階段可知，其安全性主要是基于Diffie?Hellman算法的安全，而對于實體A與B所選取的隨機數在此階段中只是判斷A與B在本階段協議完成之后，是否共享密鑰的臨時作用。對協議安全沒有決定性作用。所以，本階段的改進協議滿足Diffie?Hellman的難解問題DDH，故攻擊者要想得到是不可能的。

然后證明第三階段的安全性：

第三階段：由改進協議的第三階段可知，協議的安全也是基于Diffie?Hellman難解問題，只要滿足了Diffie?Hellman協議算法的要求即可，所以主要是證明雙向認證動態因子是否滿足真正偽隨機，且已知是偽隨機的，是單向函數。

不妨設事件分別為：表示是偽隨機的，由定義1得：

表示是單向函數，由定義2得：

由于可知，事件是由事件同時發生才發生的，如果令表示事件則事件可表示為：。由此可知：

由于與是兩個獨立事件，因為是偽隨機與是單向函數是相互獨立的，所以由式（3）得到：

由式（1）～式（4）得到：即由此可見，對于每個概率多項式算法和有足夠大的存在一個單向函數使得事件

滿足：所以是一個真正偽隨機數。由定理1可知具有抗選擇密文攻擊下不可區分，不可偽造等安全性。同理可證也是真正偽隨機數，滿足定理1。

由此可以得到是真正偽隨機數。從改進協議第三階段得到，通信實體A與B相互之間在網上傳輸與。由引理1可知，這些網上傳輸的消息滿足DDH難解問題。

由兩階段的安全性證明可知，本文提出的協議安全性是基于DDH困難性假設的，也就是說如果DDH是困難的，則該協議在標準模型下是安全的。

4 結 論

本文研究隨機密鑰協商協議的可證明安全問題。首先分析密鑰協商協議的相關算法，基于Diffie?Hellman協議提出隨機密鑰協商協議。該協議解決了SAKA及其改進協議的一些缺陷， 繼承了SAKA及其改進協議的優點，并能抵抗猜測攻擊；在協議中，應用動態雙向認證因子認證方法和非時間同步技術，使得該協議適合OTP動態口令系統設計，從而解決了Diffie?Hellman協議算法以及它的改進協議SAKA，E?SAKA等算法的動態認證問題，解決了協商雙方的時間非一致性問題。

參考文獻

[1] DIFFIE W， HELLMAN M E. New directions in cryptography [J]. IEEE transactions on information theory， 1976， 22（6）： 644?654.

[2] SEO D， SWEENEY P. Simple authenticated key agreement algorithm [J]. Electronics， 1999， 35（13）： 1073?1074.

[3] 王圣寶，曹珍富，董曉蕾.標準模型下可證安全的身份基認證密鑰協商協議[J].計算機學報，2007，30（10）：1842?1852.

[4] 任勇軍，王建東，王箭，等.標準模型下基于身份的認證密鑰協商協議[J].計算機研究與發展，2010（9）：1604?1610.

[5] JIANG Qi， MA Jianfeng， LU Xiang， et al. An efficient two?factor user authentication scheme with unlinkability for wireless sensor networks [J]. Peer?to?peer networking and applications， 2015， 8（6）： 1070?1081.

[6] 任艷麗，谷大武.公鑰密碼方案的可證明安全性注記[J].計算機應用研究，2008，25（4）：1130?1133.

[7] 楊炤璐，范磊，李建華.E?SAKA密鑰協商算法[J].通信技術，2003（3）：85?86.

[8] 李亞敏，李小鵬，吳果.身份認證的密鑰交換算法[J].計算機工程，2006，32（12）：171?172.

[9] BONEH D. The decision Diffie?Hellman problem [C]// Proceedings of 1998 the Third Algorithmic Number Theory Symposium. Berlin： Springer， 1998： 48?63.

[10] HSIEH B T， SUN H M， HWANG T. Cryptanalysis of enhancement for simple authentication key agreememt algorithm [J]. Electronics letters， 2002， 38（1）： 20?21.

[11] 德爾夫斯，克內貝爾.密碼學導引：原理與應用[M].肖國鎮，張寧，譯.北京：清華大學出版社，2008.