標量乘法底層域快速算法研究＊

蔣輝芹

（泰州學院 教務處，江蘇 泰州225300）

0 引言

隨著全球經(jīng)濟一體化進程的推進和電子商務等網(wǎng)絡新業(yè)務的興起，人類已經(jīng)進入了信息化時代，計算機網(wǎng)絡的安全問題已引起全球范圍的高度重視.在計算機網(wǎng)絡中，密碼安全是保證信息安全的主要手段之一.在橢圓曲線密碼體制的實施過程中，仍存在一些缺陷和弊端，需要進一步改進和完善.一方面，如何合理地選擇橢圓曲線是需要深入探討的問題；另一方面，如何快速實現(xiàn)橢圓曲線密碼體制，提高實現(xiàn)效率，還需要進一步研究.在橢圓曲線密碼實施操作中，標量乘法所消耗的空間和時間資源最少，計算效率最高，因此可以用標量乘法計算橢圓曲線群，從而快速、準確的實現(xiàn)橢圓曲線密碼體制.近幾年，隨著標量乘法效率和準確性的不斷提高，推動了橢圓曲線公鑰密碼的發(fā)展，在各大領域得到了廣泛的應用.本文以基于標量乘法的橢圓曲線快速算法為主要內容進行研究.

1 預備知識

1985年，Koblitz、Miller等人［1］以橢圓曲線理論為依據(jù)，提出了ECC 橢圓曲線密碼體制.該密碼體制的優(yōu)點主要包括以下幾方面：單比特安全性高，可靠性強；可選擇性、可行性強，在基域不變的情況下，靈活性更高；計算機處理方便，基域GF（P）中的素數(shù)P可以根據(jù)需要主動選擇，如Mersene素數(shù)等；消耗的空間資源低，資源利用率高；具有較低的帶寬要求，無線、Smart卡等網(wǎng)絡環(huán)境都能適用.橢圓曲線密碼體制一經(jīng)提出，就引起了業(yè)界內的強烈反響.

假設已知大整數(shù)k和在橢圓曲線上的點P，求另一點kP稱為橢圓曲線上點的標量乘法［2］.這個運算過程可以分為兩個階段：①上層運算，形成有限阿貝爾群計算，點加橢圓曲線上的兩點；②底層運算，采用平方、乘法、求逆等算法，點加或倍加橢圓曲線上的點.因此，可以采用下列兩種方法計算變量乘法：

（1）為了減少點加運算的次數(shù)，提高運算效率，選擇有效的表達方式，準確、快速的描述標量k；

（2）改變以倍加、點加為主的傳統(tǒng)底層運算方法，擴展運算閾到3P、mP＋Q（m＝2，3，4）、2kP等，研究底層快速算法，提高底層運算效率［3］.

假設：E：y2＋xy＝x3＋ax2＋b，其中a，b∈F2m，b≠0，為二元域F2m上的橢圓曲線方差，點P＝（x，y）在橢圓曲線上，且P≠－P.可按下列公式計算：

在二進制域F2m的逆運算和乘法中分別用I和M表示，只需要移位操作就能實現(xiàn)二元域上的平方計算，倍點和點加的運算量為1I＋1M.

假設已知Q，計算滿足Q＝2P的點P是倍點計算的逆過程，稱為折半運算.在橢圓曲線E上，有一個n階（n為奇數(shù)）子群，用｛G｝來表示，可以推導出它的點的折半和倍點運算的自同構.假設已知Q∈｛G｝，必然能找到符合Q＝2P約束條件的唯一的點P∈｛G｝.將倍點運算用折半取代，能夠顯著減少計算量，提高標量乘運算的效率，計算量為2M.

近幾年，隨著數(shù)字處理技術和計算機技術的發(fā)展，底層快速算法逐漸成為研究焦點.1997年，Guajardo和Paar［4］針對底層算法的優(yōu)化，提出了4P，自此開創(chuàng)了底層快速算法研究的開端，并經(jīng)歷了有償代換－歸納推廣－多元優(yōu)化三個發(fā)展階段.1997年，Guajardo和Paar深入研究了底層快速算法，提出了有償代換的思想，為了減少逆運算的次數(shù)，用乘法運算來替代，將多個中間變量引入其中，4P、8P、16P的計算直接在F2m域上進行.1999年，Han和Tan［5，6］在有償代換思想的基礎上，提出了3P、5P、6P和7P在F2m域上直接計算的方法，顯著提高了計算效率.2003年，Ciet、Joye和Lauter以前人的研究結果為基礎，對2P＋Q、3P、3P＋Q、4P和4P＋Q的快速計算方法進行了深入的研究，明確了有償代換理論的本質，將逆運算用乘法運算來替代，顯著提高了計算效率.

對加法公式進行分析和研究發(fā)現(xiàn)，為了減少乘法運算，可以將部分中間變量省略、簡化或整合，減少mP、mP±Q的計算量，提高點乘運算的效率.然而，有限域、橢圓曲線類型、約束條件等制約了“有償代價”快速算法的發(fā)展，只適用于特定條件，無法滿足大部分條件的需求.2001年，Sakai和Sakurai［7，8］提出了2kP快速計算的通用算法，簡化、總結并整合了加法公式，顯著提高了算法效率.在存儲能力較高的條件下，為了減少運算量和運算時間，提高運算效率，與基點p相關的數(shù)據(jù)計算可以通過預計算和存儲來實現(xiàn)，提高標量乘計算固定基點的效率.Fixed-base Comb和Fixed-base Windowing是最廣泛使用的固定基點標量乘算法.

2 基于折半算法的comb算法

假設，k的二進制可以用（kl－1…k1k0）2來描述，

w為窗口寬度，w≥2，求解

在1～（wd－1）位補0，保證k滿足wd位，接著將k＝（kl－1…k1k0）2分為w段，用k＝Kw－1｜｜｜…｜｜K1｜｜K0來表示被分為w段的k＝（kl－1…k1k0）2.每個Kj都是二進制串，長度為d.用w行d列的矩陣描述k，可以參見下列公式：

已知橢圓曲線上一點P，對所有（aw－1，…，a1，a0）∈Z2w定義為：

算法描述如下，即Fixed-base comb算法：

輸入：橢圓曲線上的基點P，窗口寬度w，標量k＝（kl－1…k1k0）2.

輸出：kP.

（2）首先計算2dP，22dP，…2（w－1）dP，然后對所有的（aw－1，…，a1，a0）∈Z2w，預計算［aw－1，…，a1，a0］P.

（3）將k表示成w行d列的矩陣形式.

（4）Q←P.

（5）foriformodd－2down to 0.①pre＿B［0］＝P；for ifrom 0to c doQ←2Q；②for trfrom 0to r－1doR ＝O；Q＋［Kw－1i，…，K1i，K0i］P.

（6）ReturnQ.

上述算法的第2個步驟為預計算，第4和②步驟的操作以預計算結果組成的表為依據(jù).賦值階段是指上述操作中的第5步.可以按照下列兩步操作實現(xiàn)預計算：

①經(jīng)過（w－1）d次倍加運算，得到2dP，22dP，…2（w－1）dP；

②經(jīng)過2w－w－1次加法，計算全部滿足約束條件的點.

假設點加和倍點運算分別用A和D表示，則算法總運算量為：

在ECC中，經(jīng)常會使用Comb標量乘算法，是一種切實可行的算法，能夠有效解決標量乘的運算.為了提高算法的效率，改進和優(yōu)化Comb算法，可以從以下幾個方面入手：

（1）在二元域上，將耗費時間資源和空間資源的倍點運算用折半算法替代，減少計算量和計算時間，提高計算效率.在素數(shù)域中，在賦值階段，為了提高標量乘法的效率，用預計算表來描述，對矩陣進行動態(tài)掃描，2kP算法的計算以底層域的快速算法為基礎；

（2）在預計算階段，為了提高計算效率，擴大計算空間，提供充足的計算存儲容量；

（3）在標量重編碼階段，為了提高全零列的概率，將NAF編碼引入其中.

以下是改進的Comb標量乘算法：

輸入：P∈E＼O，行數(shù)r，窗口寬度w，標量k.

輸出：kp∈E＼O.

（1）將k寫成r行c列矩陣：①pre＿B［0］＝P；for ifrom 0to c do；②for trfrom 0to r－1doR ＝O；Matr（k，r，M）.

（2）對M 矩陣的0至r－1進行NAF編碼：

forifrom 1tor－1do

cB0B＝0；M［i］［c＋1］B＝0；M［i］［c］＝0；

forjfrom 0tocdo

【cj＋1＝［（cj＋M［i］［j］＋M［i］［j＋1］）／2］；M［i］［j］＝cj＋M［i］［j］－2cj＋1；】

（3）存儲預計算表pre＿B和pre＿Com：

forifrom 1tor－1do

pre＿B［i］＝dirD（P，c）；

forjfrom 0to 2w－1do

【pre＿Com［tr］［j］＝O；

Bin（j，b［0…w－1］；

Q＝O；

fortcfromw－1to 0do｛Q＝2Q；if（b［tc］）Q＝Q＋pre＿B［tr］；｝

pre＿Com［tr］［j］＝pre＿Com［tr］［j］＋Q；】

（4）使用Yen－Laih法計算標量乘法kP：

All＿Z［i］＝0；

Forjfrom 0tor－1do

All＿Z［i］＝All＿Z［i］∨M［j］［i］；

s＝find＿Z（All＿Z，i，w）－1；

if（s＞＝0）

【Q＝O；

fortrfrom 0tor－1do｛Dec（［Ktr，iKtr，i－1…Ktr，i－s］，p）；

if（p＞0）Q＝Q＋pre＿Com［tr］［p］；

else if（p＜0）Q＝Q－pre＿Com［tr］［－p］；｝

R＝dirD（R，s）＋Q；

i＝i＋s；】

elseR＝2R；

（5）ReturnR.

3 算法性能和效率分析

新算法中，用r行c列矩陣來描述Matr（k，r，M）的k，用M［0...r－1］［0…c－1］這個二維數(shù)組存儲矩陣的內容.2icP，i∈｛0，…，r－1｝存儲在pre＿B［0..r－1］中；2cP的直接計算方法用dirD（P，c）來描述.

存儲在pre＿Com［0…r－1］［0…2w－1］中.將j經(jīng)過Bin（j，b［0…w－1］）處理轉換成二進制序列，用b［0…wr－1］存儲該二進制序列.M 矩陣某列0至r－1行邏輯或的計算值存儲在All＿Z［0…c］.find＿Z（All＿Z，i，w）不會獲得w的值，會將All＿Z從i至i－w＋1零的位置顯示出來.M 矩陣經(jīng)過Dec（［Ktr，iKtr，i－1…Ktr，i－s］，p）的處理，二進制序列的第tr行第i列至第i－s列會轉換成十進制數(shù)p.

接下來，對改進算法的效率進行檢測和研究.

（1）可以忽略其運行時間，只進行重組二進制序列的操作.

（2）用NAF編碼矩陣的每一行，零和非零的概率分別是2／3和1／3，原始矩陣某一列為全零的概率為（1／2）r，改進算法的概率為（2／3）r.

（3）經(jīng)過r－1次dirD 運算得到pre＿B，經(jīng)過點加運算r2w（w／2＋1）次和倍加運算rw2w次獲得pre＿Com 表.

（4）忽略全零列的影響，可以忽略使用Yen-Laih法計算標量乘法kP中的①和②消耗的事件資源，點加和dirD 運算分別要進 行c／w＊（r＋1）次和c／w次.下列公式的計算結果考慮了全零列的影響.

如表1所示，為傳統(tǒng)Comb算法和本文提出的改進算法的計算量.由表1可知，本文提出的改進算法計算量大幅減少，計算效率顯著提高.

表1 底層運算的計算量

可以忽略重編碼所消耗的時間，無需頻繁更改預計算表，因此賦值階段的效率決定了ECC 的效率，直接影響Comb標量乘算法的整體效率.

在網(wǎng)絡安全、密鑰加密等實際應用領域中，橢圓曲線公鑰密碼的發(fā)展前景最為廣闊，其具有理論高深、安全度高、可靠性強等優(yōu)點，在各大領域得到廣泛應用.在橢圓曲線密碼系統(tǒng)中，點的標量乘法是該系統(tǒng)的靈魂和關鍵，系統(tǒng)的穩(wěn)定性、整體效率直接取決于該點標量乘法的效率.改進的Comb標量乘算法從三個方面提出了優(yōu)化途徑和措施，保證了計算結果的準確性，提高了算法的效率.

［1］張寶華，殷新春.橢圓曲線公鑰密碼體制中標量乘法運算快速算法的研究［D］.揚州大學碩士學位論文，2004.

［2］汪彩梅，殷新春.安全橢圓曲線選取算法及其應用［D］.揚州大學碩士學位論文，2006.

［3］張寧，肖國鎮(zhèn).橢圓曲線上點的標量乘法［D］.西安電子科技大學碩士學位論文，2005.

［4］侯整風，李嵐.橢圓曲線密碼系統(tǒng)（ECC）整體算法設計及優(yōu)化研究［J］.電子學報，2004，32（11）：1904～1906.

［5］殷新春，張寶華.公鑰密碼中大數(shù)模冪的并行窗口算法［J］.計算機工程與應用，2004（18）：50～53.

［6］郝林，羅平，彭小寧.一種改進的橢圓曲線離散對數(shù)快速冗余算法［J］.計算機研究與發(fā)展，2004，41（1）：79～82.

［7］唐禮勇，陳鐘.基于Markov鏈的橢圓曲線標量乘法算法性能分析［J］.電子學報2004，32（11）：1778～1781.

［8］白國強，周濤，陳弘毅.一類安全橢圓曲線的選取及其標量乘法的快速計算［J］.電子學報，2002，30（11）：1654～1657.