基于動態模型的ＮＴＲＵ算法

(1.淮陰工學院 計算機工程系 江蘇 淮安 223001； 2.南京郵電大學 計算機學院 南京 210003)

摘 要：提出一種新的方法來改進NTRU算法執行速度。分析NTRU算法中多項式系數可能存在重復出現“11”“101”等模型的分布特征，然后用貪心算法找出在多項式卷積計算時可以重復使用最多次數的模型，過濾多項式系數對模型的干擾，從而實現在多項式中發現模型數最大化。重復使用模型相應的卷積值，可以提高NTRU算法的密鑰產生、加密和解密的速度。

關鍵詞：公開密鑰體系；樣本；NTRU加密；卷積

中圖分類號：TP309.7文獻標志碼：A

文章編號：1001-3695(2009)05-1896-04

Algorithm of dynamic patterns for NTRU

BU Shanyue1 ZHANG Haiyan1，WANG Ruchuan2

(1.Dept. of Computer Engineering Huaiyin Institute of Technology Huaian Jiangsu 223001 China；2.School of Computer Technology Nanjing Post Communication University Nanjing 210003 China)

Abstract:This paper presented a new method to enhance the executive speed of NTRU algorithm.First，analyzed the polynomial coefficients to find out the distribution characteristics of patterns，such as “11”“101” and so on which were possible to occur repetitively. Then using greedy algorithm determined the patterns that could be used most frequently when calculating the convolution of polynomial and eliminating the interferential effects that polynomial coefficients would have on patterns thereby ultimately maximized the number of patterns found in the polynomial. By using the convolution of related patterns repetitively，speeds up the key generation as well as the encryption and decryption operation of NTRU.

Key words:publickey cryptanalysis；patterns；NTRU encrypt；convolution

NTRU(number theory research unit )

算法是1996年由美國布朗大學三位數學教授Jeffrey Hoffstsin、Jill Pipher 和Joseph H.Silverman發明的公開密鑰體制。相對于RSA、ECC等公開密鑰體制算法來說，它是一種具有獨特優勢的算法。在安全性方面，文獻[1]中認為NTRU算法具有抵抗量子計算攻擊的能力，而RAS和ECC算法是無法抵抗量子計算的。在算法的速度和對存儲器需求方面，NTUR機構宣稱在無線通信安全解決方案中應用NTRU算法要比其他的公開密鑰算法快2 000倍，而所需內存只需其他公開密鑰算法的1/50。在標準化方面，NTRU已正式成為IEEE P1363標準，并被CEES(Consortium for Efficient Embedded Security)、IETF(Internet Engineering Task Force)、IEEE 802.15.3等機構所接受。

正是由于NTRU算法的優越性，吸引了眾多的國外密碼學家對其進行深入的研究。在對NTRU算法的快速和有效實現方面，文獻[2]使用特定的多項式形式來簡化NTRU算法計算量，提出了將用于產生密鑰的隨機多項式f改寫成f=1+p*F形式，減少了產生密鑰和解密時的計算量，這對于NTRU算法在智能卡等受限器件中的應用有著重要的意義。文獻[3]通過降低海明權重值的方法來減少NTRU算法中的卷積計算量。文獻[4]給出了將NTRU算法中的二元多項式卷積運算變為加法運算的方法。文獻[5]針對NTRU算法提出了滑動窗口方法(sliding window method)來提高計算卷積的速度，也就是根據多項式中可能存在的模型和不同模型的個數來簡化計算卷積過程。但在研究過程中發現用該方法產生的模型個數不是優化的，在時間度和空間度方面也待改善。

本文提出了一種基于動態模型的快速NTRU實現方法，進一步提高算法實時性和響應能力。與文獻[5]中的算法相比，本文給出的算法可以在多項式中發現更多的模型，發現的模型個數是優化的；在時間復雜度方面，僅使用d個數，而不是N個數，通常d≤N/2；在空間復雜度方面，僅需要N+di個臨時存儲單元，而不是N(w-1)個單元，這里的di<1。

1 NTRU算法回顧

NTRU算法運行在多項式環R=Z[X]/(XN-1)上，所有多項式的次數等于N-1，所有多項式的系數為整數。NTRU算法需要初始化三個整數參數(N，p，q)和四個具有N-1 階多項式f、g、r、m。其中：N為素數；p可以是多項式或整數；q通常為整數，但要保證gcd(p，q)=1。多項式f、g、r中非0系數的個數分別用df、dg、dr表示。下面是NTRU算法過程。

1)密鑰產生 根據NTRU參數N、p、q、dF、dg，隨機選擇兩個多項式F、g∈R，F中的非0系數的個數為dF，計算多項式h:

f=1+p*F(1)

f*fq≡1(mod q)(2)

h≡p*g*fq(mod q)(3)

得到公開密鑰為h和私人密鑰f。

2)加密 設有明文多項式m，m∈R，根據參數dr隨機選擇多項式r，r∈R，使用公開密鑰h加密明文m多項式，得到密文e為

e≡r*h+m(mod q)(4)

3)解密 使用私人密鑰f解密密文e，計算a為

a≡f*e(mod q)(5)

解密后的明文m為

m≡a(mod p)(6)

從式(1)～(6)可以看出，除去求逆過程外，共需要五次卷積計算，卷積計算是運行NTRU算法中耗時和占用臨時資源較多的主要因素。所以，提高計算卷積速度是改進NTRU算法又一個有效的途徑。

2 多項式環的卷積計算

設a(x)、b(x)、c(x)是具有N-1次、其系數為整數的多項式，a、b、c∈R。a(x)與b(x)的卷積計算可以表示為c(x)=a(x)*b(x)，為便于編程和書寫方便，將a(x)、b(x)改寫成向量形式：a=(a0，a1，a2，…，aN-1)，b=(b0，b1，b2，…，bN-1)，c= (c0，c1，c2，…，cN-1)。

由于XN≡1 mod(XN-1)，當a、b進行卷積計算時與普通多項式相乘基本相同，但要將乘積后的XN變成1，XN+1變成X，XN+2變成X2，…，即

ck=i+j≡k mod Nai bj（7）

其中:i，j，k=1，…，N-1。當然也可以用矩陣形式來表示卷積計算的過程，但計算效率要低于式(7)。

完成a(x)*b(x)的計算需要N2次的整數乘法和N-1次模運算。根據式(7)給出用C++語言描述的計算卷積算法：

3 基于HW的快速卷積計算

對于NTRU算法，通常取F(x)、g(x)、r(x)的系數為二元系數(0，1)。這樣在計算a(X)*b(X)時，如果ai=0或ai=1時，一定有aibj=0或aibj=bj。因此，在計算a(x)*b(x)時只需要進行加法計算即可。

引理1 如果a(x)是一個具有海明權重(Hamming weight)HW(a)的二元多項式，即a(x)的系數有HW(a)個“1”，計算a(x)*b(x) mod q時需要HW(a)×N次加法運算和N-1次模q約化運算^[3]。

示例1 N=6，HW(a)=4，a(X)=(0，1，1，0，1，1)，b(X)=(2，3，4，1，5，6)，使用算法1進行計算時，可以用圖1表示。計算結果為c(x)=a(x)*b(x)=(18，13，11，18，13，11)。根據圖1計算過程，可以用算法2描述快速計算卷積的過程。

算法2 HW的快速卷積計算

input：N，q，a，b

output：c

convolution_2(N，q，a，b，c){

1：initialization：

HW=0；

for (i=0;i<2*N;i++) c[i]=0;

2：for (i=0;i

3：{if(a[i]!=0)

4：{t[HW]=i; HW++}

5：}

6：for(i=0;i<=HW;i++)

7： {for (k=0;k

8： } 

9：for (i=0;i<=N;i++) c[i]=(c[i]+c[i+N])%q; 

}

算法2中，a(x)為二元多項式[0，1]。1、2步主要對c清0；3～5步將a中的非0系數的位置存儲于向量t中，HW+1記錄a中的非0系數的個數；6～8步分別以a中非0系數的位置為起點，按順序分別將b的所有系數加到c中；9步將c中次數為N以后的系數分別加到c中次數為0以后的系數中，即對c進行模XN-1運算，同時對c的系數進行模q約化。

從算法2的6～8步中可以看到，a(x)*b(x)的計算只需要HW(a)*N次的加法。針對示例1來說，如用算法1共需要36次乘法計算，而用算法2只需要24次加法運算。對于一個實際的NTRU應用系統，通常取N>100，為了獲取最大的搜索空間，取HW(a)≤N/2。顯然使用算法2理論上可以提高卷積計算速度至少在50%以上。

4 發現模型 

仔細觀察圖1，就會注意到3+2共進行了兩次計算，同樣4+3、1+4、5+1、6+5、2+6也進行了兩次計算。這主要是因為字符“11”在a中重復出現了兩次。如果先將3+2、4+3、1+4、5+1、6+5、2+6的值暫時存儲起來，當需要時就可以重復使用它了，這樣就可以減少6次加法。也就是在算法2的基礎上，由原來的24次加法減少到18次加法，理論上提高計算速度可以達到25%。

顯然，對于任意多項式a(x)，如果“11”在多項式a(x)中出現的頻率越高，就可以減少更多的加法計算量。如果“11”在a(x)中出現i次，減少的加法次數將為N(i-1)次。還可以在a(x)中尋找其他的模型，如“101”“1001”等。如果這些模型在a(x)中出現的頻率比較高時，同樣可以利用它們減少加法計算量。

引理2 如果在具有N個系數的二元多項式a(x)中包含n個“1”的模型發生m次時，則可以減少的整數加法次數為N(m-1)(n-1)次。

證明 假設a(x)中只有一種模型，該模型包含n個“1”，并在a(x)中出現了m次，則HW(a)=nm，與b(x)相乘所需要的加法次數為N(n+m-1)次，所以減少的加法次數為N HW(a)-N(n+m-1)=N(m-1)(n-1)。

引理3 如果在a(x)中有w個不同的模型p1，p2，…，pw，則減少的加法次數T=Nwi=1(mi-1)(ni-1)。其中:mi表示在a(x)中包含n個“1”的第i個模型pi發生m次；ni表示在a(x)中第i個模型pi包含n個“1”的個數。

引理3是引理2的延伸，證明略。從引理3中可以看到，如果一個模型中只包含一個“1”，或只出現一次是不能減少加法次數的。所以進一步加速NTRU中的卷積計算的關鍵是使T最大化。 

定理1 設HW(a)是二元多項式a(x)系數為1的個數，a(x)的其他系數為0，p= HW(a)/N，d為相鄰兩個“1”之間的距離，則模型發生概率Pr[Z=d]=(1-p)d-1p^[5]。

如當N=251，dr=48時，按照定理1可以計算出當d=1時發生模型“11”的概率為0.191；當d=2時發生模型“101”的概率為0.156。對于其他模型，如模型

所以，只要考慮兩個“1”之間有很少的“0”模型，如“11”“101”“1001’”等。用兩個“1”之間距離來定理不同的模型，如模型“1001”用3表示，對于模型“1”則用0表示。下面先給出在a(x)中發現模型的算法3，然后再用文獻[5]中的例子來說明算法過程。

算法3 在a(x)中發現模型

input：d，b

output：pi，ni，di，w

patterns(b，d，pi，ni，di，w){

1.initialization：

j=0;w=1;pm=0;di=0;pkd++;

2.for(i=1;i<=d;i++)

3. {e[i]=b[i+1]-b[i];

4.t[e[i]]++;

5.if(e[i]>j) {j=e[i];M=e[i]}; 

6. }

7.for(i=1;i

8.if(t[i]>j){j=t[i];pm=i;};

9.if(e[0]==pm) t[e[1]]--;

10.for(i=1;i

11. {if((e[i]==pm)(e[i-1]!=pm)) t[e[i-1]]--;

12.if((e[i]==pm)(e[i+1]!=pm)) t[e[i+1]]--;

13. }

14.for(i=1;i

15.if(t[i]>1){di[w]=i;w++;}

16. i=0；

17. do{ 

18.for(k=1;k<=w;k++)

19.if(di[k]==e[i])

20.{nk++;pk[pkd]=b[i];pkd++;i=i+2;}

21.else{n0++;p0[p0d]=b[i];p0d++;i++;}

22. }while(i<=d);

}

示例2 設N=28，d=11，a=(1，0，0，0，0，1，1，0，0，1，0 0，0，1，0，0，1，0，1，0，1，0，1，1，0，0，0，1)。d表示a中系數為“1”的個數。用向量b存放a中“1”元素的位置，即b=(0，5，6，9，13，16，18，20，22，23，27)。pi表示在a中第i個模型的起始位置，該模型的個數為ni，該模型的距離為di，模型的總個數為w。具體過程如下：

a)利用向量b，從左到右(也可以從右到左)找出相鄰“1”系數之間的距離，并放到向量e中，這樣就可以發現a中可能存在的模型(算法2～3步)。示例2的e=(5，1，3，4，3，2，2，2，1，4)。

b)找出a中不同模型的可能的最大個數，并放到向量t中(算法4～6步)，5步中M變量是用來記錄模型中相鄰“1”的最大距離。示例2的t=(2，3，2，2，1)，t中的第1個元素表示模型的距離為1，即“11”的個數是2；第2個元素表示模型的距離為2，即“101”的個數是3；其他元素含義依此類推。

c)在t中找出除模型“1”外，發生頻率最高的模型pm(算法7～8步)。示例2的pm=“101”，它最多可以出現3次。

d)針對發生頻率最高的模型，過濾與此關聯的其他模型，找出a中經過一次優化后的不同模型的最大個數，并放到向量t中(算法9～13步)。示例2是以模型“101”為優先模型，刪除與此關聯的其他模型后，得到t=(1，2，2，0，1)。從t中可以看到模型“101”“1001”出現了兩次，可以為提高卷積計算的速度做出貢獻。而模型“11”和“100001”只出現了一次，對算法速度是沒有貢獻的。

e)將對卷積計算有貢獻的模型放到di中，w表示可用模型的個數(算法14～15步)。示例2的di=(2，3)，di中的2表示模型距離為2，即“101”;3表示模型距離為3，即“1001”。



f)用貪心算法從右到左(也可以從左到右)掃描向量b，如果di[k]=e[i]則將相應的模型在a中的起始位置放到pk中，用nk記錄模型pk的個數(算法16～22)。針對示例2，如果e的值是“2”，則將模型“101”在a中的起始位置放到p1中，也就是b[i]中的值，同時指針向左移2位；如果e的值是“3”，則將“1001”在a中的起始位置放到p2中，同時指針向左移2位；否則將模型“1”在a中的起始位置放到p0中，同時指針向左移1位。這樣就可以得到示例2的模型如下：

p0=[27，22，21]，p1=[9，5]，p2=[14，0]

5 基于動態模型的快速卷積計算

假設利用算法3已經發現a(x)中不同的模型，下面就可以使用算法4來加速卷積計算。算法4可以看成是對算法2的改進。

算法4 基于動態模型的快速卷積計算

input:pi，ni，di，w，b，N，q 

output：C

convolution_3(pi，ni，di，w，b，N，q，c){

1.initialization：

N1=N+N;

for(i=0;i

2.for(j=1;j<=n0;j++)

3.for(k=0;k

4.for(i=1;i<=w;i++)

5.{for(j=0;j

6.for(j=di;j

7.for(j=N;j

8.for(j=1;j<=ni;j++)

9.for(k=0;k

10. }

11. for(i=0;i

}

算法4中2～3步用來計算a中模型的距離為0，即“1”與b相乘的值，并放到c中。當然這里的“相乘”實際上是采用算法2中相加運算；4～10步用來計算a中模型的距離為非0與b相乘的值，其中，5～7步將a中對應一個模型與b相乘的值暫存到向量t中，8～9步計算出a中所有該模型與b相乘的值，并放到c中；11步是對c進行模XN-1、q運算。

6 結束語

本文提出的算法是在原有NTRU算法結構體系中完成的，所以不會對NTRU算法的安全性有任何影響。算法3產生的模型是a(x)可能出現的最大模型集合，而不是事先設定的模型集合，產生的模型是動態的，產生模型的個數是優化的。例如，大家很難在示例2中找到其他更多的模型。也正是由于算法產生的是動態模型，使得算法3適用于文獻[6]中隨機產生的多項式g、r、F的兩種方式。該算法過程相對文獻[5]要多一些，但只對d個數進行操作，而不是對N個數進行操作，通常d≤N/2。按照算法4進行的卷積計算只需要Nw0ni+w0di+(N-1)次計算，而使用的臨時存儲單元只需要N+di個單元。

筆者對本文提出的算法進行了編程驗證，實驗使用的筆記本電腦硬件配置是CUP為1.66 GHz的T2300，1 GB內存。操作系統是Windows XP，編程環境是Visual C++ 6.0。實驗使用的數據采用文獻[6]中SVES參數集。實驗結果表明使用算法2的速度比使用算法1的速度要快40%左右；而使用算法4的速度要比算法2的速度快19%左右。特別是當值越大時，算法4的優越性就會更明顯。

參考文獻：

［1］LUDWIG C.A faster lattice reduction method using quantum search[C]//Proc of the 14th International Symposium on Algorithms and Computation.Berlin:Springer，2003:199208.

[2]HOFFSTEIN J，SILVERMAN J H.Optimizations for NTRU[C]//Proc of PublicKey Cryptography and Computational Number Theory.Warsaw:de Gruyter，2000:1115.

[3]HOFFSTEIN J，SILVERMAN J H.Random small hamming weight products with applications to cryptography[J].Discrete Applied Mathematics，2003，130(1)：37-49.

[4]BAILEY D V，COFFIN D，ELBIRT A，et al.NTRU in constrained devices[C]//Proc of the 3rd International Workshop on Cryptographic Hardware and Embedded SystemsCHES.Berlin:Springer，2001:262272.

[5]LEE M K，KIM J W，SONG J E，et al.Sliding window method for NTRU[C]//Proc of the 5th International Conference on Applied Cryptography and Network Security.Berlin:Springer，2007:432-444.

[6]IEEE P1363.1/D9，Draft standard for publickey cryptographic techniques based on hard problems over lattices[S].2007.

[7]QING Jun，ZHANG Yuli.Subliminal channels in the NTRU and the subliminalfree methods[J].Wuhan University Journal of Natural Sciences，2006，11(6):15411544.

[8]GAUBATZ G，KAPS J P，SUNAR B.Public key cryptography in sensor networksrevisited[C]//Proc of the 1st European Workshop on Security in Ad hoc and Sensor Networks.Berlin:Springer，2005:218.

[9]MOL P，YUNG M.Recovering NTRU secret key from inversion oracles[C]//Proc of the 11th International Workshop on Practice and Theory in PublicKey Cryptography.Berlin:Springger，2008:18-36.