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

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

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

1 概述

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

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

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

2 基本方法

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

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

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

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

3.1 滑動(dòng)窗口法

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

算法1

輸入M,e,n

輸出C

(1)計(jì)算并存儲(chǔ)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時(shí)，掃描一位，若是0，歸入ZW，S=ZW；若是1，歸入新的NW，S=NW。

3)當(dāng)S=NW時(shí)，掃描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的長(zhǎng)度。

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

(5)返回C。

3.2 復(fù)雜度分析

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

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

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

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

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

(3)NW：對(duì)于每一個(gè)掃描位定義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)前位已為上一非零窗口掃描過(guò)的最后一位，下一窗口狀態(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í)驗(yàn)數(shù)據(jù)對(duì)比

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

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

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

4 預(yù)計(jì)算中的加法鏈應(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

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

4.2 算法分析及步驟

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

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

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

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

算法2

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

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

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

(2)保存a0=w0i，計(jì)算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中只剩下一個(gè)元素wi1。

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

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

(7)返回A。

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

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

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

經(jīng)過(guò)步驟(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計(jì)算所有非零窗口值共需14次計(jì)算，而傳統(tǒng)方法則需要計(jì)算出全部值，共26–1=32次計(jì)算。

4.3 實(shí)驗(yàn)數(shù)據(jù)

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

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

4.4 上下界分析

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

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

4.5 其他應(yīng)用

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

5 結(jié)束語(yǔ)

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

[7]曾 皓,范明鈺,王光衛(wèi),等.模冪與點(diǎn)乘m_ary算法中窗口大小的最優(yōu)化估計(jì)[J].計(jì)算機(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]董付國(guó),厲玉蓉.幾種方冪?？焖偎惴ǖ募臃ㄦ溡恢滦苑治鯷J].計(jì)算機(jī)工程與應(yīng)用,2010,46(36):48-50.