一種基于編碼的數(shù)字簽名算法的改進

任 方, 鄭 東

(1. 西安郵電大學 通信與信息工程學院, 陜西 西安 710121；2. 西安郵電大學 無線網(wǎng)絡(luò)安全技術(shù)國家工程實驗室, 陜西 西安 710121)

一種基于編碼的數(shù)字簽名算法的改進

任 方1,2, 鄭 東2

(1. 西安郵電大學 通信與信息工程學院, 陜西 西安 710121；2. 西安郵電大學 無線網(wǎng)絡(luò)安全技術(shù)國家工程實驗室, 陜西 西安 710121)

為提高基于編碼的數(shù)字簽名算法CFS的效率，利用基于編碼的Hash函數(shù)對其進行改進。引入一個Hash函數(shù)，其輸出是一個重量不超過碼的糾錯能力t的正則字的校驗子，用該函數(shù)替換原CFS算法中使用的隨機Hash函數(shù)，使簽名過程中譯碼算法只需執(zhí)行一次，從而避免多次嘗試帶來的時間消耗。改進算法的簽名時間比原始算法縮短了t!倍，簽名效率擺脫了碼的糾錯能力的限制，且二者的安全性依賴于等價的NP完全問題。

數(shù)字簽名；編碼；校驗子；Hash函數(shù)；量子攻擊

基于編碼的公鑰密碼技術(shù)是目前公認的可以抵抗量子攻擊的公鑰密碼技術(shù)[1-2]，是公鑰密碼學未來發(fā)展的主流之一?；诰幋a的公鑰加密算法最早由McEliece提出[3]，該算法基于二元不可約Goppa碼，加密過程等價于給明文碼字添加一個隨機選擇的錯誤向量，而解密相當于譯碼。McEliece算法的安全性可以有效歸約到兩個NP完全問題：二元隨機碼的譯碼問題以及Goppa碼和隨機碼的區(qū)分問題[4-5]。其后出現(xiàn)的Niederreiter算法[6]的安全性被證明與McEliece算法等價。編碼密碼技術(shù)誕生以來產(chǎn)生了大量的研究成果，包括加密、數(shù)字簽名[7-8]、認證[9]、Hash函數(shù)[10]、流密碼[11]等，其中的Courtois-Finiasz-Sendrier(CFS)簽名算法[7]已經(jīng)成為該領(lǐng)域的經(jīng)典算法。

CFS算法是第一個安全的基于編碼的簽名算法，它是一種基于二元Goppa碼的簽名算法，由Niederreiter加密算法改造而來。對于CFS的安全性已經(jīng)有了充分的討論[12-13]，各種改進算法如mCFS[13]和并行CFS[14]等也相繼出現(xiàn)，此外基于CFS可以用來構(gòu)建其它特殊用途的簽名如環(huán)簽名[15-16]和盲簽名[17]等。所有這些簽名算法的核心都與CFS一致，即簽名時對消息的Hash值進行處理使其成為一個Goppa碼的校驗子，簽名過程是利用秘密的譯碼算法對該校驗子進行譯碼，將碼字作為簽名值，而驗證簽名時通過計算碼字的校驗子并與消息的Hash值進行對比來檢驗簽名的有效性。

CFS系列簽名算法都有較高的安全性，但其缺陷也是明顯的，即簽名效率很低。以基本CFS算法為例，要得到一個可以譯碼的校驗子，平均需要進行t！次嘗試，其中t是所使用的Goppa碼的糾錯能力。顯然隨著t的增加，簽名時間將會呈指數(shù)迅速增長，而較小的t值又會帶來安全性低的缺陷，同時與糾錯碼追求較強的糾錯能力成為矛盾，這在一定程度上阻礙了CFS系列算法的應(yīng)用。

本文針對CFS算法的這一缺陷，通過分析算法的實現(xiàn)細節(jié)，尋找簽名效率低下的主要原因，并對算法的簽名過程進行改進，使其簽名時間不隨參數(shù)t的增加而迅速增長。

1 基礎(chǔ)知識

1.1 糾錯碼

定義2 一個(n,k)線性分組碼C的生成矩陣是一個k×n的矩陣G，其中G的行向量構(gòu)成了C的一組基。

線性分組碼C的生成矩陣G不唯一，但是不同的生成矩陣可以通過初等行變換相互轉(zhuǎn)化，即若G是C的一個生成矩陣，P是一個初等矩陣，則PG也是C的一個生成矩陣。

定義3 一個(n,k)線性分組碼C的校驗矩陣是一個(n-k)×n的矩陣H，其中H的任意行向量與C的生成矩陣G的任意行向量正交，即HGT=0。

線性分組碼的校驗矩陣不唯一且可以通過初等行變換相互轉(zhuǎn)化。長為n的向量c是C的一個碼字的充分必要條件是HcT=0。對于任意的字c，將HcT稱為c的校驗子。

定義4 線性分組碼的兩個碼字

u=(u1,u2,…,un),v=(v1,v2,…,vn)

的Hamming距離d(u,v)定義為u和v的不同分量的個數(shù)，即

d(u,v)=|{i:ui≠vi}|,

碼字u的Hamming重量w(u)定義為u與全0碼字0的距離，即

w(u)=d(u,0),

碼C的非零碼字的最小Hamming重量稱為C的最小距離，一般記作dmin。

Goppa碼是一種特殊的線性分組碼，McEliece加密算法使用的Goppa碼的參數(shù)滿足

n=2m， k=n-mt。

利用Goppa碼的具體結(jié)構(gòu)知識可以進行有效的譯碼，這也是構(gòu)造基于編碼的密碼算法的基礎(chǔ)。即將Goppa碼的結(jié)構(gòu)作為秘密的陷門信息，或者解密私鑰，可以實現(xiàn)單向陷門函數(shù)，從而構(gòu)造公鑰加密與簽名算法。

以下只討論F2上的線性分組碼與Goppa碼。

1.2 困難問題

基于編碼的公鑰密碼算法主要依賴于一些困難問題，它們均已被證明是NP完全問題，可以有效抵抗目前已知的量子攻擊。

Goppa碼的區(qū)分(Goppa Code Distinguishing，GD)問題 輸入有限域Fq上的一個(n-k)×n的矩陣H，問H是一個(n,k) Goppa碼的校驗矩陣還是一個隨機(n,k)碼的校驗矩陣？

2 CFS簽名算法及其分析

2.1 CFS簽名算法

構(gòu)造數(shù)字簽名算法一般有三種方法：一是利用現(xiàn)有的公鑰加密算法；二是利用現(xiàn)有的身份認證算法；三是直接構(gòu)造。CFS簽名算法屬于第一種，它是基于Niederreiter加密算法構(gòu)造的簽名算法。此類算法簽名過程的模式一般為

(1) 使用公開的Hash函數(shù)計算待簽名消息的Hash值。

(2) 將這個Hash值看做加密算法的密文，用私鑰進行解密。

(3) 將這一解密結(jié)果附加在消息后作為簽名值。

對于基于編碼的簽名算法，上述步驟的第二步往往不可行，原因在于Niederreiter算法輸出的密文是錯誤向量的校驗子，該校驗子未必一定是可以譯碼的。只有那些重量不超出所選Goppa碼的譯碼能力t的錯誤向量的校驗子才是可以譯碼的，因此CFS算法是一種概率簽名算法。

詳細的CFS算法描述如下。

(1) 參數(shù)生成

?隨機選擇一個F2上的(n,k) Goppa碼C，糾錯能力為t，校驗矩陣為H，以及有效的校驗子譯碼算法γ。

?隨機選擇一個F2上的(n-k)×(n-k)的可逆矩陣Q，一個n×n的置換矩陣P。

?選擇一個公開的安全Hash函數(shù)

?系統(tǒng)公開參數(shù)為〈h,t,Hpub=QHP〉，私鑰為〈Q,H,P,γ〉。

(2) 簽名過程

設(shè)簽名者需要簽署的消息為m。

?計算消息的Hash值s=h(m)。

?對于i=0,1,2,…，將其轉(zhuǎn)換為二進制向量I,計算si=Q-1h(s‖I)，找到使得γ(si)存在的最小的i,記作i0。

?記ν=γ(si0)，則簽名值為(I0‖νP)。

(3) 驗證過程

設(shè)驗證者收到的消息簽名對為〈m,I‖u〉。

?計算a=h(h(m)‖I)，以及b=HpubuT。

?若a=b則簽名正確，否則簽名驗證失敗。

2.2 對CFS簽名算法的分析

CFS算法的安全性已經(jīng)獲得嚴格的形式化證明[13]，并在隨機預(yù)言機模型下被歸約到SD問題和GD問題上。由于具備了較高的安全性，目前大多數(shù)基于編碼的簽名方案均基于CFS進行構(gòu)造。

盡管CFS算法有很高的安全性，但其實現(xiàn)效率即簽名的速度卻比較低，這主要是因為進行簽名時需要進行多次譯碼嘗試。

對于選定的(n=2m,k=n-mt) Goppa碼，設(shè)可以有效譯碼的校驗子個數(shù)為Nd，總的校驗子個數(shù)為Nt，顯然有

因此CFS算法簽名成功的概率為

即平均需要嘗試t!次才能夠得到一個可以譯碼的校驗子。隨著t的增長，這一數(shù)字增長非常快，如果取t=9,則平均需要嘗試9!=362880次才能得到一個簽名[7],但是在相關(guān)攻擊下這一參數(shù)已經(jīng)不再安全[12]。建議參數(shù)需要取

m=15，t=12,

或者

m=16，t=10。

從長遠來看，隨著新的攻擊方法的出現(xiàn)，t的取值要求必然越來越大，這就使得簽名成功的次數(shù)呈指數(shù)增長，簽名速度會越來越低，算法的實現(xiàn)效率也會越來越差。

造成CFS算法簽名效率低下的主要原因是由消息的Hash值計算出的si一般不是碼C的可以譯碼的校驗子，從而要多次計算不同的si去嘗試譯碼，只有當某個si恰好在C的譯碼能力之內(nèi)，譯碼才能完成，簽名也才能成功。為了提高簽名效率，需要對算法進行改進，使得計算出的si本身一定或者至少以很大的概率是可譯碼的校驗子。

3 基于編碼的數(shù)字簽名算法改進

首先構(gòu)造基于編碼的Hash函數(shù)，以此對CFS簽名算法進行改進。

3.1 基于編碼的Hash函數(shù)

基于編碼的Hash函數(shù)構(gòu)造方法，最早只是基于一個壓縮函數(shù)f對給定消息進行多輪循環(huán)計算，最終得到消息的Hash值?？梢宰C明按照這種方法構(gòu)造出的Hash函數(shù)安全性不低于壓縮函數(shù)的安全性[10]。

設(shè)壓縮函數(shù)f的輸入為e位，輸出為r(r

(1) 在第一輪，先選擇長度為r的初始向量vI,再從給定消息中選取e-r位，與vI連接組成長為e的向量，作為函數(shù)f的輸入，得到r位的輸出。

(2) 從第二輪開始，每輪迭代將前一輪r位的輸出反饋回輸入端，再從給定消息中選取e-r位，共同組成長為e的向量作為f的輸入,計算新的r位輸出。

(3) 循環(huán)這一過程直至消息位被取完，最后一輪當消息剩余位數(shù)不足e-r位時，隨機選擇若干比特進行填充，使其滿足輸入位數(shù)要求。將函數(shù)f的最后一輪輸出作為消息的Hash值。

上述迭代過程可參看圖1。

圖1 Hash迭代過程

Hash函數(shù)的構(gòu)造中，最核心的部分是壓縮函數(shù)f。以下給出一種基于編碼困難問題的壓縮函數(shù)f的構(gòu)造方法。

選擇一個(n,k) Goppa碼，其中

n=2m,k=n-mt，

選擇正整數(shù)w|n，顯然有

w=2m′(m′

另取

則可以將長度為n的每一個字分成等長的w個塊，每一塊包含l個比特。如果一個重量為w的字c在每一個塊((i-1)l,il](i=1,2,…,w)內(nèi)恰好有一個1，則稱c為正則字。

所選Goppa碼的校驗矩陣是一個(n-k)×n的矩陣H，可以將H分成w個子矩陣，即

H=(H1，H2，…，Hw),

其中每一個子矩陣

Hi=(hj) (i=1,2,…,w;j=(i-1)l+1, (i-1)l+2,…,il),

而hj為矩陣H的第j列。

定義壓縮函數(shù)

x=(x1,x2,…,xw)，

則函數(shù)的輸出

f(x)=z。

定理1 上述壓縮函數(shù)f的輸出等價于計算一個長為n、重量為w的正則字的校驗子，即對于任意的f(x)，存在正則字c，使得HcT=f(x)。

證明 首先有

定義一個長為n的字

c=(c1,c2,…,cn),cj=1 ? ?xi, (i-1)l+xi+1=j,

即存在xi，將其轉(zhuǎn)換為數(shù)后所選擇的列號恰好對應(yīng)cj的位置標號j。

由于計算一個字的校驗子相當于把該字非零位所對應(yīng)的H矩陣的列進行相加，因此根據(jù)定義f(x)恰好就是c的校驗子，即HcT=f(c)。

又由c的定義，在每一個塊((i-1)l,il](i=1,2,…,w)內(nèi)c有且僅有一個1，因此c是重量為w的正則字。

利用壓縮函數(shù)f，定義基于編碼的Hash函數(shù)

即對于給定的消息m，選擇(n,k) Goppa碼并按照以上定義得到一個壓縮函數(shù)f，采用Augot的循環(huán)迭代方法[10]多次通過f對m的比特位進行壓縮，最終得到的輸出為m的Hash值。hc將任意長度的消息Hash至一個長度為r=n-k的比特串。

定理2 由上述定義得到的基于編碼的Hash函數(shù)hc的輸出是一個長度為n、重量為w的正則字的校驗子。

證明 根據(jù)Hash函數(shù)的循環(huán)迭代構(gòu)造方法，最后一輪輸出的Hash值也是函數(shù)f的輸出，根據(jù)定理1，對于任意的消息m，hc(m)都是一個長度為n、重量為w的正則字的校驗子。

3.2 基于編碼的數(shù)字簽名改進算法

利用基于編碼的Hash函數(shù)hc，對CFS簽名算法進行改進，并將改進算法簡記為CFSc簽名算法，該算法的簽名效率較CFS有較大提升，且其安全性并不會因此而降低。

具體的CFSc簽名算法可描述如下。

(1) 參數(shù)生成

?隨機選擇一個F2上的(n,k) Goppa碼C，糾錯能力為t，校驗矩陣為H，以及有效的校驗子譯碼算法γ。

?隨機選擇一個F2上的n×n置換矩陣P。

?選擇正整數(shù)w≤t且w|n，構(gòu)造基于編碼的Hash函數(shù)

?系統(tǒng)公開參數(shù)為〈hc,t,Hpub=HP〉，私鑰為〈H,P,γ〉。

(2) 簽名過程

設(shè)簽名者需要簽署的消息為m。

?選擇隨機值R，將其轉(zhuǎn)換為二進制向量R，計算

s=hc(hc(m)‖R)。

?記ν=γ(s)，則簽名值為(R‖νP)。

(3) 驗證過程

設(shè)驗證者收到的消息簽名對為〈m,R′‖u〉。

?計算

a=hc(hc(m)‖R′)，b=HpubuT。

?若a=b則簽名正確，否則簽名驗證失敗。

CFSc簽名算法中驗證過程的正確性是指，若〈m,R′‖u〉是根據(jù)簽名過程得到的一對合法的消息-簽名對，則一定有

b=HpubuT=HP(νP)T=HPPTνT=HνT=s=hc(hc(m)‖R′)=a。

4 算法性能分析

對改進后的基于編碼的簽名算法CFSc進行分析，并與原始的CFS算法進行對比。

4.1 算法效率分析

根據(jù)CFSc簽名算法，簽名者在對消息m進行簽名的過程中，需要執(zhí)行兩次Hash運算和一次校驗子譯碼算法。根據(jù)定理2，Hash函數(shù)hc的輸出恰好是一個重量為w的正則字的校驗子，不超過所選Goppa碼的譯碼能力t。因此只要擁有校驗子譯碼算法γ，總是可以有效譯出一個長度為n、重量為w的正則字。與CFS算法平均需要嘗試t!次才能得到一個可以譯碼的校驗子相比，新的算法最大的優(yōu)勢在于不需要進行多次譯碼嘗試，可以提升簽名速度。從長遠來看，這也使算法擺脫了參數(shù)t的限制，為提高安全性選擇較大的t時不會帶來簽名速度的降低。

兩種算法的效率對比如表1所示。

表1 算法的效率對比

4.2 算法安全性分析

與CFS簽名算法相比，新算法CFSc的主要區(qū)別在于將一個隨機的Hash函數(shù)h換成了基于編碼的Hash函數(shù)hc，這一改動的實質(zhì)是將普通Hash函數(shù)改成了陷門Hash函數(shù)，而陷門信息就是所選Goppa碼譯碼算法中的γ。對于這一類Hash函數(shù)，知道陷門信息的人可以有效計算該Hash的逆，不知道該陷門信息的人則無法進行計算。

在CFSc中，由于譯碼算法中的γ是簽名者所持有的私鑰，除了簽名者本人外沒有其他任何人知道。因此只要私鑰保密，該Hash函數(shù)的安全性就可以保證，CFSc的安全性就等價于CFS的安全性。因此這一改動并不會帶來安全性的降低。

兩種算法的安全性對比如表2所示。

表2 算法的安全性對比

5 結(jié)束語

作為最重要的基于編碼的數(shù)字簽名算法，CFS算法自提出以來其安全性和實現(xiàn)效率都得到了廣泛的研究，但是其簽名速度隨參數(shù)增加而急劇降低這一缺陷卻一直沒有好的解決辦法，因此影響了該算法的進一步應(yīng)用。

將基于編碼的Hash函數(shù)引入CFS簽名算法，設(shè)計一種基于編碼的簽名改進算法CFSc。該算法在進行簽名時不需要對校驗子進行多次譯碼嘗試，從而有效提升了簽名速度，可以在不降低碼的糾錯能力t的前提下使簽名時間較CFS有較大的縮短。同時該算法的安全性與CFS算法保持相同，是一種更實用的基于編碼的簽名算法。

[1] Overbeck R, Sendrier N. Code-based cryptography[C]//Bernstein D J, Buchmann J. Post-quantum cryptography. Berlin Heidelberg: Springer, 2009: 95-145.

[2] 鄭東, 趙慶蘭, 張應(yīng)輝. 密碼學綜述[J]. 西安郵電大學學報, 2013, 18(6): 1-10.

[3] McEliece R J. A public-key cryptosystem based on algebraic coding theory[J]. DSN Progress Report, 1978, 42(44): 114-116.

[4] Engelbert D, Overbeck R, Schmidt A. A Summary of McEliece-Type Cryptosystems and their Security[J]. Journal of Mathematical Cryptology, 2007, 1(2): 1-51.

[5] Berlekamp E R, McEliece R J, van Tilborg H C A. On the inherent intractability of certain coding problems[J]. IEEE Transactions on Information Theory, 1978, 24(3): 384-386.

[6] Niederreiter H. Knapsack-type cryptosystems and algebraic coding theory[J]. Problems of Control and Information Theory, 1986, 15(2): 159-166.

[7] Courtois N T, Finiasz M, Sendrier N. How to achieve a McEliece-based digital signature scheme[C]//Boyd C. Advances in Cryptology-ASIACRYPT 2001. Berlin Heidelberg: Springer, 2001: 157-174.

[8] Preetha M K, Sachin V, Pandu R C. On Provably Secure Code-based Signature and Signcryption Scheme[EB/OL]. (2013-07-29)[2014-11-11]. http://eprint.iacr.org/2012/585.

[9] Cayrel P L, Véron P. Improved code-based identification scheme[EB/OL]. (2010-01-18)[2014-10-10]. http://arxiv.org/pdf/1001.3017v1.pdf.

[10] Augot D, Finiasz M, Sendrier N. A family of fast syndrome based cryptographic hash functions[C]//Dawson E, Vaudenay S. Progress in Cryptology-Mycrypt 2005. Berlin Heidelberg: Springer, 2005: 64-83.

[11] Gaborit P, Lauradoux C, Sendrier N. SYND : a fast code-based stream cipher with a security reduction[C]//IEEE International Symposium on Information Theory. France Nice: IEEE Information Theory Society, 2007: 186-190.

[12] Finiasz M, Sendrier N. Security bounds for the design of code-based cryptosystems[C]//Matsui M. Advances in Cryptology-ASIACRYPT 2009. Berlin Heidelberg: Springer, 2009: 88-105.

[13] Dallot L. Towards a concrete security proof of Courtois, Finiasz and Sendrier signature scheme[C]//Lucks S, Sadeghi A-R, Wolf C. Research in Cryptology. Berlin Heidelberg: Springer, 2008: 65-77.

[14] Finiasz M. Parallel-CFS[C]//Biryukov A, Gong G, Stinson D R. Selected areas in cryptography. Berlin Heidelberg: Springer, 2011: 159-170.

[15] Zheng Dong, Li Xiangxue, Chen Kefei. Code-based Ring Signature Scheme[J]. International Journal of Network Security, 2007, 5(2): 154-157.

[16] Melchor C A, Cayrel P, Gaborit P, et al. A new efficient threshold ring signature scheme based on coding theory[J]. IEEE Transactions on Information Theory, 2011, 57(7): 4833-4842.

[17] Overbeck R. A Step Towards QC Blind Signatures[EB/OL]. (2009-03-02)[2014-10-30]. http://eprint.iacr.org/2009/102.

[責任編輯:瑞金]

《西安郵電大學學報》版權(quán)聲明

為適應(yīng)我國信息化建設(shè)的需要，擴大刊物影響，拓寬信息交流渠道，本刊已加入“中國知網(wǎng)CNKI系列期刊數(shù)據(jù)庫”、“中國核心期刊(遴選)數(shù)據(jù)庫”(萬方數(shù)據(jù)——數(shù)字化期刊群)、“中國期刊網(wǎng)”等數(shù)據(jù)庫。本刊已許可以上數(shù)據(jù)庫以數(shù)字化方式復(fù)制、匯編、發(fā)行、信息網(wǎng)絡(luò)傳播本刊所載文章的全文信息。稿件一經(jīng)刊登，將在本刊稿酬中一次性支付著作權(quán)使用報酬(包括印刷版、光盤版和網(wǎng)絡(luò)版等各種使用方式的報酬)。作者向本刊提交文章的行為即視為同意我刊上述聲明。

西安郵電大學學報編輯部

An improved code based digital signature algorithm

REN Fang1,2, ZHENG Dong2

(1. School of Communication and Information Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710121, China；2. National Engineering Laboratory for Wireless Security, Xi’an University of Posts and Telecommunications, Xi’an 710121, China)

In order to solve the problem of inefficiency of CFS algorithm, an improved code based digital signature algorithm is proposed by using code based Hash function. The output of this Hash function is a syndrome of a regular word which weight is no more than error correcting capacity of the code. The substitute of this function for the random Hash function makes the decoding algorithm execute only once in signing phase and avoid the time-consuming syndrome decoding attempt. The signing time of the improved algorithm can reduce t! times than CFS algorithm and the efficiency can get rid of the restriction from error correcting capacity. Furthermore, the securities of these two algorithms depend on the equivalent NP complete problems.

digital signature, code, syndrome, Hash function, quantum attack

10.13682/j.issn.2095-6533.2015.04.008

2014-12-12

國家自然科學基金資助項目(61272037，61472472)；陜西省自然科學基金重點資助項目(2013JZ020)；陜西省自然科學基金資助項目(2015JQ6262)；陜西省教育廳專項科研計劃資助項目(2013JK1097);西安郵電大學青年基金資助項目(ZL2013-06)

任方(1981-)，男，博士，講師，從事密碼學與網(wǎng)絡(luò)安全研究。E-mail:renfang_81@163.com 鄭東(1964-)，男，博士，教授，博導(dǎo)，從事密碼學與云計算安全研究。E-mail:zhengdong@xupt.edu.cn

TN918.3

A

2095-6533(2015)04-0038-06