探測窗口的NAFω算法

蔣洪波，馮新宇，欒 兵，沈顯慶

（1.黑龍江科技學院 黑龍江 哈爾濱 150027；2.東北農業大學 成棟學院，黑龍江 哈爾濱 150025）

橢圓曲線自引入密碼學以來一直備受人們青睞，它的突出特點吸引著密碼愛好者們對它的不斷探索和研究，隨著計算能力的增強對其實現速度也提出了更高的要求，關于實現速度的研究大部分集中在影響加密速度的幾個關鍵點上，其中橢圓曲線上的點乘運算是研究熱點之一，而研究點乘又主要集中在NAF標量乘[1]上，它們大都是將NAF算法與其他算法結合實現，沒有從NAF算法本身出發提高速度，而本文則是立足NAF算法進行分析研究。在NAF算法中若NAF的長度為，那么算法中的移位運算就要進行次，該移位運算消耗了大部分的算法時間。本文提出的探測窗口法實現NAF則大大減少了算法中的移位次數，為所有基于NAF的算法提高了運算效率。該算法簡單便于實現，實現效率高。

1 窗口寬度ω的AFω算法

假設實現平臺的字長是W位，并且W是8的整數倍。則字U的W位，分別以W-1到0標記，且第W-1位為最高有效位。

設 f（z）是一個，次的二進制既約多項式，記做 f（z）=zm+r（z），則GF（2m）上的元素是次數最多為m-1的二進制多項式。

一個域元素a（z）=am-1zm-1+…+a2z2+a1z+a0與一個m維向量 a=（am-1，…，a2，a1，a0）相對應。 令 s=[m/W]，t=Ws-m。 軟件實現時 k 用 s個 W 字的一個數組 K=（K[s-1]，…，K[1]，K[0]）來存儲，最低有效位k0存儲到K[0]中，并且K[s-1]的最左t位沒有用（總是設置為0）。

因為域元素的移位是整體移位，因此總共只需要個s字的移位。

橢圓曲線點乘運算中，若允許利用額外的存儲器和預計算，那么用加減法實現點乘可以獲得更高效的點乘算法，把它叫做計算點乘的窗口方法[2]。

1.1 非相鄰表示型

橢圓曲線點乘算法中需要先計算 NAF（k）或 NAFω（k），其中NAF稱作非相鄰表示型。

設 P=（x，y）∈E（Fq）。若 Fq是二進制域，則-P=（x，x+y）；若Fq的特征大于 3，則-P=（x，-y）。 因此橢圓曲線的點的減法與點的加法一樣有效。它促使我們使用k的帶符號數字表示

這種特別帶符號數字表示就是非相鄰表示型。

定理1（的性質）令是一個正整數。

1）k 有惟一的 NAF，并記為 NAF（k）。

2）NAF（k）在k的所有帶符號表示中具有最少的非零位。

3）NAF（k）的長度最多比k的二進制表示的長度大1。

4）若 NAF（k）的長度是 l，則 2l/3＜k＜2l+1/3。

5）所有長度為l的NAF中非零數字的平均密度約為1/3。利用算法1可以有效地計算NAF（k）。

算法1計算一個正整數的NAF

輸入：一個正整數k。

輸出：NAF（k）。

1）i=0。

2）當 k≥1 時，重復執行

若k是奇數，

則 ki=2-（k mod4），k=k-ki。

否則，ki=0。

k=k/2，i=i+1

3）返回（ki-1，ki-2，…，k1，k0）。

NAF（k）的各位數字可通過連續用2去除k且允許余數取 0 或±1 來得到。 若 k 是奇數，則余數 r∈{-1，1}，以使商（k-r）/2是偶數，這將確保下一個NAF數字是0。

1.2 窗口寬度的

寬度為ω的NAF記為：

定義2令ω≥2，那么每一個正整數k都有惟一的寬度為ω的NAF表達式：

其中非零系數 ki都是奇數，|ki|＜2ω-1，kl-1≠0，且任意連續 ω個數字中最多有1位為非零。寬度為ω的NAF的長度是l[3]。

定理2（寬度ω的NAF的性質）令k是一個正整數。

1）k 有惟一的寬度 ω 的 NAF，并記為 NAfω（k）。

2）NAF2（k）=NAF（k）。

3）NAFω（k）的長度最多比k的二進制表示的長度大1。

4）所有長度為l的寬度ω的NAF中，平均非零數字的密度約為 1/（ω+1）。

整數k在計算機中都以二進制形式存放，因此若令k=987 654 321，那么k的二進制表示為：

算法2計算一個正整數窗口寬度為ω的NAF算法

輸入：一個正整數k。

輸出：非相鄰表示型 NAFω（k）

1）c←k

2）s←＜＞

3）當 c＞0，重復執行

如果c是奇數

那么 u←c mod2ω

c←c-u

否則u←0

在S中將u追加在前

c=c/2

4）返回 S

這里 c mod2ω表示一個正整數 u，u 滿足 u≡c（mod2ω）且-2ω-1≤u≤2ω-1。

NAFω（k）的各位數字通過c連續除以2并使余數 r在區間[-2ω-1，2ω-1-1]內來獲得。

2 探測窗口的算法

用算法 2可以計算 NAFω（k），若如上例所示 k=987 654 321，則用算法2計算ω分別為3、4、5和6時的NAF如下：

從中可以看出若k是奇數并且余數 r=k mod2ω，則（k-r）/2將能被2ω-1整除，從而使后面的ω-1個數字均為零[3]。因此可以將k←k/2改寫為k←k/2ω，即把k一次向右移動1位改為 k 一次向右移動 ω 位。 與此同時將 ki+1，ki+2，…，ki+ω-1均賦值為0。

算法2采用從右向左的順序進行運算。在k向右移動ω位之前為了避免在ω+1位、ω+2位、位之后還有多個零出現，因此提出了用寬度為1的小窗口w來向左探測后方是否還有零的出現，若探測窗口值為零，則將相應的值置0，并且窗口w向左移動1位繼續探測是否還有0的存在。這種移動探測一直進行到探測窗口值等于1為止，此時先將k向右移位到窗口所在的位置，然后再進行相應的計算。探測窗口工作原理如圖1所示。

圖1 探測窗口原理圖Fig.1 Schematic of detection window

圖1中若ω=4且當前計算完ki-3的值，則可以直接將ki-1、和ki的值置0，探測窗口w從ai+1開始取值判斷該位是否為0。若探測窗口w為0，則ki=0，探測窗口w繼續向左移動一位，并且判斷該位的值，值若為0，則ki+1=0，探測窗口w繼續向左移動一位，重復上述判斷和窗口移動的過程；值若為1，則將k向右移動ω+窗口移動次數位，然后再計算ki+1的值。計算完ki+1之后的處理過程和計算完ki-3之后的過程相同，如此往復循環下去，直至k=0為止，算法結束。

經過上述分析提出了如算法3所示的探測窗口的NAFω（k）算法。

算法3計算一個正整數的探測窗口的NAFω

輸入：一個正整數k，窗口寬度ω。

輸出：非相鄰表示型 NAFω（k）

1）i←0。

2）窗口w取的最低位。

3）當 k≥1 時，重復執行

若探測窗口 w=0，則 ki←0，i←i+1，窗口 w 左移 1位。

否則，k右移到窗口w所在位置，

ki←k mod2ω，

k←k-ki，

將 ki+1，ki+2，…，ki+ω-1均賦值為 0，

i←i+ω，窗口w取第ω位的 k值。

4）返回（ki-1，ki-2，…，k1，k0）

其中k mod2ω與算法1中的c mod2ω含義相同。

3 實驗結果及分析

算法2和算法3中的整數k在計算機中都是以二進制形式存放，因此算法中的k除以2等同于k向右移動1位，而k除以2ω等同于k向右移動ω位，本算法的時間復雜度可以用占用時間最多的移位運算來衡量[4]。

設 NAF的長度為 l，則算法 2需要 l（2s-1）次字移位，需要l（s-1）次字異或。在窗口寬度ω的NAF中，非零元素的平均密度近似為 1/（ω+1）[5]，零元素的平均密度為 ω/（ω+1）[6]，以平均密度來看，一位非零元素到下一位非零元素共間隔ω個零，因此算法 3 中共需要移位 l（2s-1）/（ω+1）次，異或 l（s-1）/（ω+1）次。

在域 GF（2283）上用 C對算法2和算法3建模，用 gcc在linux平臺下編譯仿真，進行多組隨機數據驗證，得到如表1所示的實驗結果。

表1 m=283時算法2和算法3運行時間比較Tab.1 Running time of algorithm 2 and algorithm 3 when m=283

表1中的運行時間為算法關鍵部分的運行時間，即循環部分的運行時間。該仿真在W=32的平臺上完成，所以每次算法中的移位需要由移位運算和異或運算共同來完成，且m=283，因此s=9，則每次移位需要17個字移位，每次異或需要8次字異或。

算法3與算法2相比其中的移位次數有了明顯的減少，但是相對增加了探測窗口移動的運算，探測窗口移動的時間消耗為一個字的按位與，而算法中的一次移位操作需要2s-1個字的移位和s-1個字的異或，從總體上來看，一次探測窗口移動的時間要遠遠小于算法中的一次移位，即不會影響整個算法的時間復雜度。

算法2與算法3在不同ω值時的時間消耗曲線如圖2所示。

圖2 當取不同值時算法2和算法3的時間曲線Fig.2 Time curve of algorithm 2 and algorithm 3 when ω is deffrent

4 結束語

本文對文獻[2]提出的NAFω算法進行了分析和研究，根據其特點提出了探測窗口的NAFω算法，該算法大大減少了原始算法的移位次數，經理論分析和建模仿真驗證，該算法的時間消耗約為算法2的1/（ω+1）倍，且隨ω的增大運算效率也在提高，探測窗口的NAFω算法為快速實現橢圓曲線上的點乘運算和其他基于NAF的運算奠定了基礎。

[1]沈學利，張龍華，姜麗.NAF標量乘算法的改進 [J].計算機仿真，2010，27（2）:316-319.

SHEN Xue-li，ZHANG Long-hua，JIANG Li.Improvement of NAF scalar multiplication algorithm[J].Computer Simulation，2010，27（2）:316-319.

[2]JEROME A.SOLINAS.Efficient Arithmetic on Koblitz Curves[J].Designs， Codes and Cryptography，2000 （19）:195-249.

[3]Darrel H，Alfred M，Scott V.橢圓曲線密碼學導論[M].張煥國，譯.北京:電子工業出版社，2005:92-95.

[4]Gordon D M.A survey of fast exponentiation methods[J].Journal of Algorithms，1998，27（1）:129-146.

[5]Morain F，Olivos J.Speeding up the Computations on an Elliptic Curve using Addition-subtraction Chains[J].Informatique Théorique et Applications，1990（24）:531-544.

[6]瞿云云，包小敏.模冪運算的窗口NAF方法[J].西南大學學報：自然科學版，2009，31(9):60-64.

QU Yun-yun，BAO Xiao-min.A window NAF algorithm for modular exponentiation[J].Journal of Southwest University:Natural Science Edition，2009，31（9）:60-64.