基于NTRU公鑰體制的密鑰交換協(xié)議

1、基于NTRU公鑰體制的密鑰交換協(xié)議胡新祥 褚映紅 胡予濮基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(60273084)作者簡(jiǎn)介：胡新祥(1980-)，男，西安電子科技大學(xué)碩士研究生，研究方向?yàn)镹TRU的安全性分析褚映紅(1979-)，女，西安電子科技大學(xué)碩士研究生，研究方向?yàn)镹TRUSign的安全性分析胡予濮(1955-)，男，西安電子科技大學(xué)教授，博士生導(dǎo)師，主要研究方向?yàn)槊艽a學(xué)和信息安全(西安電子科技大學(xué) 計(jì)算機(jī)網(wǎng)絡(luò)與信息安全教育部重點(diǎn)實(shí)驗(yàn)室 107信箱 西安 710071)摘要：低效率是現(xiàn)有的基于離散對(duì)數(shù)的Diffie-Hellman密鑰交換協(xié)議不可避免的一個(gè)重要缺陷。如何提高協(xié)議的運(yùn)行效率是一

2、個(gè)倍受關(guān)注的問(wèn)題。本文首次提出了基于NTRU公鑰體制的密鑰交換協(xié)議，由于NTRU體制良好的密碼特性，該協(xié)議與現(xiàn)有的基于離散對(duì)數(shù)的Diffie-Hellman協(xié)議相比，效率有了明顯的提高。關(guān)鍵字：NTRU；公鑰；協(xié)議中圖號(hào) TN918.1Key Exchange Protocol based on the NTRU Public-Key CryptosystemHU Xin-xiang CHU Ying-hong HU Yu-pu (Key Laboratory of Computer Networks & Information Security, Ministry of Educat

3、ion Xidian University, Xian 710071, China)Abstract: Diffie-Hellman key exchange protocol available based on the discrete logarithm problem is low in efficiency, which is a great inevitable drawback. Thus much attention has been paid to obtaining the protocol that can achieve high operational efficie

4、ncy. In this paper we firstly present a key exchange protocol based on the NTRU public-key cryptosystem. The protocol has the advantages over those available of high efficiency due to the favorable property of the NTRU cryptosystem.Key words: NTRU; public-key; protocol1. 引言NTRU公鑰體制1是由Hoffstein，Piphe

5、r和Silverman于1996年首先提出的，由于該公鑰體制只使用了簡(jiǎn)單的模乘法和模求逆運(yùn)算，因此它的加解密速度很快，密鑰生成速度也很快，是目前為止已知的最快的公鑰密碼體制。由于其良好的密碼性質(zhì)，NTRU已引起了眾多密碼學(xué)家的關(guān)注，與此同時(shí)基于NTRU體制的數(shù)字簽名NTRUSign2,3也于2003年提出。Diffie-Hellman密鑰交換協(xié)議是Diffie和Hellman在1976年提出的，它是第一個(gè)公開(kāi)發(fā)表的公開(kāi)密鑰密碼算法，其安全性基于Zp上的離散對(duì)數(shù)問(wèn)題。雖然Diffie-Hellman協(xié)議安全性得到了解決，但是由于用到了指數(shù)運(yùn)算，所以它的效率并不高。此后出現(xiàn)的基于橢圓曲線和XTR4

6、公鑰體制的密鑰交換協(xié)議都未能避免這一缺陷。本文首次提出了基于NTRU公鑰體制的密鑰交換協(xié)議，由于NTRU體制良好的密碼特性(加解密速度快，密鑰生成速度快)，本文的密鑰交換協(xié)議與傳統(tǒng)的協(xié)議相比，效率有了明顯的提高。2. NTRU公鑰體制系統(tǒng)公開(kāi)參數(shù)：(N, p, q)，其中N為一大素?cái)?shù)，p為一小的奇素?cái)?shù)，且(p, q)=1，q遠(yuǎn)大于p。在加解密過(guò)程中將用到三個(gè)模運(yùn)算(mod p)，(mod q)和(mod xN-1)。(mod q)的結(jié)果將限制在上，而不是上。(mod p)的結(jié)果將限制在上，而不是上。GF(p)上的元素也是限制在上。密鑰生成：Bob任意選取兩個(gè)次數(shù)不超過(guò)N-1的多項(xiàng)式f(x)和g

7、(x)，其中多項(xiàng)式的系數(shù)取至集合0,+1,-1。驗(yàn)證f(x)和g(x)關(guān)于(mod p, mod xN-1)和(mod q, mod xN-1)是否可逆，如果不可逆，重新選取f(x)和g(x)。計(jì)算h(x)=f(x)-1g(x) (mod q, mod xN-1)，則公鑰為h(x)，私鑰為(f(x),g(x)。加密：明文m(x)是系數(shù)為GF(p)上的次數(shù)不超過(guò)N-1次多項(xiàng)式。Alice任意選取一工作密鑰r(x)，其中r(x)是系數(shù)為GF(p)上的次數(shù)不超過(guò)N-1次多項(xiàng)式。Alice計(jì)算密文c(x)=m(x)+pr(x)h(x) (mod q, mod xN-1)。解密：Bob計(jì)算d(x)=f(

8、x)c(x) (mod q, mod xN-1)=f(x)m(x)+pr(x)g(x) (mod q, mod xN-1)。注意到f(x)、m(x)、r(x)和g(x)的系數(shù)都很小，所以多項(xiàng)式f(x)m(x)+pr(x)g(x) (mod xN-1)的系數(shù)以很大概率在區(qū)間，即d(x) = f(x)m(x)+pr(x)g(x) (mod xN-1)。Bob繼續(xù)計(jì)算d(x)f(x)-1 (mod p, mod xN-1)=f(x)f(x)-1m(x) (mod p, mod xN-1)=m(x)。最后，我們指出當(dāng)多項(xiàng)式f(x)m(x)+pr(x)g(x) (mod xN-1)的系數(shù)有一個(gè)不在區(qū)間時(shí)

9、，解密會(huì)出現(xiàn)失敗的情況。NTRU的作者已經(jīng)分析了解密失敗的概率非常的?。∟251時(shí)，失敗的概率小于2-80，當(dāng)N變大時(shí)還可以使得概率更?。?。3. 基于NTRU公鑰體制的密鑰交換協(xié)議3.1 協(xié)議描述系統(tǒng)公開(kāi)參數(shù)：(N, p, q)(同上)在網(wǎng)絡(luò)環(huán)境中用戶A和用戶B要通信時(shí)，他們可以通過(guò)下列步驟協(xié)商通信時(shí)所使用的密鑰：Step 1：用戶A生成一對(duì)任意的私鑰公鑰對(duì)(f1(x),g1(x),h1(x)，并將公鑰h1(x)發(fā)送給用戶B；Step 2：用戶B生成一對(duì)任意的私鑰公鑰對(duì)(f2(x),g2(x),h2(x)，并將公鑰h2(x)發(fā)送給用戶A；Step 3：用戶A計(jì)算m1(x)=pg1(x)，t1(

10、x)=m1(x)+pf1(x)h2(x) (mod q, mod xN-1)，并且將t1(x)發(fā)送給用戶B；Step 4：用戶B計(jì)算m2(x)=pg2(x)，t2(x)=m2(x)+pf2(x)h1(x) (mod q, mod xN-1)，并且將t2(x)發(fā)送給用戶A；Step 5：用戶A計(jì)算K=t2(x)f1(x) (mod q, mod xN-1)；Step 6：用戶B計(jì)算=t1(x)f2(x) (mod q, mod xN-1)。由于有：K=t2(x)f1(x)(mod q, mod xN-1)=(pg2(x) +pf2(x)h1(x)f1(x) (mod q, mod xN-1)=p

11、f1(x)g2(x)+pf2(x)g1(x) (mod q, mod xN-1)；=t1(x)f2(x) (mod q, mod xN-1)=(pg1(x)+pf1(x)h2(x)f2(x) (mod q, mod xN-1)=pf2(x)g1(x)+pf1(x)g2(x) (mod q, mod xN-1)；所以有K=。這樣，通信雙方A與B得到共同的密鑰K()。3.2 協(xié)議分析對(duì)于以上協(xié)議，我們指出以下幾點(diǎn)：第一、 易于看出該協(xié)議的安全性與NTRU一致的。第二、 如果敵手竊聽(tīng)到了信道上的消息t1(x)和t2(x)，由于f1(x)和f2(x)是用戶在通信時(shí)各自產(chǎn)生的臨時(shí)私鑰，敵手并不知道，所以

12、他并不能由t1(x)和t2(x)得到K。第三、 假定敵手竊聽(tīng)到了t1(x)，由于t1(x)為pg1(x)的密文，即便他通過(guò)對(duì)NTRU體制的攻擊，也僅僅得到m1(x)(mod p)=pg1(x)(mod p)=0，這對(duì)于最終的協(xié)商密鑰K并沒(méi)有任何幫助。第四、 由于NTRU體制利用的是多項(xiàng)式的加法和乘法，所以本文的密鑰交換協(xié)議與現(xiàn)有的基于離散對(duì)數(shù)的Diffie-Hellman協(xié)議相比，在同樣的安全性下效率更高。4. 總結(jié)本文首次提出了基于NTRU公鑰體制的密鑰交換協(xié)議，與傳統(tǒng)的基于離散對(duì)數(shù)的Diffie-Hellman協(xié)議相比的一個(gè)明顯的優(yōu)點(diǎn)就是，效率更高。參考文獻(xiàn)1 J. Hoffstein,

13、J. Pipher, and J.H. Silverman. NTRU :a Ring based Public Key CryptosystemAC. In Proc of ANTS III ,LNCS 1423, pages 267-288. Springer-Verlag, 1998. First presented at the rump session of Crypto 96.2 J. Hoffstein, N. Graham, J. Pipher, J. Silverman and W. Whyte, NTRUsign: digital Signatures Using the NTRU LatticeJ, CT-RSA03, LNCS, vol.2612, Springer-Verlag, pp.122-140, 2003.3 J. Hoffstein, N. Graham, J. Pipher, J. Silverman, and W. Whyte, NTRUsig