基于二進制的相鄰表示型多位生成算法研究

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

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

關鍵詞：二進制;非相鄰表示型;多位生成;標量乘

中圖分類號：TN918.4? 文獻標識碼：A? 文章編號：1673-260X（2019）09-0086-04

1 引言

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

2 非相鄰表示型（NAF）

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

文獻[1]的定理3.29給出了正整數k的NAF表示的如下性質：

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

（2）k的NAF（k）具有最少的非零數;

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

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

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

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

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

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

3 基于二進制的NAF多位生成算法

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

3.1 基于二進制的NAF兩位生成算法

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

為了進一步優(yōu)化算法，本文在k為偶數時進行了優(yōu)化.優(yōu)化算法為基于二進制的NAF多位生成算法，優(yōu)化的前提是k在計算機中是以二進制形式存放的，當然這也是我們無需特意轉換的，因為正整數k在計算機中就是以二進制形式存放的.這里為了更好地闡述基于二進制的NAF多位生成算法假設正整數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)一起計算，所以循環(huán)次數要較算法3.30少兩次，從執(zhí)行速度看上有所提高，但是在算法3.30的第3次和第4次循環(huán)上我們發(fā)現對于連續(xù)的兩個0來說，在NAF表示時也是兩個0，因此在這種情況下就可以進一步優(yōu)化算法得到算法1所示的基于二進制的NAF兩位生成算法.

算法1 基于二進制的NAF兩位生成算法

INPUT：正整數k.

OUTPUT：NAF（k）.

1.i=0;

2.k≥1時，重復執(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計算NAF（113）的過程如表4所示.

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

算法中無論k值是奇是偶，只要大于等于1，就取k的最后兩位，其實就是k對4取余.因為k在計算機中以二進制形式存放，對4取余就等同于取k的最右兩位，這樣做也是因為位操作只需要一個指令周期，而取余運算需要調用子程序來完成，代碼不僅長而且執(zhí)行速度慢.同理算法3.30中的除法運算k=k/2也被替換成了位操作k=k>>1，k=k/4替換成k=k>>2.算法1中t有四種取值：

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

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

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

（4）t=（11）2，即t=（3）10，k為奇數，ki=2-（kmod4）=-1，根據NAF性質必有ki+1=0，步長加2，算法3.30中的k=k-ki，因為ki=-1，因此k=k+1，再右移兩位.

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

3.2 基于二進制的窗口寬度w的NAF多位生成算法

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

算法2 基于二進制的窗口寬度w的NAF多位生成算法

INPUT：正整數k，窗口寬度w.

OUTPUT：NAFw（k）

1.i=0;

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

若k為奇數，則

（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的值，按值進行下列操作：

（1）末尾1個0：

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

（2）末尾2個0：

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

……

（w）末尾w個0：

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

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

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

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

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

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

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

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

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

4 算法分析及驗證

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

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

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

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

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

當k為163位時，對表4中的幾種算法進行C建模，運行于Linux平臺，運行結果見表6.

從實驗結果可以看到本文算法1較算法3.30的運算效率平均提高了50%左右.

5 結語

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

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

（2）經建模驗證效率提高50%左右，時間復雜度明顯變小.

——————————

參考文獻：

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

〔2〕蔣洪波，尚春雨，馮新宇.NAF算法的改進[J].科學技術與工程，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〕李忠，張永華.整數的最佳帶符號二進制表示的隨機生成算法[J].計算機科學，2014，41（11A）：282-283.

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

〔7〕汪翔，鮑皖蘇，呂詩飛.點乘運算中整數表示方法研究[J].微計算機信息，2006，22（3-3）：240-242.

〔8〕盧開澄，盧華明.橢圓曲線密碼算法導引[M].北京：清華大學出版社，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.