可識別非法用戶的群密鑰協(xié)商協(xié)議

莊鋒茂, 林修慧, 林昌露*

(1.福建體育職業(yè)技術(shù)學院 體育保健系， 福建 福州 350003；2.福建師范大學 數(shù)學與信息學院， 福建 福州 350117)

0 引言

隨著現(xiàn)代科技的發(fā)展, 人們的網(wǎng)絡通信日益頻繁, 對通信安全的要求也越來越高。 群密鑰協(xié)商協(xié)議在通信領域中被廣泛使用, 它分為交互式密鑰協(xié)商協(xié)議和非交互式密鑰協(xié)商協(xié)議兩種。 非交互式密鑰協(xié)商協(xié)議是由一個密鑰生成中心(key generation center, KGC) 生成密鑰, 然后注冊其他用戶, 用戶之間使用密鑰進行交流； 交互式密鑰協(xié)商不存在KGC, 而是用戶之間互相注冊, 共同協(xié)商出用于通信的密鑰。

1976 年, Diffie 和Hellman 首先提出了兩方的密鑰協(xié)商協(xié)議(簡稱為DH 協(xié)議), 其安全性建立在有限域上離散對數(shù)求解困難的假設, 克服了沒有可信任第三方的問題, 且是第一個交互式的密鑰協(xié)商協(xié)議[1]。 但是其局限是僅支持兩個用戶之間的密鑰協(xié)商, 且容易受到中間人攻擊。直到2000 年, Joux 以橢圓曲線為工具首次提出了三方的密鑰協(xié)商協(xié)議[2], 其局限性是無法支持多方用戶協(xié)商。 Steiner 等也以DH 協(xié)議為基礎提出了n 方的協(xié)商協(xié)議[3], 但是該協(xié)議不能驗證用戶的身份。 之后Boneh 等以不可區(qū)分混淆來建立多方密鑰交換協(xié)議[4]。 但這些協(xié)議都是基于公鑰加密體系而設計的, 在多方的通信交流中, 其計算復雜度比較高, 而且每個用戶都必須存儲其他用戶的公鑰, 這極大地占用了存儲空間并帶來一些密鑰管理的麻煩。 基于秘密分享的思想[5], Harn 等使用對稱雙變量多項式提出了一個非交互式的群密鑰協(xié)商協(xié)議[6], 該協(xié)議是由KGC 隨機選擇一個密鑰, 然后生成一個對稱雙變量多項式并把密鑰隱藏在多項式的常數(shù)項, 分發(fā)給指定的用戶相應的份額, 合法用戶的人數(shù)只要滿足門限就能夠正確地重構(gòu)出這個密鑰。 它的特點是用戶只要在多項式計算復雜度下就能得到密鑰, 并且可以檢測識別出非法的用戶, 也不需要存儲其他用戶的公鑰, 但該協(xié)議檢測階段的算法計算成本較高, 需要進行大量的模指數(shù)計算,在一些使用輕量級設備的場景下不能得到很好應用。 之后, 陸續(xù)有學者進行了研究[7-9], 曾繼強等通過基于DH 協(xié)議的橢圓曲線算法(ECC)提出群密鑰協(xié)商協(xié)議[10]。 Zhang 等使用屬性加密和身份驗證技術(shù), 提出了非對稱群密鑰協(xié)商協(xié)議, 適用于不安全的移動網(wǎng)絡[11], 這些協(xié)議的安全性是基于離散對數(shù)困難問題, 所以計算復雜度相對較大。 Hsu 等最近又提出了一個面向多個群的密鑰協(xié)商協(xié)議[12], 但是被Mitchell 證明它是不安全的[13]。 基于Harn 等的協(xié)議[6], 本文提出了一種高效的識別方法。 在非法用戶的識別階段, 利用對稱雙變量多項式的對稱性可快速地識別非法用戶, 用戶只需要執(zhí)行哈希運算來驗證等式是否成立。

1 預備知識

1.1 對稱雙變量多項式

定義1(對稱雙變量多項式[6]) 設p 是一個公開的大素數(shù), GF(p) 是p 元有限域, 對任意ai,j∈GF(p), i, j ∈[0, t - 1] 把F(x, y) =a0,0+ a1,0x + a1,0y + a2,0x2+ a2,0y2+ … +at-1,t-1xt-1yt-1稱作雙變量多項式； 如果對任意的i, j ∈[0, t - 1] 都有ai,j= aj,i, 那么稱它為對稱雙變量多項式。 顯然, 對任意的xi和yi, 都有F(xi, yi) = F(yi, xi)。

1.2 敵手模型

本文協(xié)議中, 只考慮兩種敵手模型： 內(nèi)部敵手和外部敵手。 內(nèi)部敵手是合法的用戶, 擁有KGC 所分發(fā)的密鑰份額, 會忠實執(zhí)行協(xié)議但會嘗試恢復其他合法用戶的密鑰份額, 并且這些敵手會秘密地交換已有的信息。 有時也稱內(nèi)部敵手為誠實且好奇的敵手。 外部敵手不是合法的用戶, 沒有KGC 所分發(fā)的密鑰份額, 不會忠實地執(zhí)行協(xié)議, 會發(fā)送錯誤的消息或者截獲合法用戶之間傳輸?shù)南? 并且試圖去獲得其他合法用戶的份額或最終協(xié)商的密鑰。 有時也稱外部敵手為惡意的敵手。

2 本文協(xié)議

本文協(xié)議是基于非公鑰加密體系構(gòu)造的, 所以不需要復雜的模指數(shù)運算, 每個用戶不需要存儲其他用戶的公鑰, 只需要存儲一個單變量多項式。 另外本文根據(jù)對稱雙變量多項式的對稱性提出了一種高效的識別非法用戶的方法, 只需校驗用戶份額的哈希值是否相等, 而不要進行大量的計算。 本文協(xié)議有以下三個階段。

密鑰生成和分發(fā)階段： KGC 隨機選擇一個密鑰, 并生成一個隨機的對稱雙變量多項式把密鑰掩蓋起來, 再公開密鑰的哈希值。 同時再為每個用戶分配相應的身份ID 值并且公開。 然后把每個用戶的ID 值分別代入對稱雙變量多項式進行計算, 會得到對應的單變量多項式, 接著秘密地分發(fā)給相應ID 值的用戶, 作為這些用戶的密鑰份額。

密鑰驗證階段： 每個用戶利用自己的密鑰份額計算出對應其他用戶的傳輸密鑰, 然后使用傳輸密鑰加密自己的密鑰份額并傳輸給其他用戶, 每個用戶收到所有其他用戶發(fā)來的信息后, 再使用相應的傳輸密鑰進行解密, 之后就能重構(gòu)出密鑰。

非法用戶識別階段： 如果發(fā)現(xiàn)重構(gòu)的密鑰哈希值與公開的密鑰哈希值不相等, 說明存在非法用戶, 那么每個用戶互相發(fā)送傳輸密鑰的哈希值給其他用戶進行識別, 這樣只要驗證哈希值是否相等就能找出非法用戶。

本文的計算都是在GF(p) 上進行的, p 是公開的大素數(shù)。 P1, P2, …, Pn表示n 個用戶, 其對應的身份ID 值x1, x2, …, xn也是公開的(如用戶P1的身份ID 值為x1)。

2.1 密鑰生成和分發(fā)階段

KGC 先隨機選取一個群密鑰s, 令a0,0= s,再隨機生成對稱雙變量多項式F(x, y) = a0,0+a1,0x + a0,1y + a2,0x2+ a1,1xy + a0,2y2+ … +at-1,t-1xt-1yt-1(mod p), t ＜n, 再公開H(s)。 然后計算si(y) = F(xi, y)(mod p), 把si(y) 秘密分發(fā)給對應的用戶Pi。

2.2 密鑰驗證階段

在這個階段, 任意≥t 個用戶都可以進行群密鑰的驗證, 如果驗證通過就可以使用密鑰進行加密通訊交流, 如果驗證不通過則進入非法用戶識別階段。 不失一般性, 本文假設前t 個用戶P1, P2, …, Pt參與驗證。

第一步： 每個用戶Pi(i = 1, 2, …, t) 計算

第二步： 每個用戶Pi使用自己的份額si(y)計算kij= si(xj)(j = 1, 2, …, t, j ≠i)。 然后計算cij= Ekij(bi), 這里Ekij是以kij為密鑰的公開常規(guī)加密函數(shù)。 最后發(fā)送cij(j = 1, 2, …, t, j ≠i) 給對應的用戶Pj。

第三步： 每個用戶Pj在收到其他用戶發(fā)送的cij(i = 1, 2, …, t, j ≠i) 后, 先使用自己的份額計算kji= sj(xi)(i = 1, 2…, t, i ≠j)。 由于本文使用的是對稱雙變量多項式, 所以會有kji=sj(xi) = F(xj, xi) = F(xi, xj) = si(xj) = kij。 再對cij進行解密計算得到bi= Dkij(cij)(i = 1, 2, …,t, i ≠j)。 這里Dkij是對應Ekij以kij為密鑰的公開證H(s′) 與H(s) 是否相等, 如果相等則說明這些用戶是合法的以及s′ 是正確的群密鑰, 否則執(zhí)行識別算法。

2.3 非法用戶識別階段

在這個階段, 本文將根據(jù)對稱雙變量多項式的對稱性來構(gòu)造識別算法。

第一步： 每個用戶Pi(i = 1, 2, …, t) 向所有其他用戶Pj(j ≠i) 發(fā)送H(kji‖xi)‖xi(符號‖表示串聯(lián)運算符)。

第二步： 每個用戶Pj在收到其他用戶Pi(i≠j) 發(fā)來的H(kji‖xi)‖xi之后可以使用自己的kij對其進行檢驗, 驗證H(kij‖xi)= H(kji‖xi)(j= 1, 2, …, t) 是否成立, 如果成立則說明Pi為合法用戶, 反之Pi就是非法用戶。 這樣, 所有的非法用戶在一輪通信過后都能識別出來。

3 協(xié)議分析

本節(jié)將對上節(jié)協(xié)議進行正確性和安全性分析。 本文協(xié)議的正確性和抵抗內(nèi)部敵手攻擊的分析與Harn 等[6]協(xié)議一致, 故不再贅述。 下文僅對本文協(xié)議抵抗外部敵手攻擊情形進行分析。

定理1 (外部敵手) 如果本文協(xié)議正確執(zhí)行, 那么外部的非法用戶不能獲得密鑰, 并且可以被識別出來。

證 先證明外部敵手不能獲得密鑰s。

在密鑰驗證階段的第二步中, 因為外部敵手沒有sj(y), 而且kij= si(xj)(j = 1, 2, …, t, j≠i), 所以外部敵手就無法通過公開的xj計算得到kij。 在第三步中, 假如外部敵手截獲了在公共網(wǎng)絡上傳輸?shù)腸ij, 但是沒有得到kij, 由bi=Dkij(cij)(i = 1, 2, …, t, i ≠j) 可知外部敵手也無法解密得到相應的bi, 從而不能獲得密鑰s。事實上, 由拉格朗日插值公式可知, s =

接下來證明外部敵手可以被快速的識別出來。

當外部敵手試圖假扮合法用戶時, 由前面的證明知道外部敵手無法得到kij, 由哈希函數(shù)的抗碰撞性可以知道, 外部敵手無法計算出正確的H(kij‖xi)‖xi, 也就是說外部敵手會被識別出來。

4 協(xié)議比較

在本文協(xié)議中, 由于ID 值是KGC 隨機分配, 所以并不會造成用戶隱私的泄露。 本文方法是基于對稱雙變量多項式所提出的, 用戶之間可以互相利用對稱雙變量多項式的對稱性, 驗證哈希值是否相等來高效識別合法用戶。 因為本文協(xié)議不是基于公鑰加密體系構(gòu)造, 故不需要公鑰基礎設施去額外的認證, 也不需要復雜的模指數(shù)運算。 表1 給出了本文協(xié)議與其他協(xié)議的具體對比。

表1 協(xié)議的特性對比

如表1 所示, 本文協(xié)議在個人隱私保護、 非法用戶識別、 計算復雜度方面均有較好的特性。

5 總結(jié)

本文是給出了一種高效識別非法用戶的協(xié)議。 只要進行哈希驗證就可以識別非法用戶。 經(jīng)過分析, 滿足了正確性和安全性要求, 可以保護用戶的個人隱私, 不需要進行復雜的模指數(shù)運算, 也不需要額外的密鑰認證設施, 相較于其他協(xié)議均有較優(yōu)的特性。