模冪滑動窗口法分析及加法鏈在預(yù)計算中的應(yīng)用

屈 曉1，孫達(dá)志1,2

(1.天津大學(xué)計算機科學(xué)與技術(shù)學(xué)院，天津 300072；2.中國科學(xué)院信息工程研究所，北京 100093)

1 概述

1978年RSA公鑰密碼算法被提出以來，公鑰加密體制逐步成為了信息安全領(lǐng)域應(yīng)用最廣泛的技術(shù)。模冪運算作為公鑰體制的核心環(huán)節(jié)，其執(zhí)行速度決定著公鑰體制的總體效率。然而計算機執(zhí)行大數(shù)模冪運算速度慢這一問題，至今沒有得到很好的解決。

大數(shù)模冪運算最基本的方法是依次計算底數(shù)的各次模冪值，然而這種方法效率低下。目前已有許多關(guān)于大數(shù)模冪運算問題的研究，提出了二進(jìn)制法、滑動窗口法、重編碼法等多種方法，使大數(shù)模冪運算速度慢這一問題得到了一定緩解。

本文首先對滑動窗口法的復(fù)雜度進(jìn)行分析，利用馬爾可夫鏈求出任意位任意窗口長度下的非零窗口數(shù)的一般表達(dá)式，然后提出一種應(yīng)用于預(yù)計算部分的改進(jìn)算法。

2 基本方法

文獻(xiàn)[1]總結(jié)了二進(jìn)制法。二進(jìn)制法將指數(shù)e表示成二進(jìn)制串的形式：

其中，k為指數(shù)e的位數(shù)。由左至右掃描每一位，每次先做一次模平方計算，若掃描位為1，再做一次模乘計算。二進(jìn)制法的平均復(fù)雜度為3(k-1)/2。

分塊法[1]作為二進(jìn)制法的改進(jìn)方法，采用空間換時間的思想來加速模冪運算過程。分塊法預(yù)計算并存儲指數(shù)長度為d的所有可能的冪值，將指數(shù)e的二進(jìn)制串劃分為長度為d的塊，根據(jù)塊值進(jìn)行計算。分塊法的平均復(fù)雜度為：

3 滑動窗口法及復(fù)雜度分析

3.1 滑動窗口法

文獻(xiàn)[2]中的滑動窗口法是一種應(yīng)用非常廣泛的模冪方法。滑動窗口法類似分塊法，將指數(shù)e劃分為零窗口和非零窗口，只需一半預(yù)計算量。這里將滑動窗口法重新闡述為算法1。

算法1

輸入M,e,n

輸出C

(1)計算并存儲Mwmodn，w=3,5,…,2d–1。

(2)根據(jù)以下策略由左至右劃分指數(shù)e，得到窗口F1,F2,…,Fs：

1)初始狀態(tài)S為零窗口狀態(tài)，用ZW表示，非零窗口狀態(tài)用NW表示。

2)當(dāng)S=ZW時，掃描一位，若是0，歸入ZW，S=ZW；若是1，歸入新的NW，S=NW。

3)當(dāng)S=NW時，掃描d–1位，將本NW結(jié)束在最后一位非0位設(shè)為i位，i+1至d–1位歸入ZW，S=ZW。

(3)初始C=MF1。

(4)i從2到s做循環(huán)：

1)C=CEimod n ，這里Ei=2Li，Li為窗口Fi的長度。

2)若Fi為NW，C=CMFimod n。

(5)返回C。

3.2 復(fù)雜度分析

文獻(xiàn)[1]提到一種帶參數(shù)q,r的變長滑動窗口法，文獻(xiàn)[3]對其進(jìn)行了復(fù)雜度分析，但存在著邏輯錯誤。文獻(xiàn)[4]給出了其近似分析及一個精確分析的例子，并未給出精確復(fù)雜度的一般表達(dá)式。下面利用馬爾可夫狀態(tài)轉(zhuǎn)移矩陣對算法1進(jìn)行精確的復(fù)雜度分析。

滑動窗口法復(fù)雜度可以表示為：

其中，T表示總復(fù)雜度；PRE表示預(yù)計算次數(shù)；LW表示最左窗口長度；NW表示非零窗口數(shù)量。

(1)PRE：預(yù)計算需要計算除去M1的指數(shù)不大于2d的所有指數(shù)為奇數(shù)的模冪值，加上M2，所以PRE=2d–1。

(2)LW：最左窗口最高位為1，窗口長度取決于d位中最后一個非零位，因此：

(3)NW：對于每一個掃描位定義3類狀態(tài)：

1)ZO：未進(jìn)行回溯即歸入ZW的0。

2)Ni：歸入NW 的第i位，i=1,2,…,d。

3)Zi：被NW掃描的第i位，后回溯歸入ZW，i=2,3,…,d。定義狀態(tài)轉(zhuǎn)移矩陣的行列狀態(tài)分別依次為：

狀態(tài)轉(zhuǎn)移矩陣P如下：

其中：

(1)ZO：已確定當(dāng)前位為ZW，下一窗口狀態(tài)只由下一位決定，下一位的狀態(tài)只可能是ZO,N1，概率均為2–1。

(2)N1～Nd–1：當(dāng)前位為i，只有當(dāng)i+1～d 位全部為0，下一位轉(zhuǎn)入ZW，以概率2–(d–i)轉(zhuǎn)為ZO，否則以1–2–(d–i)的概率停在NW，轉(zhuǎn)為Ni+1。

(3)Nd：當(dāng)前位已為該窗口最后一位，下一窗口狀態(tài)只由下一位決定，下一位的狀態(tài)只可能是ZO,N1，概率均為2–1。

(4)Z2～Zd–1：當(dāng)前位為i，由于此位經(jīng)掃描后回溯歸入ZW，因此i+1～d位必然全部為0，i位以1的概率從Zi轉(zhuǎn)為Zi+1。

(5)Zd：當(dāng)前位已為上一非零窗口掃描過的最后一位，下一窗口狀態(tài)只由下一位決定，下一位的狀態(tài)只可能是ZO,N1，概率均為2–1。

由于指數(shù)e最高位為1，初始狀態(tài)的概率分布為π0=[0,1,0,…,0]。

于是第i位狀態(tài)概率分布為πi=π0Pi–1。

3.3 實驗數(shù)據(jù)對比

為了驗證上述理論的正確性，選取較短的128位、使用及分析普遍的512位、1024位和較長的4096位，窗口d選取3～6，每個單元選取10000個隨機數(shù)進(jìn)行實際劃分，獲取實際復(fù)雜度。表1中每單元第1行為實際復(fù)雜度，第2行為理論公式計算得出的復(fù)雜度。

表1 總復(fù)雜度對比

復(fù)雜度測量值說明：由于模乘所需時間遠(yuǎn)大于其他計算所需時間，因此只記模乘的次數(shù)，一次模平方記為一次模乘。總復(fù)雜度為PRE+n–LW+NW，詳見3.2節(jié)。

4 預(yù)計算中的加法鏈應(yīng)用

4.1 加法鏈

若序列S=(a0,a1,…,as)滿足以下性質(zhì)，則稱S為e的一條加法鏈：

(1)S單調(diào)遞增。

(2)a0=1,as=e。

(3)ai=aj+ak,0≤j≤k

利用最短加法鏈加速模冪運算是理想的方法之一，但求給定整數(shù)的最短加法鏈本身是一個NPC問題[5]。文獻(xiàn)[6]介紹了幾種求最短加法鏈的方法，但從實驗可以看出，在隨機選取的十進(jìn)制4位整數(shù)中，求最短加法鏈耗時已經(jīng)將近7 s。而二進(jìn)制法、分塊法、滑動窗口法都可以看成是可行的求指數(shù)加法鏈的方法。

4.2 算法分析及步驟

在滑動窗口法確定窗口大小d后，對Mwmodn,w=3,5,…,2d–1，進(jìn)行預(yù)計算，加上計算M2，共2d–1次計算。

然而，對于任意給定位數(shù)的指數(shù)確定其最優(yōu)窗口大小，通常需要采集大規(guī)模樣本，即傳統(tǒng)的暴力搜索法；或在一定范圍內(nèi)逐一測試。兩者都相當(dāng)耗費資源。文獻(xiàn)[7]給出了一個對分塊法窗口大小的最優(yōu)化估計。

另一方面，當(dāng)窗口大小d選擇過大時，預(yù)計算量呈指數(shù)型增長，預(yù)計算結(jié)果很可能沒有被充分利用，造成資源浪費。因此，使預(yù)計算結(jié)果得到充分的利用將是一件有意義的事，而且可以提供其他提高效率的方向，例如4.5節(jié)的部分。

利用加法鏈進(jìn)行預(yù)計算的意思是，通過所有劃分出來的需要進(jìn)行預(yù)計算的非零窗口值尋找一條加法鏈。前文提到過尋找最短加法鏈?zhǔn)且粋€NPC問題，而尋找一條通過多個給定整數(shù)的最短加法鏈比尋找一個固定整數(shù)的加法鏈問題更加復(fù)雜。針對這一問題本文給出一種計算機執(zhí)行簡單可行的方法，來求出一條通過所有需要進(jìn)行預(yù)計算值的加法鏈。算法2給出了算法的細(xì)節(jié)。

算法2

輸入 經(jīng)算法1第(2)步劃分后得到的非零窗口值F1,F2,…,Fs

輸出 加法鏈A=a0,a1,…,as

(1)對F1,F2,…,Fs按升序排列并且只保留不同值得到序列W0=w01,w02,…,w0i。

(2)保存a0=w0i，計算t0=w0i–w0i–1。

(3)若t0已在W0中出現(xiàn)或t0=1，則在W0中刪去w0i，得到W1=w01,w02,…,w0i–1。否則在W0中用t0替換w0i，得到W1=w01,w02,…,w0i–1,t0。

(4)類似的，重復(fù)步驟(1)～步驟(3)，直至Wi中只剩下一個元素wi1。

(5)用任何一種計算可行的方法求出wi1的一條加法鏈，方便起見這里用二進(jìn)制法，得到ai,ai+1,…,as。

(6)對A=a0,a1,…,as按升序排列。

(7)返回A。

算法2求出的A即是一條包含所有非零窗口值的加法鏈。之后根據(jù)A依次計算出Mai，i=0,1,…,s，即可得到所有預(yù)計算所需的模冪值。

例 選擇窗口長度d=6，經(jīng)過步驟(1)后，得到W0=7,19,21,35,47,55,61；

經(jīng)過步驟(2)后，得到a0=61,t0=6；

經(jīng)過步驟(3)后，用6替換61，并按升序排列得到W1=6,7,19,21,35,47,55；

第1次循環(huán)后，有：

第2次循環(huán)后，有：

第3次循環(huán)后，有：

…

第13次循環(huán)后，有：

最后，2的一條加法鏈為1,2，添加到A后按升序排列得：

根據(jù)加法鏈A計算所有非零窗口值共需14次計算，而傳統(tǒng)方法則需要計算出全部值，共26–1=32次計算。

4.3 實驗數(shù)據(jù)

同3.3節(jié)，此處同樣選取128位、512位、1024位、4096位，窗口d選取4～7，每個單元選取10000個隨機數(shù)進(jìn)行實際劃分，利用算法2進(jìn)行預(yù)計算，結(jié)果如表2所示。表中數(shù)據(jù)為相應(yīng)位數(shù)下計算劃分出來所有非零窗口值所需模乘次數(shù)。傳統(tǒng)方法的預(yù)計算量在d為4～7時，分別為固定的8、16、32、64。

表2 預(yù)計算量對比

4.4 上下界分析

在4.3節(jié)的實驗中，可以看出，應(yīng)用算法2雖然在d選擇過大時，對預(yù)計算量增長影響較小，比傳統(tǒng)方法全部計算呈指數(shù)型增長具有較大的改進(jìn)，但在選擇最優(yōu)d的情況下，并沒有減少較多的模乘次數(shù)，可以說效率基本相同。對于一個固定整數(shù)的最短加法鏈問題，其長度的上界為：[lbe]+H(e)–1，文獻(xiàn)[8]給出了其下界：lbe+lbH(e)–2.13。文獻(xiàn)[9]指出了加法序列問題，即尋找一條通過多個給定整數(shù)的最短加法鏈問題，與向量加法鏈間存在一一對應(yīng)的關(guān)系。文獻(xiàn)[10]給出了一個向量加法鏈的界：l(r1,r2,…,rt)=lbr+(t+o(1))lbr/lblbr，其中，r=max{r1,r2,…,rt}。

當(dāng)窗口長度d取得越大，劃分出來的窗口數(shù)就越少。應(yīng)用加法鏈思想簡化預(yù)計算，當(dāng)d取得足夠大及加法鏈長度足夠短時，就可以在總復(fù)雜度上低于傳統(tǒng)方法的總復(fù)雜度。文獻(xiàn)[11]提出了一種方法，可以在一定程度上縮短加法鏈的長度，但其方法十分復(fù)雜，計算機執(zhí)行起來存在一定困難，非常消耗資源。

4.5 其他應(yīng)用

在信息發(fā)送中，會出現(xiàn)這樣一種情況：發(fā)送方A有一條消息M，需要發(fā)送給多個接收方B,C,D等。這一問題相當(dāng)于需要計算Cb=Mb,Cc=Mc,Cd=Md,…。通常情況下，會對這些模冪單獨進(jìn)行計算，如果應(yīng)用加法鏈的思想，即求一條包含b,c,d,…的加法鏈，然后根據(jù)加法鏈進(jìn)行模冪計算，將會大大降低需要執(zhí)行的模冪運算次數(shù)。然而一個完整的指數(shù)不像窗口，對多個指數(shù)應(yīng)用加法鏈的思想，將需要不少的空間，這種方法還有許多待改進(jìn)的地方。

5 結(jié)束語

本文給出了有限位指數(shù)模冪計算應(yīng)用滑動窗口法的平均復(fù)雜度精確表達(dá)式，非零窗口中的各位及零窗口中的零位都可表示成馬爾可夫鏈中的某一狀態(tài)，各狀態(tài)間以固定概率相互轉(zhuǎn)化，并通過實驗進(jìn)行誤差對比，在選取的各個條件下，誤差均小于0.1次模乘。提出一種計算機執(zhí)行簡單可行的求加法序列的算法，使之能應(yīng)用于預(yù)計算部分，實驗表明，隨著選擇窗口長度的增加，該方法比傳統(tǒng)方法提升的效率愈加明顯，使預(yù)計算的結(jié)果得到100%利用。今后將對算法2進(jìn)行改進(jìn)，在計算機執(zhí)行簡單可行的前提下，進(jìn)一步縮短加法鏈的長度；對于同一消息多方發(fā)送問題，考慮如何只利用少量空間應(yīng)用加法鏈提高加密效率。文獻(xiàn)[12]指出二進(jìn)制法、分塊法等方法在本質(zhì)上都是加法鏈算法，今后將研究基于冪樹思想的構(gòu)造加法鏈的算法，結(jié)合滑動窗口法減少非零窗口數(shù)，從而減少總復(fù)雜度。

[1]Knuth D E.The Art of Computer Programming:Semi-numerical Algorithms[M].New Jersey,USA:Addison-Wesley,1981.

[2]Menezes A J,Van Oorschot P C,Vanstone S A.Handbook of Applied Cryptography[M].[S.l.]:CRC Press,1996.

[3]Koc C K.Analysis of Sliding Window Techniques for Exponentiation[J].Computers&Mathematics with Applications,1995,30(10):17-24.

[4]Park H,Park K,Cho Y.Analysis of the Variable Length Nonzero Window Method for Exponentiation[J].Computers&Mathematics with Applications,1999,37(7):21-29.

[5]Downey P,Leong B,Sethi R.Computing Sequences with Addition Chains[J].SIAM Journal on Computing,1981,10(3):638-646.

[6]王曉東.最短加法鏈算法[J].小型微型計算機系統(tǒng),2001,22(10):1250-1253.

[7]曾 皓,范明鈺,王光衛(wèi),等.模冪與點乘m_ary算法中窗口大小的最優(yōu)化估計[J].計算機應(yīng)用研究,2007,24(10):35-36.

[8]Sch?nhage A.A Lower Bound for the Length of Addition Chains[J].Theoretical Computer Science,1975,1(1):1-12.

[9]OlivosJ.On Vectorial Addition Chains[J].Journal of Algorithms,1981,2(1):13-21.

[10]Yao A C C.On the Evaluation of Powers[J].SIAM Journal on Computing,1976,5(1):100-103.

[11]Bos J,Coster M.Addition Chain Heuristics[C]//Proc.of the 9th Annual International Cryptology Conference.New York,USA:Springer,1989:400-407.

[12]董付國,厲玉蓉.幾種方冪模快速算法的加法鏈一致性分析[J].計算機工程與應(yīng)用,2010,46(36):48-50.