無雙線性對的網(wǎng)絡(luò)編碼無證書簽密

俞惠芳楊 柯

(西安郵電大學(xué)網(wǎng)絡(luò)空間安全學(xué)院 西安 710121)

1 引言

網(wǎng)絡(luò)編碼[1,2]是一種數(shù)據(jù)路由方法。不同于傳統(tǒng)路由機(jī)制，網(wǎng)絡(luò)編碼允許中間節(jié)點(diǎn)在傳輸數(shù)據(jù)包之前對其進(jìn)行編碼。這種做法可讓網(wǎng)絡(luò)達(dá)到最大流最小割定理所規(guī)定的最大吞吐量。網(wǎng)絡(luò)編碼實(shí)際應(yīng)用中的污染問題較為嚴(yán)重，如果網(wǎng)絡(luò)節(jié)點(diǎn)未檢測出被污染的數(shù)據(jù)包直接編碼轉(zhuǎn)發(fā)，會導(dǎo)致污染多個(gè)節(jié)點(diǎn)甚至整個(gè)網(wǎng)絡(luò)。RSA同態(tài)簽名[3]能應(yīng)對污染攻擊和代間重放攻擊。有雙線性對的同態(tài)簽名[4]使用了組合簽名和相應(yīng)節(jié)點(diǎn)的公鑰來驗(yàn)證組合數(shù)據(jù)包，能抗污染攻擊。

無證書公鑰密碼體制由用戶和密鑰生成中心(Key Generation Center,KGC)合作生成用戶完整私鑰，解決了證書管理和密鑰托管。無證書公鑰體制與簽密體制相結(jié)合形成無證書簽密(Certificate-Less SignCryption,CLSC)，首個(gè)CLSC[5]不能防止偽造攻擊。目前大部分CLSC都采用了雙線性對運(yùn)算，雙線性對的運(yùn)算復(fù)雜性高。因此，Selvi等人[6]提出安全的無對運(yùn)算的CLSC。現(xiàn)有沒有使用雙線性映射的無證書簽密[7—9]不適合直接用在網(wǎng)絡(luò)編碼環(huán)境中。

無證書的網(wǎng)絡(luò)編碼同態(tài)簽名[10,11]可擺脫繁瑣的證書管理和對公鑰基礎(chǔ)設(shè)施的嚴(yán)重依賴，同時(shí)具有抗污染攻擊的特性。為了獲得更低的計(jì)算復(fù)雜度，本文構(gòu)建可證安全的不使用雙線性對的網(wǎng)絡(luò)編碼無證書簽密(CertificateLess Pairing-Free SignCryption for Network Coding,NC-CLPFSC)，這是一個(gè)多源的網(wǎng)絡(luò)編碼方法，避免了證書的管理和密鑰的托管，沒有雙線性對運(yùn)算使計(jì)算效率有所提高，同時(shí)通過同態(tài)哈希函數(shù)具備防御污染攻擊能力。

2 基礎(chǔ)知識

2.1 網(wǎng)絡(luò)編碼模型

網(wǎng)絡(luò)編碼模型按源節(jié)點(diǎn)個(gè)數(shù)分成單源節(jié)點(diǎn)的單源網(wǎng)絡(luò)編碼和多源節(jié)點(diǎn)的多源網(wǎng)絡(luò)編碼。多源網(wǎng)絡(luò)編碼模型用無環(huán)多重圖G=(E,M)表示，E是邊集，M是點(diǎn)集。S={s1,s2,···,sm}∈M表示源節(jié)點(diǎn)，T={t1,t2,···,tm}∈M表示目的節(jié)點(diǎn)。圖1展示網(wǎng)絡(luò)中信息流沿一個(gè)方向從源節(jié)點(diǎn)流向非源節(jié)點(diǎn)。

圖1 多源網(wǎng)絡(luò)傳輸模型

每個(gè)消息Vi∈{V1,V2,···,Vm}由有限域F中n個(gè)元素組成，表示為Vi={vi,1,vi,2,···,vi,m}。每個(gè)中

Ho等人[12]描述的隨機(jī)線性網(wǎng)絡(luò)編碼允許選擇用于執(zhí)行分組的線性組合的編碼系數(shù)。在隨機(jī)線性網(wǎng)絡(luò)編碼中，源節(jié)點(diǎn)將m維消息向量Vi擴(kuò)展為m+n維，給每個(gè)消息向量添加一個(gè)規(guī)范向量。擴(kuò)展后消息向量表示為

2.2 困難問題

計(jì)算性D iffie-Hellm an(Com pu tational D iffie-Hellman,CDH)問題：給定大素?cái)?shù)階q的乘法群G,g表示群G的任意生成元，已知(g,ga,gb)∈G，對任意未知的a,b∈,CDH問題的目標(biāo)是計(jì)算

離散對數(shù)(Discrete Logari thm,DL)問題：給定大素?cái)?shù)階q的乘法群G,g表示群G的任意生成元，已知∈G,DL問題的目標(biāo)是計(jì)算

3 具體方案

3.1 系統(tǒng)初始化

乘法循環(huán)群G的階為大素?cái)?shù)q,g是G的一個(gè)生成元。密鑰生成中心(Key Generation Cen ter,KGC)選擇安全的哈希函數(shù)

其中，l1表示任意身份的長度，l2表示簽名的驗(yàn)證標(biāo)識符id長度，l3表示任意消息長度。KGC隨機(jī)選取主公鑰s∈，并計(jì)算系統(tǒng)的公鑰Ypub=gs∈G。公開系統(tǒng)的全局參數(shù)φ={q,G,g,Ypub,H1,H2,H3,ID,M}，其中ID是身份空間，M是明文消息空間。

3.2 密鑰生成

(1)源節(jié)點(diǎn)用戶si選取任意的di∈，計(jì)算Y i=g d i，其中Yi是公開的，隨機(jī)值di是保密的。

(2)K G C 隨機(jī)選取ri∈，分別計(jì)算N i=g r i∈G(Ni是公開的)，h1i=H1(IDi,N i,Y i),t i=(r i+sh1i)modq，KGC發(fā)送ti給源節(jié)點(diǎn)用戶。源節(jié)點(diǎn)用戶使用公式進(jìn)行驗(yàn)證。如果驗(yàn)證通過，說明Yi是源節(jié)點(diǎn)用戶的公鑰，相應(yīng)的私鑰是(ti,di)。

3.3 簽密

給定源節(jié)點(diǎn)用戶身份信息IDs。源節(jié)點(diǎn)用戶發(fā)送消息向量vi的密文給目的節(jié)點(diǎn)。每個(gè)源節(jié)點(diǎn)用戶在發(fā)送消息時(shí)都會附上一個(gè)消息標(biāo)識符id作為整個(gè)數(shù)據(jù)包的一部分而發(fā)送到下游節(jié)點(diǎn)，下游節(jié)點(diǎn)能根據(jù)對應(yīng)的id確定出收到的簽名是由哪一個(gè)節(jié)點(diǎn)發(fā)送的，從而達(dá)到確定出污染節(jié)點(diǎn)位置信息的目的。簽密操作如下：

3.4 組合

3.5 解簽密

4 正確性分析

(1)解密階段正確性分析

(2)單個(gè)數(shù)據(jù)包簽名驗(yàn)證正確性分析

(3)組合驗(yàn)證

5 安全性分析

NC-CLPFSC易受到AI和AII兩類敵手的攻擊。外部攻擊者AI可更改任何用戶的公鑰，卻無法得知系統(tǒng)主密鑰；內(nèi)部攻擊者AII掌握系統(tǒng)的主密鑰，卻不能修改任何用戶的公鑰。注意不允許相同身份的詢問。

定理1(AI攻擊下的機(jī)密性)如果AI能攻破NC-CLPFSC的保密性，則必然存在算法C能解決CDH問題。

證明 假設(shè)C是解決CDH問題實(shí)例＜g,ga,gb＞的挑戰(zhàn)者，a,b∈對于C和AI是未知的，C的目標(biāo)在于計(jì)算gab∈G。AI在游戲中扮演C的子程序。C從q(對H1的詢問次數(shù))個(gè)身份中選擇挑戰(zhàn)身份IDt，＜IDt,t＞對AI是未知的。C維護(hù)起初為空的列表＜L1,L2,L3,L4,LK＞。

C首先輸出運(yùn)行設(shè)置算法得到的φ=＜ q,G,g,Ypub=gb,H1,H2,H3,ID,M ＞。然后，AI在階段1執(zhí)行一系列適應(yīng)性詢問。

H2詢問：C收到AI對H2的詢問時(shí)，C檢查L2中是否存在＜id,vi,h2i＞。如果存在，C返回h2i給AI；否則，C返回任意選取的h2i∈，儲存＜id,vi,h2i＞到L2中。

H3詢問：C收到AI對H3的詢問時(shí)，C檢查L3中

挑戰(zhàn)：階段1結(jié)束時(shí)，AI生成兩個(gè)等長vi0,vi1∈M和身份IDs,IDr(IDs,IDr表示源節(jié)點(diǎn)用戶和目的節(jié)點(diǎn)用戶的身份信息)。在階段1中IDr的完整私鑰不能詢問。如果IDr≠IDt，C放棄游戲；否則，C調(diào)用H1諭言機(jī)和公鑰諭言機(jī)分別獲得＜Ys,Yr＞和＜ts,ds＞，然后計(jì)算得到挑戰(zhàn)密文σ*：

AI在階段2發(fā)出與階段1相同的詢問。AI不能詢問IDr的私鑰也不能對(σ*,c*,R*)執(zhí)行解簽密詢問。L2存儲的元組中存在一個(gè)元組含有CDH問題實(shí)例的解答。最后，C輸出CDH問題實(shí)例的解答

在概率分析中e 表示自然對數(shù)底，qs是詢問私鑰的次數(shù)，qp是詢問部分私鑰的次數(shù)，qr是替換公鑰的次數(shù)，q3是詢問H3的次數(shù)，ε1表示AI攻破NCCLPFSC保密性的概率。根據(jù)文獻(xiàn)[13]方法可得，C在游戲中獲得CDH問題實(shí)例解答的概率是證畢

定理2(AII攻擊下的機(jī)密性)如果AII能攻破NC-CLPFSC的保密性，則必定存在算法能解決CDH問題。

證明 假設(shè)C是解決CDH問題實(shí)例＜g,ga,gb＞的挑戰(zhàn)者，a,b∈對于C和AII是未知的，C的目標(biāo)在于計(jì)算gab∈G。AII在游戲中扮演C的子程序。C從q(對H1的詢問次數(shù))個(gè)身份中選擇挑戰(zhàn)身份IDt，＜IDt,t＞對AII是未知的。C維護(hù)起初為空的列表＜L1,L2,L3,L4,LK＞。

C首先輸出運(yùn)行設(shè)置算法得到的＜φ,s＞給AII。然后，AII執(zhí)行多項(xiàng)式有界次適應(yīng)性詢問。H2,H3詢問與定理1相同，故略去。

公鑰詢問：AII詢問身份IDi的公鑰。如果IDi=IDt，C設(shè)置Y i=g b,N i=g r i(ri∈)。C返回公鑰Yi給AII，添加＜IDi,ri,*,*,Ni,Yi＞到LK中；否則，C選擇＜ri,di＞∈Zq*，計(jì)算Y i=g d i,N i=g r i，返回Yi給AII，添加＜IDi,ri,di,*,Ni,Yi＞到LK中。

H1詢問：C收到AII對H1的詢問時(shí)，C檢查L1中是否存在元組＜IDi,Ni,Yi,h1i＞。如果存在，C返回h1i給AII；否則，C調(diào)用公鑰諭言機(jī)，返回相應(yīng)的h1i給AII，儲存＜IDi,Ni,Yi,h1i＞在L1中。

部分私鑰詢問：收到身份IDi的私鑰詢問時(shí)，C從L1找到h1i，AII掌握主密鑰s，自行計(jì)算出部分私鑰，使用＜IDi,ri,di,ti,Ni,Yi＞更新LK。

私鑰詢問：收到身份IDi的私鑰生成詢問時(shí)，C檢查是否IDi=IDt。如果相等，C終止游戲；否則，C從LK中獲得元組＜IDi,ri,di,ti,Ni,Yi＞，返回完整的私鑰＜ti,di＞給AII。

簽密詢問：C收到元組＜IDs,IDr,vi＞的簽密詢問。如果IDs≠IDt，C通過簽密算法返回密文給AII；否則，C執(zhí)行下述操作：

挑戰(zhàn)：階段1 結(jié)束時(shí)，AII生成等長vi0,vi1∈M和身份IDs,IDr(IDs,IDr分別是源節(jié)點(diǎn)用戶和目的節(jié)點(diǎn)用戶的身份信息)。階段1中IDr不能詢問。如果IDr≠IDt，C放棄游戲；否則，C調(diào)用H1諭言機(jī)和公鑰提取算法分別獲得＜Ys,Yr＞和＜ts,ds＞，然后通過計(jì)算得到挑戰(zhàn)密文σ*：

AII在階段2發(fā)出與階段1相同的詢問。AII不能詢問IDr的秘密值也不能對(σ*,c*,R*)進(jìn)行解簽密詢問。

L2存儲的元組中存在一個(gè)元組含有CDH問題實(shí)例的解答。C從L中隨機(jī)選擇＜id,vi,h2＞，輸出為C D H 問題的解答

在概率分析中e表示自然對數(shù)底，qs表示詢問私鑰的次數(shù)，q3表示詢問H3的次數(shù)，ε1表示AII攻破NC-CLPFSC保密性的概率。由定理1可得，C在游戲中未終止且C解決CDH問題的概率是：e—1ε1/q3qs。證畢

5.1 不可偽造性

定理3(AI攻擊下的不可偽造性)如果AI能攻破NC-CLPFSC的不可偽造性，則必定存在算法C能解決DL問題。

證明 假設(shè)C是解決DL問題實(shí)例＜g,gb＞的挑戰(zhàn)者，其目的在于計(jì)算b∈。AI在游戲中扮演C的子程序。C從q1個(gè)身份中選擇第t個(gè)身份作為挑戰(zhàn)身份IDt，＜IDt,t＞對AI是未知的。C維護(hù)起初為空的列表＜L1,L2,L3,L4,LK＞。

C首先輸出運(yùn)行設(shè)置算法得到的φ=＜q,G,g,Ypub=gb,H1,H2,H3,ID,M＞。然后，AI進(jìn)行和定理1的階段1完全相同的多項(xiàng)式有界次適應(yīng)性詢問。

偽造：階段1詢問結(jié)束時(shí)，AI輸出偽造密文。AI無法得知IDt的私鑰，IDt的部分私鑰不能提取且其公鑰不能替換，AI不能對偽造密文發(fā)出解簽密詢問。如果IDt≠IDi，C失敗。根據(jù)分叉引理，AI通過生成另一個(gè)偽造密文。如果C成功，則式(14)成立

根據(jù)式(14)，C輸出D L問題實(shí)例解答b=

如果C在游戲過程中沒有終止且AI以概率ε1攻破NC-CLPFSC的不可偽造性，則根據(jù)定理1可得，C解決DL問題的優(yōu)勢是：e—1ε1/(qs+qp+qr)。證畢

定理4(AII攻擊下的不可偽造性)若AII能攻破NC-CLPFSC的不可偽造性，則必定存在算法C能解決DL問題。

證明 假設(shè)C是解決DL問題實(shí)例＜g,gb＞的挑戰(zhàn)者，其目標(biāo)在于計(jì)算b∈。AII在游戲中扮演C的子程序。C從q1個(gè)身份中選擇第t個(gè)身份作為挑戰(zhàn)身份IDt，＜IDt,t＞對AII是未知的。C維護(hù)起初為空的列表＜L1,L2,L3,L4,LK＞。

C首先輸出運(yùn)行設(shè)置算法得到的＜φ,s＞給AII。然后AII執(zhí)行和定理2的階段1完全相同的多項(xiàng)式有界次適應(yīng)性詢問。

偽造：經(jīng)過上述詢問時(shí)，AII輸出偽造密文。IDt的私鑰不能提取且AII不能對偽造密文發(fā)出解簽密詢問。如果IDt≠IDi，C失??；否則，根據(jù)分叉引理，AII生成另一個(gè)偽造密文。如果C成功，則式(15)成立

根據(jù)式(15)，C輸出D L問題實(shí)例解答b=

如果AII以概率ε1攻破NC-CLPFSC的不可偽造性，則根據(jù)定理3可得C解決DL問題的優(yōu)勢是：e—1ε1/qs。證畢

5.2 抗污染攻擊

定理5 NC-CLPFSC能有效防御多源網(wǎng)絡(luò)編碼環(huán)境下的污染攻擊。

證明 如果攻擊者試圖偽造一個(gè)密文，就必須得解決離散對數(shù)問題獲得簽密私鑰，然而成功求解離散對數(shù)問題的概率幾乎可忽略。如果攻擊者想要偽造一個(gè)有效密文，攻擊者需要偽造秘密值對消息簽密。從Ri得到秘密值ui等價(jià)于解決離散對數(shù)困難問題。因此，敵手不可能獲得有效密文。綜上，NCCLPFSC具有抗污染特性。

6 性能分析

本節(jié)依據(jù)計(jì)算效率比較NC-CLPFSC與文獻(xiàn)[14—16]的方案。

表1描述使用軟件VC++調(diào)用基于雙線性對的密碼學(xué)庫(Pairing-Based C ryp tography library,PBC)獲得的各種密碼操作的平均計(jì)算時(shí)間。表2主要描述4種方案在各個(gè)階段的耗時(shí)比較。表3主要描述4種方案總耗時(shí)比較。

表1 各密碼操作的計(jì)算時(shí)間(m s)

表2 分段耗時(shí)比較(m s)

表3 總耗時(shí)比較(m s)

做仿真實(shí)驗(yàn)的計(jì)算機(jī)的主要性能參數(shù)：W in10操作系統(tǒng)，CPU 1.60 GHz，內(nèi)存16 GB。Origin工具繪制仿真實(shí)驗(yàn)結(jié)果圖。圖2—圖5中橫坐標(biāo)表示消息向量維度，縱坐標(biāo)表示計(jì)算消耗時(shí)長。伴隨著消息向量維度的增多，在各階段、整體方案的計(jì)算消耗時(shí)增長相對比較緩慢，這說明NC-CLPFSC計(jì)算開銷更小。

圖2 系統(tǒng)初始化及密鑰生成耗時(shí)比較

圖3 簽密耗時(shí)比較

圖4 解簽密耗時(shí)比較

圖5 總耗時(shí)比較

7 結(jié)束語

多源網(wǎng)絡(luò)編碼環(huán)境下不使用雙線性對的無證書簽密(NC-CLPFSC)的安全證明中，挑戰(zhàn)者用1次成功偽造不足以解決困難問題，需要兩個(gè)及以上特定關(guān)系的成功偽造才能攻破難題，此情況下需要使用分叉引理進(jìn)行安全性證明，因而NC-CLPFSC在不可偽造性證明過程中使用了分叉引理。

NC-CLPFSC支持節(jié)點(diǎn)間處理數(shù)據(jù)，是很好的網(wǎng)絡(luò)路由解決方案。NC-CLPFSC在計(jì)算D iffie-Hellman問題和離散對數(shù)問題的困難假設(shè)下可保證消息的機(jī)密性、不可偽造性和不可污染等安全屬性。從仿真實(shí)驗(yàn)結(jié)果得出NC-CLPFSC的計(jì)算開銷更低。