基于編碼的數字簽名技術綜述

摘要：為抵抗量子算法的攻擊，編碼密碼技術成為了近期密碼學領域的熱點研究內容之一。將編碼密碼技術與數字簽名技術有效的聯系起來成為了當代密碼學及信息安全領域研究的重要課題之一。本文首先對編碼理論及相關基礎知識做了一定的介紹，其次介紹了幾種高級數字簽名;最后分析了經典的CFS簽名算法。

關鍵詞：編碼;數字簽名;CFS簽名

中圖分類號：TP311 文獻標識碼：A 文章編號：1007-9416（2020）09-0186-04

0 引言

數字簽名是信息安全技術中的重要組成部分，可應用于日常生活及商業、政治、軍事等重大領域。1976年，Diffie和Hellman首次在“密碼學新方向”一文中提出數字簽名的概念，概念描述為簽名人保存其私鑰用于產生簽名，公布其公鑰用于驗證簽名。目前，存在RSA公鑰數字簽名、ECC橢圓曲線數字簽名、ElGamal數字簽名等很多種不同的數字簽名，但是，隨著數字簽名技術的不斷發展，盲簽名、群簽名等不同形式的高級數字簽名相繼出現，這些高級數字簽名不僅擁有數字簽名的基本性質，還具有其特殊性。雖然這些不同種類的數字簽名算法都得到了廣泛的應用，但是由于其多是基于數學困難問題構建的，無法有效的抵制量子攻擊算法。因此，基于編碼問題研究環簽名、群簽名等應用于特殊領域的數字簽名技術具有非常重要的意義。

1990年西安電子科技大學的王新梅教授[1]首先嘗試將編碼問題用于數字簽名技術。隨后Courtois等學者于2001年利用線性分組碼的譯碼困難問題構造了CFS（Courtois finasz sendrier）[1]數字簽名算法，其簽名是利用Hash函數對消息進行重復計算，直到輸出可譯碼的校驗子為止，該簽名體制的安全性能夠規約到McEliece問題，是真正嚴格意義上比較安全的基于編碼的數字簽名算法。2007年，Dallot[2]對CFS算法進行修正并給出安全性證明。2009年，Finiasz[3]等學者對CFS算法做了進一步的安全性分析，并給出新的安全參數。

此外，學者們也致力于基于編碼問題研究各種不同應用領域的數字簽名。2007年，鄭東教授基于CFS簽名算法提出了一種基于編碼的環簽名方案[4];同年，Cayrel等學者[5]首次利用編碼問題實現了基于身份的數字簽名方案。Overbeck于2009年基于QC碼[6]首次提出了基于編碼的盲簽名方案，但由于其簽名長度較長，實用性不高;同年Leonard等[7]學者提出了可證明安全性的基于編碼的門限環簽名，這是首次給出的可證明安全性的基于編碼的數字簽名方案。2013年，李澤慧等學者基于Niederreiter公鑰體制[8]和McEliece公鑰體制[9]提出了兩種基于編碼的盲簽名方案。

本文首先介紹了基于編碼的數字簽名技術的相關基礎知識，并對數字簽名做了簡單的概述，然后介紹了經典了CFS方案。

1 基礎知識

1.1 編碼基礎

定義1：線性分組碼（Linear block codes）有限域F2上的一個（n，k）線性分組碼C是n維線性空間的一個k維子空間，C中的向量稱為碼字，n稱為碼長，k稱為碼的維數。

定義2：生成矩陣（generating matrix）與校驗矩陣（parity check matrix）（n，k）線性分組碼C的生成矩陣是一個k×n階的矩陣G，其中G的行向量構成了C的一組基。校驗矩陣是一個（n-k）×n階的矩陣H，其中校驗矩陣H的任意行向量與生成矩陣G的任意行向量正交，即HGT=0。

定義3：SD問題（Syndrome Decoding）給定有限域F2上的r×n矩陣H，字及整數，是否存在字滿足且重量小于。

1.2 數字簽名基礎

數字簽名（Data Signature），是一種可以為消息的接收者確認消息發送者的身份，并且可以驗證消息完整性的算法方案，同時，簽名及消息的真實性可由第三方驗證。一個數字簽名算法的基本結構如圖1所示。

一個數字簽名算法一般由簽名人和驗證者兩個參與實體構成，通常包括3個算法，密鑰生成算法、簽名算法和驗證算法：

（1）密鑰生成：密鑰生成算法是一個概率多項式時間算法，簡記為keygen（k），系統輸入安全參數k，輸出簽名人的公鑰pk、私鑰sk，其中，公鑰pk公開，私鑰sk交由簽名人保密;

（2）簽名：簽名算法是一個概率多項式時間交互協議，簡記為sign（sk，M），簽名人用私鑰sk對消息M進行簽名，得到消息的簽名σ;

（3）驗證：驗證者利用公鑰pk驗證消息的簽名σ，簡記為verify（pk，σ），輸出“1”（表示簽名有效）、“0”（表示簽名無效）。

一個基本的數字簽名算法，應滿足以下幾點：1）驗證者應能驗證消息內容及消息來源的真實性，并且可以驗證簽名人的身份;2）除簽名人之外的任何人均不可偽造出消息的合法簽名，簽名人也不可否認其簽名;3）當簽名人和驗證者對簽名的真實性發生爭執時，可在第三方（仲裁者）處對簽名的真偽進行驗證。

2 高級數字簽名

數字簽名技術在身份認證、匿名性及不可否認性等信息安全領域，特別是在電子商務、電子政務等需要計算機網絡安全的領域都有著非常重要的作用，是信息安全的核心技術之一。隨著電子商務、電子政務的不斷發展，出現了很多基于不同領域的高級數字簽名，下面對其進行簡要的介紹：

（1）盲簽名（blind signature）：1982年，Chaum首次提出盲簽名的概念。消息擁有者通過簽名人獲得消息的簽名，而簽名人只能證明自己對消息簽過名，卻無法得到消息的任何具體內容，也無法追蹤消息與執行簽名過程間的相互關系。如在電子交易中，貨幣的使用人實現電子交易，卻不希望銀行知道自己賬戶的信息以及變化詳情，這就可以用到盲簽名。

（2）群簽名（group signature）：群簽名的概念是Chaum和Heyst于1991年首次提出的。在一個群簽名體制中，群體中的任一成員都可以代表整個群體以匿名的方式對消息進行簽名，驗證者只能確定簽名是由群體中的某一成員產生的，但不知道具體是哪一個成員，即匿名性。當存在爭議時，群管理員可通過打開簽名查出簽名人的實際身份，使簽名人不可否認自己的簽名，即可追蹤性。另外，在不打開群簽名的條件下，任何人不能確定兩個群簽名是否為同一群成員生成。

（3）環簽名（ring signature）：環簽名的概念是在群簽名的基礎上提出的，于2001年由Rivest等人在亞洲密碼學年會上提出。在環簽名體制中，簽名人隨意選取n-1人，連同自己一起構成一個n人的環，然后用自己的私鑰和其他n-1人的公鑰一起對消息進行環簽名操作。由于環簽名是環中成員自發進行的，體制中無法追蹤簽名人的身份，具有不可撤銷的匿名性。

（4）基于身份的數字簽名（IBS，Identity Based Signature）：1984年，Shamir提出了一種基于身份的密碼思想，利用用戶公開的身份信息計算或者由公開的身份信息通過公開的算法計算用戶的公鑰，由密鑰生成器生成用戶的私鑰，并由用戶自己保密，交互雙方通過對方的身份信息加密或簽名驗證。

（5）民主群簽名（democratic group signature）：民主群簽名是一種特殊的群簽名，由Manulis于2006年提出，民主群簽名即群中的任意成員都可代表群體產生群簽名，并且群體中的任意成員都可從群簽名中恢復出該簽名的群成員身份。

（6）具有消息恢復的簽名：Nyberg和Rueppel于1994年提出了基于消息恢復簽名方案，該簽名可根據簽名結果恢復被簽名的消息。

（7）多重簽名：Itakura等學者于1983年提出了一種特殊的數字簽名，即多重簽名，即多人參與對文件的簽名，并分別對其進行簽名。

除了以上數字簽名外，還有不可否認簽名、指定確認人簽名等其他形式的數字簽名，這些不同類型的數字簽名也得到了學者的廣泛關注。

3 基于編碼的數字簽名

目前基于編碼的數字簽名方案在一般數字簽名、環簽名等領域取得了一定的成果，如Courtois等學者提出的CFS簽名方案，鄭東教授提出的基于編碼的環簽名方案等。本節主要介紹經典的CFS簽名算法，其安全性可以歸結為一般譯碼問題和Goppa碼與隨機線性碼的不可區分問題等NP困難問題。算法的具體過程如下所示。

3.1 初始化Setup

在有限域F2上選取一個m次既約多項式g（x），由多項式g（x）生成一個（n，k，t）既約Goppa碼，其中n=2m為碼長，k=n-mt為碼的維數，t為碼的糾錯能力。碼的（n-k）×n階校驗矩陣記為H0，對應的譯碼算法記為γ。隨機選擇的（n-k）×（n-k）階非奇異矩陣U，n×n階置換矩陣P，計算H=UH0P，H可看做（n，k，t）線性分組碼C的（n-k）×n階校驗矩陣。公開公鑰H，私鑰U、P、H0、γ由簽名人保密。

3.2 簽名Sing

（1）簽名人選擇一個公開的哈希函數h，并對消息M進行哈希運算得到n-k長的序列s：s=h（M）;

（2）用哈希函數h計算n-k長的序列si：si=h（s|i），其中i=0，1，2…;

（3）簽名人使用秘密的譯碼算法γ對si嘗試譯碼，將最小的使si可譯碼的i記為i0，并將譯出的字記作z，滿足：HzT=si0，ω（z）=t;

（4）令i1i2…it為z中取值為1的位置標號，計算z的標號Iz：

（5）公開消息-簽名對（M，σ）=（M，[Iz|i0]）。

3.3 驗證Verify

（1）驗證者收到（M，σ），根據消息M的哈希值h（M）和簽名σ中的i0計算n-k長的序列s1：s1=h（[h（M）|i0]）;

（2）根據簽名σ中的標號Iz恢復出z，將z左乘公鑰H計算其校驗子s2：s2=HzT;

（3）若s1=s2，則簽名有效，否則簽名無效。

由于簽名時的平均譯碼嘗試次數約為t！次，而一個快速有界譯碼算法在幾分鐘內即可完成約一百萬次譯碼，則t的取值應不超過10（10！=3628800）[10]。因此，在Canteaut-Chabaud攻擊下，可接受的安全強度為280次CPU運算，當t=10、n=215時，譯碼開銷為287.4;當t=9、n=216時，譯碼開銷為283.7，能夠達到可接受的安全強度。

4 結語

基于編碼的數字簽名是目前可以抵抗量子算法攻擊的一類數字簽名，由于其安全性較高，受到了國內外研究學者們的重視。到目前為止，基于編碼的數字簽名的研究在不斷發展，但是仍然不夠成熟，具有很大的研究與應用的空間。本文即對基于編碼的數字簽名技術做了一個簡單的綜述介紹。

參考文獻

[1] Xinmei W.Digital signature scheme based on error-correcting codes[J].Electronics Letters，1990，26（13）：898-899.

[2] Courtois，Matthieu Finiasz，Nicolas Sendrier.How to Achieve a McEliece-Based Digital Signature Scheme[C].Advances in Cryptology - ASIACRYPT 2001，International Conference on the Theory and Application of Cryptology and Information Security， Gold Coast，Australia，December 9-13，2001，Proceedings，2001.

[3] Dallot L.Towards a Concrete Security Proof of Courtois， Finiasz and Sendrier Signature Scheme[M].Research in Cryptology.Springer-Verlag，2008.

[4] Matthieu Finiasz，Nicolas Sendrier.Security Bounds for the Design of Code-Based Cryptosystems [C].Advances in Cryptology - ASIACRYPT 2009，International Conference on the Theory and Application of Cryptology and Information Security，Tokyo，Japan， December 6-10，2009.Proceedings，2009.

[5] Zheng D，Li X，Chen K.Code-based Ring Signature Scheme[J].Chinese Journal of Electronics，2007，16（3）：154-157.

[6] Cayrel P L，Otmani A，Vergnaud D.On Kabatianskii-Krouk-Smeets Signatures[C].Proceedings of the 1st international workshop on Arithmetic of Finite Fields.Springer-Verlag，2007.

[7] Dallot，Léonard，Damien Vergnaud.Provably Secure Code-Based Threshold Ring Signatures[J].Cryptography and Coding.Springer Berlin Heidelberg，2009（5）：222-235.

[8] 李澤慧，李子臣.基于Niederreiter公鑰密碼體制的盲簽名方案[J].北京電子科技學院學報，2013，21（2）：50-55.

[9] 趙程程.基于McEliece公鑰密碼體制的盲簽名算法研究[J].北京電子科技學院學報，2012，20（2）：32-38.

[10] 王倩，鄭東，任方.基于編碼的盲簽名方案[J].計算機應用，2015，35（10）：2867-2871.