楊文山

（格爾軟件股份有限公司，上海 201112）

0 引 言

網(wǎng)絡(luò)編碼是兼具路由和編碼功能的信息通信技術(shù)，其優(yōu)點為信息吞吐量大和魯棒性強。如果節(jié)點以某種方式對消息進行編碼后轉(zhuǎn)發(fā)，這種網(wǎng)絡(luò)結(jié)構(gòu)可以獲得理論中最大的傳輸效率。當(dāng)前，研究人員一直比較關(guān)注網(wǎng)絡(luò)編碼安全問題，并設(shè)計出一系列防污染/竊聽的網(wǎng)絡(luò)編碼簽名方案[1-11]。重簽名允許多個用戶對同樣的消息進行簽名，每個用戶對收到的消息進行部分簽名，然后交給簽名收集者形成最終簽名。

目前沒有任何基于橢圓曲線的網(wǎng)絡(luò)編碼多重簽名。如何設(shè)計安全高效的網(wǎng)絡(luò)編碼多重簽名是一個值得研究的問題?；诖耍疚脑O(shè)計了防御污染/偽造的網(wǎng)絡(luò)編碼中的橢圓曲線多重簽名方案（NC-ECMSS）。每個源節(jié)點為消息生成一個有序的多重簽名，中間節(jié)點對接收的信息進行線性組合。NC-ECMSS 具有抗污染攻擊和偽造攻擊的特性，而且比起現(xiàn)有技術(shù)而言，其驗證效率較高、計算復(fù)雜度較低。

1 基礎(chǔ)知識

1.1 ECDL 問題

橢圓曲線離散對數(shù)（Elliptic Curve Discrete Logarithm，ECDL）問題，給定橢圓曲線E和橢圓曲線點X=aG，ECDL 問題是指找到一個正整數(shù)a∈，使之滿足X=aG在計算上是不可行的。

1.2 多源網(wǎng)絡(luò)編碼知識

2 形式化定義

2.1 算法定義

NC-ECMSS 包含以下6 個概率多項式時間算法。

（1）參數(shù)生成算法：輸入安全參數(shù)μ，輸出系統(tǒng)主密鑰x和系統(tǒng)公開參數(shù)λ。

（2）部分私鑰生成算法：輸入λ，x，IDi，輸出部分私鑰di，其中IDi代表用戶身份。

（3）密鑰生成算法：輸入IDi，輸出該用戶的秘密值δi、公鑰yi。

（4）多重簽名算法：輸入消息向量vi，λ，IDi，di，δi，L，用戶IDi(1≤i≤n)驗證上個用戶IDi-1傳來的部分簽名σi-1后，輸出其部分簽名σi，其中L是簽名順序。

（5）組合簽名算法：輸入消息向量(w1,w2,wl)，輸出組合后消息向量w和對應(yīng)的組合簽名σ。

（6）驗證算法：輸入λ，IDi，yi，vi，σ，如果驗證等式成立，接受簽名；否則，輸出⊥。

2.2 安全模型

防御污染/偽造的網(wǎng)絡(luò)編碼中的橢圓曲線多重簽名方案（NC-ECMSS）滿足適應(yīng)性選擇消息攻擊下的不可偽造性安全性（UF-CMA）。通過挑戰(zhàn)者C 與敵手 A1（A2）之間的實驗游戲G1（G2）來描述NC-ECMSS 的UF-CMA 安全模型。首先，通過發(fā)生器生成兩個敵手，，其中，敵手A1模擬的是惡意的密鑰生成中心（Key Generation Center，KGC），敵手A2模擬的是不誠實用戶，A1不知道主密鑰，但能替換任意用戶的公鑰；A2知道主密鑰，但無法更換任意用戶公鑰。然后，A1（A2）發(fā)出一系列適應(yīng)性詢問，詳見式（1）。

最后，由 A1（A2）輸出一個偽造簽名，在詢問中，A1不會詢問用戶的完整私鑰，A2也不能詢問用戶的私鑰，偽造的簽名不會是任何多重簽名諭言機輸出的。如果簽名驗證等式通過，則 A1（A2）在G1（G2）中獲勝，反之，則失敗。

不可偽造性。如果沒有多項式時間敵手A1（A2）在游戲?qū)嶒濭1（G2）中以不可忽略的優(yōu)勢成功，則稱防御污染/偽造的網(wǎng)絡(luò)編碼中的橢圓曲線多重簽名方案（NC-ECMSS）滿足適應(yīng)性選擇消息攻擊下的不可偽造性安全性（UFCMA）。

3 方案實例

3.1 參數(shù)生成算法

給定μ比特大素數(shù)p、橢圓曲線E，定義Gp為加法循環(huán)群，G為具有素階q的橢圓曲線的基點和群Gp的生成元，KGC 隨機選取x∈ [1,q]，計算系統(tǒng)公鑰ypub=xG。KGC 選擇安全的哈希函數(shù)為H0: {0,1}t×Gp→，H1: {0,1}*→，H2: {0,1}*→。最后，KGC保密主控鑰但公開系統(tǒng)參數(shù)為：

3.2 部分私鑰生成算法

3.3 密鑰生成算法

3.4 簽名算法

定義第n個用戶Nn對消息vi的有序多重簽名為。當(dāng)?shù)趎個用戶對消息vi的有序多重簽名完成后，將最終的簽名發(fā)送給中間節(jié)點和目的節(jié)點，中間節(jié)點對消息進行線性組合。

3.5 組合算法

3.6 驗證算法

4 正確性論證

4.1 單個簽名的驗證

計算出單個簽名的驗證過程如下：

4.2 組合簽名的驗證

5 安全性分析

定理1：在隨機諭言模型下，NC-ECMSS 針對外部敵手 A1是存在性不可偽造的。

證明：假設(shè)(G,aG)是橢圓曲線離散對數(shù)ECDL 問題的實例，挑戰(zhàn)者Γ 的任務(wù)是利用A1確定一個正整數(shù)a∈的值。挑戰(zhàn)者Γ 需要維護初始時都為空的列表list-1，list-2，list-3，list-4，以存儲針對相應(yīng)諭言機的詢問-應(yīng)答值。IDγ為挑戰(zhàn)者身份，其中γ∈ (1,2,…,l)是一個正整數(shù)，l為詢問H0諭言機的次數(shù)。挑戰(zhàn)者Γ 首先運行參數(shù)生成算法得到系統(tǒng)參數(shù)λ（ypub=aG），輸出λ給A1。然后，A1執(zhí)行以下多項式有界次適應(yīng)性詢問。

（6）秘密值詢問：A1詢問IDi的秘密值。如果對應(yīng)公鑰未被替換，則Γ 查詢列表list-4 并輸出δi給 A1。

（7）公鑰替換詢問：A1詢問IDi的公鑰替換詢問。如果IDi=IDγ，則Γ 終止游戲；否則，Γ 選取yi∈Gp替換IDi的公鑰，并用(IDi,-,y i,Ri,di)更新列表list-4。

最后，A1輸出一個偽造簽名σ。在詢問過程中，A1不能詢問用戶IDi的完整私鑰，簽名諭言機不返回σ*。如果≠IDγ，則Γ 終止游戲；否則，Γ 偽造另一個簽名σ**。則有：

Γ 調(diào)用相關(guān)諭言機，利用分叉引理計算得出ECDL 問題實例解答：

評估Γ 取得成功的概率。令E1表示Γ 不終止游戲的概率；E2表示 A1成功偽造一個簽名的概率；E3表示在成功偽造一個簽名的情況下至少存在一條與非目標(biāo)身份有關(guān)的記錄。如果這3個事件全部發(fā)生，則Γ 取得成功。事件E1存在一次及以上沒有對目標(biāo)身份進行部分私鑰詢問的概率是 Pr[E1] ≥ 1/(ls+l x+lr)（ls為詢問秘密值的次數(shù)，lx為詢問部分私鑰的次數(shù)，lr為公鑰替換的次數(shù)）；事件E2表示 A1成功偽造一個簽名的概率是 Pr[E1|E2]≥ε；事件E3表示在n次重復(fù)詢問中，該事件出現(xiàn)一次及以上的概率是Pr [E3|E1∩E2]≥1 /n。因此，解決ECDL 問題的成功概率為：

定理2：在隨機諭言模型下，NC-ECMSS 針對外部敵手A2是存在性不可偽造的。

證明：假設(shè)(G,aG)是ECDL 問題的實例，挑戰(zhàn)者Γ 的任務(wù)是利用A2確定一個正整數(shù)a∈的值。挑戰(zhàn)者Γ 需要維護初始時都為空的列表list-1，list-2，list-3，list-4，以存儲針對相應(yīng)諭言機的詢問-應(yīng)答值。IDγ為挑戰(zhàn)者身份，其中γ∈ (1,2,…,l)是一個正整數(shù)，l為詢問H0諭言機的次數(shù)。挑戰(zhàn)者Γ 首先運行參數(shù)生成算法得到系統(tǒng)參數(shù)λ（ypub=xG），輸出λ給A2。然后，A2執(zhí)行以下多項式有界次適應(yīng)性詢問，其中哈希詢問與定理1 相同，這里不再贅述。

（1）公鑰詢問：A2詢問IDi的公鑰。Γ 選取δi∈R，輸出yi=δiG，添加 (IDi,δi,yi,-,-)到列表list-4 中。

（2）部分私鑰詢問：A2詢問IDi的部分私鑰。如果IDi=IDγ，則Γ 終止游戲；否則，Γ 選取ri∈R，設(shè)置Ri=aG，計算di，使得d i=Ri+xH iG，輸出di給A2，并用(IDi,δi,yi,Ri,di)更新列表list-4，其中1≤i≤n，，Hi源自列表list-1。

（3）秘密值詢問：A2詢問IDi的秘密值。如果IDi=IDγ，則Γ 終止游戲；否則，Γ 查詢list-4 并輸出δi給A2。

最后，A1輸出一個偽造簽名σ。在詢問過程中，A2不能詢問用戶IDi的完整私鑰，簽名諭言機不返回σ。如果≠IDγ，則Γ 終止游戲；否則，Γ 偽造另一個簽名σ*。則有：

Γ 調(diào)用相關(guān)諭言機，利用分叉引理計算得出ECDL 問題實例解答：

評估Γ 取得成功的概率。令E1表示Γ 不終止游戲的概率；E2表示 A1成功偽造一個簽名的概率；E3表示在成功偽造一個簽名的情況下至少存在一條與非目標(biāo)身份有關(guān)的記錄。如果這3 個事件全部發(fā)生，則Γ 取得成功。事件E1存在一次及以上沒有對目標(biāo)身份進行部分私鑰詢問的概率是 Pr[E1] ≥ 1/(ls+l x+lr)（ls為詢問秘密值的次數(shù)）；事件E2表示 A1在游戲中獲勝的概率是 Pr[E1|E2]≥ε；事件E3表示在n次重復(fù)詢問中，該事件出現(xiàn)一次及以上的概率是Pr [E3|E1∩E2]≥1 /n。因此，解決ECCDH 問題的成功概率為：

定理3：在多源網(wǎng)絡(luò)編碼環(huán)境下，防御污染/偽造的網(wǎng)絡(luò)編碼中的橢圓曲線多重簽名方案（NC-ECMSS）能抵抗污染攻擊。

在NC-ECMSS 中，如果敵手想要偽造多重簽名，需要知道簽名人的私鑰，而私鑰的破解是非常困難的。

為了防止網(wǎng)絡(luò)中的污染攻擊，NC-ECMSS利用同態(tài)哈希函數(shù)的安全性和ECDL 問題的難解性，解決簽名過程發(fā)生在源節(jié)點處和中間節(jié)點處。對于源節(jié)點處，敵手可以捕獲網(wǎng)絡(luò)中的任何節(jié)點并利用它發(fā)起攻擊。如果在此節(jié)點發(fā)送污染的信息或偽造簽名給下一個節(jié)點，那么敵手通過簽名者公鑰計算簽名者私鑰的行為相當(dāng)于解決了ECDL 問題。對于中間節(jié)點處，敵手可以捕獲源節(jié)點發(fā)送的完整簽名偽造多重簽名，只要破解出每個簽名者的私鑰和隨機數(shù)，同樣相當(dāng)于解決了ECDL問題。解決ECDL 問題在計算上是不可行的，因此CL-NCBMS 能夠抗多源網(wǎng)絡(luò)編碼環(huán)境下的污染攻擊。

6 效率分析

本節(jié)對NC-CLMSS 的計算效率進行分析。實驗設(shè)備使用Lenovo v310-15-ISK，Windows 10 系統(tǒng)，2.5 GHz CPU、8 G 內(nèi)存。仿真平臺為MATLAB2016a。主要的密碼操作在系統(tǒng)中的計算開銷如表1 所示。簽名、驗證階段性能比較如表2 所示?？傮w而言，NC-CLMSS 具有相對較小的計算復(fù)雜度。

表1 計算耗時比較

表2 計算效率比較

7 結(jié) 語

本文利用同態(tài)哈希安全性和橢圓曲線離散對數(shù)ECDL 問題設(shè)計了防御污染/偽造的網(wǎng)絡(luò)編碼中的橢圓曲線多重簽名方案（NC-ECMSS），其具有抗污染攻擊和偽造攻擊的特性，且驗證效率更高，計算復(fù)雜度更低。在隨機諭言模型下，證明NC-ECMSS 滿足適應(yīng)性選擇消息攻擊下的不可偽造性安全性，但其安全性仍需進一步研究如何在不利用諭言模型的情況下，實現(xiàn)適應(yīng)性隨機消息攻擊下的不可偽造性，構(gòu)造出多播網(wǎng)絡(luò)的一系列防污染/竊聽的網(wǎng)絡(luò)編碼簽名方案。