基于NTRU密鑰協商協議設計

鄭鑒學 張道法 徐松艷 宋蘇鳴

(北京遙測技術研究所 北京 100094)

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

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

由于KA協議在不安全的網絡環境中運行,因此,設計出能夠抵御各種攻擊的認證KA協商協議就顯得尤為重要.目前,BR,mBR,CK,eCK,seCK[5-8]都是密鑰協商協議常用的安全模型,基于安全模型的密鑰協商方案也在不斷地發展[9-10].

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

1 相關知識描述

本節將介紹后續需要用到的關于格和NTRU格的一些基本知識,包括格的基本的定義、NTRU密碼體制的基本思想及其困難性.

1.1 NTRU算法描述

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

取2個元素f,g∈R,將符號⊕定義為環R上的加法運算符號,加法運算定義為

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

其中h∈R,hk為多項式h的k階系數.

將符號?定義為環R上的乘法運算符號.乘法運算定義為

f?g=h,

其中hk為多項式h的k階系數.容易驗證R在以上定義的加法運算和乘法運算下構成1個環.進行1次模q的乘法運算,這意味著將多項式中的系數約簡在模q下.

1.2 格

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

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

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

由生成矩陣可知,NTRU格為滿秩格,NTRU格的行列式由素數q和2N維數唯一確定,即

det(Lh)=qN,

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

2 方案設計和安全性分析

結合文獻[12],本文對文獻[11]的工作進行修改,提出2個密鑰協商方案.

2.1 方案1描述

2.1.1 方案的參數選取

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

2.1.2 密鑰生成階段

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

2.1.3 密鑰協商階段

1) Bob隨機選擇2個多項式r1B,r2B∈L(dr,dr-1),計算dB=fBr2B+pr1BcA,并把dB發給Alice.

2) Alice隨機選擇2個多項式r1A,r2A∈L(dr,dr-1),計算dA=fAr2A+pr1AcB,并把dA發給Bob.同時計算

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

其中Key=r2Ar2BfAdB(modq).

3) Bob收到dA后,計算

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

SK作為Alice和Bob的協商密鑰.

2.1.4 密鑰協商的正確性

q取值為256時,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分別由用戶隨機選擇,在線路上不傳輸,故第三方無法獲取r2A和r2B,進而第三方也就無法得到mA和mB以及Key,進而提升了密鑰協商數據的安全性.

2.1.5 對文獻[11]的分析

文獻[11]提出的NTRU-AKA協議中以下2點值得注意:

1) 文獻[11]的密鑰協商過程中:

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

而fA,fB分別為Alice和Bob的私鑰,屬于固定數據.在雙方交互的過程中,Alice和Bob分別發送了dA和dB,而dA和dB這2個消息中,文獻[11]并沒有對用戶的私鑰進行偽隨機性保護,這給敵手攻擊預留了方便,因此文獻[11]只具有弱前向安全性,不能達到完美的前向安全性.

本文提出的方案1在密鑰協商過程對發送的消息進行改進:

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

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

2) 在文獻[11]中并沒有對其設計的NTRU密鑰協商方案進行詳細的安全證明.在2.2節中本文給出了在eCK模型下的安全方案及安全性證明.

2.2 方案1的安全性證明

2.2.1 eCK模型

敵手模型:A是擁有概率多項式計算能力的預言機,它能夠全面監控網絡,并且能夠實現竊聽、延遲、重放和篡改信息,同時還能夠執行多項式數量界的詢問.包括:

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

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

eCK安全性:1個2方認證密鑰交換協議是安全的,如果它滿足如下條件:

2.2.2 安全性證明

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

挑戰者將利用贏得偽造攻擊的敵手A構造求解器CH,以不可忽略的概率成功求解SVP問題.

Setup:CH按照以下步驟建立系統公鑰和用戶長期私鑰.

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

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

StaticKeyReveal(IDi):如果IDi=IDa,CH中止.否則,CH查詢Λusers返回(fi,gi)給A.

如果M是副本中的第2個消息,簡單接受此會話.否則,考慮以下情形:

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

Setup:與事件1的詢問類似.

Queries:CH參照事件1的實驗回答除SessionKeyReveal以外的查詢.關于SessionKeyReveal查詢,CH回答如下:

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

2.2.3 安全性分析

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

抗密鑰泄露模仿攻擊:如果敵手獲取了用戶A的長期私鑰,敵手不能冒充A以外的用戶與其他參與方進行通信.用戶的公鑰與其長期私鑰息息相關,使得公鑰和私鑰一一對應,不能冒充.

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

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

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

2.3 方案2描述

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

2.3.1 密鑰協商階段

1) Bob隨機選擇2個多項式r1B,r2B∈L(dr,dr-1),計算dB=(r2B+pr1BcA),并把dB發給Alice.

SK作為Alice和Bob的協商密鑰.

2.3.2 密鑰協商的正確性

q取值為256時,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).

進而密鑰協商數據SK可以在Alice和Bob之間保持一致.

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

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

SK也可按如下方式計算:

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

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

3 與其他方案的對比分析

本文的2個方案是基于NTRU密碼學構建的,相較于DH, ECDH等傳統的密鑰協商方案, NTRU方案基于多項式環上的運算效率更高,其安全性可以歸約到求解格上的困難問題,可以抵御量子攻擊.

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

表1 方案比較

基于NTRU密碼學的方案1和方案2與文獻[12]相比計算耗時少、效率高.文獻[13]是基于BR安全模型設計的,沒有分析臨時私鑰泄露后對方案的安全影響.文獻[11]只能滿足弱完美的前向安全性,如果臨時私鑰泄露還會降低用戶長期密鑰的安全性.本文基于更強安全性的eCK模型對文獻[11]進行改進,本文方案1在信息交互中,對用戶的私鑰進行偽隨機性保護,使得方案具有完美的前向安全性,雖然計算耗時增加,但是安全性更強;本文方案2對方案1進行了改進,提高了計算效率,計算耗時與文獻[11]相當.

4 結 語

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