楊文山

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

0 引 言

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

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

1 基礎(chǔ)知識(shí)

1.1 ECDL 問題

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

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

2 形式化定義

2.1 算法定義

NC-ECMSS 包含以下6 個(gè)概率多項(xiàng)式時(shí)間算法。

（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)驗(yàn)證上個(gè)用戶IDi-1傳來的部分簽名σi-1后，輸出其部分簽名σi，其中L是簽名順序。

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

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

2.2 安全模型

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

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

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

3 方案實(shí)例

3.1 參數(shù)生成算法

給定μ比特大素?cái)?shù)p、橢圓曲線E，定義Gp為加法循環(huán)群，G為具有素階q的橢圓曲線的基點(diǎn)和群Gp的生成元，KGC 隨機(jī)選取x∈ [1,q]，計(jì)算系統(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個(gè)用戶Nn對(duì)消息vi的有序多重簽名為。當(dāng)?shù)趎個(gè)用戶對(duì)消息vi的有序多重簽名完成后，將最終的簽名發(fā)送給中間節(jié)點(diǎn)和目的節(jié)點(diǎn)，中間節(jié)點(diǎn)對(duì)消息進(jìn)行線性組合。

3.5 組合算法

3.6 驗(yàn)證算法

4 正確性論證

4.1 單個(gè)簽名的驗(yàn)證

計(jì)算出單個(gè)簽名的驗(yàn)證過程如下：

4.2 組合簽名的驗(yàn)證

5 安全性分析

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

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

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

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

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

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

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

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

證明：假設(shè)(G,aG)是ECDL 問題的實(shí)例，挑戰(zhàn)者Γ 的任務(wù)是利用A2確定一個(gè)正整數(shù)a∈的值。挑戰(zhàn)者Γ 需要維護(hù)初始時(shí)都為空的列表list-1，list-2，list-3，list-4，以存儲(chǔ)針對(duì)相應(yīng)諭言機(jī)的詢問-應(yīng)答值。IDγ為挑戰(zhàn)者身份，其中γ∈ (1,2,…,l)是一個(gè)正整數(shù)，l為詢問H0諭言機(jī)的次數(shù)。挑戰(zhàn)者Γ 首先運(yùn)行參數(shù)生成算法得到系統(tǒng)參數(shù)λ（ypub=xG），輸出λ給A2。然后，A2執(zhí)行以下多項(xiàng)式有界次適應(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，計(jì)算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輸出一個(gè)偽造簽名σ。在詢問過程中，A2不能詢問用戶IDi的完整私鑰，簽名諭言機(jī)不返回σ。如果≠IDγ，則Γ 終止游戲；否則，Γ 偽造另一個(gè)簽名σ*。則有：

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

評(píng)估Γ 取得成功的概率。令E1表示Γ 不終止游戲的概率；E2表示 A1成功偽造一個(gè)簽名的概率；E3表示在成功偽造一個(gè)簽名的情況下至少存在一條與非目標(biāo)身份有關(guān)的記錄。如果這3 個(gè)事件全部發(fā)生，則Γ 取得成功。事件E1存在一次及以上沒有對(duì)目標(biāo)身份進(jìn)行部分私鑰詢問的概率是 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é)點(diǎn)處和中間節(jié)點(diǎn)處。對(duì)于源節(jié)點(diǎn)處，敵手可以捕獲網(wǎng)絡(luò)中的任何節(jié)點(diǎn)并利用它發(fā)起攻擊。如果在此節(jié)點(diǎn)發(fā)送污染的信息或偽造簽名給下一個(gè)節(jié)點(diǎn)，那么敵手通過簽名者公鑰計(jì)算簽名者私鑰的行為相當(dāng)于解決了ECDL 問題。對(duì)于中間節(jié)點(diǎn)處，敵手可以捕獲源節(jié)點(diǎn)發(fā)送的完整簽名偽造多重簽名，只要破解出每個(gè)簽名者的私鑰和隨機(jī)數(shù)，同樣相當(dāng)于解決了ECDL問題。解決ECDL 問題在計(jì)算上是不可行的，因此CL-NCBMS 能夠抗多源網(wǎng)絡(luò)編碼環(huán)境下的污染攻擊。

6 效率分析

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

表1 計(jì)算耗時(shí)比較

表2 計(jì)算效率比較

7 結(jié) 語

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