基于二進(jìn)制的相鄰表示型多位生成算法研究

蔣洪波　孫宇　張鵬南　馮新宇　王明杰

摘要：信息安全一直是研究熱點(diǎn)，而橢圓曲線加密在該領(lǐng)域占有舉足輕重的作用，橢圓曲線的標(biāo)量乘又是快速實(shí)現(xiàn)的關(guān)鍵點(diǎn)，其中二進(jìn)制數(shù)的非相鄰表示型（NAF）被應(yīng)用在該點(diǎn)運(yùn)算上，通常的NAF算法是一位一位的生成相應(yīng)數(shù)位，而這在時(shí)間上產(chǎn)生極大的浪費(fèi).為了節(jié)省運(yùn)算時(shí)間，分析NAF定義與性質(zhì)，提出一種基于二進(jìn)制的NAF多位生成算法，一次生成多位NAF值，減少了操作次數(shù)，替換了費(fèi)時(shí)運(yùn)算，從而節(jié)省了運(yùn)行時(shí)間.經(jīng)過分析及建模驗(yàn)證多位生成算法較原算法時(shí)間效率提高50%左右.

關(guān)鍵詞：二進(jìn)制;非相鄰表示型;多位生成;標(biāo)量乘

中圖分類號：TN918.4? 文獻(xiàn)標(biāo)識碼：A? 文章編號：1673-260X（2019）09-0086-04

1 引言

在過去，傳統(tǒng)的通信是以信件為基礎(chǔ)的，支付是通過支票或現(xiàn)金以及秘密文件都保存在密封的盒子里.今天一切都改變了，而且變化得非常快.每天都有人使用手機(jī)、電子郵件，越來越多的人通過互聯(lián)網(wǎng)支付費(fèi)用.這些變化正在使生活更便捷，但同時(shí)也會產(chǎn)生安全風(fēng)險(xiǎn).信息安全問題在當(dāng)前顯得尤為重要.密碼學(xué)是一種數(shù)學(xué)工具，安全工程師用來保護(hù)數(shù)據(jù)不受未經(jīng)授權(quán)的訪問或操作.密碼學(xué)為負(fù)責(zé)安全的人提供所需的實(shí)用程序，它可以隱藏?cái)?shù)據(jù)、控制對數(shù)據(jù)的訪問、驗(yàn)證數(shù)據(jù)的完整性.橢圓曲線在密碼應(yīng)用中具有舉足輕重的地位.然而計(jì)算標(biāo)量乘法成為限制吞吐量的瓶頸.在標(biāo)量乘中應(yīng)用最多的是NAF表示型，[1]中的算法是一位一位生成的，這對長度為l的正整數(shù)k來說需要執(zhí)行l(wèi)次循環(huán)及其相關(guān)操作，為了節(jié)省時(shí)間，根據(jù)NAF定義和性質(zhì)提出一種一次生成多位NAF值的算法，該算法還可優(yōu)化模運(yùn)算和除法運(yùn)算，用運(yùn)算效率更高的位運(yùn)算和移位運(yùn)算來代替它們.經(jīng)初步分析預(yù)計(jì)可以提高至少30%的運(yùn)算時(shí)間.

2 非相鄰表示型（NAF）

Non-adjacent Form縮寫為NAF，一個(gè)正整數(shù)k可以使用二進(jìn)制表示，也可以使用帶符號的二進(jìn)制——1、0和-1來表示，如k=，其中ki∈{-1，0，1}，kl-1≠0，l為NAF的長度，且不存在非零的兩個(gè)連續(xù)數(shù)字ki.

文獻(xiàn)[1]的定理3.29給出了正整數(shù)k的NAF表示的如下性質(zhì)：

（1）對于k的非相鄰表示型是唯一的，記作NAF（k）;

（2）k的NAF（k）具有最少的非零數(shù);

（3）L≤l≤L+1，L為k的二進(jìn)制表示長度;

（4）2l/3<k<2l+1/3;

（5）NAF（k）的平均漢明密度約為1/3.

利用[1]中的算法3.30計(jì)算一個(gè)正整數(shù)k的NAF，從NAF（k）的最低位k0開始生成，需要先判斷k的奇偶性，若k為奇數(shù)則用k對4取余，當(dāng)前ki值為2減去余數(shù)的值，即ki=2-（kmod4），由于對奇數(shù)的k來說對4取余只有兩種結(jié)果——1和3，因此ki的值也只有兩種可能性，當(dāng)余數(shù)小于2時(shí)ki=1，當(dāng)余數(shù)大于2時(shí)ki=-1，計(jì)算完ki的值再用k減去ki得到新的k值，以便使得新k值為偶數(shù)，為后邊的k=k/2做準(zhǔn)備;若k為偶數(shù)，則ki=0，同樣對k做折半處理，即k=k/2，與此同時(shí)i加1，為下一位ki的生成做準(zhǔn)備.至此也看到ki的三種取值情況，算法3.30的流程圖如圖1所示.

基于此算法可以得到k=50、k=87和k=113的NAF表示見表1.

從表中可以看到三個(gè)NAF（k）的值都是由1、0和-1組成的，

3 基于二進(jìn)制的NAF多位生成算法

從圖1可以看到每次只生成1位的ki，生成步長為1，通過分析研究算法3.30可以看到NAF（k）沒有相鄰的兩個(gè)非零值，也就是說1和-1的前后肯定是0，不會有非零數(shù)值存在，那么根據(jù)這個(gè)規(guī)律，可以考慮為什么不一起生成兩位ki值呢？這樣就會加快算法進(jìn)度.此算法在文獻(xiàn)[2]中已經(jīng)給定，但是該算法對于k為偶數(shù)時(shí)是一位一位生成的，改進(jìn)也只是在k為奇數(shù)時(shí)生成步長為2.

3.1 基于二進(jìn)制的NAF兩位生成算法

[1]中算法3.30和[2]中算法2對于k=113的計(jì)算過程如表2和表3所示.

為了進(jìn)一步優(yōu)化算法，本文在k為偶數(shù)時(shí)進(jìn)行了優(yōu)化.優(yōu)化算法為基于二進(jìn)制的NAF多位生成算法，優(yōu)化的前提是k在計(jì)算機(jī)中是以二進(jìn)制形式存放的，當(dāng)然這也是我們無需特意轉(zhuǎn)換的，因?yàn)檎麛?shù)k在計(jì)算機(jī)中就是以二進(jìn)制形式存放的.這里為了更好地闡述基于二進(jìn)制的NAF多位生成算法假設(shè)正整數(shù)k=113，則k2=1 110 001，從表1可以看到NAF（113）=1 0 0 -1 0 0 0 1.

表3中由于將表2的第1次和第2次循環(huán)及第5次和第6次循環(huán)一起計(jì)算，所以循環(huán)次數(shù)要較算法3.30少兩次，從執(zhí)行速度看上有所提高，但是在算法3.30的第3次和第4次循環(huán)上我們發(fā)現(xiàn)對于連續(xù)的兩個(gè)0來說，在NAF表示時(shí)也是兩個(gè)0，因此在這種情況下就可以進(jìn)一步優(yōu)化算法得到算法1所示的基于二進(jìn)制的NAF兩位生成算法.

算法1 基于二進(jìn)制的NAF兩位生成算法

INPUT：正整數(shù)k.

OUTPUT：NAF（k）.

1.i=0;

2.k≥1時(shí)，重復(fù)執(zhí)行

2.1t=k&0X3;

2.2switch（t）

case0：ki=0;ki+1=0;i=i+2;k=k>>2;

case1：ki=1;ki+1=0;i=i+2;k=k>>2;

case2：ki=0;i=i+1;k=k>>1;

case3：ki=-1;ki+1=0;i=i+2;k=k+1;k=k>>2;

3.返回（ki-1，ki-2，k0）.

用算法1計(jì)算NAF（113）的過程如表4所示.

算法1對表2中算法3.30的第3、4次循環(huán)一起計(jì)算，但是對第7次計(jì)算由于只有1個(gè)0，不能構(gòu)成步長為2的兩個(gè)0，因此只能單獨(dú)計(jì)算該位ki值.

算法中無論k值是奇是偶，只要大于等于1，就取k的最后兩位，其實(shí)就是k對4取余.因?yàn)閗在計(jì)算機(jī)中以二進(jìn)制形式存放，對4取余就等同于取k的最右兩位，這樣做也是因?yàn)槲徊僮髦恍枰粋€(gè)指令周期，而取余運(yùn)算需要調(diào)用子程序來完成，代碼不僅長而且執(zhí)行速度慢.同理算法3.30中的除法運(yùn)算k=k/2也被替換成了位操作k=k>>1，k=k/4替換成k=k>>2.算法1中t有四種取值：

（1）t=（00）2，即t=（0）10，k為偶數(shù)，且即使右移一次后仍為偶數(shù)，對應(yīng)的ki恰好是兩個(gè)0，然后將k右移兩位也即k除以4，達(dá)到當(dāng)k為偶數(shù)時(shí)優(yōu)化算法的目的;

（2）t=（01）2，即t=（1）10，k為奇數(shù)，ki=2-（kmod4）=1，根據(jù)NAF性質(zhì)必有ki+1=0，步長加2，再右移兩位;

（3）t=（10）2，即t=（2）10，k為偶數(shù)，但右移一位后為奇數(shù)，因此不能按照步長2去生成兩個(gè)ki和ki+1的值，只能生成一位ki值，右移一位，將剩余的“1”與k的其他高位再次形成新t值，繼續(xù)判斷生成NAF（k）的其他位;

（4）t=（11）2，即t=（3）10，k為奇數(shù)，ki=2-（kmod4）=-1，根據(jù)NAF性質(zhì)必有ki+1=0，步長加2，算法3.30中的k=k-ki，因?yàn)閗i=-1，因此k=k+1，再右移兩位.

對比表2和表3可以看到表3循環(huán)次數(shù)最少，原因是在第2次循環(huán)時(shí)將表2中算法3.30的第3、4次循環(huán)合并為一步完成，提高了執(zhí)行速度.對于k值較大時(shí)這種速度提升更加明顯.

3.2 基于二進(jìn)制的窗口寬度w的NAF多位生成算法

文獻(xiàn)[1]中給出了窗口寬度w的NAF算法，經(jīng)過分析在本文算法1的基礎(chǔ)上也對該算法進(jìn)行了改進(jìn)，基于二進(jìn)制的窗口寬度w的NAF多位生成算法如算法2所示.

算法2 基于二進(jìn)制的窗口寬度w的NAF多位生成算法

INPUT：正整數(shù)k，窗口寬度w.

OUTPUT：NAFw（k）

1.i=0;

2.k≥1時(shí)，重復(fù)執(zhí)行

若k為奇數(shù)，則

（1）t=k&（2w-1）

（2）若t>2w-1，則

①ki=t-2w;

②k=k-ki;

否則，ki=t;

（3）ki+1=0;ki+2=0;…ki+w-1=0;

（4）k=k>>w;

（5）i=i+2;

否則，判斷t的值，按值進(jìn)行下列操作：

（1）末尾1個(gè)0：

ki=0;i=i+1;k=k>>1;

（2）末尾2個(gè)0：

ki=0;ki+1=0;i=i+2;k=k>>2;

……

（w）末尾w個(gè)0：

ki=0;ki+1=0;…;ki+w-1=0;

i=i+w;k=k>>w;

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

文獻(xiàn)[1]的算法3.35中若k為奇數(shù)，則ki=kmod2w，由于計(jì)算機(jī)中的按位&比取余運(yùn)算效率高得多，又由Hash散列原理可知

a%b=a-（a/b）*b

這里如果b=2w，就可以用位運(yùn)算代替取余運(yùn)算，即

a%b=a&（b-1）=a&（2w-1）

因此在本文算法2中將該步替換成t=k&（2w-1），為了保證-2w-1≤ki≤2w-1，需做t>2w-1的判斷，若為真，則ki=t-2w，并將取得的負(fù)值加到k上，這樣才能保證原k不變而進(jìn)行后續(xù)的計(jì)算;否則ki直接取t值，這里將k減余數(shù)省略，因?yàn)橄葴p后移位和不減后移位效果是相同的，而且不減又會提高運(yùn)行效率，因此這里通過直接右移w達(dá)到最終目的.根據(jù)文獻(xiàn)[1]定義3.32的任何連續(xù)w個(gè)數(shù)字中最多有1個(gè)非零值，則必有ki+1=0;ki+2=0;…;ki+w-1=0.

若k為偶數(shù)，這里根據(jù)t值的末尾有幾個(gè)0來置幾個(gè)ki的零值，然后k也跟著移動幾位，這樣能夠提高k中多個(gè)0連續(xù)的處理效率.NAF（k）是w=2的MAFw（k）形式.

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

為了便于分析說明，設(shè)NAF（k）的長度為l，這里將文獻(xiàn)[1]的算法3.30、文獻(xiàn)[2]的算法2和本文的算法1就運(yùn)算次數(shù)進(jìn)行統(tǒng)計(jì).

文獻(xiàn)[1]的算法3.30由于是奇數(shù)時(shí)才進(jìn)行模運(yùn)算，根據(jù)NAF（k）的性質(zhì)（5）有非零數(shù)值的密度約為l/3，因此該模運(yùn)算進(jìn)行約l/3次;減法進(jìn)行約2l/3次;無論奇偶數(shù)k都要除2折半處理，因此除法進(jìn)行l(wèi)次;位運(yùn)算&在這里主要是用來判斷k的奇偶性，因此也進(jìn)行l(wèi)次;加法體現(xiàn)在變量i+1.

文獻(xiàn)[2]的算法2除法次數(shù)由k為奇數(shù)時(shí)的l/3次k=k/4和k為偶數(shù)時(shí)的l/3次k=k/2組成，加法次數(shù)同理，其他運(yùn)算次數(shù)與算法3.30相同.

算法1的模運(yùn)算被替換成位運(yùn)算&且不判斷k的奇偶性，因此模運(yùn)算次數(shù)為0;減法0次;除法替換成移位運(yùn)算，所以除法運(yùn)算0次;生成步長為2，所以位運(yùn)算&約為l/2次;每次取末尾兩位后都會進(jìn)行移位操作，因此移位次數(shù)與位運(yùn)算次數(shù)相同;加法次數(shù)為l/2次+case 3中k=k+1的次數(shù)（l/8）.

算法2沒有模運(yùn)算和除法;減法根據(jù)NAFw（k）的性質(zhì)（iv）非零數(shù)值密度為1/（w+1）算得大約有l(wèi)/（w+1）次;位運(yùn)算包括奇偶判斷和t值計(jì)算，因此有2l/（w+1）次;移位運(yùn)算接近l/（w+1）;加法與位運(yùn)算次數(shù)相同.運(yùn)算次數(shù)統(tǒng)計(jì)表見表5.

當(dāng)k為163位時(shí)，對表4中的幾種算法進(jìn)行C建模，運(yùn)行于Linux平臺，運(yùn)行結(jié)果見表6.

從實(shí)驗(yàn)結(jié)果可以看到本文算法1較算法3.30的運(yùn)算效率平均提高了50%左右.

5 結(jié)語

本文對[1]和[2]提出的NAF（k）算法進(jìn)行了分析，在此基礎(chǔ)上對其除法運(yùn)算和模運(yùn)算進(jìn)行了替換改進(jìn)，針對一次處理一位，提出了一次生成多位的NAF（k）算法，經(jīng)理論分析和建模驗(yàn)證得出以下u語結(jié)論：

（1）本文NAF（k）算法不需模運(yùn)算、減法和除法運(yùn)算，位運(yùn)算和移位運(yùn)算均l/2次，加法次數(shù)也較前兩種算法有減少.

（2）經(jīng)建模驗(yàn)證效率提高50%左右，時(shí)間復(fù)雜度明顯變小.

——————————

參考文獻(xiàn)：

〔1〕Hankerson D， Menezes A， Vanstone S. Guide To Elliptic Curve Cryptography[M]. Springer， 2004： 98-100.

〔2〕蔣洪波，尚春雨，馮新宇.NAF算法的改進(jìn)[J].科學(xué)技術(shù)與工程，2012，12（19）：4663-4666.

〔3〕J.López and R.Dahab. High-speed software multiplication in [C]//Progress in Cryptology —INDOCRYPT2000（LNCS1977） [393]. India ：Springer Verlag， 2000： 203-212.

〔4〕N. Koblitz. Elliptic curve cryptosystems[J]. Mathematics of Computation， 1987， 48： 203-209.

〔5〕李忠，張永華.整數(shù)的最佳帶符號二進(jìn)制表示的隨機(jī)生成算法[J].計(jì)算機(jī)科學(xué)，2014，41（11A）：282-283.

〔6〕丁勇.橢圓曲線快速算法理論[M].北京：人民郵電出版社，2012.21-30.

〔7〕汪翔，鮑皖蘇，呂詩飛.點(diǎn)乘運(yùn)算中整數(shù)表示方法研究[J].微計(jì)算機(jī)信息，2006，22（3-3）：240-242.

〔8〕盧開澄，盧華明.橢圓曲線密碼算法導(dǎo)引[M].北京：清華大學(xué)出版社，2008.101-102.

〔9〕MIIER B. Improved Techniques for Fast Exponentiation[C]. Information Security and Cryptology 2002 （LNCS 2587） [277]. Berlin： Springer Verlag， 2003： 298-312.

〔10〕MORAIN F， OLIVOS J. Speeding Up the Computations on An Elliptic Curve Using Addition-subtraction Chains[J]. Informatique Theorique et Applications， 1990， 24： 531-544.

〔11〕JEROME A. Efficient Arithmetic on Koblitz Curves[J]. Designs， Codes and Cryptography， 2000， 19：195-249.