一種二進(jìn)制域非相鄰表示型的生成算法

蔣洪波, 李釗樞, 林憲峰, 楊慶江, 馮新宇

(1.黑龍江科技大學(xué) 電子與信息工程學(xué)院, 哈爾濱 150022; 2.國(guó)網(wǎng)黑龍江省電力有限公司 黑河供電公司, 黑龍江 黑河 164300)

0 引 言

橢圓曲線加密的核心運(yùn)算就是標(biāo)量乘。標(biāo)量乘的窗口非相鄰表示型NAF算法[1]分為兩步:第一步需要先將標(biāo)量k表示成NAF型記為F(k);第二步采用F(k)與橢圓曲線上的點(diǎn)進(jìn)行標(biāo)量乘計(jì)算。文獻(xiàn)[2-3]中的標(biāo)量乘算法均采用以上兩個(gè)步驟,諸如此類標(biāo)量乘算法中使用的NAF值計(jì)算都是窗口寬度w的NAF算法[1]。目前,對(duì)標(biāo)量乘的研究較多,而對(duì)NAF算法的研究非常少。改進(jìn)的NAF算法[4-5]在計(jì)算速度上進(jìn)行了提升,但生成的NAF值所需存儲(chǔ)空間較大。蔣洪波等[6]則在二進(jìn)制NAF的存儲(chǔ)空間上進(jìn)行了優(yōu)化,且占用空間有了較大幅度壓縮,其僅對(duì)窗口寬度為2的NAF型進(jìn)行了改進(jìn),而NAF算法的窗口寬度w可以滿足w≥2,且為了達(dá)到提升標(biāo)量乘的速度,選擇寬度大于2的情況較多,因此,研究一個(gè)在存儲(chǔ)空間上有優(yōu)勢(shì)的NAF算法還是非常有必要的。

1 非相鄰表示型

非相鄰表示型定義:若一個(gè)正整數(shù)k使用帶符號(hào)的二進(jìn)制(1、0和-1)來(lái)表示,其表達(dá)式為

(1)

其中,ki∈{-1,0,1},kl-1≠0,l為NAF的長(zhǎng)度,且不存在兩個(gè)連續(xù)的非零數(shù)字ki和ki+1。

1.1 非相鄰表示型性質(zhì)

窗口的寬度w≥2時(shí),k的NAF表示成Fw(k),當(dāng)w=2時(shí),k的NAF表示成F2(k)。為了簡(jiǎn)潔通常也將其簡(jiǎn)寫(xiě)成F(k),關(guān)于F(k)的性質(zhì)參見(jiàn)定理3.29[1]。定理3.33[1]給出了正整數(shù)k的Fw(k)性質(zhì):

(1)對(duì)于k有唯一的寬度w的NAF表示,記作Fw(k)。

(2)F2(k)=F(k)。

(3)Fw(k)的長(zhǎng)度最多比k的二進(jìn)制表示的長(zhǎng)度大1。

(4)在所有長(zhǎng)度為l的Fw(k)中,平均非零數(shù)字的密度近似為1/(w+1)。

該性質(zhì)涵蓋了w=2時(shí)的性質(zhì),即涵蓋了定理3.29[1]。

1.2 非相鄰表示型算法

利用算法3.35[1]計(jì)算一個(gè)正整數(shù)k的窗口寬度w的Fw(k),從Fw(k)的最低位k0開(kāi)始生成,如果k≥1,則重復(fù)執(zhí)行,直至k=0為止。重復(fù)部分判斷k。

(1)若k為奇數(shù),則用k對(duì)2w取余,余數(shù)值ki一定是奇數(shù),且小于等于2w-1,又由算法3.35[1]可知,kmod 2w表示一個(gè)正整數(shù)u,u滿足u≡k(mod 2w)且-2w-1

(2)若k為偶數(shù),則ki=0。

(3)k=k/2,i=i+1。

基于此算法可以得到,k=1 122 334 455的NAF表示,如表1所示。

表1 正整數(shù)k=1 122 334 455的NAF對(duì)比

由表1可知,Fw(k)值都是由正負(fù)奇數(shù)組成的,且都在(-2w-1,2w-1)區(qū)間內(nèi)。由表1可知,算法3.35[1]每次僅生成NAF的1位,即ki,生成步長(zhǎng)為1,且每位ki單獨(dú)存放在一個(gè)存儲(chǔ)字中,如果這樣以表1中的k值為例,則需要31個(gè)單元(或者字)存放該NAF值,而通過(guò)分析可知,NAF值中大部分為零值,根據(jù)性質(zhì)(4)可知,非零值個(gè)數(shù)為其NAF值長(zhǎng)度的1/(w+1),這是平均值,經(jīng)分析會(huì)發(fā)現(xiàn),其非零值的個(gè)數(shù)與w有關(guān)系,且最壞情況下其非零值的個(gè)數(shù)為l/w,也就是說(shuō)非零值個(gè)數(shù)是小于等于l/w的。若l固定,則w越大非零值的個(gè)數(shù)就越少,存儲(chǔ)那么多的零值就會(huì)顯得浪費(fèi)存儲(chǔ)資源,所以只要將非零值存儲(chǔ)起來(lái)并記錄其在NAF值中的位置即可,這樣在后邊進(jìn)行點(diǎn)乘計(jì)算時(shí)會(huì)方便許多。

2 字存儲(chǔ)的NAF多位生成算法

2.1 NAF多位生成算法

在原來(lái)一次生成1位NAF值的基礎(chǔ)上,分析可知,可以一次生成位或1位的NAF值,具體見(jiàn)文獻(xiàn)[2]。在此基礎(chǔ)上,將存儲(chǔ)方式進(jìn)一步改進(jìn)得到算法1。該算法僅將非零值存儲(chǔ)起來(lái),對(duì)于表1中w=3時(shí),不再需要31個(gè)單元存放數(shù)值,而僅需要9個(gè)單元即可,當(dāng)w=6時(shí),需要5個(gè)存儲(chǔ)單元。

算法1基于字存儲(chǔ)的NAF多位生成算法

輸入:正整數(shù)k,窗口寬度。

輸出:存放Fw(k)的數(shù)組A。

初始化:數(shù)組A[l/w];i=0;j=0;

k≥1時(shí),重復(fù)執(zhí)行;

若k為奇數(shù),則t=kmod 2w;

若t>2w-1,則t=t-2w,k=k-t;

Aj0=i,Aj1=t;

k=k/2w;

i=i+w;

j=j+1;

否則,k=k/2,i=i+1;

返回?cái)?shù)組A與j。

算法1中數(shù)組A的單元數(shù)量按照非零值數(shù)量的最壞情況(l/w)來(lái)預(yù)留單元。其Aj0和Aj1分別表示字的高16位和低16位(以字長(zhǎng)32位為例),也就是說(shuō),使用字的高16位記錄NAF值中非零值在原NAF中的位置,低16位存放具體的非零值。存儲(chǔ)示意如圖1a所示。當(dāng)然算法1中還可以進(jìn)一步優(yōu)化,用一個(gè)字來(lái)存放兩個(gè)NAF的非零值,也就是將32位按8位一劃分,分成四個(gè)部分,分別存放兩個(gè)相鄰的非零值,存儲(chǔ)示意如圖1 b所示。這完全可以根據(jù)算法的應(yīng)用環(huán)境來(lái)決定,當(dāng)然使用16位存放非零值和使用8位存放非零值所表示的數(shù)值范圍有著巨大的變化,使用8位可以表示的最大值為255,也就是說(shuō)它可以用來(lái)存放w=9的NAF值。如果值再大就需要擴(kuò)大存放位寬,就使用16位存放非零值可以存放最大w=17的NAF值,其實(shí)真正應(yīng)用時(shí)用不到這么大的w。

圖1 字存儲(chǔ)示意

圖1 b中的is和iv分別表示兩個(gè)相鄰非零值在NAF序列中的位置,ts和tv分別表示對(duì)應(yīng)這兩個(gè)位置的非零值。若對(duì)應(yīng)表1中的w=3,則算法1計(jì)算完成后的存儲(chǔ)內(nèi)容,如圖2所示。

圖2 表1中w=3的數(shù)組存儲(chǔ)示意

若采用8位存儲(chǔ)的形式,則存儲(chǔ)字個(gè)數(shù)會(huì)在算法1的基礎(chǔ)上再折半,圖2中使用了9個(gè)單元(字),那么采用8位存儲(chǔ)就會(huì)使用5個(gè)單元(字)存放NAF的非零值。這里示意圖不再給出。

算法中用來(lái)記錄非零值在NAF中的位置,j表示第j個(gè)非零值(非零值的個(gè)數(shù)從0開(kāi)始計(jì)數(shù)),當(dāng)然最后它也表示數(shù)組A的最后一個(gè)非零值的索引位置,它將在做點(diǎn)乘時(shí)還要起到關(guān)鍵作用。經(jīng)過(guò)以上分析,算法流程,如圖3所示。

圖3 字存儲(chǔ)的NAF多位生成算法流程

該算法當(dāng)k≥1不成立時(shí)結(jié)束,否則重復(fù)進(jìn)行如下操作。判斷k的奇偶性,結(jié)果有兩種情況。

(1)當(dāng)k為奇數(shù)時(shí),取k的后w位,這里可以用t=kmod 2w實(shí)現(xiàn),也可以用t=k&(2w-1)實(shí)現(xiàn)。然后判斷t>2w-1是否成立,如果成立取t=t-2w,以保證t的值落入(-2w-1,2w-1)內(nèi),更新k的值取k=k-t。若不成立,則不用對(duì)取得的t值進(jìn)行處理,也不用更新k的值,注意正常這里是需要對(duì)k做減t處理的,但是由于t(0,2w-1),k減t的結(jié)果就是k的后w位為0,后邊還要一次性的整除2w,相當(dāng)于對(duì)k右移w位,這樣看來(lái)減與不減的意義不大,而且還浪費(fèi)時(shí)間。至此已經(jīng)得到了非零值和它在NAF中的位置,將兩個(gè)值分別存入存儲(chǔ)字的低16位和高16位。k的低w位處理完畢,需要更新k的值,做k整除2w或者k右移w位。記錄非零值在NAF中位置的計(jì)數(shù)變量加w,表示一次處理了k的w位,而不是算法3.35[1]的一次處理1位,數(shù)組索引變量加1。

(2)當(dāng)k為偶數(shù)時(shí),即最低位為0,那么k的最低位轉(zhuǎn)換成NAF時(shí)一定是1位零值,零值不需要存儲(chǔ),所以索引變量不進(jìn)行處理,直接將k做除2運(yùn)算,或者將k右移1位得到新的k值。雖然不記錄該零值,但它卻是NAF中的一位,因此,該算法中記錄非零值在NAF中位置的計(jì)數(shù)變量需要加1。

2.2 基于字存儲(chǔ)的NAF點(diǎn)乘算法

橢圓曲線中的標(biāo)量乘也稱為點(diǎn)乘。該算法使用NAF值時(shí),可以用算法3.36[1]或算法1[7],然而當(dāng)使用了算法1生成的NAF后,再用此算法就不合適了,因此此處給出相應(yīng)的點(diǎn)乘算法2。

算法2基于字存儲(chǔ)的NAF點(diǎn)乘算法

輸入:正整數(shù)k,窗口寬度w,PE(Fq)。

輸出:kP。

初始化:Q←∞。

用算法1計(jì)算Fw(k)=A[j];

對(duì)于i∈{1,3,5,…,2w-1-1}計(jì)算Pi=iP;

從j到0,重復(fù)執(zhí)行;

Q←2Q;

若Aj1>0,則Q←Q+PAj1;

否則Q←Q-P-Aj1;

j=j-1;

從A(j+1)0-1到Aj0+1,重復(fù)執(zhí)行Q←2Q;

返回Q。

算法2中根據(jù)非零值A(chǔ)j1的正負(fù)決定加PAj1還是減P-Aj1,而減P-Aj1可以理解為加-P-Aj1。算法中使用了預(yù)計(jì)算,提前計(jì)算Pi=iP,由橢圓曲線的封閉性可知,該計(jì)算結(jié)果仍是橢圓曲線上的點(diǎn)。算法流程如圖4所示 。

圖4 點(diǎn)乘運(yùn)算流程

點(diǎn)乘計(jì)算開(kāi)始時(shí)需要對(duì)Q點(diǎn)進(jìn)行初始化,即Q點(diǎn)為∞,它表示在二進(jìn)制橢圓曲線中唯一的一個(gè)無(wú)窮遠(yuǎn)點(diǎn),用投影坐標(biāo)可表示為(0∶1∶0),雅克比投影坐標(biāo)表示為(1∶1∶0),點(diǎn)Q用來(lái)存放每次倍點(diǎn)或點(diǎn)加的結(jié)果,最后返回點(diǎn)乘的結(jié)果。圖中點(diǎn)-P-Aj1可以理解為點(diǎn)P-Aj1的負(fù)點(diǎn),若點(diǎn)P-Aj1的坐標(biāo)為(X∶Y∶Z),那么-P-Aj1的坐標(biāo)無(wú)論是投影坐標(biāo)還是雅克比投影坐標(biāo)都可表示為(X∶-Y∶Z)。

該算法用到的點(diǎn)加和倍點(diǎn)運(yùn)算可以使用兩種坐標(biāo)表示的任何一種算法進(jìn)行,具體算法可參見(jiàn)文獻(xiàn)[1]。

3 算法分析及驗(yàn)證

算法從空間、時(shí)間和訪問(wèn)內(nèi)存三方面進(jìn)行分析。首先,空間上算法1計(jì)算的結(jié)果需要一個(gè)長(zhǎng)度為j+1的一維數(shù)組存放,其中,j+1為實(shí)際NAF中非零值的個(gè)數(shù),這里前提為數(shù)組從0開(kāi)始索引,j在算法中的初始值為0,所以非零值的個(gè)數(shù)為j+1。因此,算法1需要的存儲(chǔ)空間就是j+1個(gè)存儲(chǔ)字。

而算法3.35[1]、文獻(xiàn)[2]和[3]的NAF算法存儲(chǔ)NAF值都需要L或L+1個(gè)字(L為k的二進(jìn)制表示長(zhǎng)度),又由定理3.33[1]的(3)可知,L和l滿足L≤l≤L+1。根據(jù)(4)可知非零值的平均密度為1/(w+1)。

綜合以上對(duì)比,可得到j(luò)+1≤(L+1)/(w+1),由此可以看出,存儲(chǔ)空間得到了極大的節(jié)約。w值越大,節(jié)省空間越多。以NIST推薦的二進(jìn)制域上的隨機(jī)橢圓曲線m=283為例,即數(shù)據(jù)長(zhǎng)度為283位,以上三種算法和算法1存儲(chǔ)NAF值所占空間曲線如圖5所示。圖中,當(dāng)數(shù)據(jù)k的二進(jìn)制長(zhǎng)度m=283且w=2時(shí),算法1執(zhí)行后會(huì)有平均95個(gè)非零值,即需要95個(gè)單元存放非零值及其在NAF中的位置,而算法3.35[1],文獻(xiàn)[2]和[3]的NAF算法存儲(chǔ)NAF值會(huì)需要283個(gè),以此類推w=6時(shí)算法1執(zhí)行完平均需要41個(gè)單元,其他三種算法還是需要283個(gè)單元,由此可見(jiàn),算法1所需存儲(chǔ)空間較其他NAF算法要少很多,且隨著窗口寬度w的變大,算法1所需的存儲(chǔ)空間越小。

圖5 算法1與其他算法占用空間比較

特別說(shuō)明,若w=2時(shí),則就是求k的F(k),這里不建議用算法1,更建議用文獻(xiàn)[4]的算法1,它能將存儲(chǔ)空間進(jìn)一步壓縮。當(dāng)3≤w≤17可采用文中的算法1求得NAF值,若w>17則可用單字的前n位存放非零值在NAF中的位置,單字的后32-n位存放非零值,具體要根據(jù)w的值來(lái)確定n的值,文中僅提供思路不再給出詳細(xì)的算法。

其次,運(yùn)算時(shí)間上算法1與文獻(xiàn)[3]中的算法2基本相同。使用Linux平臺(tái)gcc編譯c對(duì)算法1和文獻(xiàn)[3]的NAF算法建模,測(cè)試數(shù)據(jù)長(zhǎng)度m選取NIST推薦的二進(jìn)制域上的三個(gè)長(zhǎng)度,具體測(cè)試數(shù)值參見(jiàn)表2。

表2 測(cè)試數(shù)據(jù)

由于每組數(shù)據(jù)每次測(cè)試時(shí)運(yùn)行時(shí)間總是有些微不同,因此取每組數(shù)據(jù)測(cè)試后的平均仿真時(shí)間作為當(dāng)前長(zhǎng)度NAF算法的運(yùn)行時(shí)間,算法運(yùn)行時(shí)間比較,如表3所示。從表3可知,運(yùn)行時(shí)間相差不大。

表3 兩個(gè)NAF算法的運(yùn)行時(shí)間

最后,從訪問(wèn)內(nèi)存方面看,算法1存儲(chǔ)非零值時(shí)需要訪問(wèn)內(nèi)存j+1次,其他NAF算法則無(wú)論值是否為零都需要訪問(wèn)內(nèi)存,即需要L或L+1次訪問(wèn)內(nèi)存。算法2也僅需j+1次讀取非零值,而文獻(xiàn)[1]的點(diǎn)乘算法3.36需要訪問(wèn)L或L+1次內(nèi)存以取得NAF的各位值,進(jìn)而判斷是否做點(diǎn)加運(yùn)算。當(dāng)然兩個(gè)算法都需要j+1次讀取預(yù)計(jì)算的Pi=iP值。因此,從這里可以看到,算法1和2在時(shí)間上還是要稍快于其他NAF算法和點(diǎn)乘算法的。

4 結(jié) 論

對(duì)文獻(xiàn)[1]的算法和NAF的Fw(k)定義與性質(zhì)進(jìn)行了分析,針對(duì)一次生成1位NAF值并存儲(chǔ)的

方式進(jìn)行了改進(jìn)。結(jié)合文獻(xiàn)[3]的一次生成多位NAF值算法,對(duì)其結(jié)果的存儲(chǔ)方式進(jìn)行了改變,經(jīng)過(guò)理論分析得到如下結(jié)論:

(1)其他NAF的算法返回值需要L或L+1個(gè)存儲(chǔ)單元。算法1僅需j+1個(gè)存儲(chǔ)單元,而j+1≤(L+1)/(w+1),L為k的二進(jìn)制長(zhǎng)度,w為NAF的窗口寬度。w值越大,節(jié)省空間越多。

(2)算法1和2訪問(wèn)內(nèi)存次數(shù)為j+1次,即非零值的個(gè)數(shù)次,其他NAF算法和點(diǎn)乘算法需要訪問(wèn)L或L+1次內(nèi)存。