基于格的數(shù)字簽名方案研究與設(shè)計(jì)

顧晶晶　儲(chǔ)逸　崔洛賓　卞歡陸　蔡秋茹

【摘 要】NTRU 是一種公鑰密碼體制，由于其效率高、快速、運(yùn)算方便、可抵抗量子計(jì)算，因此取得了廣泛的應(yīng)用，密碼學(xué)界廣泛認(rèn)為其安全性基于理想格中最近向量的困難問(wèn)題，本文將介紹一種基于格上難題（最短向量NP問(wèn)題）的NTRU型數(shù)字簽名方案的密鑰生成，加密算法，解密算法的具體實(shí)現(xiàn)過(guò)程。

【關(guān)鍵詞】格；NTRU；數(shù)字簽名；格上最短向量問(wèn)題

中圖分類(lèi)號(hào)： TN918.1；O153.1 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 2095-2457（2018）06-0013-002

【Abstract】NTRU is a public key cryptosystem.Because it is efficient，fast，easy to operate，and resistant to quantum computation，it has been widely used.The cryptography community widely believes that its security is based on the difficulty of the nearest vector in the ideal lattice.This article will introduce a specific implementation process of key generation，encryption algorithm，and decryption algorithm based on the NTRU type digital signature scheme based on the lattice problem （shortest vector NP problem）.

【Key words】Lattice；NTRU；Digital signature；Lattice shortest vector problem

0 引言

NTRU公鑰密碼被認(rèn)為是可以抵抗量子計(jì)算機(jī)攻擊，因其密鑰量小、加解密效率高、安全性好的特點(diǎn)，在公鑰密碼學(xué)中一直是一個(gè)研究的熱點(diǎn)[1]，并于2009年被納入IEEE P1363.1標(biāo)準(zhǔn)[2]。在數(shù)字簽名上，?；诟裆想y題問(wèn)題（最短向量問(wèn)題SVP、最近向量問(wèn)題CVP等），但是由于設(shè)計(jì)者[3]采用了附加的結(jié)構(gòu)來(lái)完成簽名構(gòu)造，而正因這些附加結(jié)構(gòu)的引入，使得簽名和其理論基礎(chǔ)之間出現(xiàn)了不完整和模糊關(guān)系，致使基于NTRU的數(shù)字簽名方案仍有缺陷（簽名值會(huì)泄露私鑰部分信息），例如：R-NSS和NTRU Sign都已經(jīng)被證實(shí)不安全[4]。

針對(duì)這些問(wèn)題，本文將介紹一種新的基于格中最短向量難題的數(shù)字簽名方案，方案通過(guò)NTRU格中已知短向量尋找另一組短向量，從而構(gòu)造一個(gè)完整的短格基，同時(shí)還添加了消息擾動(dòng)結(jié)構(gòu)，用于提升已有攻擊方案破解數(shù)字簽名的難度，因此具有更好的抗攻擊能力。

本文結(jié)構(gòu)如下：第一部分為引言部分，第二部分介紹相關(guān)數(shù)學(xué)概念和定理[5，6]。第三部分介紹具體數(shù)字簽名、密鑰生成，加密算法，解密算法的具體實(shí)現(xiàn)過(guò)程。第四部分介紹對(duì)安全性的分析。

1 預(yù)備知識(shí)

1.1 多項(xiàng)式環(huán)與多項(xiàng)式的逆

NTRU是建立在整數(shù)環(huán)Z[x]/（XN-1）上面的密碼體制，令Z為整數(shù)環(huán)，設(shè)P為整數(shù)多項(xiàng)式上的商環(huán)Z[x]/（XN-1），則P可用集合Z[x]/（xN-1）來(lái)表示，即P上每一個(gè)元素都可以表示為■，令a，b？綴P，a+b定義為兩個(gè)多項(xiàng)式對(duì)應(yīng)的系數(shù)相加，P上的兩個(gè)元素的乘用*表示，令c=a*b，則c的第k個(gè)系數(shù)為：

3 安全性分析

3.1 簽名方案的依難題據(jù)：

由于該方案是建立在格CVP難題上，用私鑰構(gòu)造出格中短循環(huán)基，由于私鑰生成格中短向量，因此為嚴(yán)格的格中CVP問(wèn)題，具有可靠的安全性。

3.2 GCD攻擊的可能：

若攻擊者用GCD攻擊獲得f。對(duì)于NSS簽名，由于NSS中有一個(gè)mod p的條件，從而攻擊者進(jìn)行歸納，將mod q的f*wmodq和g*wmodq值提升到R（實(shí)數(shù)域）上，得到?jīng)]有模的f*w和g*w的值，通過(guò)公因子方式得到：導(dǎo)致攻擊成功，但是本文中的方案，要構(gòu)造：

由于只有一個(gè)modq使得簽名復(fù)雜度O（N2）程度形式上升。

3.3 副本攻擊偽造簽名：

NTRU類(lèi)數(shù)字簽名會(huì)泄露一定信息，若收集其副本，通過(guò)大量的副本會(huì)導(dǎo)致信息泄露，因此在該數(shù)字簽名方案中對(duì)消息引入了擾動(dòng)。

由于擾動(dòng)的引入使得矩陣信息泄露的數(shù)量成指數(shù)形式遞減，從而本方案對(duì)副本攻擊是安全有效的。

4 結(jié)束語(yǔ)

本文對(duì)當(dāng)前基于格的數(shù)字簽名方案進(jìn)行了研究，對(duì)算法進(jìn)行改進(jìn)，基于循環(huán)格基，建立在嚴(yán)格的CVP問(wèn)題之上，避免了NSS、NTRUSign中的線(xiàn)性構(gòu)造關(guān)系，同時(shí)加入了擾動(dòng)，保證了方案的安全性，同時(shí)具有良好的時(shí)效性并且便于實(shí)現(xiàn)。

【參考文獻(xiàn)】

[1]Borrows M，Abadi M，Needham R M.A logic of authentication[J].ACM Transactions on Computer Systems，8（1）：18-36，1990.

[2]古春生.NTRU公鑰密碼的可視化教學(xué).江蘇理工學(xué)院學(xué)報(bào)，2014，20（4）：90-92.

[3]GoldreichO.GoldwasserS.Halevy.Public-key cryptography from lattice reduction problems，1294（56）：112-131，1997.

[4]RivestR，ShamirA，Adleman L.A method for obtaining digital signatures and public-key cryptosystems[J].Communication of the ACM，21（2）：120 -126，1978.

[5]李筱熠.一種基于NTRU格的數(shù)字簽名.上海工程技術(shù)大學(xué)學(xué)報(bào)，23（1）：56-59，2009.

[6]潘彥豐.基于NTRU的數(shù)字簽名方案分析.計(jì)算機(jī)工程，2010，36（22）：145-146.

[7]Gentry C.JonssonJ.SternJ.Ctyptanalysis of the NTRU Signature Scheme（NSS），2248：1-20，2001.

[8]張卷美、曹杰等.一種基于NTRU新型數(shù)字簽名方案的設(shè)計(jì).四川大學(xué)學(xué)報(bào)，47（1）：49-53，2015.

[9]楊智超、付紹靜等.基于NTRU算法的新型廣播攻擊.密碼學(xué)報(bào)，36（22）：596-606，2016.

[10]張建航、胡予濮、來(lái)齊齊.基于高斯抽樣算法的NTRU類(lèi)數(shù)字簽名方案.計(jì)算機(jī)工程，38（17）：126-128，2012.

[11]畢經(jīng)國(guó).格理論在公鑰密碼分析和計(jì)算機(jī)代數(shù)中的應(yīng)用[D].山東：山東大學(xué)，2007.