無雙線性對的網絡編碼無證書簽密

俞惠芳楊 柯

(西安郵電大學網絡空間安全學院 西安 710121)

1 引言

網絡編碼[1,2]是一種數據路由方法。不同于傳統路由機制，網絡編碼允許中間節點在傳輸數據包之前對其進行編碼。這種做法可讓網絡達到最大流最小割定理所規定的最大吞吐量。網絡編碼實際應用中的污染問題較為嚴重，如果網絡節點未檢測出被污染的數據包直接編碼轉發，會導致污染多個節點甚至整個網絡。RSA同態簽名[3]能應對污染攻擊和代間重放攻擊。有雙線性對的同態簽名[4]使用了組合簽名和相應節點的公鑰來驗證組合數據包，能抗污染攻擊。

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

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

2 基礎知識

2.1 網絡編碼模型

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

圖1 多源網絡傳輸模型

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

Ho等人[12]描述的隨機線性網絡編碼允許選擇用于執行分組的線性組合的編碼系數。在隨機線性網絡編碼中，源節點將m維消息向量Vi擴展為m+n維，給每個消息向量添加一個規范向量。擴展后消息向量表示為

2.2 困難問題

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

離散對數(Discrete Logari thm,DL)問題：給定大素數階q的乘法群G,g表示群G的任意生成元，已知∈G,DL問題的目標是計算

3 具體方案

3.1 系統初始化

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

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

3.2 密鑰生成

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

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

3.3 簽密

給定源節點用戶身份信息IDs。源節點用戶發送消息向量vi的密文給目的節點。每個源節點用戶在發送消息時都會附上一個消息標識符id作為整個數據包的一部分而發送到下游節點，下游節點能根據對應的id確定出收到的簽名是由哪一個節點發送的，從而達到確定出污染節點位置信息的目的。簽密操作如下：

3.4 組合

3.5 解簽密

4 正確性分析

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

(2)單個數據包簽名驗證正確性分析

(3)組合驗證

5 安全性分析

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

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

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

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

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

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

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

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

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

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

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

C首先輸出運行設置算法得到的＜φ,s＞給AII。然后，AII執行多項式有界次適應性詢問。H2,H3詢問與定理1相同，故略去。

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

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

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

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

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

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

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

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

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

5.1 不可偽造性

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

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

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

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

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

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

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

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

C首先輸出運行設置算法得到的＜φ,s＞給AII。然后AII執行和定理2的階段1完全相同的多項式有界次適應性詢問。

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

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

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

5.2 抗污染攻擊

定理5 NC-CLPFSC能有效防御多源網絡編碼環境下的污染攻擊。

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

6 性能分析

本節依據計算效率比較NC-CLPFSC與文獻[14—16]的方案。

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

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

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

表3 總耗時比較(m s)

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

圖2 系統初始化及密鑰生成耗時比較

圖3 簽密耗時比較

圖4 解簽密耗時比較

圖5 總耗時比較

7 結束語

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

NC-CLPFSC支持節點間處理數據，是很好的網絡路由解決方案。NC-CLPFSC在計算D iffie-Hellman問題和離散對數問題的困難假設下可保證消息的機密性、不可偽造性和不可污染等安全屬性。從仿真實驗結果得出NC-CLPFSC的計算開銷更低。