單/多源網(wǎng)絡編碼同態(tài)簽名方案

俞惠芳，李雯

（西安郵電大學網(wǎng)絡空間安全學院，陜西 西安 710121）

1 引言

網(wǎng)絡編碼[1]是一種新型的信息傳輸技術，在提升網(wǎng)絡的吞吐量、增加網(wǎng)絡的強壯性、減少網(wǎng)絡寬帶資源的消耗等方面比傳統(tǒng)的路由技術都具有明顯的優(yōu)勢。但是當節(jié)點受到惡意攻擊或網(wǎng)絡傳輸信道不穩(wěn)定時，產(chǎn)生的污染信息將會隨著編碼傳輸與其他有效消息進行編碼組合，進而將污染傳染給其他消息，最終使信宿節(jié)點無法正確解碼恢復出原始消息。

近年來，研究人員提出了一些抵抗污染攻擊的方案，使網(wǎng)絡編碼污染問題在傳統(tǒng)的簽名方法中得到了很好解決。Yu 等[2]提出了基于同態(tài)簽名的線性網(wǎng)絡編碼方案，可以檢測出污染攻擊的發(fā)生。但是Yun 等[3]已證明了Yu 等[2]提出的算法不滿足同態(tài)性質(zhì)，雖然能檢測出污染攻擊的發(fā)生，但是不能處理該節(jié)點。Boneh 等[4]提出了一種全局編碼向量的簽名方案，可以抵御代內(nèi)/外污染，但是簽名和驗證的計算復雜度高，時延較長。Li 等[5]提出了分布式污染節(jié)點定位方案，每個節(jié)點都可運行算法，自行判斷污染節(jié)點，缺點是算法精度不高，存在誤判概率，并且需要運行多次才能確定污染處。Charles 等[6]利用橢圓曲線上的點設計了一種同態(tài)簽名方案，缺點是存在漏洞，可以偽造通過驗證[7]。He 等[8]提出了自適應網(wǎng)絡編碼方案，中間節(jié)點可根據(jù)網(wǎng)絡污染情況自動調(diào)整策略進行驗證，缺點是網(wǎng)絡節(jié)點必須保證時間同步，這樣會消耗大量網(wǎng)絡資源。裴恒利等[9]使用時間戳生成網(wǎng)絡編碼的隨機系數(shù)，利用RSA 同態(tài)簽名抵抗污染攻擊和重放攻擊，但是數(shù)據(jù)分組部分的正交分量計算復雜，增加了資源浪費。蒙云番等[10]構造了橢圓曲線密碼體制（ECC,elliptic curve cryptography）下的同態(tài)簽名方案，保障了無線體域網(wǎng)的通信安全，缺點是不能抵抗代間污染，計算開銷大。Wu 等[11]提出了一種基于密鑰預分發(fā)的標簽編碼方案，可以抵御污染攻擊和標簽污染攻擊，但是不能檢測出代間污染攻擊。Cheng 等[12]提出了一種改進的同態(tài)子空間網(wǎng)絡編碼簽名方案，將代間標識符結(jié)合到密鑰生成過程中，不足之處是簽名過程較復雜，網(wǎng)絡負載大，易造成緩存溢出。

上述的抵抗污染攻擊算法僅限于單源的網(wǎng)絡編碼，多源網(wǎng)絡編碼中的污染問題比單源網(wǎng)絡編碼復雜。Agrawal 等[13]針對多源網(wǎng)絡編碼構造了同態(tài)簽名機制，當中間節(jié)點組合來自多個源的數(shù)據(jù)分組時，該機制能提供完整性，然而每個分組需要進行多次的簽名驗證，導致計算開銷大。Yang 等[14]提出了能夠保證數(shù)據(jù)完整性的無條件安全認證碼的多源網(wǎng)絡編碼方案，不足之處是存在安全漏洞，容易受到重放攻擊。Zhang 等[15]提出了一種實時簽名方案以抵抗多源網(wǎng)絡污染攻擊，但在安全性方面存在一些缺陷。Le 等[16]提出了適用于多源網(wǎng)絡編碼的基于同態(tài)消息認證碼的簽名方案，缺點是中間節(jié)點不能將被污染的數(shù)據(jù)分組過濾掉。Li 等[17]為了解決網(wǎng)絡編碼認證問題，提出了一種多源線性同態(tài)網(wǎng)絡編碼簽名方案，但節(jié)點的簽名和驗證運算中需要進行大量的模指數(shù)運算，增加了計算復雜度。俞惠芳等[18]采用Schnorr 簽名機制，提出了適用于多源網(wǎng)絡編碼的環(huán)簽名方案，在環(huán)簽名中引入時間概念，既能抵抗污染攻擊又能抵抗重放攻擊。彭勇等[19]為了預防多源網(wǎng)絡的污染攻擊和背叛攻擊，提出了多源網(wǎng)絡編碼同態(tài)簽名算法，改變了數(shù)據(jù)分組的組合方式，但是接收節(jié)點解碼速度較慢。牛淑芬等[20]提出了一種多源網(wǎng)絡編碼數(shù)據(jù)完整性驗證方案，利用私鑰對散列值進行聚合簽名，接收節(jié)點利用公鑰驗證線性編碼消息的完整性，但需要在有限域中進行大量的指數(shù)運算，降低了驗證效率。

針對單源網(wǎng)絡編碼中簽名、驗證計算復雜度高、效率低、資源浪費、不能有效地抵抗代間污染等不足，本文借鑒文獻[10,21]的思想提出了一種單源網(wǎng)絡編碼體制下橢圓曲線同態(tài)簽名方案，實現(xiàn)了確定污染節(jié)點和過濾污染信息的功能，從而可以抵抗代內(nèi)/間的污染，仿真實驗顯示，所提方案比同類方案[22]提高了節(jié)點驗證效率，減少了能源消耗。同時，針對所述多源網(wǎng)絡編碼方案中計算開銷大、簽名驗證過程復雜、不能預防重放攻擊等缺點，本文在文獻[9,23]的理論基礎上提出了基于雙線性映射的多源網(wǎng)絡編碼同態(tài)簽名方案，能有效抵抗污染攻擊和重放攻擊，分析表明，所提方案比同類方案降低了對節(jié)點計算能力的要求，減少了系統(tǒng)開銷和節(jié)點的驗證時間。

2 預備知識

2.1 單源線性網(wǎng)絡編碼模型

圖1 適用于網(wǎng)絡編碼的單源傳輸網(wǎng)絡模型

源節(jié)點在發(fā)送數(shù)據(jù)M之前將其分為m個塊，即M1,M2,…,Mm，每塊用n維向量來表示，即，p是一個大素數(shù)，同時將所有的文件塊按照如下規(guī)則進行擴充

將原始傳輸?shù)奈募O為M1,M2,…,Mm，恢復原始文件時計算

2.2 多源線性網(wǎng)絡編碼模型

文獻[23]的多源網(wǎng)絡編碼模型中，每個源節(jié)點發(fā)送的每條消息都有統(tǒng)一分配的唯一的二維索引[25]，不同的源節(jié)點發(fā)送相同的多播消息有著相同的索引。將多播的多源網(wǎng)絡編碼用G=(V,E)來描述，其中V和E分別是節(jié)點和邊的集合，S={s1,s2,…,sm}?V是源節(jié)點集，D={d1,d2,…,dk}?V是目的節(jié)點集。D接收S發(fā)送的m條多播消息，如圖2所示。

圖2 適用于網(wǎng)絡編碼的多源傳輸網(wǎng)絡模型

將m條多播消息表示為V1,…,V m，將每條消息Vi看成是n維向量空間V/Fp中的一個向量，記為，其中1≤i≤m。

設W=(W1,W2,…,Wl)為多播網(wǎng)絡中任意一條邊上發(fā)送的消息，接收節(jié)點收到l條消息的線性組合，即

其中，α=(a1,a2,…,al)稱為局部編碼向量。易知，任意一條邊上發(fā)送的消息W也是原消息Vj(1≤j≤m)的線性組合，即

其中，β=(β1,β2,…,βm)稱為全局編碼向量。

設接收節(jié)點ti收到m個線性無關的編碼消息W1,W2,…,Wm，而且相關的全局編碼向量用G表示，恢復原消息

原消息V1,…,Vm為

消息后面附加全局編碼向量βi與消息一起傳輸，擴展的原消息可看成m+n維的向量空間V/Fp中的一個向量，記作

所以，編碼消息可以表示為Wi=(wi,1,…,wi,n,βi,1,βi,2,…,βi,m)，為了方便，將編碼消息表示成Wi=(wi,1,…,wi,m+n)。

2.3 雙線性對

令a,b∈Zp*；令G1是階為大素數(shù)q的加法循環(huán)群，生成元為P；令G2是階為q的乘法循環(huán)群。若映射e:G1×G1→G2滿足如下性質(zhì)，則為雙線性對[26]。

1)雙線性：對于任意的P,Q∈G1，都有e(aP,bQ)=e(P,Q)ab。

2)非退化性：存在P,Q∈G1使e(P,Q)≠1。

3)可計算性：對于任意的P,Q∈G1，e(aP,bQ)=e(P,Q)ab=e(P,abQ)=e(abP,Q)。

2.4 橢圓曲線密碼簡介

橢圓曲線密碼體制（ECC）是基于橢圓曲線離散對數(shù)問題的公鑰密碼體制，橢圓曲線加法群的離散對數(shù)問題的求解比有限域乘法群的離散對數(shù)問題求解更難，它可用小密鑰來保證高級別的安全性。選取橢圓曲線E(a,b)：y2≡x3+ax+b(modp)。E(a,b)通過一組參數(shù)(p,a,b,G,q,h)唯一確定。在有限域Fp中，p是一個大素數(shù)，表示域的大??；a,b∈Fp是橢圓曲線方程的參數(shù)，滿足方程4a3+27b2(modp)≠0，G是橢圓曲線上階為大素數(shù)q的基點，q＜＜p，且q＞2160和，要滿足q不能整除pk-1。

2.5 散列碰撞

輸入P1,…,Pr（r>1）是有限域Fp中階為q的橢圓曲線上的點

輸出元組a=(a1,…,ar)，b=(b1,…,br)∈Fpr，使a≠b且

橢圓曲線上q階循環(huán)群上的離散對數(shù)到散列碰撞有一個多項式時間約簡。

3 單源網(wǎng)絡編碼同態(tài)簽名方案

3.1 方案實例

3.1.1 系統(tǒng)設置

HG是一個單向抗碰撞 hash 函數(shù)，。其中G1是階為大素數(shù)q的加法循環(huán)群，G是橢圓曲線上的基點。密碼學安全的散列函數(shù)選取秘密隨機數(shù)假設源節(jié)點要發(fā)送l個代的消息，標識符I表示消息代。計算SPK=HG(I)，SSK=α SPK，SSK是代對應的私鑰。

1)源節(jié)點處

2)中間節(jié)點處

3.1.2 簽名算法

1)源節(jié)點的簽名過程

2)組合

3)中間節(jié)點簽名過程

4)驗證

①接收節(jié)點收到傳遞來的消息向量時，先對每一個接收到的簽名進行驗證，通過驗證后再進行編碼。

③計算

如果X=0，則拒絕簽名，否則，令。若成立，則接受簽名；否則，拒絕該簽名。

④驗證依據(jù)

將式(8)代入式(13)，得到組合后消息的散列函數(shù)為

由此說明了散列函數(shù)具有同態(tài)性質(zhì)。

將式(10)和式(11)代入X=U1G+U2Pid=(x1id,y1id)中，可得

3.2 安全性分析

在單源網(wǎng)絡編碼橢圓曲線同態(tài)簽名中，為了防止污染攻擊，在每個轉(zhuǎn)發(fā)節(jié)點處進行一次簽名驗證和簽名。在證明中利用了隨機預言模型，假設某個節(jié)點被攻擊者攻破，得到該節(jié)點的私有數(shù)據(jù)及所有公共參數(shù)，要偽造能通過驗證的信息，必須破解橢圓曲線離散對數(shù)難題。攻擊者A 可以用這些參數(shù)來偽造簽名，但是這相當于在求解橢圓曲線離散對數(shù)難題。

定理1當且僅當在多項式時間內(nèi)求解橢圓曲線離散對數(shù)問題是困難的，單源網(wǎng)絡編碼橢圓曲線同態(tài)簽名是安全的。

證明令B 是一個挑戰(zhàn)者，B 的目標是利用攻擊者A 攻破橢圓曲線離散對數(shù)困難問題。A 和B 進行的游戲如下。A 選擇消息提交給B。

系統(tǒng)設置。B 通過運行系統(tǒng)初始化算法得到(G,Kid,K′,H G(I),R)，然后發(fā)送系統(tǒng)參數(shù)給A。

h詢問。B 在任意時刻都可以詢問h預言機，h-list 是一個起初為空的列表。如果表h-list 有匹配的元組，則返回該值；否則，B 隨機選擇值返回，并將該值添加到表h-list 中。

h1詢問。B 在任意時刻都可以詢問h1預言機，h1-list 是一個起初為空的列表。如果相應的值已經(jīng)在表h1-list 中，則返回該值；否則，B 隨機選擇值返回，然后添加該值到表h1-list 中。

證畢。

定理2當且僅當在多項式時間內(nèi)散列函數(shù)是抗碰撞的，單源網(wǎng)絡編碼橢圓曲線同態(tài)簽名是安全的。

證明攻擊者A 偽造信息w′(w′≠w)，使λ′=λ。因為，可得，但是A 的偽造過程等價于在有限域Fp上證明式(16)成立。

證畢。

定理3當且僅當在多項式時間內(nèi)能抵抗代間重放攻擊，單源網(wǎng)絡編碼橢圓曲線同態(tài)簽名是安全的。

證明當I′≠I時，在隨機預言模型下，散列函數(shù)H G(I)被看成是一個隨機預言機，而攻擊者不能在多項式時間內(nèi)找到I′≠I使H G(I′)=H G(I)。因此，所提方案中代間重放攻擊無法成功實施。

證畢。

3.3 實驗結(jié)果與分析

本節(jié)利用Matlab工具對所提方案和Cheng等[22]方案進行計算開銷對比，主要密碼操作的計算成本定義如下。

執(zhí)行一次指數(shù)運算的時間用Cme表示，Cme=0.83 ms。

執(zhí)行一次橢圓曲線上標量乘運算的時間用Cmul表示，Cmul=0.75 ms。

執(zhí)行一次散列運算的時間用Cmtp表示，Cmtp=1.18 ms。

執(zhí)行一次雙線性對運算的時間用Cpar表示，Cpar=2.75 ms。

所提方案和Cheng 等方案的性能比較如表1所示?？紤]到橢圓曲線上標量乘（160位）比相同安全級別下的模指數(shù)運算（1024位）成本更低，因此所提方案平均具有最優(yōu)的計算復雜度。具體來說，數(shù)據(jù)分組簽名時，Cheng 等方案需要(m+n+2)Cmul+(m+n+2)Cme，而所提方案需要(m+n+2)Cmul+2Cmtp。為了驗證數(shù)據(jù)分組，Cheng等方案需要(3(m+n)+2)Cmul+3(m+n+1)Cme，而所提方案需要(m+n+1)Cmul+2Cmtp。很明顯，所提方案效率優(yōu)于Cheng 等方案，因為所提方案中簽名和驗證也是基于橢圓曲線實現(xiàn)的，運算中用到橢圓曲線上的標量乘，沒有模指數(shù)運算，從而減少了運算時間。

圖3和圖4分別表示所提方案和Cheng 等[22]方案簽名耗時和驗證耗時的仿真曲線。本節(jié)選用橢圓曲線的安全參數(shù)q=2159+217+1，q是160位的Solinas 素數(shù)，p是512位素數(shù)，令m=50，消息向量維數(shù)m+n分別為100、200、300、400、500、600、700、800。由圖3和圖4可以看出，隨著消息向量維數(shù)的增加，所提方案簽名和驗證的耗時低于Cheng 等方案，因此得出所提方案優(yōu)于Cheng 等方案的結(jié)論。

4 多源網(wǎng)絡編碼同態(tài)簽名方案

4.1 方案實例

1)系統(tǒng)設置

G1是階為大素數(shù)q的加法循環(huán)群，其中G為G1的生成元，用戶ud(1≤d≤s)隨機選擇作為私鑰，計算pk=s kG作為公鑰。Hg是一個單向抗碰撞hash 函數(shù)，Hg:{0,1}*→G1。Ti為時間戳，且，T為當前時刻。，其中β1,β2,…,βm是隨機系數(shù)，當前時刻T收到的m條消息組合中的時間戳為(T1,T2,…,Tm)。

表1 單源網(wǎng)絡編碼簽名性能比較

圖3 簽名耗時比較

圖4 驗證耗時比較

2)簽名算法

一個消息Vj的簽名為σj(ud)，其中第k個數(shù)據(jù)分量的簽名是

輸出用戶ud對Vj(1≤j≤m)的簽名。當不涉及其他用戶時，簽名可以記為

3)組合

α=(α1,α2,…,αl)為局部編碼向量，σ1,…,σl分別為消息向量W1,…,Wl的簽名，其中組合后形成的向量為

生成W的簽名(σ1,σ2,…,σs)為

其中，σi,k(1≤i≤m,1≤k≤s)是σi的第k個元素。

4)簽名驗證算法

公鑰為p1,p2,…,p s∈G1，消息向量W的全局編碼向量是β=(β1,β2,…,βm)，簽名為σ，驗證H g(T)=Hg((β1T1+β2T2+…+βmT m)modp)是否成立，若不成立，則拒絕驗證；若成立，則驗證等式

是否成立，若成立，則驗證成功。

4.2 正確性分析

1)由多源網(wǎng)絡編碼可得

為了區(qū)分不同用戶的相同消息可組合在一起，設

在消息W的組合過程中，消息Vj來源于用戶u1,u2,…,us，βj為消息Vj的全局組合系數(shù)。βj(u1),…,βj(us)分別是每個用戶u1,u2,…,us對消息Vj賦予的組合系數(shù)，因此W可以表示為

組合的簽名為

簽名σ第k個分量σk為

其中，σj,k(ud)是用戶ud對消息Vj簽名σj(ud)的第k個分量。

2)由于

4.3 安全性分析

定理4采用雙線性對的多源網(wǎng)絡編碼簽名能夠抵抗污染攻擊。

證明挑戰(zhàn)者B 運行系統(tǒng)初始化算法，生成公開參數(shù)和系統(tǒng)私鑰，然后將系統(tǒng)公開參數(shù)發(fā)送給攻擊者A，保存私鑰。

當m*不是時間戳Ti時刻的消息時，證明方式與文獻[22]類似。在詢問階段，A 選擇的消息子空間V°是由向量(V1,V2,…,Vm)張成的，并向B 詢問此消息子空間中各消息向量的簽名。B 收到詢問請求后，先選取Ti作為V°的時間戳，然后生成各向量Vi的簽名σi，并將簽名σi和時間戳Ti發(fā)送給A。由此A 可獲得式(22)所示的方程組

A 輸出一系列偽造消息(Ti,m*,σ*)，m*?V°，若偽造的消息量可通過驗證，那么式(23)所示方程組成立

設在式(22)中，ζ為系數(shù)矩陣與增廣矩陣的秩，其解的個數(shù)為p n-ζ，即式(23)的秩為ζ+1，解為p n-ζ-1，易知式(22)中將有p個解滿足式(23)。A 贏得游戲的概率為，可忽略不計（p是一個很大的素數(shù)）。

簽名偽造。由式(17)易知，簽名σj,k(ud)是關于n個未知Hg(T)sk的一個線性方程。A 試圖從傳輸?shù)臄?shù)據(jù)分組中推導出Hg(T)sk，而Hg(T)是m個時間戳Ti線性組合的單向碰撞散列函數(shù)，A 不能通過解決單向碰撞散列函數(shù)問題得到Hg(T)sk，沒有Hg(T)sk就不能偽造一個有效的簽名，即簽名不可偽造。

證畢。

定理5采用雙線性映射的多源網(wǎng)絡編碼簽名能夠抵抗重放攻擊。

證明攻擊者A截獲(m,T,σ)并將其重放到網(wǎng)絡中，重放簽名(m,T′,σ′)在中間節(jié)點處重復發(fā)送，但因消息組合中的時間T′(T′≠T)，即Hg(T)≠Hg(T′)，則可以斷定該消息為重放消息簽名并丟棄，所以攻擊無效。

證畢。

4.4 實驗結(jié)果與分析

本節(jié)中的主要密碼操作的定義與3.3節(jié)中的一樣，此處不再贅述，信源節(jié)點的個數(shù)用s表示，表2顯示了不同方案的簽名性能。

所提方案與Li 等[17]方案、Zhang 等[15]方案的簽名耗時仿真曲線如圖5所示，三者的驗證耗時仿真曲線如圖6所示。通過Matlab 仿真數(shù)據(jù)可以看出，隨著消息向量維數(shù)的增加，不同方案的運行時間均線性增長，但是所提方案比Li 等方案、Zhang 等方案增長緩慢，而且所提方案的簽名和驗證的耗時比同類方案低。

經(jīng)過幾組方案的對比可得出，所提方案效率優(yōu)于同類方案是因為運算大多是標量乘，幾乎不用指數(shù)運算，減少了運算時間的開銷。

表2 多源網(wǎng)絡編碼簽名性能比較

5 結(jié)束語

單源網(wǎng)絡編碼橢圓曲線同態(tài)簽名是在ECC 簽名的基礎上結(jié)合了同態(tài)散列函數(shù)和“代”的概念提出的，能夠有效抵抗代內(nèi)/代間污染。相比于同類方案，該方案的簽名和驗證計算時間短，能節(jié)約資源，減少通信開銷。使用雙線性對的多源網(wǎng)絡編碼同態(tài)簽名是采用時間戳的同態(tài)簽名方案，能夠抵御污染攻擊和重放攻擊，該方案中的雙線性對內(nèi)部進行的是標量乘運算，與進行大量的指數(shù)運算的雙線性對同類方案相比計算復雜度低，簽名和驗證效率更高；該方案在選擇性攻擊情況下是安全的。強安全性和更高簽名驗證效率的多源網(wǎng)絡編碼同態(tài)簽名是本文下一步計劃之一。