基于編碼的數(shù)字簽名技術(shù)綜述

摘要：為抵抗量子算法的攻擊，編碼密碼技術(shù)成為了近期密碼學(xué)領(lǐng)域的熱點(diǎn)研究內(nèi)容之一。將編碼密碼技術(shù)與數(shù)字簽名技術(shù)有效的聯(lián)系起來成為了當(dāng)代密碼學(xué)及信息安全領(lǐng)域研究的重要課題之一。本文首先對編碼理論及相關(guān)基礎(chǔ)知識做了一定的介紹，其次介紹了幾種高級數(shù)字簽名;最后分析了經(jīng)典的CFS簽名算法。

關(guān)鍵詞：編碼;數(shù)字簽名;CFS簽名

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2020）09-0186-04

0 引言

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

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

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

本文首先介紹了基于編碼的數(shù)字簽名技術(shù)的相關(guān)基礎(chǔ)知識，并對數(shù)字簽名做了簡單的概述，然后介紹了經(jīng)典了CFS方案。

1 基礎(chǔ)知識

1.1 編碼基礎(chǔ)

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

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

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

1.2 數(shù)字簽名基礎(chǔ)

數(shù)字簽名（Data Signature），是一種可以為消息的接收者確認(rèn)消息發(fā)送者的身份，并且可以驗(yàn)證消息完整性的算法方案，同時(shí)，簽名及消息的真實(shí)性可由第三方驗(yàn)證。一個(gè)數(shù)字簽名算法的基本結(jié)構(gòu)如圖1所示。

一個(gè)數(shù)字簽名算法一般由簽名人和驗(yàn)證者兩個(gè)參與實(shí)體構(gòu)成，通常包括3個(gè)算法，密鑰生成算法、簽名算法和驗(yàn)證算法：

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

（2）簽名：簽名算法是一個(gè)概率多項(xiàng)式時(shí)間交互協(xié)議，簡記為sign（sk，M），簽名人用私鑰sk對消息M進(jìn)行簽名，得到消息的簽名σ;

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

一個(gè)基本的數(shù)字簽名算法，應(yīng)滿足以下幾點(diǎn)：1）驗(yàn)證者應(yīng)能驗(yàn)證消息內(nèi)容及消息來源的真實(shí)性，并且可以驗(yàn)證簽名人的身份;2）除簽名人之外的任何人均不可偽造出消息的合法簽名，簽名人也不可否認(rèn)其簽名;3）當(dāng)簽名人和驗(yàn)證者對簽名的真實(shí)性發(fā)生爭執(zhí)時(shí)，可在第三方（仲裁者）處對簽名的真?zhèn)芜M(jìn)行驗(yàn)證。

2 高級數(shù)字簽名

數(shù)字簽名技術(shù)在身份認(rèn)證、匿名性及不可否認(rèn)性等信息安全領(lǐng)域，特別是在電子商務(wù)、電子政務(wù)等需要計(jì)算機(jī)網(wǎng)絡(luò)安全的領(lǐng)域都有著非常重要的作用，是信息安全的核心技術(shù)之一。隨著電子商務(wù)、電子政務(wù)的不斷發(fā)展，出現(xiàn)了很多基于不同領(lǐng)域的高級數(shù)字簽名，下面對其進(jìn)行簡要的介紹：

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

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

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

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

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

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

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

除了以上數(shù)字簽名外，還有不可否認(rèn)簽名、指定確認(rèn)人簽名等其他形式的數(shù)字簽名，這些不同類型的數(shù)字簽名也得到了學(xué)者的廣泛關(guān)注。

3 基于編碼的數(shù)字簽名

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

3.1 初始化Setup

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

3.2 簽名Sing

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

（2）用哈希函數(shù)h計(jì)算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的位置標(biāo)號，計(jì)算z的標(biāo)號Iz：

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

3.3 驗(yàn)證Verify

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

（2）根據(jù)簽名σ中的標(biāo)號Iz恢復(fù)出z，將z左乘公鑰H計(jì)算其校驗(yàn)子s2：s2=HzT;

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

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

4 結(jié)語

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

參考文獻(xiàn)

[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].北京電子科技學(xué)院學(xué)報(bào)，2013，21（2）：50-55.

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

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