探測窗口的NAFω算法

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

（1.黑龍江科技學(xué)院 黑龍江 哈爾濱 150027；2.東北農(nóng)業(yè)大學(xué) 成棟學(xué)院，黑龍江 哈爾濱 150025）

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

1 窗口寬度ω的AFω算法

假設(shè)實(shí)現(xiàn)平臺(tái)的字長是W位，并且W是8的整數(shù)倍。則字U的W位，分別以W-1到0標(biāo)記，且第W-1位為最高有效位。

設(shè) f（z）是一個(gè)，次的二進(jìn)制既約多項(xiàng)式，記做 f（z）=zm+r（z），則GF（2m）上的元素是次數(shù)最多為m-1的二進(jìn)制多項(xiàng)式。

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

因?yàn)橛蛟氐囊莆皇钦w移位，因此總共只需要個(gè)s字的移位。

橢圓曲線點(diǎn)乘運(yùn)算中，若允許利用額外的存儲(chǔ)器和預(yù)計(jì)算，那么用加減法實(shí)現(xiàn)點(diǎn)乘可以獲得更高效的點(diǎn)乘算法，把它叫做計(jì)算點(diǎn)乘的窗口方法[2]。

1.1 非相鄰表示型

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

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

這種特別帶符號(hào)數(shù)字表示就是非相鄰表示型。

定理1（的性質(zhì)）令是一個(gè)正整數(shù)。

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

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

3）NAF（k）的長度最多比k的二進(jìn)制表示的長度大1。

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

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

算法1計(jì)算一個(gè)正整數(shù)的NAF

輸入：一個(gè)正整數(shù)k。

輸出：NAF（k）。

1）i=0。

2）當(dāng) k≥1 時(shí)，重復(fù)執(zhí)行

若k是奇數(shù)，

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

否則，ki=0。

k=k/2，i=i+1

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

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

1.2 窗口寬度的

寬度為ω的NAF記為：

定義2令ω≥2，那么每一個(gè)正整數(shù)k都有惟一的寬度為ω的NAF表達(dá)式：

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

定理2（寬度ω的NAF的性質(zhì)）令k是一個(gè)正整數(shù)。

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

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

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

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

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

算法2計(jì)算一個(gè)正整數(shù)窗口寬度為ω的NAF算法

輸入：一個(gè)正整數(shù)k。

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

1）c←k

2）s←＜＞

3）當(dāng) c＞0，重復(fù)執(zhí)行

如果c是奇數(shù)

那么 u←c mod2ω

c←c-u

否則u←0

在S中將u追加在前

c=c/2

4）返回 S

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

NAFω（k）的各位數(shù)字通過c連續(xù)除以2并使余數(shù) r在區(qū)間[-2ω-1，2ω-1-1]內(nèi)來獲得。

2 探測窗口的算法

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

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

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

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

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

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

算法3計(jì)算一個(gè)正整數(shù)的探測窗口的NAFω

輸入：一個(gè)正整數(shù)k，窗口寬度ω。

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

1）i←0。

2）窗口w取的最低位。

3）當(dāng) k≥1 時(shí)，重復(fù)執(zhí)行

若探測窗口 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 實(shí)驗(yàn)結(jié)果及分析

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

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

在域 GF（2283）上用 C對算法2和算法3建模，用 gcc在linux平臺(tái)下編譯仿真，進(jìn)行多組隨機(jī)數(shù)據(jù)驗(yàn)證，得到如表1所示的實(shí)驗(yàn)結(jié)果。

表1 m=283時(shí)算法2和算法3運(yùn)行時(shí)間比較Tab.1 Running time of algorithm 2 and algorithm 3 when m=283

表1中的運(yùn)行時(shí)間為算法關(guān)鍵部分的運(yùn)行時(shí)間，即循環(huán)部分的運(yùn)行時(shí)間。該仿真在W=32的平臺(tái)上完成，所以每次算法中的移位需要由移位運(yùn)算和異或運(yùn)算共同來完成，且m=283，因此s=9，則每次移位需要17個(gè)字移位，每次異或需要8次字異或。

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

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

圖2 當(dāng)取不同值時(shí)算法2和算法3的時(shí)間曲線Fig.2 Time curve of algorithm 2 and algorithm 3 when ω is deffrent

4 結(jié)束語

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

[1]沈?qū)W利，張龍華，姜麗.NAF標(biāo)量乘算法的改進(jìn) [J].計(jì)算機(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.橢圓曲線密碼學(xué)導(dǎo)論[M].張煥國，譯.北京:電子工業(yè)出版社，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]瞿云云，包小敏.模冪運(yùn)算的窗口NAF方法[J].西南大學(xué)學(xué)報(bào)：自然科學(xué)版，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.