基于雙基鏈的快速標量乘算法研究

武永波，彭青松，高茂庭

（上海海事大學信息工程學院，上海　201306）

基于雙基鏈的快速標量乘算法研究

武永波，彭青松，高茂庭

（上海海事大學信息工程學院，上海201306）

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

橢圓曲線密碼體制；標量乘法；雙基數系統；Tate配對

0　引言

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

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

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

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

（2）引入預計算的窗口算法和comb算法等［3］。

（3）根據橢圓曲線的特點使用不同的坐標表示，例如仿射坐標、射影坐標和Inverted Edwards坐標［7］等。

因此，從抗多種功耗攻擊的能力和系統計算性能優化兩個方面考慮，本文結合基于貪心算法的雙基數系統標量乘算法，給出了一種執行效率高和安全性強的防御方案。主要從標量n入手，通過tate配對來優化系數n的表示，使得標量n在基于tate配對的雙基鏈基礎之上展開，并且這樣雙基鏈展開速度更加高效，從而達到加快標量乘算法的目的。

1　基礎知識

1.1橢圓曲線標量乘

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

若n＜0，Q=［-n］（-P）=-（-n）P，n稱為標量，nP稱為橢圓曲線標量乘法。一般的，將P+P+…+P記為nP，即nP=P+P+…+P。特別的，OP=O（O是無窮遠點）。標量乘運算是橢圓曲線密碼體制中的核心運算，加密和驗證時都需要計算標量乘，它的運算速度決定著橢圓曲線密碼體制的運算速度。因此，高效率標量乘運算的實現是設計橢圓曲線密碼系統過程的關鍵之一［6-7］。

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

1.2基于貪心算法的雙基數系統

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

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

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

然后計算其差異，繼續循環這個過程，直到0的時候停止算法。

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

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

綜上所述，841232=2738+2136-2232+2對于整個計算而言，最簡單直接的方法計算雙基鏈。因為它的形式下，一個雙基鏈使得可能僅使用增加一倍和兩倍的先前的部分結果，并與加法和減法累積達到nP。其中一個最有意義的就是如何就橢圓曲線的效率選擇最合適的雙基鏈，然而，這并不是那么簡單的事情。通常情況下，這樣計算出來的雙基鏈并不適合橢圓曲線標量乘，因為通常不考慮數的雙倍和三倍的最優化。例如，219+ 312是最短DBNS表示1055729。但是更佳組合運算在NAF中表示是220+213-210-24+1。為了獲得更合適的雙基鏈，需要提出改進的算法。

1.3基于Tate配對的雙基鏈

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

定義為：

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

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

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

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

2　雙基鏈標量乘算法的改進

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

為了簡化操作，兩個條件寫為：

（1）f1=1

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

算法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中，盡管雙倍乘法和三倍乘法取代了之前的加法減法，在實際場合中可以不用完全取代。因為至少存在一個u或v一定大于0，每次加法和減法都被組合為fj2或者fj3。并且在算法1的步驟9中，K.Eisentrager［11］曾這樣提及過，可以用PZ，-3Z來表示一個拋物線穿過三次方程。評估函數成本中，使用拋物線方程則將會降低運算成本。

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

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

3　基于Tate配對雙基鏈算法

3.1最短雙基鏈算法

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

注意到ni，j和ni，j=0的情況，如果鏈表Ci，j存在最大項，則為正數。如果鏈表存在最大項，則為負數。

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

對于我們在數值實驗中，我們使用的評估算法成本［6］，因為它們覆蓋的整個范圍內，我們感興趣的是它們當然應該由具體的比例換成是否需要一個具體鏈。

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

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

1、Ci，j=Ci-1，j（當且僅當ni，j=ni-1，j）

2、Ci，j=2i-13j+Ci-1，j（當且僅當ni，j=2i-13j+ni-1，j）

3、Ci，j=2i-13j+（當且僅當ni，j=2i-13j+）

4、Ci，j=Ci，j-1（當且僅當ni，j=n（i，j-1））

5、Ci，j=2i3j-1+Ci，j-1（當且僅當ni，j=2i3j-1+ni，j-1）

6、Ci，j=2i3j-1+Ci，j-1（當且僅當ni，j=2i3j-1+）

上面給出了Ci，j，由i，j其中任何一個減少或者增大，都可以看出鏈表相鄰兩項的關系。其中也包括同時增大同時減小。其關系如表1所示。

表1　Ci，j和 ni，j關系

表2　Ci，j中最大的項是2ij-13jor 2ij3j-1

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

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

根據以上結果，得到的算法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鏈存在，那么，鏈中最大的項是r，r=2i-13j那么第二項如果是正，那么轉到情況2，如果第二項是負，那么轉到情況3。

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

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

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

3.2基于Tate配對雙基鏈算法

在3.1所述鏈，我們僅僅對它們的漢明權進行了優化。然而，在實踐中，這通常不是獲得最快配對計算的最佳方法。根據基礎組合運算，一些操作可被組合（例如加倍加入變成“加倍并加上”），并且2i3j可以將其改變（因為點加法和點減法在米勒的算法不同的效果）。

在本節中，我們考慮了成本與每一個類型的組合運算，從n的雙基鏈表示米勒算法方面。由于我們的算法計算從最低一項的標量上升，但米勒的算法從最顯著長期下降，我們必須調整我們評估相應的成本的方式。

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

根據鏈的最大項的形式，可以將Ci，j分成三種情況：

最大項是形式2i3b而且b＜j，則

最大項是形式2a3j而且a＜i，則

最大項是形式2a3b而且a＜i和b＜j，則

對于Ci，j和Ci，j兩種情況對于任何i，算法都僅僅保留一個副本。而該算法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）。

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

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

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

算法3預計算最小最優雙基鏈算法

Input：n>0，計算α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

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

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

正鏈只能從ιi，j（而不允許任何），一直遞增到ιi，j。同樣，負鏈從（允許ιi，j）一直遞增至個（最后期限為正），適應算法來做到這一點很簡單。在提出的操作成本［6］，負鏈要比正鏈更有利（因為二者β2-和β3-是大約三小于β2+和β3+次），實驗結果表明，其成本僅僅比最小鏈稍大。

4　算法實驗比較和分析

本節將新提出的算法與第一節中提到的算法進行了性能的分析和效率的比較。對每個區間都隨機選取大量的素數進行數值實驗。其中實驗中需要對比的5種算法分別是基于雙基鏈的貪心算法、Dolce和Habsieger（+符號）無限制平均漢明權重算法、最小Tate雙基鏈算法、最小負鏈算法和NAF理論值。實驗中主要分別對5種算法的漢明重量和消耗的總成本進行比較，得出以下結論。

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

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

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

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

從圖1中，似乎更合理考慮雙基鏈如具有線性增長，漢明重量約為0.25/bit的最小化的負鏈，0.23為雙基鏈具有為雙基最小化成本和0.19鏈以最小的漢明權重。基于樹的方法，我們觀察的下限為每約0.20bit的漢明權重，而Dolce［10］和Habsieger算法大概為0.215（1/4.6419）。

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

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

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

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

5　結語

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

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

［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］王圓圓，殷新春.基于雙基數子集表示的快速標量乘算法［期刊論文］-江蘇大學學報（自然科學版），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.，Pang，H.，Zhou，J.（Eds.）Ispec 2005.Lncs，Springer，Heidelberg 2005，3439：85-96.

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

［10］許凱平，鄭洪源，劉錦峰等.橢圓曲線密碼體制中快速標量乘方法研究［J］.計算機工程與應用，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］．西南科技大學學報，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］周夢，周海波.橢圓曲線快速點乘算法優化［J］．計算機應用研究，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-），男，河南開封人，學生，專業方向為軟件開發方法與軟件項目管理彭青松，男，工學博士，管理學博士生，副教授，碩士生導師，研究方向為安全管理、智能信息處理高茂庭，男，教授，研究方向為數據挖掘、數據庫與信息系統

2016-05-27

2016-09-20