武永波，彭青松，高茂庭

（上海海事大學(xué)信息工程學(xué)院，上?！?01306）

基于雙基鏈的快速標(biāo)量乘算法研究

武永波，彭青松，高茂庭

（上海海事大學(xué)信息工程學(xué)院，上海201306）

在有限域GF（2m）上，實(shí)現(xiàn)橢圓曲線密碼體制（ECC）中關(guān)鍵運(yùn)算是標(biāo)量乘算法，該算法也是橢圓曲線密碼體制中耗時(shí)最長、極易受到攻擊的運(yùn)算之一。為了提高橢圓曲線密碼算法計(jì)算的安全性和效率性，從分析以2、3為底的雙基鏈橢圓曲線標(biāo)量乘特點(diǎn)出發(fā)，在現(xiàn)在有的雙基鏈算法基礎(chǔ)之上，提出一種新的快速標(biāo)量乘算法。新算法中，通過應(yīng)用米勒算法和2-3鏈相結(jié)合的方法，尋找出權(quán)重更小的雙基鏈。此外，考慮到小權(quán)重也有其局限性。引入了技術(shù)Tate配對與2-3鏈相結(jié)合來提高算法效率，比基于貪心算法的雙基鏈更加高效。經(jīng)仿真實(shí)驗(yàn)比較分析和研究，表明該改進(jìn)算法可以很好提高計(jì)算效率，并且同時(shí)能大大降低存儲量。

橢圓曲線密碼體制；標(biāo)量乘法；雙基數(shù)系統(tǒng)；Tate配對

0　引言

1985年，N.Koblitz和V.Miller各自獨(dú)立地提出了橢圓曲線公鑰密碼體制 （ECC，Elliptic-Curve-Cryptographic），這是橢圓曲線理論在密碼學(xué)中又一次全新的應(yīng)用［1］。橢圓曲線密碼體制的安全性是基于橢圓曲線上離散對數(shù)問題求解的困難性，并且目前還沒有找到解決此問題的亞指數(shù)時(shí)間算法，具有一些其他公鑰密碼體制無法比擬的優(yōu)點(diǎn)，例如在相同的安全強(qiáng)度下，具有系統(tǒng)參數(shù)和密鑰尺寸短 （如160 bits的ECC和1024 bits的RSA具有相當(dāng)?shù)陌踩珡?qiáng)度），選擇機(jī)會較大等特點(diǎn)［2］。正因如此，十幾年來，ECC一直是數(shù)學(xué)界、密碼學(xué)界和計(jì)算機(jī)科學(xué)界所關(guān)注的重大課題。ECC加解密方面速度快、節(jié)省能源、節(jié)省帶寬和節(jié)省存儲空間，特別適用于ECC密碼引擎協(xié)處理器的SIM卡、Smart卡和FPGA、ASIC芯片等的開發(fā)。憑借其諸如此類眾多的優(yōu)點(diǎn)，ECC技術(shù)在信息安全領(lǐng)域中發(fā)揮越來越大的作用［3］。

在ECC中，標(biāo)量乘的計(jì)算決定著橢圓曲線密碼體制的運(yùn)算效率。所謂的標(biāo)量乘即在域Fq上的橢圓曲線E上的一個(gè)點(diǎn)P和已知的一個(gè)整數(shù)n（即標(biāo)量），計(jì)算nP的過程就是計(jì)算標(biāo)量乘的過程，可以分為3級模塊來完成：頂級模塊為點(diǎn)乘運(yùn)算；中級運(yùn)算模塊是把點(diǎn)乘運(yùn)算分解成了有限域Fq上點(diǎn)加 （ECADD）和倍點(diǎn)（ECDBL）構(gòu)成的Abel群上的運(yùn)算；最底級的運(yùn)算模塊就是完成有限域模塊上的所有運(yùn)算，包括Fq上大整數(shù)的域乘法、域逆和域平方運(yùn)算［4-5］。

橢圓曲線密碼由于具有密鑰短、安全性高等其他公鑰密碼體制所無法比擬的特點(diǎn)，近年來已經(jīng)成為密碼學(xué)領(lǐng)域研究的熱點(diǎn)之一［1-2］。計(jì)算標(biāo)量乘nP（又稱點(diǎn)乘法）是最基本、最耗時(shí)的操作，在許多基于橢圓曲線的密碼方案中，科學(xué)家已經(jīng)提出多種形式多種方法來改進(jìn)標(biāo)量乘算法的運(yùn)算效率：

（1）通過對標(biāo)量n展開形式的優(yōu)化，來提高運(yùn)算效率，代表性算法有NAF表示、τ-adic表示、雙基表示等［3-6］。

（2）引入預(yù)計(jì)算的窗口算法和comb算法等［3］。

（3）根據(jù)橢圓曲線的特點(diǎn)使用不同的坐標(biāo)表示，例如仿射坐標(biāo)、射影坐標(biāo)和Inverted Edwards坐標(biāo)［7］等。

因此，從抗多種功耗攻擊的能力和系統(tǒng)計(jì)算性能優(yōu)化兩個(gè)方面考慮，本文結(jié)合基于貪心算法的雙基數(shù)系統(tǒng)標(biāo)量乘算法，給出了一種執(zhí)行效率高和安全性強(qiáng)的防御方案。主要從標(biāo)量n入手，通過tate配對來優(yōu)化系數(shù)n的表示，使得標(biāo)量n在基于tate配對的雙基鏈基礎(chǔ)之上展開，并且這樣雙基鏈展開速度更加高效，從而達(dá)到加快標(biāo)量乘算法的目的。

1　基礎(chǔ)知識

1.1橢圓曲線標(biāo)量乘

設(shè)Fq是一個(gè)有限域，P是定義在有限域Fq上的橢圓曲線E（n）上的一點(diǎn)，n是一個(gè)大整數(shù)。根據(jù)橢圓曲線上點(diǎn)的加法公式將點(diǎn)P與自身相加n次，即橢圓曲線上的點(diǎn)乘nP的計(jì)算公式為：

若n＜0，Q=［-n］（-P）=-（-n）P，n稱為標(biāo)量，nP稱為橢圓曲線標(biāo)量乘法。一般的，將P+P+…+P記為nP，即nP=P+P+…+P。特別的，OP=O（O是無窮遠(yuǎn)點(diǎn)）。標(biāo)量乘運(yùn)算是橢圓曲線密碼體制中的核心運(yùn)算，加密和驗(yàn)證時(shí)都需要計(jì)算標(biāo)量乘，它的運(yùn)算速度決定著橢圓曲線密碼體制的運(yùn)算速度。因此，高效率標(biāo)量乘運(yùn)算的實(shí)現(xiàn)是設(shè)計(jì)橢圓曲線密碼系統(tǒng)過程的關(guān)鍵之一［6-7］。

當(dāng)然，影響標(biāo)量乘法運(yùn)算效率的因素很多，例如特殊的曲線的特性會有助于提高運(yùn)算效率，如在ECDSA簽名生成中，若點(diǎn)基點(diǎn)P是固定的，點(diǎn)乘算法可以利用一些與計(jì)算數(shù)據(jù)提高運(yùn)算效率，而這些數(shù)據(jù)僅與P有關(guān)，與n無關(guān)。

1.2基于貪心算法的雙基數(shù)系統(tǒng)

雙基數(shù)字系統(tǒng)（DBNS，Double Base Number System）是其中每一個(gè)正整數(shù)n表示為形式的數(shù)字的總和或差的表示方案pbqt，即：

式（2）中的m是DBNS的漢明重量。

在本文中，主要考慮p=2，q=3，通過貪心算法可以很簡單地找到一個(gè)表示整數(shù)n的方法。即，每次都尋找a和b的值，使得2a3b最接近指定的整數(shù)。

然后計(jì)算其差異，繼續(xù)循環(huán)這個(gè)過程，直到0的時(shí)候停止算法。

貪心算法常用來求解整數(shù)的雙基表達(dá)式，在文獻(xiàn)［8］中提出了基于LineSearch方法的貪心算法，該算法在效率方面有著良好的表現(xiàn)。但是，貪心算法并不能保證多輪迭代后的結(jié)果仍然是最優(yōu)的。在O（log n/loglogn）時(shí)間復(fù)雜度內(nèi)利用貪心算法來求出其DBNS的形式［9］。

例：令n=841232，利用貪心算法可以求出n的DBNS表示：

綜上所述，841232=2738+2136-2232+2對于整個(gè)計(jì)算而言，最簡單直接的方法計(jì)算雙基鏈。因?yàn)樗男问较?，一個(gè)雙基鏈?zhǔn)沟每赡軆H使用增加一倍和兩倍的先前的部分結(jié)果，并與加法和減法累積達(dá)到nP。其中一個(gè)最有意義的就是如何就橢圓曲線的效率選擇最合適的雙基鏈，然而，這并不是那么簡單的事情。通常情況下，這樣計(jì)算出來的雙基鏈并不適合橢圓曲線標(biāo)量乘，因?yàn)橥ǔ２豢紤]數(shù)的雙倍和三倍的最優(yōu)化。例如，219+ 312是最短DBNS表示1055729。但是更佳組合運(yùn)算在NAF中表示是220+213-210-24+1。為了獲得更合適的雙基鏈，需要提出改進(jìn)的算法。

1.3基于Tate配對的雙基鏈

設(shè)E（Fq）是組上的橢圓曲線有限域Fq，并且n和正整數(shù)q互質(zhì)（一般情況下n為素?cái)?shù)）。用E（Fq）［n］表示在Fq中的n拐點(diǎn)。令P∈E（Fq）［n］和Q∈E（F（qk））［n］，用DP和DQ表示E的兩個(gè)除數(shù)，其中分別滿足DP=（P）-（∞）和DQ=（Q）-（∞）。讓fp是橢圓曲線的除子是div（fp）=n（P）-n（∞）的有理函數(shù)［4］。減少的Tate對τn為τn：E（Fq）［n］×E（Fqk）［n］→F*qk

定義為：

如果k>1且Q不具備Fq的有理性，可以避免與除數(shù)并簡單的與點(diǎn)Q并行，這樣就可以減小Tate就如上公式。

米勒算法可以很有效地計(jì)算Tate配對，它解決的主要問題是如何構(gòu)造一個(gè)有理函數(shù)Fq，使得div（fp）=n（P）-n（∞）。米勒的思想是將加倍和加算法結(jié)合起來，標(biāo)量乘［n］P上直線穿過在加法/加倍方法中使用的點(diǎn)的過程。

設(shè)［j］P和［k］P為橢圓曲線E上兩個(gè)不同的點(diǎn)（均為P的倍數(shù)），其中j，k∈Z，經(jīng)過這兩點(diǎn)的直線l的除子為：div（fζp）=n（P）-n（∞）

div（ζjp，kp）=（［j］P）+（［k］P）+（-［j+k］P）-3（∞）進(jìn)一步來說，穿過［j］P和-［j］P的豎線表示為ζjp，那么div（ζjp）=（［j］P）+（-［j］P）-2（∞）。

2　雙基鏈標(biāo)量乘算法的改進(jìn)

雙基數(shù)系統(tǒng)可以將標(biāo)量n的雙基數(shù)鏈表示的長度限制在o（logn/loglogn）范圍內(nèi)，這樣就可以減少標(biāo)量乘法中的上層計(jì)算。在底層域快速算法方面，可以直接計(jì)算3kP快速算法。通常情況下，計(jì)算Tate配對的一個(gè)重要部分是在DQ對每一個(gè)點(diǎn)S求值，米勒算法的主要思想是：任取點(diǎn)R，DP=（P+R）-（R），?j∈Z，定義DjP=j（P+R）-j（R）-（jP）+（o）則存在有理函數(shù)fj使得div（fj）=DjP，特別地，fn=fP成立，因?yàn)镻∈E［n］，使nP=0。

為了簡化操作，兩個(gè)條件寫為：

（1）f1=1

米勒的算法對于nP用加法鏈計(jì)算FP，也就是說，（FP）=N（P）N（∞）。這個(gè)算法是通過將n用二進(jìn)制位展開表示的，那么，可以將標(biāo)量n用雙基鏈表示，其中在米勒算法的基礎(chǔ)上利用雙基鏈表示標(biāo)量n來計(jì)算標(biāo)量乘。

算法1基于米勒算法的雙基鏈

Input：bi，ti，n=，si=｛-1，1｝，b1≥b2≥…≥bm≥0，t1≥t2≥…tm≥0，P∈E（Fq）［n］，Q∈E（Fqk）［n］

Output：f=fn（Q）

1：if s1=1 then

2： f←1，Z←P

3：else

5：for i←1，2，…，m-1 do

6：u←bi-bi+1，v ti-ti+1

7：for j←1，2，…，v do

9：for j←1，2，…，u do

10：f←f2·，Z←2Z.

11：if si+1=1 then

13：else

15：return f

算法1中，盡管雙倍乘法和三倍乘法取代了之前的加法減法，在實(shí)際場合中可以不用完全取代。因?yàn)橹辽俅嬖谝粋€(gè)u或v一定大于0，每次加法和減法都被組合為fj2或者fj3。并且在算法1的步驟9中，K.Eisentrager［11］曾這樣提及過，可以用PZ，-3Z來表示一個(gè)拋物線穿過三次方程。評估函數(shù)成本中，使用拋物線方程則將會降低運(yùn)算成本。

用α2，α3分別表示米勒算法中2倍和3倍的花銷，點(diǎn)加和倍點(diǎn)相結(jié)合的總成本被寫成α2+β2+。相似的，2倍和減法記為α2+β2-，3倍和加法相結(jié)合記為α3+β3+。

如果2Pi±Pi和3Pi±P作為組合操作被執(zhí)行，那么希望β2+≠β3+和β2-≠β3-成立，然而，如果分開執(zhí)行的操作（作為原始形式米勒算法），那么，將會導(dǎo)致β2+=β3+和β2-=β3-成立。當(dāng)然相同的符號可以用于“標(biāo)準(zhǔn)”（非配對）標(biāo)量乘法運(yùn)算，其中α2，α3，β2+，β2-，β3+和β3-應(yīng)解釋為相關(guān)聯(lián)的組的運(yùn)行成本（無功能評估）。

3　基于Tate配對雙基鏈算法

3.1最短雙基鏈算法

如上所述可以將多個(gè)步驟組合操作并且執(zhí)行，這樣能降低算法運(yùn)行成本。從而可以定義雙基鏈C（i，j），其中i，j分別表示鏈表中2的指數(shù)和3的指數(shù)的最大值。也就是說其他項(xiàng)任意項(xiàng)±2a3b都滿足a＜i，b＜j。

注意到ni，j和ni，j=0的情況，如果鏈表Ci，j存在最大項(xiàng)，則為正數(shù)。如果鏈表存在最大項(xiàng)，則為負(fù)數(shù)。

對于ni，j，如果li，j是最小的鏈表。其中包含子鏈表。Ca，b對于na，b來說，并且a≤i，b≤j那么Ca，b一定比na，b小。相似的加個(gè)負(fù)號也是一樣的。

對于我們在數(shù)值實(shí)驗(yàn)中，我們使用的評估算法成本［6］，因?yàn)樗鼈兏采w的整個(gè)范圍內(nèi)，我們感興趣的是它們當(dāng)然應(yīng)該由具體的比例換成是否需要一個(gè)具體鏈。

由于雙基鏈為基礎(chǔ)，如果系數(shù) α3/α2≈log23= 1.58496...（對應(yīng)于基2和基3的相對長度擴(kuò)展）。即使α3/α2與log23相差比較多，我們的算法仍然可以使用，但輸出很可能接近單基表示在更有利的形式。

那么，令Ci，j是任意ni，j的雙基鏈表。只要Ci，j！=0則有以下情況。

1、Ci，j=Ci-1，j（當(dāng)且僅當(dāng)ni，j=ni-1，j）

2、Ci，j=2i-13j+Ci-1，j（當(dāng)且僅當(dāng)ni，j=2i-13j+ni-1，j）

3、Ci，j=2i-13j+（當(dāng)且僅當(dāng)ni，j=2i-13j+）

4、Ci，j=Ci，j-1（當(dāng)且僅當(dāng)ni，j=n（i，j-1））

5、Ci，j=2i3j-1+Ci，j-1（當(dāng)且僅當(dāng)ni，j=2i3j-1+ni，j-1）

6、Ci，j=2i3j-1+Ci，j-1（當(dāng)且僅當(dāng)ni，j=2i3j-1+）

上面給出了Ci，j，由i，j其中任何一個(gè)減少或者增大，都可以看出鏈表相鄰兩項(xiàng)的關(guān)系。其中也包括同時(shí)增大同時(shí)減小。其關(guān)系如表1所示。

表1　Ci，j和 ni，j關(guān)系

表2　Ci，j中最大的項(xiàng)是2ij-13jor 2ij3j-1

定義 ij，就獲得2ij3j-1＜2ij-13j≤nij，j=n

所以 nij-1，j≠nij，j而且 nij，j-1≠nij，j，那么 Ci，j一定會進(jìn)入情況2，3，5，6。通過定義，其中鏈表中最大項(xiàng)，是2ij3j。

根據(jù)以上結(jié)果，得到的算法2。i和j都是從0開始，分別是從2和3的冪。

算法2最短雙基鏈算法

Input：n>0

Output：

1：Cj←?，←? for each j

2：for i←0 to「log2（n+1）?do

4：if im＜i then

5：m←m-1

6：for j←0 to m do

7：find Ci，jandfrom sheet 1，cause Cj=li-1，j

8：find Ci，jandfrom sheet 2，cause Cj-1=li，j-1

9：Cj←Ci，j（Cj=li，j）

11：if i=ijthen

13： lj←min（Cj，）

14：return l

很顯然，給定任意鏈Ci，j，以上所有條件均為互斥的。如果Ci，j鏈存在，那么，鏈中最大的項(xiàng)是r，r=2i-13j那么第二項(xiàng)如果是正，那么轉(zhuǎn)到情況2，如果第二項(xiàng)是負(fù)，那么轉(zhuǎn)到情況3。

如果鏈表中最大的項(xiàng)目r=2i-13j-1。那么第五項(xiàng)如果是正，那么轉(zhuǎn)到情況5，如果第六項(xiàng)是負(fù)，那么轉(zhuǎn)到情況6；如果r=2a3j的形式其中a≤i-2那么就只能是情況1；如果r=2i3b的形式其中b≤j-2那么就只能是情況4。

只有當(dāng)ni，j=ni-1，j-1的時(shí)候，那么情況1和情況4同時(shí)發(fā)生。如果r=2a3b的形式其中a≤i-2，b≤j-2那么鏈表就會同時(shí)進(jìn)入情況1和情況4。

雖然上面這個(gè)定理在尋找最佳雙基鏈的算法中有些時(shí)候不是必須的。對于每一個(gè)j而言，都存在一個(gè)最小的鏈（如果沒有j，那么可以完全忽略）。

3.2基于Tate配對雙基鏈算法

在3.1所述鏈，我們僅僅對它們的漢明權(quán)進(jìn)行了優(yōu)化。然而，在實(shí)踐中，這通常不是獲得最快配對計(jì)算的最佳方法。根據(jù)基礎(chǔ)組合運(yùn)算，一些操作可被組合（例如加倍加入變成“加倍并加上”），并且2i3j可以將其改變（因?yàn)辄c(diǎn)加法和點(diǎn)減法在米勒的算法不同的效果）。

在本節(jié)中，我們考慮了成本與每一個(gè)類型的組合運(yùn)算，從n的雙基鏈表示米勒算法方面。由于我們的算法計(jì)算從最低一項(xiàng)的標(biāo)量上升，但米勒的算法從最顯著長期下降，我們必須調(diào)整我們評估相應(yīng)的成本的方式。

此外，我們選擇相結(jié)合的操作方式可能取決于有多少增加一倍和兩倍的連續(xù)兩項(xiàng)鏈之間進(jìn)行。然后，我們需要分開鏈成子情況：

根據(jù)鏈的最大項(xiàng)的形式，可以將Ci，j分成三種情況：

最大項(xiàng)是形式2i3b而且b＜j，則

最大項(xiàng)是形式2a3j而且a＜i，則

最大項(xiàng)是形式2a3b而且a＜i和b＜j，則

對于Ci，j和Ci，j兩種情況對于任何i，算法都僅僅保留一個(gè)副本。而該算法i=ij=「log2（（n+1）/3j?其中j的變化是有固定的i來決定的。因此，「log3（（n+1）/2j?∈｛「log3（（n+1）/3j?，「log2（（n+1）/3j?+1｝因此im=i-1等式可能成立，所以我們不需要考慮配對（im，m）。

正如上一節(jié)所講，我們認(rèn)為，對于任何i和j都存在C-1，j=?=Ci，-1，這樣不處理負(fù)數(shù)的情況，也是與實(shí)際相聯(lián)系的，算法會更加高效。在實(shí)際執(zhí)行它會更有效分開處理這些情況，從來沒有使用負(fù)指數(shù)。特別是，從定義可以得到ι0，0=0=

設(shè)n是一個(gè)正整數(shù)，則算法2返回最小雙基鏈O（（log n）2）步驟O（（log n）4）位操作），以及需要O（（log n）3）內(nèi)存位。

如果在鏈中的只計(jì)算2和3的權(quán)重 （例如，288被記錄為一配對（5，2）），則每個(gè)鏈減小的內(nèi)存需求到O（log n log log n）。如果它們被記錄為它們的區(qū)別（再次以2的冪和3的冪）與前一項(xiàng)，每個(gè)鏈的內(nèi)存要求為O（log n），所以算法2的內(nèi)存要求可以降低到O（log n）2）位。

算法3預(yù)計(jì)算最小最優(yōu)雙基鏈算法

Input：n>0，計(jì)算α2，α3，β2-，β2+，β3-，β3+

Output：

2：for i←0 to「log2（n+1）?do

4：if im＜i then

5：m←m-1

6：for j←0 to m do

13：if i=ijthen

15：lj←min（Cj，）

16：return l

如果我們假設(shè)加速整數(shù)計(jì)算，每算法的步驟的成本降低到O（log n）時(shí)間位操作，并且該算法的總成本變得O～（（log n）3）位的操作。

此外，我們提出“正鏈”和“負(fù)鏈”，其中所有的術(shù)語具有相同的符號（除非在負(fù)鏈的項(xiàng)）的概念。

正鏈只能從ιi，j（而不允許任何），一直遞增到ιi，j。同樣，負(fù)鏈從（允許ιi，j）一直遞增至個(gè)（最后期限為正），適應(yīng)算法來做到這一點(diǎn)很簡單。在提出的操作成本［6］，負(fù)鏈要比正鏈更有利（因?yàn)槎擀?-和β3-是大約三小于β2+和β3+次），實(shí)驗(yàn)結(jié)果表明，其成本僅僅比最小鏈稍大。

4　算法實(shí)驗(yàn)比較和分析

本節(jié)將新提出的算法與第一節(jié)中提到的算法進(jìn)行了性能的分析和效率的比較。對每個(gè)區(qū)間都隨機(jī)選取大量的素?cái)?shù)進(jìn)行數(shù)值實(shí)驗(yàn)。其中實(shí)驗(yàn)中需要對比的5種算法分別是基于雙基鏈的貪心算法、Dolce和Habsieger（+符號）無限制平均漢明權(quán)重算法、最小Tate雙基鏈算法、最小負(fù)鏈算法和NAF理論值。實(shí)驗(yàn)中主要分別對5種算法的漢明重量和消耗的總成本進(jìn)行比較，得出以下結(jié)論。

對每比特的漢明重量和每比特消耗的成本進(jìn)行對比。結(jié)果示于圖1和2。對于成本的評估，使用系數(shù)之間的比例［6］為：α2=1，α3=1.5705，β2-=0.1107，β3+=0.3648，和β3-=0.1047。

圖1各算法每比特的漢明重量

圖1中，由于n比較大，橫坐標(biāo)用log0n代替。粗線表示雙基鏈貪心算法，+符號表示Dolce和Habsieger無限制平均漢明權(quán)重，o符號表示最小的漢明權(quán)，普通線為最小化Tate對成本，虛線表示最小負(fù)鏈，以及用于NAF理論值。

每個(gè)“標(biāo)準(zhǔn)”的二進(jìn)制表示的位的平均漢明權(quán)重為0.50，而對于NAF它減少到0.33。從圖1中，貪心算法的性能似乎減少為n的增加到慢慢變更接近一個(gè)NAF，無限接近于0.30。另外，Doche和Habsieger和我們的算法（被認(rèn)為所有三種情況下）的基于樹的方法的性能稍微增大為n個(gè)的尺寸增大，但遠(yuǎn)不可能接近所預(yù)期的用于DBNS的算法。

從圖1中，似乎更合理考慮雙基鏈如具有線性增長，漢明重量約為0.25/bit的最小化的負(fù)鏈，0.23為雙基鏈具有為雙基最小化成本和0.19鏈以最小的漢明權(quán)重?；跇涞姆椒?，我們觀察的下限為每約0.20bit的漢明權(quán)重，而Dolce［10］和Habsieger算法大概為0.215（1/4.6419）。

在配對計(jì)算性能方面，雙基鏈以最小的成本配對提供了一個(gè)近似的12.3%的漲幅比原來的 （標(biāo)準(zhǔn)二進(jìn)制）米勒算法（1.152α2/bit），4.22%，較NAF-配對（1.069α2/bit），較貪心的雙基鏈低3.48%，比最低1.40%。

圖2　各算法每比特的平均配對成本

粗線表示雙基鏈貪心算法，+符號表示Dolce和Habsieger的無限制版本，o符號表示最小的漢明權(quán)，普通線表示最小化Tate對成本，虛線表示最小化的負(fù)鏈），以及用于NAF理論值。

結(jié)合在 Dolce和 Habsieger（在實(shí)踐中大概為1.74%［10］）超過雙基鏈具有最小漢明權(quán)和1.06%。使用負(fù)鏈和真正最小雙基鏈之間的差異似乎是小于0.065%，由于減少了開銷，這可以通過從具有較簡單的程序的增益進(jìn)行補(bǔ)償。需要注意的是在大約每比特1.025α2，優(yōu)化的鏈可以被認(rèn)為是絕對的下限米勒狀算法，其成本僅僅只有2.59%。

5　結(jié)語

我們提出的這個(gè)算法，能夠更加有效的將整數(shù)n進(jìn)行雙基鏈表示。我們描述了如何適應(yīng)我們的算法以最小化表示的任一漢明權(quán)或優(yōu)化的鏈上的tate配對計(jì)算的效果。這些算法也可以很容易地適用于其他情況下（尤其是如果各個(gè)Tate對操作的成本改變）。我們還介紹了負(fù)鏈，其提供接近最佳的性能，并允許以簡化的配對執(zhí)行的概念。

適應(yīng)多基地?cái)?shù)字系統(tǒng)保留為一個(gè)開放的問題。三基鏈（例如2-3-5鏈）是一個(gè)自然延伸和最有可能需要我們算法的立體版本。人們也可以考慮雙基鏈具有較大的系數(shù)集合［5］。適應(yīng)我們的算法，以這些表示將需要更新的表結(jié)構(gòu)，以及最有可能的一組較大的可能鏈的每個(gè)位置（i，j）。此外，我們還必須考慮到較大的位數(shù)在米勒算法的費(fèi)用設(shè)置的影響。

［1］Bernstein D J，Lange T.Fast Addition and Doubling on Elliptic Curves［A］.Asiacrypt 2007［C］.Lncs 4833，2007.29-50.

［2］Chevallier-Mames B，Ciet M，Joye M.Low-Cost Solutions for Preventing Simple Side Channel Analysis：Side-Channel Atomicity［J］. Ieee Transactions On Computers，2004，53（6）：760-768.

［3］Cryptanalysis of A Remote User Authentication Scheme for Mobile Client-Server Environment with Provable Security Based on ECC. Information Fusion，2013，41（4）：498-503.

［4］Mishra P K，Dimitrov V.Efficient Quintuple Formulas for Elliptic Curves and Efficient Scalar Multiplication Using Multibase Number Representation［C］.Proc.Of The 10th International Conference on Information Security.［S.L.］：Springer-Verlag，2007：390-406.

［5］王圓圓，殷新春.基于雙基數(shù)子集表示的快速標(biāo)量乘算法［期刊論文］-江蘇大學(xué)學(xué)報(bào)（自然科學(xué)版），2009（3）.

［6］On the Security of an Improved Password Authentication Scheme Based on Ecc.Proceedings of the Third International Conference Information Computing and Applications（Icica 2012），Chende，China，Lncs 7473：181-188.

［7］Pang Shi-Chun，Tong Shou-Yu，Congfu-Zong，et a1.An Efficient Elliptic Curve Scalar Multiplication Algorithm Against Side Channel Attacks［C］.Proceedings of the 2010 International Conference on Computer，Mechatronics，Control and Electronic Engineering（Cmce2010），Springer-Verlag，Berlin：2010：361-364.

［8］Hedabou，M.，Pinel，P.，B'En'Eteau，L.：Countermeasures for Preventing Comb Method Against Sca Attacks.In：Deng，R.H.，Bao，F(xiàn).，Pang，H.，Zhou，J.（Eds.）Ispec 2005.Lncs，Springer，Heidelberg 2005，3439：85-96.

［9］李忠，彭代淵.橢圓曲線標(biāo)量乘法中標(biāo)量的有效表示［期刊論文］-南京師大學(xué)報(bào)（自然科學(xué)版），2010，33（3）.

［10］許凱平，鄭洪源，劉錦峰等.橢圓曲線密碼體制中快速標(biāo)量乘方法研究［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（15）：112-115．

［11］Lu C Y，Jen S M，Laih C S．A General Framework of Side-Channel Atomicity for Elliptic Curve Scalar Multiplication［J］.Ieee Transactions on Computers，2013，62（3）：428-438．

［12］Abdulrahman E，Reyhani-Masoleh A.New Regular Radix-8 Scheme for Elliptic Curve Scalar Multiplication Without Precomputation［J］.Computers，Ieee Transactions On，2015，64（2）：438-451.

［13］白羽，范恒英．一種改進(jìn)的橢圓曲線標(biāo)量乘的快速算法［J］．西南科技大學(xué)學(xué)報(bào)，2011，26（3）：48-52.

［14］Mishra P K，Dimitrov V．Eficient Quintuple Formulas for Elliptic Curves and Effieient Scalar Multiplication Using Muhibase Number Representation［C］.Isc 2007：Proceedings of the 10th International Conference of Information Security，Lncs 4779.Springer-Verlag，2007：390-406．

［15］Adikari J，Dimitrov V S，Imbert L_Hybrid Binary-Ternary Number System for Elliptic CurveCryptosystems［J］.IEEE Transactions Computers，2011，60（2）：254-265．

［16］周夢，周海波.橢圓曲線快速點(diǎn)乘算法優(yōu)化［J］．計(jì)算機(jī)應(yīng)用研究，2012，29（8）：3056-3058.

［17］Purohit G，Rawat A S，Kumar M．Elliptic Chive Point Multiplication Using Mbnr and Point Halving［J］．International Journal of Advanced Networking And Applications，2012，3（5）：1329-1337．

［18］Mahdavi R，Saiadian A Efficient Scalar Multiplications for Elliptic Curve Cryptosystems Using Mixed Coordinates Strategy and Direct

Computations［C］.Cryptology And Network Security（Lncs6467）．2010：184-198.

Elliptic Curve；Scalar Multiplication；Double Base Number System；Tate Pairing

Research on Fast Scalar Multiplication Algorithm Based on Double-Base Chain

WU Yong-bo，PENG Qing-song，GAO Mao-ting
（School of Information Engineering，Shanghai University of Maritime，Shanghai 201306）

In order to improve the security of elliptic curve cryptographic algorithms and efficiency of the existing side-channel attacks and scalar multiplication algorithm on the basis of a new scalar multiplication algorithm is proposed.Scalar multiplication is the elliptic curve cryptosystem（ECC）of the basic operation，is also one of the most time-consuming and vulnerable to attack.Elliptic curve scalar multiplication，2-3 double-base chain represents an integer N，can improve the efficiency of the scalar multiplication.In a scalar Multiplication algorithm，to find the optimal 2-3 double-base chain will takes longer than scalar multiplication itself，the cost of pay more.New algorithm，the application of Tate pairing and 2-3 chain combination，to find out better 2-3 chain.In addition，than 2-3 chain based on greedy algorithm.Simulation results show that the improved algorithm can reduce the storage with improving the calculation efficiency.

1007-1423（2016）29-0003-08

10.3969/j.issn.1007-1423.2016.29.001

武永波（1992-），男，河南開封人，學(xué)生，專業(yè)方向?yàn)檐浖_發(fā)方法與軟件項(xiàng)目管理彭青松，男，工學(xué)博士，管理學(xué)博士生，副教授，碩士生導(dǎo)師，研究方向?yàn)榘踩芾怼⒅悄苄畔⑻幚砀呙?，男，教授，研究方向?yàn)閿?shù)據(jù)挖掘、數(shù)據(jù)庫與信息系統(tǒng)

2016-05-27

2016-09-20