單/多源網絡編碼同態簽名方案

俞惠芳，李雯

（西安郵電大學網絡空間安全學院，陜西 西安 710121）

1 引言

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

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

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

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

2 預備知識

2.1 單源線性網絡編碼模型

圖1 適用于網絡編碼的單源傳輸網絡模型

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

將原始傳輸的文件設為M1,M2,…,Mm，恢復原始文件時計算

2.2 多源線性網絡編碼模型

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

圖2 適用于網絡編碼的多源傳輸網絡模型

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

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

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

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

設接收節點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是階為大素數q的加法循環群，生成元為P；令G2是階為q的乘法循環群。若映射e:G1×G1→G2滿足如下性質，則為雙線性對[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）是基于橢圓曲線離散對數問題的公鑰密碼體制，橢圓曲線加法群的離散對數問題的求解比有限域乘法群的離散對數問題求解更難，它可用小密鑰來保證高級別的安全性。選取橢圓曲線E(a,b)：y2≡x3+ax+b(modp)。E(a,b)通過一組參數(p,a,b,G,q,h)唯一確定。在有限域Fp中，p是一個大素數，表示域的大小；a,b∈Fp是橢圓曲線方程的參數，滿足方程4a3+27b2(modp)≠0，G是橢圓曲線上階為大素數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階循環群上的離散對數到散列碰撞有一個多項式時間約簡。

3 單源網絡編碼同態簽名方案

3.1 方案實例

3.1.1 系統設置

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

1)源節點處

2)中間節點處

3.1.2 簽名算法

1)源節點的簽名過程

2)組合

3)中間節點簽名過程

4)驗證

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

③計算

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

④驗證依據

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

由此說明了散列函數具有同態性質。

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

3.2 安全性分析

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

定理1當且僅當在多項式時間內求解橢圓曲線離散對數問題是困難的，單源網絡編碼橢圓曲線同態簽名是安全的。

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

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

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

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

證畢。

定理2當且僅當在多項式時間內散列函數是抗碰撞的，單源網絡編碼橢圓曲線同態簽名是安全的。

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

證畢。

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

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

證畢。

3.3 實驗結果與分析

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

執行一次指數運算的時間用Cme表示，Cme=0.83 ms。

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

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

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

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

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

4 多源網絡編碼同態簽名方案

4.1 方案實例

1)系統設置

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

表1 單源網絡編碼簽名性能比較

圖3 簽名耗時比較

圖4 驗證耗時比較

2)簽名算法

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

輸出用戶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的組合過程中，消息Vj來源于用戶u1,u2,…,us，βj為消息Vj的全局組合系數。βj(u1),…,βj(us)分別是每個用戶u1,u2,…,us對消息Vj賦予的組合系數，因此W可以表示為

組合的簽名為

簽名σ第k個分量σk為

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

2)由于

4.3 安全性分析

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

證明挑戰者B 運行系統初始化算法，生成公開參數和系統私鑰，然后將系統公開參數發送給攻擊者A，保存私鑰。

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

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

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

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

證畢。

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

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

證畢。

4.4 實驗結果與分析

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

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

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

表2 多源網絡編碼簽名性能比較

5 結束語

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