close

摘

要

網絡編碼融合了路由和編碼的信息通信技術，能夠節約無線網絡資源和提升網絡吞吐量。而傳統的多重簽名不適合用於網絡編碼環境，鑑於此，提出一種網絡編碼中的橢圓曲線多重簽名方案，每個源節點為發送的消息生成多重簽名，中間節點對收到的信息進行線性組合。該方案針對多源網絡編碼設計融合了無證書有序多重簽名和同態哈希函數，與消息大小無關，能抗污染攻擊和偽造攻擊，驗證效率高。

內容目錄

1 基礎知識
1.1 ECDL 問題
1.2　多源網絡編碼知識
2 形式化定義
2.1 算法定義
2.2 安全模型
3 方案實例
3.1 參數生成算法
3.2 部分私鑰生成算法
3.3 密鑰生成算法
3.4 簽名算法
3.5 組合算法
3.6 驗證算法
4 正確性論證
4.1 單個簽名的驗證
4.2 組合簽名的驗證
5 安全性分析
6 效率分析
7 結 語
網絡編碼是兼具路由和編碼功能的信息通信技術，其優點為信息吞吐量大和魯棒性強。如果節點以某種方式對消息進行編碼後轉發，這種網絡結構可以獲得理論中最大的傳輸效率。當前，研究人員一直比較關注網絡編碼安全問題，並設計出一系列防污染/竊聽的網絡編碼簽名方案。重簽名允許多個用戶對同樣的消息進行簽名，每個用戶對收到的消息進行部分簽名，然後交給簽名收集者形成最終簽名。
目前沒有任何基於橢圓曲線的網絡編碼多重簽名。如何設計安全高效的網絡編碼多重簽名是一個值得研究的問題。基於此，本文設計了防禦污染/偽造的網絡編碼中的橢圓曲線多重簽名方案(NC-ECMSS)。每個源節點為消息生成一個有序的多重簽名，中間節點對接收的信息進行線性組合。NC-ECMSS具有抗污染攻擊和偽造攻擊的特性，而且比起現有技術而言，其驗證效率較高、計算複雜度較低。



1　基礎知識

1.1　ECDL問題
橢圓曲線離散對數(Elliptic Curve DiscreteLogarithm，ECDL)問題，給定橢圓曲線E和橢圓曲線點，ECDL問題是指找到一個正整數，使之滿足在計算上是不可行的。
1.2　多源網絡編碼知識
令(B,C)為多播網絡，其中B為節點集，C為邊集。每個源節點發送的消息為，每條消息都由有限域上的n個元素組成，可看作n維向量空間中的一個向量，用表示，其中。多播網絡中任意邊上的消息為，中間節點收到的條消息的線性組合為，編碼係數向量稱為局部編碼向量。則亦可以用原消息的線性組合表示為，其中，全局編碼向量附在消息中傳輸，則將消息擴展成，編碼消息的具體標識為。



2　形式化定義

2.1　算法定義
NC-ECMSS包含以下6個概率多項式時間算法。
(1)參數生成算法：輸入安全參數，輸出系統主密鑰和系統公開參數。
(2)部分私鑰生成算法：輸入，，，輸出部分私鑰，其中代表用戶身份。
(3)密鑰生成算法：輸入，輸出該用戶的秘密值、公鑰。
(4)多重簽名算法：輸入消息向量，，，，用戶驗證上個用戶傳來的部分簽名後，輸出其部分簽名，其中是簽名順序。
(5)組合簽名算法：輸入消息向量，輸出組合後消息向量和對應的組合簽名。
(6)驗證算法：輸入，如果驗證等式成立，接受簽名；否則，輸出⊥。
2.2　安全模型
防禦污染/偽造的網絡編碼中的橢圓曲線多重簽名方案(NC-ECMSS)滿足適應性選擇消息攻擊下的不可偽造性安全性(UF-CMA)。通過挑戰者C與敵手之間的實驗遊戲來描述NC-ECMSS的UF-CMA安全模型。
首先，通過發生器生成兩個敵手，，其中，敵手模擬的是惡意的密鑰生成中心(Key Generation Center，KGC)，敵手模擬的是不誠實用戶，不知道主密鑰，但能替換任意用戶的公鑰；知道主密鑰，但無法更換任意用戶公鑰。然後，發出一系列適應性詢問，詳見式(1)。
最後，由輸出一個偽造簽名，在詢問中，不會詢問用戶的完整私鑰，也不能詢問用戶的私鑰，偽造的簽名不會是任何多重簽名諭言機輸出的。如果簽名驗證等式通過，則在中獲勝，反之，則失敗。不可偽造性。如果沒有多項式時間敵手在遊戲實驗中以不可忽略的優勢成功，則稱防禦污染/偽造的網絡編碼中的橢圓曲線多重簽名方案(NC-ECMSS)滿足適應性選擇消息攻擊下的不可偽造性安全性(UF-CMA)。



3　方案實例

3.1　參數生成算法
給定比特大素數、橢圓曲線，定義Gp為加法循環群，為具有素階的橢圓曲線的基點和群的生成元，KGC隨機選取，計算系統公鑰。KGC選擇安全的哈希函數為，，。最後，KGC保密主控鑰但公開系統參數為：
3.2　部分私鑰生成算法
首先，KGC隨機選取參數，計算生成參數，其中，。其次，KGC計算哈希值，部分私鑰。最後，KGC公開，並發送部分私鑰給擁有身份的用戶。通過來驗證的有效性。
3.3　密鑰生成算法
用戶選取一個隨機數作為秘密值，計算公鑰，其中，公鑰合集。
3.4　簽名算法
源節點用戶按照順序進行多重簽名，其中，定義個用戶的身份集合為。針對消息計算，，部分簽名，並且輸出對消息的部分簽名給。
用戶收到發來的後，計算，其中。然後，通過計算等式來驗證的有效性。如果成立，則繼續進行操作，計算
定義第個用戶對消息的有序多重簽名為。當第個用戶對消息的有序多重簽名完成後，將最終的簽名發送給中間節點和目的節點，中間節點對消息進行線性組合。
3.5　組合算法
給定的消息局部編碼向量為，中間節點收到的消息向量為，則組合後的消息向量為。任意消息也是的線性組合，即。所對應的簽名的生成過程為，其中為的第個元素，簽名的生成可以表示為。
3.6　驗證算法
當目的節點接收到多重簽名和組合簽名後，計算，，其中。如果等式成立，則簽名有效，反之，則簽名無效。



4　正確性論證

4.1　單個簽名的驗證
計算出單個簽名的驗證過程如下：
4.2　組合簽名的驗證
給定消息、全局編碼向量，則中間節點收到的消息向量為，假設消息向量所對應的簽名為，然後驗證是否成立。依據網絡編碼理論可知，不同的源節點可能會發送相同的消息，為了區分相同消息可能被組合到一起的情況，表示為，其中標識符。消息來源於不同的源節點，每個源節點的全局編碼向量可以表示，則消息向量，所對應的多重簽名可以用哈希函數的同態性表示為，則多重簽名中第個分量為：
式中：為用戶對消息生成的多重簽名的第個分量。對於組合密文，則有：



5　安全性分析

定理1：在隨機諭言模型下，NC-ECMSS針對外部敵手是存在性不可偽的。
證明：假設是橢圓曲線離散對數ECDL問題的實例，挑戰者的任務是利用確定一個正整數的值。挑戰者需要維護初始時都為空的列表list-1，list-2，list-3，list-4，以存儲針對相應諭言機的詢問-應答值。為挑戰者身份，其中是一個正整數，為詢問諭言機的次數。挑戰者首先運行參數生成算法得到系統參數，輸出給。然後，執行以下多項式有界次適應性詢問。
(1)詢問：針對元組詢問諭言機，如果列表list-1中有相應的記錄，則輸出給；否則，輸出，添加到列表list-1中。
(2)詢問：針對元組詢問諭言機，如果列表list-2中有相應的記錄，則輸出給；否則，輸出，添加到列表list-2中。
(3)詢問：針對元組詢問諭言機，如果列表list-3中有相應的記錄，則輸出給；否則，輸出，添加到列表list-3中。
(4)公鑰詢問：提交公鑰詢問。選取，輸出，添加到列表list-4中。
(5)部分私鑰詢問：詢問的部分私鑰。如果，則終止遊戲；否則，選取，計算，調用list-1得到並計算，使得，輸出給，並用更新列表list-4，其中。
(6)秘密值詢問：詢問的秘密值。如果對應公鑰未被替換，則查詢列表list-4並輸出給。
(7)公鑰替換詢問：詢問的公鑰替換詢問。如果，則終止遊戲；否則，選取替換的公鑰，並用更新列表list-4。
(8)多重簽名詢問：詢問對消息的簽名。如果，則正常運行多重簽名算法並輸出簽名給；否則，以簽名順序對消息進行簽名。針對消息計算，，部分簽名，然後按順序進行簽名。順序對順序的，先計算，，其中。然後，通過計算等式來驗證的有效性，如果成立，繼續計算。最後輸出多重簽名給。
(9)組合簽名詢問：詢問對消息的組合簽名。如果，則Γ正常運行組合算法並輸出簽名給；否則，計算組合消息向量，其中，消息局部編碼向量為，消息向量為。任意消息也是的線性組合，即，其中。則所對應的簽名的生成過程為，其中為的第個元素，最後輸出組合簽名給A1。
(10)驗證詢問：詢問對消息的組合簽名。如果，則正常運行驗證算法並輸出一個結果給；否則，計算，，然後驗證是否成立，如果成立，則輸出；否則，輸出。
最後，輸出一個偽造簽名。在詢問過程中，不能詢問用戶的完整私鑰，簽名諭言機不返回。如果，則終止遊戲；否則，偽造另一個簽名。則有：
調用相關諭言機，利用分叉引理計算得出ECDL問題實例解答：
評估取得成功的概率。令表示不終止遊戲的概率；表示成功偽造一個簽名的概率；E3表示在成功偽造一個簽名的情況下至少存在一條與非目標身份有關的記錄。如果這3個事件全部發生，則取得成功。事件存在一次及以上沒有對目標身份進行部分私鑰詢問的概率是(為詢問秘密值的次數，為詢問部分私鑰的次數，為公鑰替換的次數)；事件E2表示成功偽造一個簽名的概率是；事件E3表示在次重複詢問中，該事件出現一次及以上的概率是。因此，解決ECDL問題的成功概率為：
定理2：在隨機諭言模型下，NC-ECMSS針對外部敵手是存在性不可偽的。
證明：假設是ECDL問題的實例，挑戰者的任務是利用確定一個正整數的值。挑戰者需要維護初始時都為空的列表list-1，list-2，list-3，list-4，以存儲針對相應諭言機的詢問-應答值。為挑戰者身份，其中是一個正整數，為詢問諭言機的次數。挑戰者首先運行參數生成算法得到系統參數，輸出給。然後，執行以下多項式有界次適應性詢問，其中哈希詢問與定理1相同，這裡不再贅述。
(1)公鑰詢問：詢問的公鑰。選取，輸出，添加到列表list-4中。
(2)部分私鑰詢問：詢問的部分私鑰。如果，則終止遊戲；否則，選取，設置，計算，使得，輸出給，並用更新列表list-4，其中，，源自列表list-1。
(3)秘密值詢問：詢問的秘密值。如果，則終止遊戲；否則，查詢list-4並輸出給A2。
(4)多重簽名詢問：詢問對消息的簽名。如果，則正常運行多重簽名算法並輸出簽名給；否則，以簽名順序對消息進行簽名。針對消息計算，並計算使之滿足，然後按順序進行簽名。順序對順序，先計算，其中。然後，通過計算等式來驗證的有效性，如果成立，繼續計算，並計算。最後輸出多重簽名。
(5)組合簽名詢問：詢問一個組合簽名。如果，則正常運行組合算法並輸出組合簽名給；否則，計算組合消息向量，其中，消息局部編碼向量為，消息向量為。任意消息也是的線性組合，即，其中。則所對應的簽名的生成過程為，其中為的第個元素，最後輸出組合簽名。
(6)驗證詢問：進行驗證詢問。如果，則正常運行驗證算法並輸出一個結果；否則，計算，然後驗證是否成立，如果成立，則輸出；否則，輸出⊥。
最後，輸出一個偽造簽名。在詢問過程中，不能詢問用戶的完整私鑰，簽名諭言機不返回。如果，則終止遊戲；否則，偽造另一個簽名。則有：
調用相關諭言機，利用分叉引理計算得出ECDL問題實例解答：
評估取得成功的概率。令表示不終止遊戲的概率；表示成功偽造一個簽名的概率；表示在成功偽造一個簽名的情況下至少存在一條與非目標身份有關的記錄。如果這3個事件全部發生，則取得成功。事件存在一次及以上沒有對目標身份進行部分私鑰詢問的概率是(為詢問秘密值的次數)；事件表示在遊戲中獲勝的概率是；事件表示在n次重複詢問中，該事件出現一次及以上的概率是。因此，解決ECCDH問題的成功概率為：
定理3：在多源網絡編碼環境下，防禦污染/偽造的網絡編碼中的橢圓曲線多重簽名方案(NC-ECMSS)能抵抗污染攻擊。
在NC-ECMSS中，如果敵手想要偽造多重簽名，需要知道簽名人的私鑰，而私鑰的破解是非常困難的。
為了防止網絡中的污染攻擊，NC-ECMSS利用同態哈希函數的安全性和ECDL問題的難解性，解決簽名過程發生在源節點處和中間節點處。對於源節點處，敵手可以捕獲網絡中的任何節點並利用它發起攻擊。如果在此節點發送污染的信息或偽造簽名給下一個節點，那麼敵手通過簽名者公鑰計算簽名者私鑰的行為相當於解決了ECDL問題。對於中間節點處，敵手可以捕獲源節點發送的完整簽名偽造多重簽名，只要破解出每個簽名者的私鑰和隨機數，同樣相當於解決了ECDL問題。解決ECDL問題在計算上是不可行的，因此CL-NCBMS能夠抗多源網絡編碼環境下的污染攻擊。



6　效率分析

本節對NC-CLMSS的計算效率進行分析。實驗設備使用Lenovo v310-15-ISK，Windows 10系統，2.5 GHz CPU、8 G內存。仿真平台為MATLAB2016a。主要的密碼操作在系統中的計算開銷如表1所示。簽名、驗證階段性能比較如表2所示。總體而言，NC-CLMSS具有相對較小的計算複雜度。
表 1　計算耗時比較
表 2　計算效率比較



7　結　語

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

引用本文：楊文山.網絡編碼中的橢圓曲線多重簽名方案[J].信息安全與通信保密,2022(8):112-120.

作者簡介 >>>

楊文山，男，碩士，高級工程師，主要研究方向為信息安全。

選自《信息安全與通信保密》2022年第8期（為便於排版，已省去原文參考文獻）


商務合作 | 開白轉載 | 媒體交流 | 理事服務

請聯繫：15710013727（微信同號）

《信息安全與通信保密》雜誌投稿

聯繫電話：13391516229（微信同號）

郵箱：xxaqtgxt@163.com

《通信技術》雜誌投稿

聯繫電話：15198220331（微信同號）

郵箱：txjstgyx@163.com

arrow
arrow
    全站熱搜
    創作者介紹
    創作者 鑽石舞台 的頭像
    鑽石舞台

    鑽石舞台

    鑽石舞台 發表在 痞客邦 留言(0) 人氣()