鄭鑒學(xué) 張道法 徐松艷 宋蘇鳴

(北京遙測(cè)技術(shù)研究所 北京 100094)

如今,網(wǎng)絡(luò)通信已經(jīng)成為人們生活中交流通信的重要渠道.然而,在開放的網(wǎng)絡(luò)通信環(huán)境下信息很容易遭到攻擊者的攻擊.相較于對(duì)稱密碼,公鑰密碼可以在不安全的信道上傳輸加密的信息.然而公鑰密碼的加解密計(jì)算復(fù)雜,速度比對(duì)稱密碼加解密慢得多,所以加密大量的數(shù)據(jù)還需使用對(duì)稱密碼.因此公鑰密碼用于解決在開放網(wǎng)絡(luò)通信環(huán)境中建立雙方通信會(huì)話密鑰的安全性問(wèn)題.密鑰協(xié)商(key agreement, KA)就是在不安全的信道下讓2個(gè)或多個(gè)用戶計(jì)算共同的會(huì)話密鑰進(jìn)行安全通信.

1998年,Hoffstein 等人[1]提出了NTRU格的概念,設(shè)計(jì)了一個(gè)基于多項(xiàng)式環(huán)上的公鑰密碼體制,通常被稱為NTRU加密體制.隨后幾年,這種簽名、加密方案不斷出現(xiàn),但一直沒(méi)有提出可證明安全的方案,直到2008年,Lyubashevsky等人[2]、Gentry等人[3]先后提出了2個(gè)可證明安全性的格基數(shù)字簽名方案.因此,基于格基上的公鑰加密和數(shù)字簽名技術(shù)取得了巨大的進(jìn)步[4],然而基于格的KA(lattice-based KA, LBKA)協(xié)議目前仍然沒(méi)有很好的發(fā)展.

由于KA協(xié)議在不安全的網(wǎng)絡(luò)環(huán)境中運(yùn)行,因此,設(shè)計(jì)出能夠抵御各種攻擊的認(rèn)證KA協(xié)商協(xié)議就顯得尤為重要.目前,BR,mBR,CK,eCK,seCK[5-8]都是密鑰協(xié)商協(xié)議常用的安全模型,基于安全模型的密鑰協(xié)商方案也在不斷地發(fā)展[9-10].

在文獻(xiàn)[11]中,將dA=(fA+prAcB),dB=(fB+prBcA)作為協(xié)商雙方交互的信息,其中fA,fB分別為Alice和Bob的私鑰,屬于固定數(shù)據(jù).該方案并沒(méi)有對(duì)用戶的私鑰進(jìn)行偽隨機(jī)性保護(hù),這給敵手攻擊預(yù)留了方便.受此啟發(fā),本文對(duì)文獻(xiàn)[11]進(jìn)行改進(jìn),提出了2個(gè)基于NTRU格上的密鑰協(xié)商協(xié)議.方案1中,本文在雙方協(xié)商交互的過(guò)程中增加了2個(gè)隨機(jī)化因子(r1A,r2A)和(r1B,r2B),使得參與密鑰協(xié)商過(guò)程的發(fā)起方和響應(yīng)方每次生成的會(huì)話密鑰和協(xié)商的信息都不相同,保證了在密鑰協(xié)商中會(huì)話密鑰與隨機(jī)序列的不可區(qū)分性.方案2中,本文利用NTRU加密方法,把雙方隨機(jī)選取的多項(xiàng)式(r1A,r2A)和(r1B,r2B)進(jìn)行加密,得到dA=(r2A+pr1AcB)和dB=(r2B+pr1BcA)發(fā)送給對(duì)方,雙方收到dA和dB后再對(duì)消息用自己的私鑰進(jìn)行解密.該方案密鑰協(xié)商的過(guò)程中雙方交互的消息都不包含各自的秘密信息(私鑰),安全性完全依賴于NTRU加密方案的安全性,如果NTRU加密方案是安全的,那么該密鑰協(xié)商方案在基于格上最短向量計(jì)算困難性SVP假設(shè)下會(huì)話密鑰也同樣具有不可區(qū)分性和不可偽造性.

1 相關(guān)知識(shí)描述

本節(jié)將介紹后續(xù)需要用到的關(guān)于格和NTRU格的一些基本知識(shí),包括格的基本的定義、NTRU密碼體制的基本思想及其困難性.

1.1 NTRU算法描述

NTRU加密系統(tǒng)取決于3個(gè)整數(shù)參數(shù)(N,p,q)和4個(gè)階為N-1的系數(shù)是整數(shù)的多項(xiàng)式集合Lf,Lg,Lφ,Lm.注意p和q不需要是素?cái)?shù),但是本文假設(shè)gcd(p,q=1),并且設(shè)q?p.本文的運(yùn)算在多項(xiàng)式環(huán)R=[x]/(XN-1)上進(jìn)行.1個(gè)元素f∈R可以寫成多項(xiàng)式或者向量:

取2個(gè)元素f,g∈R,將符號(hào)⊕定義為環(huán)R上的加法運(yùn)算符號(hào),加法運(yùn)算定義為

f⊕g=h,hk=fk+gk,

其中h∈R,hk為多項(xiàng)式h的k階系數(shù).

將符號(hào)?定義為環(huán)R上的乘法運(yùn)算符號(hào).乘法運(yùn)算定義為

f?g=h,

其中hk為多項(xiàng)式h的k階系數(shù).容易驗(yàn)證R在以上定義的加法運(yùn)算和乘法運(yùn)算下構(gòu)成1個(gè)環(huán).進(jìn)行1次模q的乘法運(yùn)算,這意味著將多項(xiàng)式中的系數(shù)約簡(jiǎn)在模q下.

1.2 格

定義1.NTRU格.令q為大于5的素?cái)?shù),n為2的冪次,多項(xiàng)式f,g∈R(且f模q是可逆的).令h=g/f(modq),則由多項(xiàng)式h和q確定的NTRU格定義為

Λh,q={(u,v)∈R2|u+v×h=0(modq)}.

由定義1可知NTRU格Lh可以通過(guò)下面的2N×2N階矩陣生成:

由生成矩陣可知,NTRU格為滿秩格,NTRU格的行列式由素?cái)?shù)q和2N維數(shù)唯一確定,即

det(Lh)=qN,

Λh,q是2N上的一個(gè)滿秩格,Λh,q中的元素通過(guò)(v,r)Lh的行向量生成,其中r∈R.

2 方案設(shè)計(jì)和安全性分析

結(jié)合文獻(xiàn)[12],本文對(duì)文獻(xiàn)[11]的工作進(jìn)行修改,提出2個(gè)密鑰協(xié)商方案.

2.1 方案1描述

2.1.1 方案的參數(shù)選取

公開參數(shù)(N,p,q),其中選取N=251,p=3,q一般為2的冪次,可以取q=128或者q=256;多項(xiàng)式[x]/(xN-1)和[x]/(xN-1),其中:和分別代表有理數(shù)環(huán)和整數(shù)環(huán);商環(huán)q[x]/(XN-1)和p[x]/(XN-1),其中模q運(yùn)算的結(jié)果在[-q/2,q/2]內(nèi),而模p運(yùn)算的結(jié)果在{-1,0,1}中.L(a,b)代表多項(xiàng)式環(huán)[x]/(XN-1)中的特定多項(xiàng)式的全體,這些特定的多項(xiàng)式有a個(gè)系數(shù)為1,b個(gè)系數(shù)為-1,其他系數(shù)為0.

2.1.2 密鑰生成階段

不妨取df=dg=dr=36,p=3.

2.1.3 密鑰協(xié)商階段

1) Bob隨機(jī)選擇2個(gè)多項(xiàng)式r1B,r2B∈L(dr,dr-1),計(jì)算dB=fBr2B+pr1BcA,并把dB發(fā)給Alice.

2) Alice隨機(jī)選擇2個(gè)多項(xiàng)式r1A,r2A∈L(dr,dr-1),計(jì)算dA=fAr2A+pr1AcB,并把dA發(fā)給Bob.同時(shí)計(jì)算

mA=r2AfAdB(modq)(modp),
SK=H(Key,dA,dB,IDA,IDB),

其中Key=r2Ar2BfAdB(modq).

3) Bob收到dA后,計(jì)算

mB=r2BfBdA(modq)(modp),
SK=H(Key,dA,dB,IDA,IDB),

SK作為Alice和Bob的協(xié)商密鑰.

2.1.4 密鑰協(xié)商的正確性

q取值為256時(shí),p=3,而df和dg皆為36,故q>2p×max{df,dg}.

mA=r2AfAdB(modq)(modp)=
r2AfA(fBr2B+pr1BcA)(modq)(modp)=
(r2AfAfBr2B+pr2Ar1BgA)(modq)(modp)=
(r2AfAfBr2B+pr2Ar1BgA)(modp)=fAfBr2Ar2B,

同理mB=fAfBr2Ar2B,mA=mB=Key.

值得注意的是,由于r2A和r2B分別由用戶隨機(jī)選擇,在線路上不傳輸,故第三方無(wú)法獲取r2A和r2B,進(jìn)而第三方也就無(wú)法得到mA和mB以及Key,進(jìn)而提升了密鑰協(xié)商數(shù)據(jù)的安全性.

2.1.5 對(duì)文獻(xiàn)[11]的分析

文獻(xiàn)[11]提出的NTRU-AKA協(xié)議中以下2點(diǎn)值得注意:

1) 文獻(xiàn)[11]的密鑰協(xié)商過(guò)程中:

dA=(fA+prAcB),dB=(fB+prBcA),
Key=mA=fAdB(modq)(modp)=
fBdA(modq)(modp)=mB=Key.

而fA,fB分別為Alice和Bob的私鑰,屬于固定數(shù)據(jù).在雙方交互的過(guò)程中,Alice和Bob分別發(fā)送了dA和dB,而dA和dB這2個(gè)消息中,文獻(xiàn)[11]并沒(méi)有對(duì)用戶的私鑰進(jìn)行偽隨機(jī)性保護(hù),這給敵手攻擊預(yù)留了方便,因此文獻(xiàn)[11]只具有弱前向安全性,不能達(dá)到完美的前向安全性.

本文提出的方案1在密鑰協(xié)商過(guò)程對(duì)發(fā)送的消息進(jìn)行改進(jìn):

dA=(fAr2A+pr1AcB),dB=(fBr2B+pr1BcA),

其中(r1A,r2A),(r1B,r2B)∈L(dr,dr-1)是Alice和Bob分別選擇的隨機(jī)多項(xiàng)式.因此在每次的密鑰協(xié)商中dA和dB中都沒(méi)有直接使用Alice和Bob的私鑰固定值.即使雙方的長(zhǎng)期私鑰泄露也不能破解會(huì)話密鑰.

2) 在文獻(xiàn)[11]中并沒(méi)有對(duì)其設(shè)計(jì)的NTRU密鑰協(xié)商方案進(jìn)行詳細(xì)的安全證明.在2.2節(jié)中本文給出了在eCK模型下的安全方案及安全性證明.

2.2 方案1的安全性證明

2.2.1 eCK模型

敵手模型:A是擁有概率多項(xiàng)式計(jì)算能力的預(yù)言機(jī),它能夠全面監(jiān)控網(wǎng)絡(luò),并且能夠?qū)崿F(xiàn)竊聽、延遲、重放和篡改信息,同時(shí)還能夠執(zhí)行多項(xiàng)式數(shù)量界的詢問(wèn).包括:

StaticKeyReveal(IDi).敵手獲取身份為IDi的參與方i的私鑰(fi,gi).

EstablishParty(IDi).敵手能模擬參與者i注冊(cè)1個(gè)合法用戶的身份IDi,并且可以獲取其長(zhǎng)期私鑰.

eCK安全性:1個(gè)2方認(rèn)證密鑰交換協(xié)議是安全的,如果它滿足如下條件:

2.2.2 安全性證明

令k表示安全參數(shù),A定義為1個(gè)關(guān)于k的poly(k)敵手.假設(shè)游戲中,A最多能夠讓nq(N)個(gè)不同的誠(chéng)實(shí)參與方進(jìn)行安全實(shí)驗(yàn)(敵手A可進(jìn)行np(N)次StaticKeyReveal詢問(wèn)),每個(gè)參與方最多能參與np(N)個(gè)會(huì)話(敵手A可進(jìn)行np(N)次EphemeralKeyReveal和SessionKeyReveal詢問(wèn)),A至多進(jìn)行n0次H詢問(wèn).如果A能夠以1/2+f(k)的概率優(yōu)勢(shì)獲得安全實(shí)驗(yàn)游戲的勝利,其中f(k)是不可忽略的,則A就有不可忽略的概率獲得成功.H詢問(wèn)都被看作隨機(jī)預(yù)言機(jī),執(zhí)行Test查詢(成功概率為1/2).

挑戰(zhàn)者將利用贏得偽造攻擊的敵手A構(gòu)造求解器CH,以不可忽略的概率成功求解SVP問(wèn)題.

Setup:CH按照以下步驟建立系統(tǒng)公鑰和用戶長(zhǎng)期私鑰.

CH隨機(jī)選擇fi∈Lf(df,df-1)和gi∈Lg(df,df-1),設(shè)置(fi,gi)為第i個(gè)剩余參與方i的私鑰i≠b.

Queries:A模擬poly(k)次的除Test查詢外的其他詢問(wèn),并將所有哈希函數(shù)看作隨機(jī)預(yù)言機(jī).A只詢問(wèn)1次Test查詢.對(duì)于A進(jìn)行的詢問(wèn),CH對(duì)每個(gè)詢問(wèn)都有初始空列表,需要進(jìn)行維護(hù).

StaticKeyReveal(IDi):如果IDi=IDa,CH中止.否則,CH查詢?chǔ)玼sers返回(fi,gi)給A.

如果M是副本中的第2個(gè)消息,簡(jiǎn)單接受此會(huì)話.否則,考慮以下情形:

CH解決SVP問(wèn)題的優(yōu)勢(shì)為Pr[CH成功]≥p1(k)/n0nq(N)2np(N),其中p1(k)為事件1發(fā)生并且敵手A成功偽造會(huì)話密鑰的概率,即敵手A的優(yōu)勢(shì).1/n0為n0次H詢問(wèn)發(fā)生碰撞的概率,1/nq(N)np(N)是在詢問(wèn)nq(N)np(N)次SessionKeyReveal詢問(wèn)后成功偽造會(huì)話密鑰概率,1/nq(N)為nq(N)次StaticKeyReveal詢問(wèn)后成功偽造IDb的長(zhǎng)期私鑰的概率.因此如果敵手的優(yōu)勢(shì)p1(k)是不可忽略的,則CH解決SVP問(wèn)題的優(yōu)勢(shì)也是不可忽略的.這與SVP假設(shè)矛盾.

Setup:與事件1的詢問(wèn)類似.

Queries:CH參照事件1的實(shí)驗(yàn)回答除SessionKeyReveal以外的查詢.關(guān)于SessionKeyReveal查詢,CH回答如下:

CH解決SVP問(wèn)題的優(yōu)勢(shì)為Pr[CH成功]≥p2(k)/n0nq(N)2np(N)2,其中p2(k)是事件2發(fā)生并且敵手A成功偽造會(huì)話密鑰的概率即為敵手A成功的優(yōu)勢(shì).1/n0為n0次H詢問(wèn)發(fā)生碰撞的概率,1/nq(N)np(N)為在詢問(wèn)nq(N)np(N)次SessionKeyReveal詢問(wèn)后成功偽造會(huì)話密鑰概率,1/nq(N)為在nq(N)次StaticKeyReveal詢問(wèn)后成功偽造IDb的長(zhǎng)期私鑰的概率,1/np(N)為在針對(duì)IDa的SessionKeyReveal詢問(wèn)中,成功偽造出匹配會(huì)話的密鑰.因此如果p2(k)是不可忽略的,則CH的優(yōu)勢(shì)也是不可忽略的.這與SVP假設(shè)矛盾.

2.2.3 安全性分析

已知密鑰安全:如果之前會(huì)話密鑰泄露被敵手獲取,他利用之前的會(huì)話密鑰仍然不能解密本次會(huì)話密鑰的任何信息.安全性實(shí)驗(yàn)中通過(guò)EphemeralKeyReveal查詢,模仿敵手的已知密鑰攻擊.

抗密鑰泄露模仿攻擊:如果敵手獲取了用戶A的長(zhǎng)期私鑰,敵手不能冒充A以外的用戶與其他參與方進(jìn)行通信.用戶的公鑰與其長(zhǎng)期私鑰息息相關(guān),使得公鑰和私鑰一一對(duì)應(yīng),不能冒充.

前向安全性:1個(gè)或多個(gè)參與方長(zhǎng)期私鑰的泄露不影響之前建立的會(huì)話密鑰的安全性.協(xié)商的會(huì)話密鑰由雙方的長(zhǎng)期私鑰和每次會(huì)話的臨時(shí)密鑰共同生成,即使雙方長(zhǎng)期私鑰泄露也不能破解會(huì)話密鑰,因此方案有完美前向安全性.

抗臨時(shí)秘密密鑰泄露:參與方臨時(shí)私鑰泄露并不影響利用此臨時(shí)私鑰進(jìn)行會(huì)話的會(huì)話密鑰的安全性.在安全證明實(shí)驗(yàn)中,利用EphemeralKeyReveal查詢,模擬敵手獲取參與方臨時(shí)私鑰的能力.

抗臨時(shí)中間結(jié)果泄露:臨時(shí)中間結(jié)果(即臨時(shí)共享秘密值)的泄露不會(huì)影響該會(huì)話密鑰的安全性(在不知道任何參與方長(zhǎng)期私鑰的情況下).在安全證明實(shí)驗(yàn)中,Send查詢模擬了敵手可以截獲密鑰協(xié)商雙方交互的信息.

2.3 方案2描述

方案2的密鑰系統(tǒng)建立和密鑰生成與本文的方案1類似.

2.3.1 密鑰協(xié)商階段

1) Bob隨機(jī)選擇2個(gè)多項(xiàng)式r1B,r2B∈L(dr,dr-1),計(jì)算dB=(r2B+pr1BcA),并把dB發(fā)給Alice.

SK作為Alice和Bob的協(xié)商密鑰.

2.3.2 密鑰協(xié)商的正確性

q取值為256時(shí),p=3,而df和dg皆為36,故q>2pmax{df,dg}.

m1A=fAdB(modq)(modp)=
fA(r2B+pr1BcA)(modq)(modp)=
(fAr2B+pr1BgA)(modq)(modp)=
(fAr2B+pr1BgA)(modp).

進(jìn)而密鑰協(xié)商數(shù)據(jù)SK可以在Alice和Bob之間保持一致.

分析:方案2的安全性證明和分析與方案1類似.由于r2A和r2B分別由用戶隨機(jī)選擇,在線路上不傳輸,故第三方無(wú)法獲取r2A和r2B,進(jìn)而第三方也就無(wú)法得到mA和mB以及Key,進(jìn)而提升了密鑰協(xié)商數(shù)據(jù)的安全性.

方案2密鑰協(xié)商的過(guò)程中雙方交互的消息都不包含各自的秘密信息(私鑰),安全性完全依賴于NTRU加密方案的安全性,如果NTRU加密方案是安全的,那么該密鑰協(xié)商方案也是基于格上最短向量計(jì)算困難性假設(shè)(SVP)下會(huì)話密鑰也同樣具有不可區(qū)分性和不可偽造性.與文獻(xiàn)[11]相比,減少了長(zhǎng)期私鑰泄露的風(fēng)險(xiǎn),提高了安全性.

SK也可按如下方式計(jì)算:

SK=H(r2A+r2B,IDA+IDB),

這樣可以讓Alice和Bob處于平等地位.

3 與其他方案的對(duì)比分析

本文的2個(gè)方案是基于NTRU密碼學(xué)構(gòu)建的,相較于DH, ECDH等傳統(tǒng)的密鑰協(xié)商方案, NTRU方案基于多項(xiàng)式環(huán)上的運(yùn)算效率更高,其安全性可以歸約到求解格上的困難問(wèn)題,可以抵御量子攻擊.

將本文方案與其他方案進(jìn)行比較.首先比較方案的計(jì)算代價(jià),其中TE表示橢圓曲線密碼學(xué)加解密的計(jì)算耗時(shí),TNE,TND,TNM分別表示NTRU密碼學(xué)加密、解密和多項(xiàng)式模運(yùn)算的計(jì)算耗時(shí).因?yàn)樵贜TRU加解密算法中多項(xiàng)式系數(shù)僅為{-1,0,1},分析文獻(xiàn)[13-14]得到的NTRU加解密運(yùn)算時(shí)間與分析文獻(xiàn)[12]得到橢圓曲線加解密運(yùn)算時(shí)間相比較,TE?TNE,TND,TNM.NTRU密碼運(yùn)算效率和計(jì)算耗時(shí)遠(yuǎn)遠(yuǎn)優(yōu)于橢圓曲線密碼運(yùn)算.其次,本文還分析方案是否具有完美的前向安全性(perfect forward security, PFS)和方案使用的安全模型,比較了各方案的安全性.比較的結(jié)果如表1所示:

表1 方案比較

基于NTRU密碼學(xué)的方案1和方案2與文獻(xiàn)[12]相比計(jì)算耗時(shí)少、效率高.文獻(xiàn)[13]是基于BR安全模型設(shè)計(jì)的,沒(méi)有分析臨時(shí)私鑰泄露后對(duì)方案的安全影響.文獻(xiàn)[11]只能滿足弱完美的前向安全性,如果臨時(shí)私鑰泄露還會(huì)降低用戶長(zhǎng)期密鑰的安全性.本文基于更強(qiáng)安全性的eCK模型對(duì)文獻(xiàn)[11]進(jìn)行改進(jìn),本文方案1在信息交互中,對(duì)用戶的私鑰進(jìn)行偽隨機(jī)性保護(hù),使得方案具有完美的前向安全性,雖然計(jì)算耗時(shí)增加,但是安全性更強(qiáng);本文方案2對(duì)方案1進(jìn)行了改進(jìn),提高了計(jì)算效率,計(jì)算耗時(shí)與文獻(xiàn)[11]相當(dāng).

4 結(jié) 語(yǔ)

本文對(duì)文獻(xiàn)[11]的認(rèn)證密鑰協(xié)商協(xié)議方案進(jìn)行了改進(jìn),提出了一種基于NTRU格的密鑰協(xié)商協(xié)議.在隨機(jī)預(yù)言機(jī)模型下給出了詳細(xì)的游戲模型,并證明了該方案在eCK模型中是可證明安全的.而現(xiàn)階段,基于LWE和RLWE的加密方案[15]得到飛速發(fā)展,如何在安全目標(biāo)不變的情況下找到計(jì)算量更小的LWE和RLWE的密鑰協(xié)商協(xié)議是本文下一步的重點(diǎn)研究方向.