基于二叉樹的非簽名認證密鑰協商協議

吳福生 張煥國

(武漢大學計算機學院 武漢 430072) (空天信息安全與可信計算教育部重點實驗室(武漢大學) 武漢 430072)

基于二叉樹的非簽名認證密鑰協商協議

吳福生 張煥國

(武漢大學計算機學院 武漢 430072) (空天信息安全與可信計算教育部重點實驗室(武漢大學) 武漢 430072)

(liss@whu.edu.cn)

協議是網絡通信的規范，密碼協議是信息安全的關鍵技術之一，安全的密碼協議常常依賴于簽名或消息認證技術.簽名或消息認證給密鑰協商協議通信帶來大量計算，不利于計算能力有限設備的網絡通信.設計具有計算量小又實用的安全協議是信息安全研究目標之一.故以整數乘法同態映射和二叉樹為基礎，提出一種新的密鑰協商協議，并在開源的OpenSSL環境下實現新協議模擬實驗，給出二叉樹葉子結點數變化對網絡通信影響的模擬實驗和實驗結果分析.新協議在隨機預言模型下可證明安全，即在公鑰加密方案中新協議滿足選擇明文攻擊不可區分性的(IND-CPA)安全.新協議與經典的密鑰協商協議相比(例如MTI，MQV，HMQV)，計算量小、強安全假設少、無需額外的簽名與消息認證，且可以在非安全通信信道上進行安全通信.

協議；密碼學；同態；二叉樹；可證明安全

密鑰協商協議是網絡空間信息安全研究的重點[1].已經在很多方面得到應用，特別是基于分布式安全多方計算的密鑰協商協議的應用，引起學者們廣泛的關注[2].Diffie和Hellman[3]在1976年提出著名的Diffie-Hellman密鑰協商協議(簡稱Diffie-Hellman協議)，第1次在非安全的公共通信信道上實現密鑰協商.此后，許多研究者以Diffie-Hellman協議為基礎，提出改進的密鑰協商協議，著名的有MTI系列[4-6]密鑰協商協議、MQV[7]密鑰協商協議和KEA密鑰協商協議[8].MQV協議的改進協議[9]引起研究者極大的關注，已成為IEEE P1363-2000標準[10].目前，以MQV為基礎的最新研究成果有：HMQV[11]，OAKE[12]，sHMQV[13]，YAK[14-15]等密鑰協商協議.其中，最具代表性的是HMQV密鑰協商協議.

這些協議在密鑰協商方面已有很大的改進，但是仍存在一些不足：Diffie-Hellman協議無法抵抗中間人攻擊；MTI系列容易受到未知密鑰攻擊、Lim-Lee攻擊、身份假冒攻擊；MQV容易受到密鑰泄露偽裝攻擊； HMQV協議及以它為基礎的改進協議無法在多種移動終端設備上實行(受計算能力有限或安全性不高等因素制約).上述密鑰協商協議的安全性必須依賴于簽名或消息認證，因此增加協議的時間開銷.更詳細的密鑰交換協商協議參考文獻[16].

本文以整數乘法同態映射*整數乘法同態映射：設α，β∈Z-{0}，f：Z-{0}→Z-{0}，滿足f(α)*f(β)= f(α*β).和二叉樹為基礎，提出一種新的密鑰協商協議，并且在OpenSSL的C語言環境下給出新協議葉子結點參數變化的網絡通信模擬實驗和實驗結果分析.新協議無需依賴額外簽名或消息認證，也能提供協議參與者之間隱式認證和抵抗中間人攻擊.由于無須簽名或認證，可減少通信時間開銷，新協議應用于計算能力有限的設備或大數據、云計算網絡環境下的通信時，在計算量的開銷上有一定的優勢.

1 基礎知識

本文以整數環上的乘法同態映射為基礎，根據群的同態概念給出基本定義與定理.

1.1 基本定義

定義1. 群同態[17].設G1，G2是2個群(半群、幺半群)，“*” 為二元乘法運算.f是G1到G2的映射，如果f滿足：

?x,y∈G1,f(x)∈G2,
f(x)*f(y)=f(x*y)，

(1)

則稱f是群(半群、幺半群)G1到群(半群、幺半群)G2的一個同態映射，簡稱同態.

定義2. 映射.由于f是半群或幺半群+上的一個映射，“*”為二元乘法運算，f滿足：

f(x)×f(y)=f(x×y)x,y∈+.

(2)

根據定義1，稱f是半群或幺半群+到自身的一個整數乘法同態映射，x,y∈+稱之為整數同態點，而對應的點f(x*y)∈+稱為整數同態值.

1.2 基本定理

定理1. 如果在整數環上的半群或幺半群+上存在一個整數乘法同態映射f，從半群或幺半群+任意取n個數ai∈+,i=1,2,…,n，則一定存在一個整數乘法同態值f(a1*a2*…*an)與之對應.

證明: 任取n個整數，?a1,a2,…ai,…,an∈+，計算f(a1)*f(a2)*…*f(an)，令其值為v：

f(a1)*f(a2)*,…,*f(an)=v.

(3)

根據乘法的結合律兩兩結合，式(3)可變為

(4)

1) 當n為偶數時，剛好兩兩匹配，適合乘法結合律，即式(4)不變.

2) 當n為奇數時，增加一項f(1)=1，不影響式(4)積值.

由1)和2)可知，總是存在式(4)的表示法.由定義2，式(4)可變為

f(a1*a2)*…*f(an-1*an)=v.

(5)

根據乘法結合律兩兩結合，以此類推，最后等式成立：

f(a1*a2*…*an-1*an)=v.

(6)

由此可得，式(3)與式(6)相等:

f(a1)*f(a2)*…*f(an)=
f(a1*a2*…*an)=v.

(7)

證畢.

2 整數乘法同態二叉樹的構造與分析

二叉樹在計算機科學中是一種常用的數據結構.它既可用抽象的代數理論表示，也可用程序語言偽代碼表示，介于理論與程序代碼之間.因此，二叉樹結構非常容易轉化為實際執行的計算機程序代碼.

2.1 整數乘法同態二叉樹的構造

2) 根據定義2，計算f(xi)*f(xj)=vi,j，f(xi*xj)=f(vi,j)=vi,j.

3) 由定理1，等式f(xi)*f(xj)=f(xi*xj)=vi,j成立.

4) 以f(xi)=vi為左子樹、f(xj)=vj為右子樹、f(xi*xj)=vi,j為根結點，構造1棵二叉樹.下面給出任意2個結點的構造二叉樹，如圖1所示:

Fig. 1 The binary tree structure of any two nodes圖1 任意2結點的構造二叉樹

5) 隨機選取xi+1,xj+1∈+，執行過程1)～4)構造第2棵二叉樹，得到以f(vi+1*vj+1)=vi,j,i+1,j+1為根結點的二叉樹，如圖2所示:

Fig. 2 The binary tree structure of any two nodes圖2 任意2結點的構造二叉樹

6) 由定理1可知:

f(xi*xj)*f(xi+1*xj+1)=
f(xi*xj*xi+1*xj+1)

成立，則以f(xi*xj)=vi,j為根結點為左子樹、以f(xi+1*xj+1)=vi+1,j+1為根結點的右子樹、以f(vi+1*vj+1)=vi,j,i+1,j+1為根結點，構造1棵二叉樹，如圖3所示：

Fig. 3 A binary tree圖3 二叉樹

7) 以此類推，當n個隨機數兩兩匹配結束，則構造成1棵葉子結點數為n的二叉樹T，稱之為整數乘法同態二叉樹，如圖4所示：

The binary tree with n leaf nodes圖4 n個葉子結點的構造二叉樹

2.2 整數乘法同態二叉樹的基本遍歷與性質

整數乘法同態二叉樹沒有空樹，即不會有空操作.整數乘法同態二叉樹的基本遍歷與性質類似于數據結構[18]中的二叉樹的基本遍歷與性質.整數乘法同態二叉樹的基本遍歷和性質如下：

2.2.1 整數乘法同態二叉樹的先序遍歷

為了清楚整數乘法同態二叉樹的先序遍歷，給出先序遍歷步驟：

1) 訪問根結點；

2) 先序遍歷左子樹；

3) 先序遍歷右子樹.

① 雖然通信雙方A與B注冊有相同的點，但其認證結構不同于以往的Diffie-Hellman擴展協商協議，即使敵手E能得到A或B的所有注冊點，也無法獲得A與B的共享密鑰.詳細分析見4.3節.

2.2.2 整數乘法同態二叉樹的基本性質

性質1. 整數乘法同態二叉樹的第i層上至多有2i-1個結點(i≥1).

性質2. 整數乘法同態二叉樹的深度為k時，二叉樹至多有2k-1個結點(k≥1).

3 整數乘法同態二叉樹的密鑰協商協議

通信雙方A和B在可信第三方TA中一次性注冊一些相同的可信同態點①(素數，且A端的同態點集合中不會有相同點，同理B端的同態點集合中不會有相同點).這些點數量滿足2h,h∈n，即葉子結點是以2h配對增加，(如h=1時葉子結點為2，h=2時葉子結點為4，h=3時葉子結點數為8，即葉子結點是以2h配對增加).當協議運行時，分別在A和B端構造1棵整數乘法同態二叉樹(其葉子結點為素數).通過整數乘法同態二叉樹的先序遍歷，找到認證點(即同態值)，取同態值的左、右子樹根結點作為參數，然后基于Diffie-Hellman協議進行密鑰協商，得到共享會話密鑰kAB，即完成通信雙方的隱式認證.該共享會話密鑰kAB可應用于認證、加密、簽名等.當協議結束時，通信雙方釋放構造的整數乘法同態二叉樹.

3.1 構造1棵葉結點為素數的整數乘法同態二叉樹

根據2.1節的整數乘法同態二叉樹構造方法，構造1棵葉子結點為素數的整數乘法同態二叉樹.構造方法如下：

設Z1?+和Z2?+是2個整數環上的半群或幺半群，Z1，Z2是+上的一個劃分，且Z1={pi|p∈primes∧i∈n}.f是+到自身的一個整數乘法同態映射，pi,pj∈Z1，i,j∈n,i≠j不同的素數.隨機選取pi,pj，構造1棵葉子結點為素數的同態二叉樹，其步驟為：

1) 隨機選取不同的素數pi，pj，計算f(pi)=pi，f(pj)=pj，f(pi*pj)=vi,j.

2) 以f(pi)=pi為左子樹、f(pj)=pj為右子樹、f(pi*pj)=vi,j為根結點，構造1棵葉子結點為素數的同態二叉樹.

3) 隨機選取pi+1，pj+1，計算f(pi+1)=pi+1，f(pj+1)=pj+1，f(pi+1*pj+1)=vi+1，j+1，以f(pi+1)=pi+1為左子樹，f(pj+1)=pj+1為右子樹，f(pi+1*pj+1)=vi+1，j+1為根結點，構造1棵葉子結點為素數的同態二叉樹.

4) 分別以步驟2)的根結點f(pi*pj)=vi,j為左子樹根結點、步驟3)的根結點f(pi+1*pj+1)=ni+1，j+1為右子樹根結點，構造1棵葉子結點為素數的同態二叉樹.

5) 重復步驟1)～4)，n個素數葉子結點兩兩配對完成后，構造出1棵葉子結點為素數的同態二叉樹，稱之為Ti，j，如圖5所示:

Fig. 5 The homomorphic binary tree with n leaf nodes of the primenumbers圖5 葉子結點為n個素數的同態二叉樹

3.2 整數乘法同態二叉樹密鑰協商協議具體步驟

Ti，j是已經構造好的葉子結點為素數的同態二叉樹.為證明方便，用一個集合{Ti，j}表示構造好的同態二叉樹，分別存儲于通信雙方(A和B).pi,pj∈Z1,i,j∈n,i≠j是葉子結點(即為素數).G是一個素數階為N的循環群，g∈G是群G的生成元.

f為+到自身的一個同態映射：f(x)=x，x∈+.

參數設置：{Ti，j}，ri,rj∈{Ti，j},i,j∈n,i≠j保密；結點ri,j∈{Ti，j}，G，g公開.協議執行步驟：一輪A與B密鑰協商，如圖6所示，“‖”表示連接.

Fig. 6 One round A and B key exchange protocols圖6 一輪A與B密鑰交換協議

1)A在整數乘法同態二叉樹中，如圖5所示，隨機選取2個兄弟結點數ri,rj，且計算：f(ri)=ri，f(rj)=rj，f(ri)*f(rj)=f(ri*rj)=ri，j，X=grimodN，把(X‖ri，j)發送給B.

2)B收到(X‖ri,j)，根據2.2.1節整數同態二叉樹的先序遍歷，查找ri,j.如果查找成功，取ri,j的左子樹根結點ri，計算Y′=grimodN，然后驗證等式X=Y′，相等則B相信(X‖ri,j)是由A發送.否則，終止協議執行.

所以A與B生成共享密鑰kAB，即完成通信雙方的密鑰協商.

4 協議安全分析

新協議可以抵抗中間人攻擊.當只有2個大素數葉子結點時，新協議的安全性等價于大整數因式分解的困難.新協議滿足CDH與DDH安全性假設及GDH[19]假設.給出新協議結構的安全證明.

4.1 一般安全性分析

1) 建立敵手模型.設E是攻擊者，E具有Dolev-Yao[20]模型的能力：①完全控制網絡信息交換，即敵手可以獲得網絡上的任何信息；②主動攻擊與被動攻擊(冒充、截取、注入、重放等能力)；③詢問隨機預言模型；④離線計算能力.

2) 假設在通信雙方A和B端當且僅當取2個大素數葉子結點pi,pj時，即為pi*pj=ni,j，其安全性等同于RSA算法.

3) 新協議以Diffie-Hellman為基礎，滿足CDH與DDH假設.

① 滿足CDH假設：存在一個PPT算法C，在樹{Ti，j}隨機選取ri,rj，存在:

Pr[Cg,gri,grj=gri]≤ε(n)，

(8)

其中,ε(n)為概率可忽略不計函數.即協議滿足CDH假設安全.

② 滿足DDH假設：存在一個PPT算法C，在樹{Ti，j}隨機選取ni,nj，存在:

Pr[Cg,gri,grj,grirj=1]-
Pr[Cg,gri,grj,gc=1]≤ε(n)，

(9)

其中,ε(n)為概率可忽略不計函數.即協議滿足DDH假設安全.

4) 新協議沒有使用簽名與消息認證，但可以抵抗中間人攻擊和具有隱式認證功能.

Ⅰ必須解決離散對數難解問題，即求解截獲X的指數ri；

Ⅱ整數因式分解問題，即分解截獲的大整數ri,j的因子ri.故協議可以抵抗中間人攻擊.

5) 會話密鑰kAB的前向安全.由同態二叉樹可知，ri,j是隨機選擇，具備新鮮度,所以每次得到的會話密鑰kAB都不一樣，且每次都是獨立.故前后生成的kAB不會相互泄密信息，保證新協議的前向安全成立.

4.2 基于隨機預言模型(random oracle model)的可證明安全分析

設DDH(·)為預言機，D為一個求解GDH問題的算法.

定義求解的優勢概率為

Pr[D(g,gri,grj,gri)=1]-
Pr[D(g,gri,grj,gc)=1].

(10)

如果其優勢概率滿足：

Pr[D(g,gri,grj,gri)=1]-
Pr[D(g,gri,grj,gc)=1]≤ε(n)，

(11)

ri,rj∈+,g∈G，ε(n)可忽略不計的.則稱協議滿足GDH假設.

(12)

當n→∞時，優勢概率可忽略不計，協議在RO模型下是可證明安全的，即滿足IND-CPA安全.

證畢.

4.3 新協議結構的安全分析

由新協議構造可知，假設敵手E在2種情況下成立，則E可以攻破協議.

1)E可獲取A或B端的注冊點，即同態點.

2) 二叉樹的結點不唯一(例如存在：當ri≠rj≠rk≠rm,i,j,k,m∈n，有rirj=rkrm).

證明.

1) 假設E獲取了A或B端的注冊點，設為{p1,p2,…,p2n}.由3.1節可知，在構造二叉樹時，葉子結點是配對組成由數學的排列組合可知h∈n.

(13)

證畢.

5 新協議性能比較與分析

本文分別從3個方面分析新協議的性能.

5.1 新協議的二叉樹存儲與遍歷

二叉樹是計算機科學中常用的一種數據結構，其常用存儲方式有2種：1)順序存儲;2)鏈式存儲.不管是哪一種存儲，在它最壞情況下空間復雜度為O(n)，遍歷的時間復雜度為O(n).

設新協議的二叉樹葉子結點為n，分析新協議最壞情況的存儲.根據性質1(見2.2.2節)得到新協議的二叉樹深度為i=lbn+1.根據性質2(見2.2.2節)得到新協議總結點數為：2lb n+1-1=2n-1.由此可知，新協議存儲空間為線性O(n).根據其存儲方式可知其遍歷復雜度為線性O(n)，故新協議可實現.

5.2 計算量比較

選取4種以Diffie-Hellman協議為基礎的相似協議和同類橫向2種身份識別協議，比較它們在最壞情況下計算量大小和在協議中會用的安全假設個數，結果如表1所示，其中的Texp表示1次指數運算的時間.

Table 1 Compared Performance of the Protocols表1 協議的性能比較

表1中協議使用的簽名或消息認證為

從表1可以看出，提出的新協議在計算量的開銷方面具有明顯優勢，原因是新協議不需要加入簽名和消息認證.同時協議只使用1個強安全假設GDH，與使用2個強安全假設(GDH，KEA[21]假設)的密鑰協商協議(HMQV，OAKE)相比，新協議在實際應用中安全性更高.

5.3 參數n對網絡通信的影響

參數n對新協議在網絡通信中的影響主要表現為：1)結點的查找；2)通信時間開銷.

(14)

當n→∞時，平均查找長度為：lbn.故新協議查找長度為對數可以實現.

2) 新協議基于OpenSSL下的C語言代碼模擬實驗，分析參數n變化對新協議在網絡通信中所用時間的影響.

本文給出n的2種變化形式對新協議在網絡通信中的影響：①二叉樹素數葉子結點個數(numbers of nodes,N)；②葉子結點的位數(node bits,bits).

實驗環境：Intel?CPU G3240，內存4 GB；Win7，Visual studio 2010，openSSL-1.0.1 s.使用OpenSSL函數庫的大數運算，其中包括大數模指數運算函數、大素數生成函數等使用.參與者之間的通信經過Socket API的TCP連接.

采用服務器與客戶端模式進行模擬實驗，分別得出葉子結點個數與結點位數變化在網絡通信中的時間開銷，如表2所示(行表示葉子結點的位數，列表示葉子結點的個數N，行列交點表示網絡傳輸花費的時間).

Table 2 The Effect of the Network Communication Based on Binary Tree Nodes表2 二叉樹結點的網絡通信影響 s

對表2的數據分別以行、列及網絡通信時間(s)作為坐標進行分析.實驗數據分析結果：圖7表示葉子結點個數變化對網絡通信時間的影響；圖8表示葉子結點位數變化對網絡通信時間的影響.

Fig. 7 The effect of the number of leaf nodes on communication time in network圖7 葉子結點個數變化對網絡通信時間的影響

Fig. 8 The effect of the bit of leaf nodes on communication time in network圖8 葉子結點位數變化對網絡通信時間的影響

3) 結果分析：

① 從圖7與圖8可知，結點個數N和結點位數bits，在比較小的情況下，對網絡通信并沒有太大的影響.但隨著它們變大，網絡通信時間開銷隨之增長.②結點位數帶來的網絡時間開銷增長比結點的個數帶來的時間開銷增長快.③不防設結點個數與位數的比值為：δ=N/b.當δ越小，則葉子結點位數越大，需要的葉子結點個數越少.這不僅保證了新協議的安全，而且消耗的資源更少(如葉子結點的個數、二叉樹結點尋找時間等).例如，如果葉子結點是1 024 b二進制素數，新協議只需要2個大素數葉子結點，就能生成1個2 048 b二進制整數根結點.這時新協議的安全等價于1個2 048 b二進制大整數因式分解的困難.故新協議的安全完全等價于RSA的安全[23].

6 結束語

本文對已有密鑰協商協議進行了研究，提出一種計算量小、無需簽名和消息認證等額外時間開銷的密鑰協商協議.提出的新協議方案具有計算量小、強安全假設少、占用資源少等優點，具有一定的創新性與適用性.其安全性依賴離散對數與大整數因式分解困難問題.新協議引入二叉樹及其性質和特點，使得協議更容易轉化為實際的程序語言代碼，適用于云計算、 物聯網、 社交網絡和大數據等新興網絡通信服務.協議并發通信的安全與認證將作為未來的研究方向.

[1]Zhang Huanguo, Han Wenbao, Lai Xuejia, et al. Survey on cyberspace security[J]. Scientia Scinica: Informations, 2116, 46(2): 125-164 (in Chinese)(張煥國, 韓文報, 來學嘉, 等. 網絡空間安全綜述[J]. 中國科學: 信息科學, 2016, 46(2): 125-164)

[2] Jian Han, Xu Qiuliang. Advances in key techniques of practical secure multi-party computation[J]. Journal of Computer Research and Development, 2015, 52(10): 2247-2257 (in Chinese)(蔣瀚, 徐秋亮. 實用安全多方計算協議關鍵技術研究進展[J]. 計算機研究與發展, 2015, 52(10): 2247-2257)

[3] Diffie W, Hellman M. New directions in cryptography[J]. IEEE Trans on Information Theory, 1976, 22(6): 644-654

[4] Lim C H, Lee P J. A key recovery attack on discrete long-based schemes using a prime order subgroup[G] //LNCS 1294: Advances in Cryptology 1997. Berlin: Springer, 1997: 249-263

[5] Just M, Vaudenay S. Authenticated multi-party key agreement[G] //LNCS 1163: Advances in Cryptology 1996. Berlin: Springer, 1996: 36-49

[6] Goss K C. Cryptographic method and apparatus for public key exchange with authentication: USA, US4956863[P]. 1990-09-11

[7] Menezes A, Qu M, Vanstone S. Some new key agreement protocols providing implicit authentication[C] //Proc of the 2nd Workshop Selected Areas in Cryptography. Berlin: Springer, 1995: 89-98

[8] Schneier B. Skipjack and kea algorithm specification version 2.0[R/OL]. Washington: National Security Agency, 1998 [2016-10-30]. http://ece.gmu.edu/coursewebpages/ECE/ECE646/F09/project/reports_1999/carlton_report.pdf

[9] Law L, Menezes A, Qu M, et al. An efficient protocol for authenticated key agreement[J]. Designs, Codes and Cryptography, 2003, 28(2): 119-134

[10] IEEE. Standard specifications for public-key cryptography[S]. New York: Institute of Electrical Electronics Engineers, 2000: 1-228

[11] Krawczyk H. Hmqv: A high-performance secure Diffie-Hellman protocol[G] //LNCS 3621: Advances in Cryptology 2005. Berlin: Springer, 2005: 546-566

[12] Yao Qizhi. Zhao Yunlei. Oake: A new family of implicitly authenticated Diffie-Hellman protocols[C] //Proc of the 2013 ACM SIGSAC Conf on Computer & Communications Security. New York: ACM, 2013: 1113-1128

[13] Zhao Shijun, Zhang Qianying. Shmqv: An efficient key exchange protocol for power-limited devices[G] //LNCS 9065: Information Security Practice and Experience ISPEC 2015. Berlin: Springer, 2015: 154-167

[14] Feng Hao. On robust key agreement based on public key authentication[J]. Security and Communication Networks, 2014, 7(1): 77-87

[15] Toorani M. Cryptanalysis of a robust key agreement based on public key authentication[J]. Security and Communi-cation Networks, 2016, 9(1): 19-26

[16] Feng Dengguo. Security Protocol—Theory and Practice[M]. Beijing: Tsinghua University Press, 2011: 273-316 (in Chinese)(馮登國. 安全協議——理論與實踐[M]. 北京: 清華大學出版社, 2011: 273-316)

[17] Xu Shurun, Meng Daoji, Xiao Yongzhen, et al. Concise Mathematics Dictionary[M]. Beijing: Science Press, 2002: 45-88 (in Chinese)(徐書潤, 孟道驥, 蕭永震, 等. 簡明數學詞典[M]. 北京: 科學出版社, 2002: 45-88)

[18] Clifford A. Data Structures, Algorithm Analysis in C++[M]. 3rd ed. New York: Dover Publications, 2011: 155-160

[19] Okamoto T, Pointcheval D. The gap-problems: A new class of problems for the security of cryptographic schemes[C] //Proc of Int Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography 2001. Berlin: Springer, 2001: 104-118

[20] Dolev D, Yao Qizhi. On the security of public key protocols[J]. IEEE Trans on Information Theory, 1983, 29(2): 198-208

[21] Bellare M, Palacio A. The knowledge-of-exponent assum-ptions and 3-round zero-knowledge protocols[G] //LNCS 3152: Advances in Cryptology 2004. Berlin, Springer: 2004: 273-289

[22] Yan Weimin, Wu Weimin. Data Structure (C Language Version)[M]. Beijing: Tsinghua University Press, 2008: 118-152 (in Chinese)(嚴蔚敏, 吳偉民. 數據結構(C語言版)[M]. 北京: 清華大學出版社, 2008: 118-152)

[23] Beniwal S, Yadav E, Savita. An effective efficiency analysis of random key cryptography over Rsa[C] //Proc of the 2nd Int Conf on Computing for Sustainable Global Development. Piscataway, NJ: IEEE, 2015: 267-271

KeyAgreementProtocolsofNon-SignatureAuthenticationBasedonBinaryTree

Wu Fusheng and Zhang Huanguo

(SchoolofComputerScience,WuhanUniversity,Wuhan430072) (KeyLaboratoryofAerospaceInformationSecurityandTrustedComputing(WuhanUniversity),MinistryofEducation,Wuhan430072)

Protocol is the specification of the network communication. Then cryptographic protocol, whose safety is based on signature or authentication technology, is one of the key techniques of information security. The technique of signature or authentication needs huge computation during communicating, which brings barriers for many communication devices because of their limited computing power. Therefore, it is an aim of studying information security to design a secure cryptographic protocol, which is practical but doesn’t need huge computation. In this paper, a novel key agreement protocol is proposed, which is based on the binary tree and the homomorphic mapping of integer multiplication. Meanwhile, an experiment is carried out in an open source (OpenSSL) systems to test how nodes of leaf binary trees affect network communication and the result of the experiment is analyzed. Our scheme is successful because our key agreement protocol is proved to be safe in the random oracle model. That is to say, in the PKI system, our key agreement protocol meets the requirement of the indistinguishable chosen plaintext attack (IND-CPA ) security. Compared with previous protocols (like MTI, MQV, HMQV), our key agreement protocol has many advantages: the computation is small; only one strong security assumption is needed; it dispenses with extra authentication of MAC and digital signature; and communicating parties can authenticate implicitly through unsafe channels.

protocols; cryptography; homomorphism; binary tree; provably secure

2016-11-01；

2017-02-06

國家自然科學基金重點項目(61332019)；國家“九七三”重點基礎研究發展計劃基金項目(2014CB340601)

This work was supported by the Key Program of the National Natural Science Foundation of China (61332019) and the National Basic Research Program of China (973 Program) (2014CB340601).

TP309

WuFusheng, born in 1974. PhD. His main research interests include design of cryptographic protocols and security analysis of cryptographic protocols.

ZhangHuanguo, born in 1945. Professor and PhD supervisor in Wuhan University. His main research interests include cryptography and trusted computing, and cryptographic protocols.