基于雙難題的數(shù)字簽密方案研究

周 克 元

(宿遷學(xué)院文理學(xué)院 江蘇 宿遷 223800)

基于雙難題的數(shù)字簽密方案研究

周 克 元

(宿遷學(xué)院文理學(xué)院 江蘇 宿遷 223800)

針對基于離散對數(shù)和因子分解雙難題設(shè)計數(shù)字簽密方案的問題，給出了一個使用Hash函數(shù)的簽密方案。針對Hash函數(shù)存在被攻擊的危險，給出了一個不使用Hash函數(shù)的簽密方案。兩個方案均具有抗偽造簽名攻擊、前向安全性和公開驗證性。通過安全性分析和復(fù)雜度分析，與各類數(shù)字簽密方案比較，復(fù)雜度更低。

離散對數(shù) 因子分解 數(shù)字簽密 Hash函數(shù)

0 引 言

數(shù)字簽名技術(shù)是實現(xiàn)網(wǎng)絡(luò)身份認(rèn)證、 數(shù)據(jù)完整性保護(hù)和非否認(rèn)服務(wù)的基礎(chǔ)， 是電子商務(wù)、電子政務(wù)等的重要工具，是密碼學(xué)的研究熱點之一。數(shù)字簽名方案在使用過程中要經(jīng)過簽名和加密兩個階段。數(shù)字簽密由Zheng[1]最早提出，數(shù)字簽密技術(shù)能夠在一個合理的邏輯步驟時間內(nèi)，同時完成數(shù)字簽名和公鑰加密功能，并且復(fù)雜度和計算量要低于傳統(tǒng)的先簽名后加密，是同時實現(xiàn)保密和認(rèn)證的傳輸消息的比較理想的方法[2]。

數(shù)字簽密技術(shù)依賴的數(shù)學(xué)難題主要有離散對數(shù)、因子分解和橢圓曲線離散對數(shù)數(shù)學(xué)難題，目前數(shù)字簽密方案大部分是基于單數(shù)學(xué)難題，如文獻(xiàn)[1-10]中方案。對于基于單數(shù)學(xué)難題的簽密方案，若該難題可解則簽密方案不再安全。利用雙數(shù)學(xué)難題設(shè)計數(shù)字簽名方案沒被攻擊的目前有文獻(xiàn)[11-12]中方案，雙難題簽名方案的實現(xiàn)還需結(jié)合加解密算法先簽名后加密使用，復(fù)雜度較高。故尋找基于雙難題的數(shù)字簽密方案成為新的研究方向，目前對于該方向的研究成果較少，還沒有相關(guān)算法方案。本文給出一個基于離散對數(shù)因子分解雙難題的數(shù)字簽密方案，方案中使用Hash函數(shù)，進(jìn)行了安全性分析和復(fù)雜度分析。

Hash函數(shù)主要算法有MD5和SHA-1，王小云等[13-15]先后提出了MD5和SHA-1算法的雜湊碰撞，使得使用了Hash函數(shù)MD5和SHA-1的相關(guān)密碼算法不再安全。關(guān)于使用Hash函數(shù)和冗余函數(shù)帶來的威脅亦可見文獻(xiàn)[17-18]，故第二類研究方向是設(shè)計不使用Hash或冗余函數(shù)的數(shù)字簽密方案。目前已有的基于離散對數(shù)不使用Hash函數(shù)的簽密方案主要有文獻(xiàn)[19-22]中方案，對于基于雙難題設(shè)計簽密的方案較少，本文給出一個基于雙難題同時不使用Hash函數(shù)和冗余函數(shù)的簽密方案，進(jìn)行了安全性分析和復(fù)雜度分析。

雙難題相關(guān)理論如下：

引理1[16]大素數(shù)p，n=p1q1，n|(p-1)，其中p1、q1為大素數(shù)。g∈GF(p)，且g的階為n，設(shè)由元素g生成的乘法群為G。對于?y∈G，同余方程y=gx2modp的求解等價于離散對數(shù)方程y=gumodp的求解和二次同余方程x2=umodn的求解，而二次同余方程x2=umodn的求解等價于對整數(shù)n進(jìn)行因子的分解運算。

1 基于雙難題使用Hash函數(shù)的簽密方案(方案1)

1.1 參 數(shù)

1.2 簽 密

1.3 解簽密

1.4 正確性證明

2 安全性證明

2.1 對抗公鑰求解私鑰的攻擊

攻擊者從同余方程ya=gxa 2modp中求解私鑰xa，由引理1知，其數(shù)學(xué)難度相當(dāng)于求解因子分解問題和求解離散對數(shù)問題。

在上述三個回歸方程中，我們并不能排除誤差項與解釋變量之間的內(nèi)生性問題。但如果這些無法觀測到的因素不隨時間變化，那么這些面板數(shù)據(jù)的固定效應(yīng)將會是一致的。表3依次做了三個模型中固定效應(yīng)和隨機效應(yīng)的Hausman檢驗，以確定使用具有隨機效應(yīng)還是固定效應(yīng)的面板模型。豪斯曼檢驗結(jié)果是強烈拒絕原假設(shè)（詳見表3中 Hausman test欄）。因此，我們認(rèn)為本文使用具有固定效應(yīng)的面板計量模型是恰當(dāng)?shù)摹?/p>

2.2 對抗簽密方程求出密鑰的攻擊

2.3 對抗離散對數(shù)問題可計算的攻擊

2.4 對抗因子分解可計算的攻擊

2.5 前向安全性分析

2.6 公開驗證性分析

3 復(fù)雜度分析

使用Hash函數(shù)的基于離散對數(shù)單難題數(shù)字簽密最新的方案是Li方案[5]，基于離散對數(shù)銀子分解雙難題數(shù)字簽名最新的方案是Zhou方案[11]，將本文方案1與上述兩種方案進(jìn)行復(fù)雜度比較。結(jié)果見表1。

表1 復(fù)雜度比較

本文方案1運算復(fù)雜度比Li方案少2次模指數(shù)運算，與Zhou方案相同，簽密長度相同，但Zhou方案簽名需加密后再發(fā)送，本文方案1不需加密直接發(fā)送，故運算復(fù)雜度本文方案1更低。注：點積運算和Hash函數(shù)運算計算量較小，相對于模指數(shù)和模逆可忽略不計。

4 基于雙難題無Hash函數(shù)的簽密方案(方案2)

4.1 參 數(shù)

4.2 簽 密

4.3 解簽密

4.4 正確性證明

方案正確性證明如下:

所以

則該方案的驗證過程是正確的。

5 安全性分析

5.1 對抗公鑰求解私鑰的攻擊

攻擊者從方程ya=gxa 2modp中求解私鑰xa，由引理1可知，其數(shù)學(xué)難度相當(dāng)于求解因子分解問題和求解離散對數(shù)問題。

5.2 對抗簽密方程求出密鑰的攻擊

5.3 對抗離散對數(shù)問題可計算的攻擊

5.4 對抗因子分解可計算的攻擊

5.5 前向安全性分析

可類似于2.5節(jié)中相關(guān)證明證明方案2的前向安全性方法。

5.6 公開驗證性分析

6 復(fù)雜度分析

基于離散對數(shù)單難題不使用Hash函數(shù)和冗余函數(shù)的數(shù)字簽密方案最新的是Li方案[22]，基于離散對數(shù)因子分解雙難題使用Hash函數(shù)的數(shù)字簽密方案最新的是本文方案1，將本文方案2與上述兩種方案進(jìn)行復(fù)雜度比較。結(jié)果見表2。

表2 復(fù)雜度比較

本文方案2與Li方案[22]相比，減少3次模指數(shù)運算，與本文方案1相比運算復(fù)雜度相同，簽密長度與前兩者簽密長度均相同。注：其中的點積和Hash函數(shù)運算相對于模指數(shù)和模逆運算量較少，可忽略不計。

7 結(jié) 語

與先簽名后加密相比，簽密的最大的優(yōu)勢在于減少了計算量和通信量，適合大量數(shù)據(jù)的認(rèn)證傳遞[1,3]。本文對基于身份的雙難題數(shù)字簽密進(jìn)行了研究，對使用Hash函數(shù)和不使用Hash函數(shù)分別給出了一個簽密方案，進(jìn)行了正確性和安全性證明，并進(jìn)行了復(fù)雜度分析，安全性與復(fù)雜度比已有的方案均更優(yōu)。

[1] Zheng Y L.Digital signcryption or how to achieve cost (signature and encryption)[C]//Advances in Cryptography,Proceedings of CRYPTO’97,LNCS1294.London,UK:Springer-Verlag,1997:165-179.

[2] 李發(fā)根,胡予濮,李剛.一個高效的基于身份的簽密方案[J].計算機學(xué)報,2006,29(9):1641-1647.

[3] Zheng Y L.Signcryption and Its Applications in Efficient Public Key Solution[C]//Berlin:Proceedings of Information Security Workshop(ISW’97),LNCS1397,Springer-Verlag 1998:291-312.

[4] Lee M K,Dong K K.An authenticated encryption scheme with public verifiability[C]//Proc of Japan Korea Joint Workshop on Algorithms and Computation. Tokyo[sn],2000:49-56.

[5] 李艷平,譚示崇,王育民.一個公開可驗證和前向安全的簽密方案[J].計算機應(yīng)用研究,2006,23(9):98-99.

[6] 張串絨,肖國鎮(zhèn).一個可公開驗證簽密方案的密碼分析和改進(jìn)[J].電子學(xué)報,2006,34(1):177-179.

[7] 喻琇瑛,賴欣,何大可.一個可公開驗證且前向安全的簽密方案[J].計算機應(yīng)用研究,2009,26(1):359-260.

[8] 張建航,胡予璞,齊新社.具有前向安全性和公開可驗證性的簽密方案[J].計算機應(yīng)用研究,2011,28(2):733-734.

[9] 王天芹.一個基于橢圓曲線的可證明安全簽密方案[J].計算機應(yīng)用研究,2010,27(3):1055-1057.

[10] 于剛,黃根勛,王旭,等.基于橢圓曲線的可公開驗證和前向安全的簽密方案[J].信息工程大學(xué)學(xué)報,2008,9(3):21-23.

[11] 周克元.一個新的基于離散對數(shù)和因子分解的數(shù)字簽名[J].科學(xué)技術(shù)與工程,2013,13(26):7862-7864.

[12] 周克元.基于橢圓曲線和因子分解雙難題的數(shù)字簽名方案[J].計算機科學(xué),2014,41(6A):366-368.

[13] Wang X,Lai X,Feng D,et al.Cryptanalysis of the hash functions MD4 and RIPEMD[C]//International Conference on Theory and Applications of Cryptographic Techniques.Springer-Verlag,2005:1-18.

[14] Wang X,Yu H.How to break MD5 and other hash functions[C]//International Conference on Theory and Applications of Cryptographic Techniques.Springer-Verlag,2005:19-35.

[15] Wang X,Yin Y L,Yu H.Finding Collisions in the Full SHA-1[C]//International Conference on Advances in Cryptology.Springer-Verlag,2005:17-36.

[16] 邵祖華.基于因數(shù)分解和離散對數(shù)的數(shù)字簽名協(xié)議[J].信息安全與通信保密,1998(4):36-41.

[17] Chien H Y.Forgery attacks on multi-signature schemes for au-thenticating mobile code delegates[J].IEEE Transactions on Ve-hicular Technology,2002,51(6):1669-1671.

[18] Dobbertin H.The status of MD5 after a recent attack[J].CryptoBytes,1996,2(2):1-6.

[19] Lee W,Chang C.Authenticated encryption scheme without using a one-way function[J].Electronics Letters,1995,31(19):1656-1657.

[20] Chen K.Signature with message recovery[J].Electronics Letters,1998,34(20):1934.

[21] 于永,綦朝暉.一種基于前向安全的可公開驗證簽密方案[J].計算機應(yīng)用與軟件,2010,27(1):283-285.

[22] 李方偉,閆少軍,萬麗.新的不使用冗余和Hash的安全認(rèn)證加密方案[J].計算機工程與應(yīng)用,2011,47(28):86-88.

ANALYSISONDIGITALSIGNCRYPTIONSCHEMEBASEDONDISCRETELOGARITHMSANDFACTORING

Zhou Keyuan

(SchoolofLiberalArtsandScience,SuqianCollege,Suqian223800,Jiangsu,China)

The problem of designing digital signcryption scheme based on discrete logarithm and factoring is discussed, and a signcryption scheme using Hash function is given. In addition, a signcryption scheme that does not use Hash function is given in view of the danger of Hash function being attacked. Two schemes have the characteristics of unforgeability, forward security and public verifiability. Security analysis and complexity analysis show that the complexity of the scheme is lower than that of various digital signcryption schemes.

Discrete logarithm Factorization Digital signcryption Hash function

TP309.7

A

10.3969/j.issn.1000-386x.2017.10.056

2016-12-27。宿遷市科研項目(Z201450)。周克元，講師，主研領(lǐng)域：密碼與編碼。