趙石磊，楊曉秋，劉志偉，于 斌，黃 海

（哈爾濱理工大學計算機科學與技術學院，黑龍江哈爾濱 150080）

1 引言

橢圓曲線密碼體制的核心運算主要是橢圓曲線群上的標量乘法，它的運算速度決定著密碼系統(tǒng)整體執(zhí)行效率［1］. 一般來說，標量乘算法可分為兩種：無預計算算法和有預計算算法. 無預計算算法包括二進制算法（Double and Add，D&A）［2］、非鄰接表示算法（Non-Adjacent Form，NAF）［3］、多基鏈表算法（Double-Base Chain，DBC）［4］和相反形式算法（Mutual Opposite Form，MOF）［5］等，這些算法大都存在著計算復雜度過高的問題. 為降低計算復雜度，學者們提出了有預計算算法，如滑動窗口算法［6］、窗口非相鄰算法（window width-Non-Adjacent Form，wNAF）［7］、加法鏈算法［8］、利用素數代替奇數進行預計算并通過構建多基鏈來彌補素數與奇數之間的差值算法［9］、帶門限的動態(tài)窗口的NAF 標量乘法［10］等. 文獻［8］所提加法鏈算法相比較其他加法鏈算法計算復雜度降低了4%～18%. 文獻［9］的計算復雜度相比于wNAF 優(yōu)化了28.37%. 在文獻［10］中，帶門限的動態(tài)窗口的NAF 標量乘法的預計算量僅為基于Moller 碎片窗口技術的標量乘法的30%、基于固定窗口改進后的NAF 標量乘法的25%，其預計算利用率比基于Moller 碎片窗口技術的標量乘法提高了15%左右，比基于固定窗口改進后的NAF標量乘法提高了12%左右. 文獻［11］則提出了Alternate-Zeckendorf 表示算法，可以用加法鏈序列表示任何標量k，此算法比其他算法的成本至少降低12.7%. 文獻［12］提出了基于窗口的NAF 算法，當n={192，224，256，384}時，預計算效率提高了26.35%，當n=521時，預計算效率提高33.59%.

以上算法雖然取得了較好的結果，能夠有效降低標量k的漢明重量，減少點加操作的次數，降低標量乘的計算復雜度，但是仍然存在著不適用于窗口寬度較大、使用寄存器較多、預計算量過大等問題. 針對以上問題，本文設計了一種低復雜度的改進wNAF 算法，首先在預計算階段用2nP替換(2h-1)P（wNAF 算法中奇數與基點P的乘積），再用2nP構造加法鏈來補償2nP與(2h-1)P之間的差值. 然后，為解決隨著窗口寬度的增大，2nP與(2h-1)P之間差值過大的問題，采用有符號的wNAF 算法將標量k的二進制鏈轉換成有符號的wNAF 鏈，能將該差值范圍縮小為原來的50%，極大地減少了點加次數. 最后，實驗結果證明，所設計的算法具有所需寄存器數量少以及計算復雜度低等優(yōu)點.

2 橢圓曲線標量乘算法分析

2.1 窗口非相鄰（wNAF）標量乘

橢圓曲線標量乘法是橢圓曲線密碼系統(tǒng)中最關鍵（也是消耗資源和能量最多）的步驟，是橢圓曲線上一個點P與一個隨機的整數k的乘積，即Q=kP=P+P+…+P. 由于在雅可比坐標下，倍點的運算消耗小于點加，因此通常做法是將k進行轉換以減少其中點加次數，如wNAF 標量乘算法［13］. wNAF 標量乘算法通過將二進制形式的標量k轉化為wNAF 形式，構建一條wNAF 鏈，即其中ki∈{±1，±3，…，±(2w-1)}，m表示wNAF 鏈中的非零數字個數，λi是wNAF 鏈中每個非零數ki所在的位置. 實現標量乘時，通過調用已預計算并存儲的點{±P，±3P，…，±(2w-1)P}，其中w是窗口寬度，可極大地減少運算時的計算量.wNAF 的具體實現如算法1所示.

該算法整個過程分成3 個階段：wNAF 序列生成階段（步驟1 到步驟12）、預計算階段（步驟13）和算數運算階段（算數運算包括點加運算和倍點運算，步驟14到步驟20）.wNAF 是通過降低標量k的漢明權重、減少點加運算來降低算法的復雜度. 假設在wNAF 鏈{ki}中有非零數字m個，第i個非零數字是ki，λi是wNAF 鏈中每個ki所在的位置，則有λi-λi-1≥w+1，顯然，wNAF 的非零概率為1( )w+1，預計算階段和算數運算階段的成本分別為2w-1A+D 和，所以標量乘計算量為，其中A 是點加運算，D 是倍點運算，且有1A=12M+4S，1D=4M+6S［14］以及0.8M=1S［15］（M 是模乘運算，S 是模平方運算）. 然而，wNAF 標量乘算法也存在一定的問題：當窗口寬度增大的時候，預計算點的個數呈指數增長，大大增加了預計算量和所需的寄存器數量.

算法1 帶符號的wNAF標量乘算法輸入:標量k,基點P,窗口寬度w輸出:標量乘結果Q 1)i=0 2) While k ＞0 do 3) If k mod 2=1 then ei=k mod 2w+1;4) If ei ≥2w then ei ?ei-2w+1;5) End if 6) k ?k-ei;7) Else 8) ei=0;9) End if 10) k ?k/2; i ?i+1;11)End while 12)return{ki-1，ki-2，…，k1，k0}13)預計算:Pi=iP，i ∈{1，3，5，…，2w-1}14)for i from b-1 to 0 do 15) Q ?2Q;16) If ki ≠0 then 17) If ki ＞0 then Q ?Q+Pki;18) If ki ＜0 then Q ?Q-Pki;19) End 20)End

2.2 加法鏈標量乘算法

文獻［16］進行加法鏈標量乘運算時，首先構造一條加法鏈，定義為一個序列v=(v1，v2，…，vl)，其中，v1=1，v2=2，vi=vi-1+vi-2(3 ≤i≤l)，l是加法鏈的長度，標量k由加法鏈序列中若干個vi組成，表示成其次，將vi與基點P相乘并存儲；最后，只需點加操作即可得到標量乘的最終結果. 加法鏈標量乘算法如算法2所示.

算法2 加法鏈標量乘算法輸入:標量k,基點P輸出:標量乘結果Q 1)通過貪心算法得到k的加法鏈(v1，v2，…，vl)2)Q ?0;3)for i from 1 to l do 4) Q ?Q+vi;5)end 6)return Q

如算法2所示，步驟1是得到k的加法鏈的過程，貪心算法用于每次在加法鏈中尋找最接近ki的元素vi，然后再利用ki和vi的差值在加法鏈中找到最接近該差值的vi，進而可以得到標量k的加法鏈；步驟2～6是計算標量乘的過程，這部分只需要進行點加操作而不需要進行倍點操作即可得到標量乘的結果. 此外，由于生成k的加法鏈需要用到貪心算法，隨著k位數的增加，創(chuàng)建加法鏈所用的時間也會越長.

3 低計算復雜度的wNAF算法設計

3.1 基于2n p預計算

眾所周知，wNAF 算法在預計算階段將{±P，±3P，…， ±(2w- 1)P}存儲起來用于加速標量乘的計算，但隨著窗口寬度w的增大，預計算點的個數呈指數增長，使得該算法不適用于窗口寬度較大的情況. 本部分針對該問題，對wNAF 算法進行改進，減少預計算點以降低wNAF算法的標量乘計算復雜度.

由于倍點運算相較于點加運算、3 倍點運算和5 倍點運算需要較少的模乘次數，同時由于2n構成的集合中元素比3n，5n構成的集合中元素更加密集，2n與奇數之間的差值更小，有利于構造差值的加法鏈. 此外，考慮到在進行算數運算時也需要進行倍點運算，倍點運算結構可以通過控制器控制，反復利用，節(jié)省資源. 本文的思路是：在預計算階段用2n代替生成的wNAF鏈中的奇數，只預計算并存儲2nP. 這種替換的優(yōu)勢在于能夠大大減少預計算點的個數且預計算點只需要通過倍點運算即可得到. 例如：當窗口為5時，wNAF 算法需要存儲{P，3P，…，31P}，共計16 個點；而本文算法只需要存儲{20P，21P，…，25P}，共計6個點. 表1列出了在不同窗口寬度下所需預計算的點及個數.

表1 預計算點及個數

3.2 基于2n p的加法鏈的差值補償

由3.1 節(jié) 中 可 知，用{20P，21P，…，2nP} 代 替{P，3P，…，(2w-1)P}會產生差值. 例如當窗口寬度為w=5 時，本文預計算點為{20P，21P，…，25P}，wNAF 算法預計算點為{P，3P，…，31P}，若wNAF 鏈中存在非零數17時，24P與17P最接近，但存在差值P；當wNAF鏈中存在非零數21 時，24P與21P最接近，存在差值5P；當wNAF鏈中存在非零數23時，24P與23P最接近，存在差值7P.不同窗口寬度下的預計算點與wNAF 預計算點之間可能存在的差值如表2所示.

由表2 可知，本文預計算與wNAF 預計算之間的差值為奇數，且隨著窗口寬度的增加，該差值的最大值也不斷增加，當窗口寬度在5～11范圍內時，差值的最大值為511P.

表2 本文預計算點與wNAF預計算點之間的差值

由于任意一個標量k都可以用二進制表示并且在預計算階段已經完成了對2nP的計算和存儲，因此2nP與(2h-1)P之間的差值Δ可以通過構造2nP加法鏈來補償. 由第2.2 節(jié)可知，加法鏈是將一個大數拆分成若干個小數，在計算時，通過若干個小數相加減得到結果.因此，差值Δ 可以基于加法鏈的思想由多個2nP相加減得到，即Δ=∑2nP. 例如：在窗口寬度為w=5 時，已知wNAF 鏈中存在非零數13，且已有預計算點{20P，21P，22P，23P，24P，25P}找到與13P最接近的24P，24P與13P之間的差值為3P，3P則可以表示為22P-20P，最終13P=24P-22P+20P. 此外，根據表2，當窗口寬度為11 時，構造的加法鏈最長，需要4 次點加運算，例如：差值為299P時，299P的加法鏈可以構造為299P=28P+25P+23P+21P+20P.

3.3 改進的wNAF標量乘算法

根據第3.1 節(jié)和第3.2 節(jié)，可以總結出本文的算法：通過算法1生成wNAF鏈，用2n代替wNAF鏈中的奇數，在預計算階段，將2nP預計算出來，在算數運算階段，通過搜索k鏈中的非零數值ki，2nP與kiP之間的差值通過構建微小的2nP加法鏈來實現，最后再通過一系列的點加運算和倍點運算，得到標量乘的最終結果. 改進的wNAF標量乘算法如算法3所示.

算法3 中，步驟1～2 是預計算部分，根據窗口的大小預計算2nP；步驟3～37 是算數運算階段. 步驟8～10用于尋找與wNAF 鏈中非零數值最接近的2nP，此時，在查找k鏈時會分成兩種情況，一種是k鏈中的非零數值小于0 的情況，執(zhí)行步驟11～22；另一種是k鏈中的非零數值大于0 的情況，執(zhí)行步驟23～34. 此外，步驟11～12 以及步驟23～24 用于得到2nP和(2h-1)P之間的差值Δ；步驟14～19 以及步驟26～31 是構造差值Δ 的加法鏈的過程，先找到與Δ 接近的2nP，計算它們的差值，再找到與該差值接近的2nP，以此類推，迭代找到構成Δ的2nP加法鏈add1，最終得到標量乘結果.

算法3 改進的wNAF的標量乘算法輸入:標量k,基點P,窗口寬度w輸出:標量乘結果Q 1)預計算:2) Pi=2iP，i ∈{0，1，2，…，w}3)標量乘計算:4) Q ?0;add1 ?0;5) for i from b-1 to 0 do 6) Q ?2Q;7) add1 ?0;8) If ki ≠0 then 9) s ?Findnearst(|kiP|) //找到最接近|kiP|的2nP;10) add ?Findnearst(|kiP|);11) If ki ＜0 12) a ?kiP+s;13) j ?0;14) While(a ≠0)15) tj ?Findnearst(|a|);16) a ?|a|-tj 17) j ?j+1;18) End 19) add1 ?∑tj;20) If a ≥0 then add ?add1-add;21) Else add ?-add-add1;22) End 23) If ki ＞0 24) a ?kiP-s;25) j ?0;26) While(a ≠0)27) tj ?Findnearst(|a|);28) a ?|a|-tj 29) j ?j+1;30) End 31) add1 ?∑tj;32) If a ≥0 then add ?add-add1;33) Else add ?-add-add1 34) End 35) Q ?Q+add;36) End 37) End

3.4 算法計算復雜度分析

結合第3.1 節(jié)、第3.2 節(jié)、第3.3 節(jié)得到的本文算法，下面對算法的復雜度進行分析.

預計算部分：計算2nP時，窗口寬度為w，則需要進行w次倍點，例如，當w=5時，預計算點為{20P，21P，…，25P}，需要進行5次倍點，所以預計算的成本為

算數運算部分：設wNAF 鏈長為n，則需要進行n次倍點操作，由文獻［12］可知wNAF 的漢明重量為則k鏈中一共有個非零數字，需要進行次點加，當窗口寬度w=5 時，在構建2nP與(2h-1)P差值的加法鏈時，需要額外進行一次點加運算的點的個數占k鏈中非零數字的1/4，需要額外進行兩次點加運算的點的個數占k鏈中非零數字的3/4，因此需要額外進行次點加運算，一共需要進行次點加運算，并且窗口寬度每增加1，點加次數多增加，算數運算階段一共所需的成本為

標量乘部分：標量乘成本=預計算成本+算數運算成本，即

通過將1A=12M+4S，1D=4M+6S［14］以及0.8M=1S［15］代入到式（1）、式（2）和式（3）可以得到以模乘次數為標準的預計算計算復雜度、算數運算計算復雜度和標量乘計算復雜度，結果如圖1所示.

圖1 表示了以模乘次數為標準的本文算法在不同窗口寬度、不同曲線下的計算復雜度曲線. 計算復雜度包括預計算計算復雜度、算數運算計算復雜度和標量乘計算復雜度；曲線包括P256，P384和P521，窗口寬度范圍為2～12. 由圖1可以看出，對于所有曲線，窗口寬度為11時，標量乘計算復雜度最?。淮翱趯挾刃∮?時，標量乘計算復雜度要高于窗口寬度為5時. 而當窗口寬度大于11時，由于2nP與(2h-1)P之間的差值過大，不利于構建基于2nP的加法鏈. 根據以上結果，本文后面對算法的比較與分析都將窗口寬度限制在5～11的范圍內.

圖1 低復雜度的改進wNAF標量乘算法在不同窗口下的計算復雜度分析

4 算法計算復雜度比較

4.1 預計算計算復雜度比較

為了更直觀、更清晰地觀察本文算法在預計算方面有優(yōu)勢，將提出的算法與目前研究比較多的wNAF 算法［17］、滑動窗口非相鄰形式算法（swNAF算法）［18］和基于素數預計算的算法［9］進行了比較，比較結果如表3所示.

由表3 可以看出，相較于wNAF 算法、swNAF 算法和基于素數預計算的算法，本文算法在窗口寬度為5～11 時預計算點的個數減少，而在窗口寬度為11 時預計算點個數減少最多，分別減少了1 013 個、330 個和204個，減少的百分比分別為98.83%，96.49%和94.42%. 此外，當窗口寬度增加時，本文算法的預計算點的數量減少的百分比也隨之增加，說明本算法比其他算法更適用于窗口寬度較大的情況.

表3 預計算點比較

表4 顯示了當窗口寬度為5～11 時預計算點所需的模乘次數的比較，其中，倍點運算（用D 表示）根據1D=4M+6S 以及0.8M=1S 進行轉換. 從表4 可以看出，相較于wNAF 算法、swNAF 算法和基于素數預計算的算法，在窗口寬度為5 時，本文算法在預計算的模乘次數分別減少了81.95%，70.19%和74.19%，在窗口寬度為11 時，預計算的模乘次數分別減少了99.38%，99.07%和97.83%. 由此可知，在窗口寬度5～11 時，本文算法的預計算復雜度最低. 此外，隨著窗口寬度的增加，本文算法預計算所需模乘次數減少的百分比也隨之增加，也說明了本文算法更適用于較大窗口.

表4 預計算點所需的模乘次數比較

4.2 標量乘計算復雜度比較

標量乘計算復雜度包括了預計算計算復雜度以及算數運算計算復雜度兩部分，在第4.1節(jié)已經對預計算計算復雜度進行了對比，表5 顯示了當n為256，384，521 時，4 種算法的算數運算計算復雜度和標量乘計算復雜度對比. 由表5 可以看出，本文算法在算數運算部分的計算復雜度與其他3種算法相當，但窗口寬度增加時，本文算法的預計算優(yōu)勢越明顯. 并且隨著窗口寬度增大，在相同位數下，有符號wNAF 鏈中非零個數相比無符號wNAF 鏈中更少，這也進一步減少點加次數，從而降低標量乘的計算復雜度. 此外，在窗口寬度較大時w=11 時，本文算法的標量乘計算復雜度相較于wNAF算法、swNAF 算法和基于素數預計算算法降低了最多，分別為78.23%，68.94%和43.63%.

表5 4種算法總體計算復雜度對比

5 結論

本文提出了在有符號wNAF算法的基礎上，在預計算階段采用2nP替換(2h-1)P，替換后的差值采用2nP構造的加法鏈進行補償，該方法有效降低了預計算復雜度，并且只需要少量的寄存器即可完成預計算點的存儲，進而解決了有預計算算法不適用于窗口很大的問題. 與現有的算法相比，預計算所需模乘數相較于wNAF 算法、swNAF 算法和基于素數預計算算法最多減少了99.38%，99.07%和97.83%，標量乘的計算復雜度分別降低了78.23%，68.94%和43.63%.