NTRU 公鑰密碼的量子算法攻擊研究*

董 經, 蔡彬彬, 吳宇森, 高 飛, 秦素娟, 溫巧燕

1. 北京郵電大學網絡與交換技術國家重點實驗室, 北京 100876

2. 密碼科學技術國家重點實驗室, 北京 100878

1 引言

上述對NTRU 公鑰密碼的量子算法分析都是依托于量子搜索算法, 即Grover 算法. 那么是否仍存在其他量子算法可以實現對NTRU 的攻擊？本文發(fā)現, Claw-Finding 量子算法[20]對NTRU 密碼的分析具有同樣的攻擊效果. 但是, 原始Claw-Finding 算法針對的函數輸出值為單比特, 而分析NTRU 中所構造的函數輸出為比特串. 因此, 本文對原Claw-Finding 算法做了適當修改, 并應用修改的Claw-Finding量子算法實現對NTRU 密碼的攻擊. 在攻擊復雜度與文獻[19] 相等的情況下, 本文給出的量子攻擊避免了應用Grover 算法時強量子Oracle 的前提假設, 且不需要文獻[19] 在每次Oracle 疊加查詢時維護指數大列表O(f3).

2 預備知識

2.1 NTRU 公鑰密碼基礎

在介紹NTRU 公鑰密碼之前, 首先介紹算法中涉及的數學知識.

定義1 (模) 給定正整數m, 整數a,b, 若滿足m|(a-b), 則稱a,b模m同余, 記為a ≡b(modm).

定義1 中式子a ≡b(modm) 稱為模m的同余式,m稱為同余式的模. 在NTRU 密碼算法中涉及到的多項式的模, 與上述定義中的整數模含義一致. 在數學上, 對于模運算有以下性質:

定理1 給定整數A,B以及模數k, 若有A ≡B(modk), 那么對于任意整數C, 都有(A+C)≡(B+C) (modk) 成立.

定義2 (環(huán)) 若包含兩種代數運算的代數系統(tǒng)(A,+,*) 滿足以下條件:

(1) (A,+) 構成交換群;

(2) (A,*) 構成半群;

(3)* 運算關于+ 運算滿足左、右分配律;則稱(A,+,*) 是一個環(huán). 這里+ 和* 是二元運算. 通常情況下, + 運算為環(huán)中的加法,* 運算為環(huán)中的乘法. 在NTRU 密碼算法中二元運算是加法和乘法.

定義3 (截尾多項式環(huán), truncated polynomial ring)R= Z[x]/(xN-1) 表示N-1 次整數多項式的集合. 用N維向量[a0,a1,··· ,aN-1] 表示(N-1) 次整數多項式a=a0+a1x+···+aN-1xN-1,R上的加法運算+ 和乘法運算* 如下:

(1) [a0,a1,··· ,aN-1]+[b0,b1,··· ,bN-1]=[a0+b0,a1+b1,··· ,aN-1+bN-1];

(2) [a0,a1,··· ,aN-1]*[b0,b1,··· ,bN-1] = [c0,c1,··· ,cN-1], 其中k階系數ck為:ck=a0bk+a1bk-1+···+akb0+ak+1bN-1+ak+2bN-2+···+aN-1bk+1=∑i+j≡k(modN)aibj.

則(R,+,*) 構成的代數系統(tǒng)稱為截尾多項式環(huán), 也稱為卷積多項式環(huán), 用R= Z[x]/(xN-1) 表示, 其中Z 表示整數.

特別地, NTRU 公鑰密碼中所用到的多項式環(huán)的系數均為整數. 本文介紹的多項式環(huán)R中元素的多項式表示和向量表示將不再區(qū)分. 假設多項式a是R中的截尾多項式環(huán), 若關于模整數q有a*A= 1(modq), 則稱多項式A為截尾多項式環(huán)a的逆元.

NTRU 公鑰密碼系統(tǒng)中主要用到了三個截尾多項式環(huán), 形式如下:

多項式環(huán)Rp和Rq分別由多項式環(huán)R的系數模上p和q所得. 下面給出在NTRU 密碼中用到的三值多項式的定義.

定義4 (三值多項式) 設d1和d2是正整數, 定義

T(d1,d2) 中的多項式稱為三值多項式.

NTRU 密碼算法主要由三個整數參數(N,p,q)和四個度最多為N-1 的三值多項式集合Lf,Lg,Lr,Lm共同決定. 正整數N決定了在NTRU 中所有多項式的度最多為N- 1. 正整數p,q為NTRU密碼算法中模運算的模數, 滿足gcd (p,q) = 1, 且一般情況下q遠大于p. 本文中用* 表示截尾多項式環(huán)上的卷積運算. 例如多項式A(x) = 1 + 2x+ 3x2和B(x) = 1 +x, 此時N= 3. 卷積運算C(x)=A*B=1+3x+5x2+3x3=1+3x+5x2+3=4+3x+5x2. 這個運算包括了環(huán)上的加法和乘法, 并且運算結果的多項式的度最多仍為N-1. 三個三值多項式集合Lf,Lg,Lr的選取參照定義4, 而明文多項式Lm由通信過程中的發(fā)送方選取. 在本文中我們討論的參數集中均有正整數p=3. NTRU 密碼算法可分為三部分: 密鑰生成算法、加密算法、解密算法. 由于本文只關心在獲取公鑰信息后如何得到私鑰的信息, 所以只討論密鑰生成算法, 而并不具體推導加密和解密算法的過程. 對于NTRU 密碼系統(tǒng)工作的具體流程, 在文獻[1] 均有詳細討論. 為描述方便, 我們將通信雙方用Alice 和Bob 表示, 其中Alice表示發(fā)送方, Bob 為接收方.

2.2 NTRU 公鑰密碼密鑰生成算法

首先, Bob 選擇多項式f(x)∈Lf(df+1,df),g(x)∈Lg(dg,dg), 其中參數(df,dg) 由NTRU 相應的參數集給定, 多項式f(x) 稱為私鑰多項式,g(x) 為生成多項式. 隨后Bob 計算私鑰多項式f(x) 的模逆fp(x),fq(x), 其中fp(x)∈Rp,fq(x)∈Rq, 且滿足

若私鑰多項式f(x) 的模逆fp(x) 或fq(x) 有一個不存在, Bob 需要重新選擇f(x). 最后Bob 通過式子h(x) =pfq(x)*g(x) (modq) 得到公鑰多項式h(x), 符號* 為前面提到的卷積運算. 計算完成后, Bob將公鑰h發(fā)送給Alice. 這里f(x),fp(x),fq(x) 和g為Bob 私有, Alice 并不知道.

考慮到NTRU 密碼中用到的是卷積運算, 如果私鑰足夠稀疏(即多項式系數非零項越少), 卷積計算速度越快, 密碼算法的效率越高. 基于此, 研究學者們提出NTRU 密碼算法參數集的另一種工作模式——乘積多項式模式[1,19,21](對應的上述方式稱為直接選擇模式). 顧名思義, 在乘積多項式模式下Bob 選擇私鑰多項式f(x) 時不直接選擇私鑰, 而是選擇三個小系數多項式f1(x),f2(x),f3(x) 共同組成私鑰多項式, 即f(x) =f1(x)f2(x)+f3(x), 這里fi(x)∈Lfi(dfi,dfi),i= 1,2,3. 由于f1(x),f2(x),f3(x)中的非零項遠小于零項, 形成的向量比直接選擇的私鑰多項式向量更稀疏. 計算公鑰時, Bob 仍舊按照h(x)=pfq(x)*g(x) (modq) 得到公鑰h(x), 然后在通信過程中將公鑰h(x) 發(fā)送給Alice. Alice 用接收到的公鑰h(x) 對消息進行加密并發(fā)送給Bob, 最后Bob 通過f(x),fp(x) 進行解密得到Alice 發(fā)送的消息. NTRU 加解密的具體計算過程參考文獻[1,22–24]. 為分析方便, 本文中省略多項式表示中的自變量,如將f(x) 記為f.

3 NTRU 公鑰密碼的量子搜索算法攻擊

2015 年Fluhrer 基于Grover 搜索算法提出對NTRU 密碼的量子攻擊[19], 包括兩種密鑰恢復攻擊和兩種明文恢復攻擊. 這里我們僅介紹文獻[19] 給出的第一種密鑰恢復攻擊. 值得注意的是, NTRU 密碼算法中每一個參數集都會給定安全參數k, 這一參數表明攻擊者對參數集執(zhí)行任何攻擊復雜度都不低于2k.

由密鑰生成算法的公鑰生成等式h=pfq*g(modq) 可得, 卷積運算經過簡單的數學轉換易表示為向量的乘積形式:

其中H表示公鑰h的循環(huán)轉移矩陣. 若公鑰h的向量形式為h=h0,h1,··· ,hN-1, 那么相應的H可表示為

觀察等式(4)可以發(fā)現, 除了p是一個固定常數, 其他參數都是向量或者矩陣. 因此, 如果在等式兩邊同時模p可得

在乘積多項式模式下, 式(6)可表示為

根據定理1 有

文獻[19] 的攻擊思想是根據小系數多項式f3的系數多樣性, 存儲所有可能的(f3,(-f3H(modq))(modp))的值,如存在某個列表L中. 隨后,在f1f2上應用Grover 算法搜索f1f2滿足(f1f2H(modq))(modp) 的值在列表L中, 即搜索滿足(-f3H(modq)) (modp) = (f1f2H(modq)) (modp). 因此,Grover 算法的搜索空間為|f1f2|. 為進一步降低搜索復雜度, 文獻[19] 引用了以下引理:

引理1 給定兩個多項式A,B ∈F[x]/(xN-1),AB表示兩個多項式的乘積. 若有A′=xmA, 則有(xmA)B=xm(AB) 成立, 即A′B=xm(AB).

引理2 給定兩個多項式A,B ∈F[x]/(xN- 1),AB表示兩個多項式的乘積. 若有A′=xmA,B′=x-mB, 則有(xmA)(x-mB)=AB成立, 即A′B′=AB.

引理1 中若m是正整數, 則xm表示多項式向右移動了m位. 若m是負整數, 則xm表示多項式向左移動了m位. 引理1 表明, 多項式A′B和AB的系數是相等的, 唯一不同的是系數的位置移動了m位. 根據引理1, 式子fH=pg(modq) 有xmfH=pxmg(modq). 若用多項式xmf對密文(通常用e(x) 表示) 進行解密操作, 可以得到明文(通常用m(x) 表示) 的循環(huán)移位多項式xmm(x), 攻擊者僅通過計算xmm(x) 的循環(huán)轉移即可獲得明文消息m(x). 因此, 若多項式對(f′(x),g′(x)) 滿足fH=pg(modq), 則多項式f′(x) 便可以作為NTRU 密碼的私鑰多項式對密文進行解密. 同樣地, 在等式(8)中,目標(f1f2,f3) 也有((xmf1f2)H(modq)) (modp) = (-xmf3H(modq)) (modp) 成立, 即滿足等式(8)的多項式對((f1f2)′,f′3) 組成的多項式f′就很有可能可以作為NTRU 的私鑰多項式. 在NTRU 的密碼分析中, 通常認為攻擊者得到私鑰(明文) 多項式的任意循環(huán)轉移多項式, 都可攻破NTRU 公鑰密碼.應用引理1 和2 后可得, 等式(8)中f1f2的搜索空間由|f1f2| 降為|f1f2|/N,f3的搜索空間由|f3| 降為|f3|/N. 該攻擊在具體參數集上的分析見表1. 其中k表示安全參數, 指列表維護大小指每次Oracle 查詢需要查詢列表(f3,(-f3H(modq)) (modp)) 的大小.

表1 文獻[19] 在具體參數集上的分析Table 1 Analysis of quantum attack of Ref. [19] on parameter sets

4 NTRU 密碼的量子算法攻擊分析及改進

通過上述分析可以發(fā)現, 若預先將(f3,(-f3H(modq)) (modp)) 的值存在列表L中, Grover 搜索的量子Oracle 為以下形式:

這里有匹配的意思是指滿足等式(-f3H(modq)) (modp) = (f1f2H(modq)) (modp). 如在參數集EES593EP1 中,f1f2的搜索空間為2271.165, 提前存儲下來的(f3,(-f3H(modq)) (modp)) 的列表L的大小為O(2107.285). 在文獻[19] 中, 該攻擊是基于上述量子OracleOc(x)能以常數復雜度(即O(1))實現判斷某個f1f2對應的(f1f2H(modq)) (modp) 的值是否存在于列表L中. 而實際上, 這一操作的復雜度不能以常數時間實現. 換句話說, 該量子Oracle 的假設增大了該量子攻擊算法的實現難度, 無法達到文獻[19] 聲明的攻擊效果.

因此,為了避免上述攻擊的強量子Oracle 假設和維護指數大的列表L所帶來的消耗,本文基于Claw-Finding 量子算法[20]設計了新的攻擊. 該攻擊將類似中間相遇攻擊(MITM) 的兩部分看成兩個函數, 函數的自變量分別為f1f2和f3,因變量為對應的(f1f2H(modq)) (modp)和(-f3H(modq)) (modp).利用Claw-Finding 算法求解出滿足兩個函數相等關系的(f1f2,f3), 即可通過推導得到私鑰多項式f.

4.1 Claw-Finding 量子算法

問題1 (Claw-Finding) 給定兩個函數f:x ∈X →Z和g:y ∈Y →Z,X,Y和Z表示一個有限集合. 找到一對Claw (x,y), 其中x ∈X,y ∈Y, 使得f(x)=g(y).

2009 年, Tani[20]基于Szedegy 量子漫步算法[25]提出了解決Claw-Finding 問題的確定性算法.該算法基于Johnson 圖實現, 利用二分查找(binary search) 和四分查找(4-ary search) 解決搜索問題.Johnson 圖是一類特殊的圖, 用J(n,k) 來表示. 它是一個有(nk)個頂點的連通正則圖, 圖上的每一個頂點都是[n] 的大小為k的子集(這里[n] = 1,2,··· ,n). 當且僅當兩個子集中僅有一個元素不同時, 這兩個子集在圖上的兩個點之間有邊, 在數學上常稱之為集合之間的對稱差為2. 待檢測點集合(a,b,c,d,e,f)六個點組成的Johnson 圖J(6,3) 如圖1 所示.

圖1 頂點數為()=20 的Johnson 圖J(6,3) [26]Figure 1 Johnson graph J(6,3) with number of vertices()=20 [26]

當且僅當頂點集合的對稱差為2 時, 頂點之間才有邊. 若點a為目標點, 則在Johnson 圖中頂點abc,abd,abe,abf,acd,ace,acf,ade,adf,aef均為標記點. 容易發(fā)現, 目標點a在集合(a,b,c,d,e,f) 中的概率為, 而在Johnson 圖中由目標點a組成的標記點的概率為這使得找到目標點的概率變大[27].

在Claw-Finding 算法中, 首先定義兩個Johnson 圖Jf(|X|,l),Jg(|Y|,m), 圖中的X和Y分別對應函數f和g的自變量,l和m則對應兩個自變量的子集. 根據這兩個圖, 定義圖類積G=Jf×Jg, 若Jf(|X|,l) 上的點表示為F,Jg(|Y|,m) 上的點為G, 那么圖類積上的點為(F,G). 當且僅當Jf(|X|,l) 上的兩個點F,F′之間有邊且Jg(|Y|,m) 上的兩個點G,G′之間有邊時, 圖類積G=Jf×Jg的點(F,G),(F′,G′) 之間才有邊. 若頂點(F,G) 中存在一對(x,y)∈F×G, 使得f(x)=g(y) 成立, 那么頂點(F,G)即為目標點. 另外, 我們用LF,G來表示每一個頂點(F,G) 對應的具體函數值. 為方便分析, 令|X|=K,|Y|=M. 通常情況下,K ≤M.

容易看出上述定義的Johnson 圖是一個無向圖, 文獻[25] 通過引入自循環(huán)將原始圖變?yōu)椴糠钟邢驁D,即目標點僅會漫步到下一個目標點, 而不會漫步到其他非目標點. 這種漫步依然是通過轉移概率矩陣實現,算法中漫步算子定義為W=RBRA. 散射算子RB,RA的定義與文獻[25]相同,只是將x,y變?yōu)?F,G)和(F′,G′). 具體如下:

這里|cF,G〉和|rF′,G′〉中的系數表示圖類積中某個點的轉移概率. 如圖2 所示, 左圖是原始圖, 其中標號5是目標點, 右圖則是引入自循環(huán)后的修改的圖[28]. 原始圖中的量子漫步的轉移概率是均勻的, 但在修改的圖中并不是均勻的. 修改圖中的漫步算子W=RBRA與文獻[25] 中的量子漫步算法相同, 將根據修改圖的轉移概率矩陣來定義. 以RA為例, 當|F,G〉為目標點時,|F,G〉|F′,G′〉將標記為-|F,G〉|F′,G′〉,且不再散射到其他點. 否則|F,G〉|F′,G′〉將依據定義的RA進行散射.

并且, 為了在量子算法中讀取函數值, 文獻[20] 定義了量子OracleOf,g:|i,h,z〉 →|i,h,z ⊕Hi(h)(mod|Z|)〉,i ∈{0,1}, 這里H0(h):=f(h),H1(h):=g(h). 通過量子OracleOf,g將函數值讀出, 并存為LF,G.

圖2 (a) 原始圖, (b) 修改圖Figure 2 (a) is original graph, (b) is modified graph

下面給出該算法的具體步驟:

步驟1: 定義初態(tài)為圖上點的均勻疊加態(tài)

步驟2: 查詢量子OracleOf,g, 此時系統(tǒng)狀態(tài)為

算法可以分為兩部分, 檢測算法(Claw-Detect algorithm) 和搜索算法(Claw-Search algorithm). 其中, 檢測算法作為搜索算法的子程序, 輔助得到最終的Claw(x,y). 所以下面我們給出檢測算法的具體算法步驟(見算法1), 而搜索算法僅給出算法思想.

?

下面介紹搜索算法的思想.

圖3 Claw-Search 算法思想Figure 3 Idea of Claw-Search algorithm

如圖所示, 圖3 中X和Y分別表示函數f(x) 和g(y) 的自變量空間. 若X={x1,x2,··· ,xn},Y={y1,y2,··· ,yn}, 則X1={x1,x2,··· ,xn/2},X2={xn/2+1,··· ,xn},Y1={y1,y2,··· ,yn/2},Y2={yn/2+1,··· ,yn}. Claw-Finding 問題中通常|X|≤|Y|, 因此算法優(yōu)先判斷搜索空間Y的大小. 如果Y=cX(其中c表示某個常數), 直接將X和Y以4-ary 搜索執(zhí)行Detect 算法. 若存在Claw 于集合(X1,Y1) 中, 則將(X1,Y1) 作為新的搜索空間(X,Y). 重復執(zhí)行直至搜索空間X和Y足夠小. 如果|Y|≥|X|2, 則將Y以2-ary 搜索執(zhí)行Detect 算法, 直至Y=cX, 然后重復執(zhí)行上述4-ary 搜索判斷Claw. 最后, 當搜索空間X和Y降為O(1) 時, 通過經典查詢即可獲得目標Claw.

4.2 應用Claw-Finding 量子算法分析NTRU 密碼

現在, 我們根據Claw-Finding 算法給出對NTRU 密碼的量子攻擊. 首先, 構造函數f:X →Z和g:Y →Z, 其中f(x)=(-xH(modq)) (modp),g(y)=(yH(modq)) (modp), 即x對應f3,y對應(f1f2),z ∈Z={0,1,··· ,p-1}. 應用Claw-Finding 算法找到一對(x,y), 使得f(x)=g(y). 即找到了對應的(f3,f1f2), 計算f=f1f2+f3可得NTRU 的私鑰多項式. 當|X|=K,|Y|=M, Claw-Finding算法找到一對Claw(x,y) 的復雜度為

然而, 在原Claw-Finding 算法中兩個函數的輸出均為單比特. 而在NTRU 密碼中, 函數的輸出為比特串, 因為不論是(f1f2H(modq)) (modp) 還是(-f3H(modq)) (modp), 計算所得的結果都是一個向量. 因此, 這里我們需要通過修改Claw-Finding 算法以達到攻擊NTRU 的目的. 具體地, 在得到量子態(tài)|(f1f2H(modq)) (modp)〉(用|φa〉表示) 和|(-f3H(modq)) (modp)〉(表示為|φb〉) 后, 計算兩個量子態(tài)的重疊程度(Overlap) 表示為z(φa,φb) =|〈φa|φb〉|2. 在量子環(huán)境下若兩個比特串完全相等, 則兩個比特串的內積(即〈φa|φb〉) 為1; 否則為0. 因此我們可以用z(φa,φb) 來判斷兩個比特串(即兩個向量) 是否相等. Overlap 的計算參考文獻[29], 具體由定理2 給出.

定理2 給定兩個量子態(tài)Ua|0〉=|φa〉,Ub|0〉=|φb〉, 定義量子態(tài)

下面, 我們通過修改的Claw-Finding 算法給出對NTRU 公鑰密碼的攻擊. 首先, 通過訪問量子Oracle 得到初態(tài)(15), 觀察發(fā)現公式(15)可重寫為

(1) 制備量子態(tài)

這里

|0〉1表示單比特|0〉態(tài);

(2) 對|0〉1|ψ12〉和|0〉1|ψ22〉做量子交換測試(quantum swap test) 操作可得

(3) 應用定理2 于|ψ2〉可得

(4) 對|0〉1|ψ12〉和|0〉1|ψ22〉做逆量子交換測試操作可得

至此,|ψ4〉中已得到每一組的|F,G〉和|F′,G′〉對應(x,y) 的函數值(f(x),g(y)) 的內積. 若對應的(x,y) 為Claw, 則(f(x),g(y)) 的內積為1; 否則(f(x),g(y)) 的內積為0.|LF〉和|LG〉(|LF′〉和|LG′〉)對應的每一個函數值均可通過上述操作, 得到對應值的內積, 我們用|TF,G〉(|TF′,G′〉) 表示. 算法的檢測部分為檢測F,G(F′,G′) 對應的函數值|LF〉和|LG〉(|LF′〉和|LG′〉) 是否相等: 若|TF,G〉|TF′,G′〉為|00〉, 則F,G和F′,G′中均不存在Claw; 否則認為F,G或F′,G′中存在Claw. 具體地, 檢測|F,G〉和|F′,G′〉中是否存在Claw, 也即檢測對應的量子態(tài)|F,G〉和|F′,G′〉是否為目標點, 通過使用酉操作2|00〉〈00|-I作用到|TF,G〉|TF′,G′〉上即可實現目標量子位翻轉.

綜上所述, 在考慮引理1 和2 的情況下應用修改的 Claw-Finding 量子算法可以在復雜度為O((|f1f2|/N)1/2) 下得到對應的Claw(f3,f1f2). 表2 中給出文獻[19] 與本文所提攻擊的比較.

表2 文獻[19] 與本文所提攻擊與之間的比較Table 2 Comparison of quantum attack between Ref. [19] and proposed attack

雖然本文提出的量子攻擊復雜度與文獻[19] 相同, 但所提攻擊避免了應用Grover 算法時強量子Oracle 的前提假設, 并且文獻[19] 需要在每次Oracle 迭代中都需要調用指數大的列表, 而本文所提攻擊不需要這些額外的消耗.

5 總結

本文分析了Fluhrer 提出基于Grover 搜索算法對NTRU 公鑰密碼的攻擊. 該攻擊存在一個強量子Oracle 的前提假設, 所需的量子Oracle 實現難度較大, 且需要維護O(|f3|/N) 的指數大列表. 針對這些缺陷, 本文基于修改的Claw-Finding 算法給出對NTRU 的新的量子攻擊. 其中, 修改的Claw-Finding量子算法中定義的函數輸出為多比特串. 通過引入量子幅度放大和相位估計計算兩個函數輸出比特串的內積, 算法能有效識別目標量子態(tài). 在與文獻[19] 所提量子攻擊具有相同攻擊復雜度的情況下, 本文提出的攻擊有效地避免了強量子Oracle 的假設, 并且不需要維護指數大列表, 減少了資源消耗.