基于重編碼的快速標量乘算法

摘 要：采用回溯法設計出一種重編碼算法。該算法只需對標量序列進行一次變換、至多四個中間變量，以及只需基于比特位比較賦值操作，效率更高，利于硬件實現標量乘法，并證明了所得結果具有正則序列的性質。該算法應用到計算數字簽名中常用的gP+hQ時，得到g、h的具有最小聯合重量序列。

關鍵詞：橢圓曲線密碼體制；標量乘法；重編碼；gP+hQ；硬件設計

中圖分類號：TP309．7；TP301．6 文獻標志碼：A

文章編號：1001-3695(2008)07-2143-03



Fast algorithm of scalar multiplication based on recoding

YIN Xinchun， HOU Hongxiang



(Dept.of Computer Science Engineering， Yangzhou University，Yangzhou Jiangsu 225009， China)

Abstract: This paper designed a recoding algorithm which scans the sequence of the scalar only once， employed four intermediate variables at most as well as comparisons and evaluations on digits. The algorithm was more efficientand more convenient to application of scalar multiplication on hardware. The result is proved to possess the character of the canonicalrepresentation. When the algorithm is applied to compute gP+hQin digital signatures，the result is unique，optimaland has the least joint weight.

Key words：ECC; scalar multiplication; recoding；gP+hQ; hardware design

ECC最基本、最耗時的運算是橢圓曲線上的標量乘法：已知域中整數k和橢圓曲線上的點P，求橢圓曲線上另外一點kP的運算。常用方法為二元法，標量k表示成k =am-12m-1+am-22m-2

B(k)= (am-1am-2…a1a0)為k的二進制序列，標量乘法的效率取決于B(k)的長度和海明重量（非零量的個數）。其中：長度決定橢圓曲線上倍點運算（計算2P）的次數；海明重量決定橢圓曲線上點加運算（計算P+Q）的次數。由P求P在橢圓曲線上是很容易實現的，計算量幾乎可忽略。

研究減少B(k)海明重量的方法，一般有兩種途徑：a）直接把十進制整數k表示成符號二進制序列，如NAF^[1]、JSF^[2]、wNAF^[3]等算法；b）由B(k)轉換為符號二進制序列，如Reitwiesner算法^[4]、KT方法^[5]、M.Joye等人^[6]給出的算法、R.S.Katti等人^[7]設計的算法等。

本文的研究主要集中于第二種情況，創新點是重新編碼標量序列，使其擁有更少的海明重量。設計出重編碼算法：由標量k的二進制序列轉換為海明重量最小的符號二進制序列，而且速度更快，需要更少的存儲空間，利于硬件設計。

1 常用重編碼算法

1．1概念

引理1設n為某一正整數，則對任一正整數i，有

2n+i+2n+(i-1) +…+2n+1+2n = 2n+(i+1)-2n

證明 用數學歸納法證明，具體證明過程略。

引理1 可以將多個連續的1表示成只有首尾兩個非零量序列，要想減少原序列的海明重量，只需令引理1中的i＞2。

定義1在符號二進制數系統中，任何正整數k可以表示成

二進制序列是一種特殊的符號二進制序列，且一個整數可以由多種不同的符號二進制序列來表示。

定義2相同整數的兩種符號二進制序列具有相等的位長與海明重量，則稱這兩種序列等價。

定義3如果某序列中任意相鄰兩位的乘積ai+1×ai = 0，則稱該序列正則。

定理1^[4]在符號二進制序列中，正則數具有最小海明重量。

1．2Reitwiesner算法

從上面三步可以看出：該算法就是模擬一個加法器，實現3k+(-k) = (k+2k)+(-k)，最后舍棄0位所得。設3k =

以及結果3k+(-k) =r0+∑mi=1r′i2i

符號二進制序列是正則的。

1．3KT方法

將k的二進制序列中B(k)=(1，di，1)這樣的片段轉換為T(k)=(10，di-1，1)，很明顯在T(k)中原來的di是0變為1，原來的di是1變為0，如B(k)=(1，1101，1)(d3d2d1d0 = 1101)經過KT方法變為T(k)= 10，0010，1。如果用#(0)表示B(k)中0的個數，#(1)表示B(k)中非0的個數，那么T(k)中非0個數是#(0)+2，T(k)中0個數是#(1)-1，變化的目的是減少非0的個數，必須#(1) > #(0)+2時，KT變換才有意義，如果定義D(B)=#(1)-#(0)，那么必需滿足D(B)> 2。

2 新的重編碼算法

2．1位與法

如圖1所示，2k按位與k得到一個序列(smsm-1sm-2…s0)，當片段(0，si+t…si+1si，0)=(0，1，…，11，0)時，令(ri+t+1，ri+t，…，ri+1ri，ri-1)=(1，0，…，00，-1)。經過變換，k的二進制序列轉換成一種符號二進制序列，要使海明重量比原序列小，只需令t>2。

經過這種變換，1串相隔0的個數在兩個以上時，結果與正則序列等價，但1串間隔0的個數只是1時，需要考慮1串長度為2的情況。很明顯這種方法沒有考慮變換后的情況，且必須動態地計算t，使用了太多的中間變量。

2．2標量重編碼算法

采用基于比特位的回溯修改法來彌補上面的缺陷。如果當前位和下一位都是1，那么把當前位修改為0，前一位修改為1，并令借位標志carry為1，其余為0；由于有借位，每次修改之前都把當前位減去兩倍的前一位借位carry。經過上面的操作后，序列中將出現11片段，這時需要將其轉換成01，減少序列的海明重量。同時為了增加平均0串長度，將得到的序列中101轉換成001；101轉換成011。

引理2任何二進制序列經過算法1的（a）~(d)步后變為正則序列。

綜上所述，假設錯誤，所以對于任意i都滿足r′i+1r′i=0，任何二進制序列經過算法1的（a）~（d）步后變為正則序列。得證。

定理2算法1得到的符號二進制序列與這個數的正則序列等價。

證明 由引理2可知：任何二進制數經過算法1的（a）~（d）步后，得到正則數，即NAF。而（e）步和第（c）步是將1、0、1替換為0、1、1，（f）步是將1、0、1替換為0、1、1，海明重量沒有變化。所以算法1得到的符號二進制數與這個數的NAF有相同的海明重量，而所有的操作并不會改變序列位長，

所以結果與正則序列等價，得證。

3 算法分析

在使用符號二進制序列計算橢圓曲線上標量乘法時，連續零串的長度越大，用窗口算法劃分的窗口數就越少。為了衡量得到的符號二進制序列(r′mr′m-1r′m-2…r′0)中連續零的平均長度，這里引用R.S.Katti等人^[7]定義的一個連續零因子M(k)。

定義4M（k）=1/（m+1）∑mi=0Z(i)。其中：若r′i = 0，Z(i)=1+Z(i-1)；若r′i≠0，Z(i)=0。

隨機選取整數k=27 397 720 139 715，將該整數的二進制序列作為輸入，經過Reitwiesner算法、KT方法以及算法1后的情況，如表1所示。

算法連續零因子算法連續零因子

原始序列1．26KT方法1．43

Reitwiesner算法1．37算法21．52

從表1可以看出，算法1的連續零因子大于原始序列、Reitwiesner算法和KT方法，而且算法1效率更高，因為Reitwiesner算法需要不斷地進行除法和加法運算，消耗了大量的時間；KT方法需要動態計算D(B)的大小，只有D(B)>2時才轉換，使用這種方法在確定最低有效位時比較困難。

對于長度為m的二進制序列，以上三種算法在算術運算、計數運算、循環次數、判斷次數、賦值次數、中間變量以及1 000個192 bit二進制序列的平均時間上進行比較，得到表2。

從表2中可看出，算法1是基于比特位的簡單判斷和賦值操作，沒有Reitwiesner算法復雜的算術運算及KT方法的動態計數運算，同時還可以看出算法1使用的中間變量至多4個，復雜度明顯低于前兩種算法，執行效率更高。

4 硬件電路圖

定義0、1及1分別為(00)、(10)及(11)，本文給出從左到右的重編碼電路圖（圖2）。 圖中從左到右四個三態門部分分別實現算法1中步驟(c)~（f）的功能，每次i移動時只需將carry賦予riL、將ri-1賦予riH ，即實現算法1中（a）步驟的功能。從圖2中可以看出，輸入第i位時才可以輸出第i+2位，還須根據第i-1位的情況進行轉換。



假設使用從左到右的平方乘算法計算橢圓曲線的標量乘法，從左到右的重編碼電路可以與標量乘法同步進行（圖3）。啟動部件使得標量乘法從第一位非零量開始，MUX部件是實現ri+2HP的功能，NEG部件實現當ri+2L為1時P的功能，點加運算實現計算形如P+Q的功能，倍點運算實現計算形如2P的功能（P、Q都是橢圓曲線上的某點）。

5 應用于計算gP+hQ



標量乘法kP也可以通過下面的式子來計算：

數字簽名就經常需要計算gP+hQ形式^[8]。其中：g、h是整數；P、Q是橢圓曲線上的點。在這種情況下，文獻[9]中引用的Shamir算法表明g和h的聯合重量決定了計算gP+hQ的速度。聯合重量是g、h的二進制序列中相同位不全為零的數目。例如十進制整數g=6 699和h=4 846，二進制表示是

聯合重量是9。經過算法1得到序列：

聯合重量是9。

雖然結果可能不同，但是算法1與JSF算法都得到最小的海明重量。下面給出本文重編碼在計算gP+hQ方面的兩個性質：

a)惟一性。任何一對整數經過算法1，得到惟一確定的符號二進制序列；

b)最佳性。算法1得到的符號二進制序列，在給定整數的符號二進制序列中，聯合海明重量最小。

6 結束語

本文主要集中于減少標量k符號二進制表示的海明重量，從而減少計算標量乘法kP時所需的點加運算。重編碼算法的結果是正則的。當該算法應用到計算gP+hQ時，結果與JSF算法效果一樣，都具有相同的聯合重量。但本文算法沒有涉及到模運算，執行效率上更高。



參考文獻：

［1］ LOPEZ J， DAHAB R. An overview of elliptic curve cryptography[R]. Brazil: Institute of Computing， State University of Campinas， 2000.

[2] SOLINAS J A. Lowweight binary representations for pairs of integers[EB/OL]. (2001). http://www.cacr.math.uwaterloo.ca/techreports /2001/corr2001-41.ps .

[3] KATSUYUKI O， KATJA S S， CHRISTIAN S， et al. Signed binary representations revisited[C]//Proc of LNCS.[S.l.]:SpringerVerlag， 2004:123.

[4] REITWIESNER G W.A binary arithmetic[J]. Advances in Computers，1960，19(1):231-308.

[5] KOYAMA K， TSURUOKA Y. Speeding up elliptic cryptosystems by using a signed binary window method[C]//Proc of Advances in CryptologyCrypto’92. [S.l.]: SpringerVerlag， 1993.

[6]JOYE M， YEN S M. Optimal lefttoright binary signeddigit recoding[J]. IEEE Trans on Computers，2000，49(7):740-748.

[7] RUAN Xiaoyu， KATTI R S. On the signedbinary window method[C]//Proc of IEEE Internationd Symosium on Circuits and Systems. 2005:4501-4504.

[8] GRABNERA P J， HEUBERGERB C， PRODINGERC H. Distribution results for lowweight binary representations for pairs of integers[J]. Theoretical Computer Science，2004，319(1-3):307-331.

[9] ELGAMAL T. A publickey cryptosystem and signature scheme based on discrete logarithms[J]. The IEEE Trans on Information Theory，1985，31(14):469-472.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”