周 克 元

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

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

周 克 元

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

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

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

0 引 言

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

數(shù)字簽密技術(shù)依賴的數(shù)學(xué)難題主要有離散對(duì)數(shù)、因子分解和橢圓曲線離散對(duì)數(shù)數(shù)學(xué)難題，目前數(shù)字簽密方案大部分是基于單數(shù)學(xué)難題，如文獻(xiàn)[1-10]中方案。對(duì)于基于單數(shù)學(xué)難題的簽密方案，若該難題可解則簽密方案不再安全。利用雙數(shù)學(xué)難題設(shè)計(jì)數(shù)字簽名方案沒(méi)被攻擊的目前有文獻(xiàn)[11-12]中方案，雙難題簽名方案的實(shí)現(xiàn)還需結(jié)合加解密算法先簽名后加密使用，復(fù)雜度較高。故尋找基于雙難題的數(shù)字簽密方案成為新的研究方向，目前對(duì)于該方向的研究成果較少，還沒(méi)有相關(guān)算法方案。本文給出一個(gè)基于離散對(duì)數(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ù)帶來(lái)的威脅亦可見(jiàn)文獻(xiàn)[17-18]，故第二類研究方向是設(shè)計(jì)不使用Hash或冗余函數(shù)的數(shù)字簽密方案。目前已有的基于離散對(duì)數(shù)不使用Hash函數(shù)的簽密方案主要有文獻(xiàn)[19-22]中方案，對(duì)于基于雙難題設(shè)計(jì)簽密的方案較少，本文給出一個(gè)基于雙難題同時(shí)不使用Hash函數(shù)和冗余函數(shù)的簽密方案，進(jìn)行了安全性分析和復(fù)雜度分析。

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

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

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

1.1 參 數(shù)

1.2 簽 密

1.3 解簽密

1.4 正確性證明

2 安全性證明

2.1 對(duì)抗公鑰求解私鑰的攻擊

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

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

2.2 對(duì)抗簽密方程求出密鑰的攻擊

2.3 對(duì)抗離散對(duì)數(shù)問(wèn)題可計(jì)算的攻擊

2.4 對(duì)抗因子分解可計(jì)算的攻擊

2.5 前向安全性分析

2.6 公開(kāi)驗(yàn)證性分析

3 復(fù)雜度分析

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

表1 復(fù)雜度比較

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

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

4.1 參 數(shù)

4.2 簽 密

4.3 解簽密

4.4 正確性證明

方案正確性證明如下:

所以

則該方案的驗(yàn)證過(guò)程是正確的。

5 安全性分析

5.1 對(duì)抗公鑰求解私鑰的攻擊

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

5.2 對(duì)抗簽密方程求出密鑰的攻擊

5.3 對(duì)抗離散對(duì)數(shù)問(wèn)題可計(jì)算的攻擊

5.4 對(duì)抗因子分解可計(jì)算的攻擊

5.5 前向安全性分析

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

5.6 公開(kāi)驗(yàn)證性分析

6 復(fù)雜度分析

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

表2 復(fù)雜度比較

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

7 結(jié) 語(yǔ)

與先簽名后加密相比，簽密的最大的優(yōu)勢(shì)在于減少了計(jì)算量和通信量，適合大量數(shù)據(jù)的認(rèn)證傳遞[1,3]。本文對(duì)基于身份的雙難題數(shù)字簽密進(jìn)行了研究，對(duì)使用Hash函數(shù)和不使用Hash函數(shù)分別給出了一個(gè)簽密方案，進(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ā)根,胡予濮,李剛.一個(gè)高效的基于身份的簽密方案[J].計(jì)算機(jī)學(xué)報(bào),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] 李艷平,譚示崇,王育民.一個(gè)公開(kāi)可驗(yàn)證和前向安全的簽密方案[J].計(jì)算機(jī)應(yīng)用研究,2006,23(9):98-99.

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

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

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

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

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

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

[12] 周克元.基于橢圓曲線和因子分解雙難題的數(shù)字簽名方案[J].計(jì)算機(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ù)分解和離散對(duì)數(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] 于永,綦朝暉.一種基于前向安全的可公開(kāi)驗(yàn)證簽密方案[J].計(jì)算機(jī)應(yīng)用與軟件,2010,27(1):283-285.

[22] 李方偉,閆少軍,萬(wàn)麗.新的不使用冗余和Hash的安全認(rèn)證加密方案[J].計(jì)算機(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。宿遷市科研項(xiàng)目(Z201450)。周克元，講師，主研領(lǐng)域：密碼與編碼。