利用多基數(shù)系統(tǒng)的高效橢圓曲線多標(biāo)量乘算法

尤文珠，葛海波

（西安郵電大學(xué)電子工程學(xué)院，西安 710121）

0 概述

隨著無線通信技術(shù)的快速發(fā)展，人們對(duì)物聯(lián)網(wǎng)安全的需求與日俱增，而加密技術(shù)可在確保用戶身份驗(yàn)證和授權(quán)、通信數(shù)據(jù)機(jī)密性和完整性等方面發(fā)揮重要作用。自1975年RIVEST、SHAMIR和ADLEMAN提出RSA公鑰密碼體制以來，其得到了廣泛的研究和應(yīng)用，但該系統(tǒng)嚴(yán)重依賴使用1 024 bit和2 048 bit等大密鑰位的整數(shù)分解難題（Integer Factorization Problem，IFP）［1］。之后，MILLER［2］和KOBLITZ［3］提出的橢圓曲線密碼體制（Elliptic Curve Cryptography，ECC）使該情況得到了改善。ECC具有與RSA相同功能的公鑰密碼體制［4］，其計(jì)算原理是求解橢圓曲線離散對(duì)數(shù)問題（Ellipse Curve Discrete Logarithm Problem，ECDLP）。相比當(dāng)前主流的加密系統(tǒng)，ECC以更小的密鑰尺寸提供了更高級(jí)別的安全性，并且運(yùn)行速度快，適用于計(jì)算資源受限的智能移動(dòng)終端。

ECC中的標(biāo)量乘法相比其他運(yùn)算層是求逆次數(shù)最多且最核心的運(yùn)算，標(biāo)量乘法的運(yùn)算速率對(duì)實(shí)現(xiàn)整個(gè)密碼體制的性能起到關(guān)鍵作用。標(biāo)量乘運(yùn)算又稱為點(diǎn)乘運(yùn)算，即其中，k是一個(gè)整數(shù)，P為橢圓曲線上的一個(gè)基點(diǎn)。在多數(shù)情況下，二元表示、非鄰接形式（Non-Adjacent Form，NAF）、滑動(dòng)窗口法以及雙基多基標(biāo)量乘等［5-6］方法通過研究標(biāo)量k來改進(jìn)標(biāo)量乘運(yùn)算，從而找到更有效表示k的方法。ECC中的多標(biāo)量乘運(yùn)算在ECDH［7］等密碼協(xié)商協(xié)議中具有重要作用，可表示為k1P1+k2P2+…+km Pm，在驗(yàn)證橢圓曲線數(shù)字簽名時(shí)通常需要計(jì)算kP+JQ［8］，其中，P、Q是橢圓曲線上的兩個(gè)基點(diǎn)，k、J是兩個(gè)正整數(shù)。ECC中的直接算法、Shamir算法［9］、交錯(cuò)NAF算法［10］等多標(biāo)量乘算法都是通過將ki分解為0和1比特串使其最大限度地出現(xiàn)零列。

文獻(xiàn)［11］提出雙基數(shù)系統(tǒng)（Double-Base Number System，DBNS）。文獻(xiàn)［12］改進(jìn)雙基思想，將其擴(kuò)展為多基數(shù)系統(tǒng)（Multi-Base Number System，MBNS），且提出5倍點(diǎn)的計(jì)算公式及標(biāo)量乘法，大幅提高了計(jì)算速度。文獻(xiàn)［13］主要給出一種k1，k2，…，km的帶符號(hào)二進(jìn)制表示方法，使其全零列的數(shù)量盡可能多，并且在此基礎(chǔ)上提出一種新的計(jì)算多標(biāo)量乘的算法，降低了算法時(shí)間復(fù)雜度。文獻(xiàn)［14］提出一種基于互反形式（MOF）的標(biāo)量乘并行計(jì)算方法。文獻(xiàn)［15］從計(jì)算復(fù)雜度的角度研究ECC標(biāo)準(zhǔn)曲線優(yōu)化問題，提出一種基于w-NAF（其中w表示窗口寬度）的標(biāo)量點(diǎn)乘算法。文獻(xiàn)［16］研究基于NAF的ECC標(biāo)量乘算法優(yōu)化問題，提出一種將加減標(biāo)量乘算法與NAF表示相結(jié)合的新算法，提高了ECC計(jì)算性能。文獻(xiàn)［17］將雙基數(shù)系統(tǒng)用于多點(diǎn)乘運(yùn)算并提出3種基于雙基數(shù)系統(tǒng)的多點(diǎn)乘算法。本文在文獻(xiàn)［17］算法的基礎(chǔ)上，提出一種以2、3、7為基元的多基鏈整數(shù)表示方法和兩種多標(biāo)量乘快速算法。

1 相關(guān)概念

1.1 橢圓曲線定義

定義1有限域上的橢圓曲線方程在域K上定義為［11］：

其中，系數(shù)a1，a2，a3，a4，a6∈K，Δ≠0，Δ為橢圓曲線判別式，域K中的每個(gè)點(diǎn)(x1，y1)都滿足式（1）。在素域K=Fp上，式（1）可簡化為：

其中，a，b∈K，Δ=4a3+27b2。

在二元域K=F2上，式（1）可簡化為：

其中，a，b∈K，Δ=b≠0。

標(biāo)量乘運(yùn)算在實(shí)現(xiàn)過程中會(huì)調(diào)用點(diǎn)加和倍點(diǎn)運(yùn)算，而點(diǎn)加和倍點(diǎn)運(yùn)算又會(huì)再調(diào)用底層有限域算術(shù)運(yùn)算，即標(biāo)量乘算法的運(yùn)算效率受底層域運(yùn)算的影響。表1給出了有限域中相關(guān)操作的運(yùn)算量統(tǒng)計(jì)，其中，I表示求逆操作，S和M表示平方和乘法操作。

表1 相關(guān)操作的運(yùn)算量統(tǒng)計(jì)Table 1 Statistics of computation amount of related operations

1.2 整數(shù)k 的雙基表示

雙基鏈?zhǔn)菣E圓曲線標(biāo)量乘算法的一種加速方法，其中每個(gè)正整數(shù)n都可表示為2a3b的和或差形式。

定義2設(shè)集合B={2，3}，則整數(shù)k可表示為如下形式［1］：

該形式為整數(shù)k的雙基鏈表示，其中，{ai}，{bi} 為單調(diào)遞減序列，di∈{-1，1}。雙基鏈表示高度稀疏，可減少標(biāo)量展開的漢明權(quán)值。由于三元基表示方法引入了高效的三倍公式，因此其大幅減少了標(biāo)量乘法的運(yùn)行時(shí)間。例如，使用雙基鏈計(jì)算4012174=21137-2936-2835-2735+2532+2431-2130。

1.3 w-NAF算法

整數(shù)k可表示為長度為l的二進(jìn)制序列，考慮到NAF一次只能處理兩個(gè)連續(xù)的相鄰位。w-NAF對(duì)NAF進(jìn)行了擴(kuò)充［18］，采用整數(shù)k的w位表示，這樣便可使非零元素的取值范圍從[-1，1 ]擴(kuò)展到[-2w-1，2w-1-1]。令w≥2，則正整數(shù)k的w位寬度的NAF表達(dá)式為：

其中，ki是奇數(shù)且|kj|＜2w-1。

算法1w-NAF算法

2 多基整數(shù)表示方法和多標(biāo)量乘算法

2.1 多基整數(shù)表示方法

多基數(shù)系統(tǒng)作為雙基數(shù)系統(tǒng)的一個(gè)擴(kuò)展，其漢明重量變小，標(biāo)量表示鏈長也隨之變短，進(jìn)而使標(biāo)量乘運(yùn)算效率得到明顯提高。對(duì)于一組小整數(shù)集合B={b1，b2，…，bi}，如果用元素和的形式來表示標(biāo)量k，則任何一個(gè)整數(shù)k都可以表示為其中si表示符號(hào)位，{ei1}，{ei2}，…，{eil}≥0為單調(diào)遞減序列。由于多基整數(shù)表示系統(tǒng)將{2，3，7}作為多基系統(tǒng)的基元，因此本文提出標(biāo)量k的多基表示方法。

定義3設(shè)集合B={2，3，7}，則整數(shù)k可以表示成如下形式：

該形式即為整數(shù)的多基數(shù)表示，其中，{bi}、{ti}、{qi}變化呈遞減形式，si∈{-1，1}，m為多基數(shù)表示的長度。多基鏈相較雙基鏈冗余度不僅更高，而且漢明重量也更小。例如，當(dāng)si=1時(shí)，整數(shù)100總計(jì)有402個(gè)雙基數(shù)表示方法，而多基數(shù)表示可達(dá)8 425個(gè)［19］。bi、ti、qi的數(shù)值大小對(duì)2、3、7倍點(diǎn)運(yùn)算的運(yùn)算次數(shù)有直接影響。使用DBNS表示一個(gè)160位的大數(shù)，需約23項(xiàng)，然而使用MBNS表示則僅需約15項(xiàng)［20］。由此可看出，使用多基鏈能有效提高ECC中的標(biāo)量乘法運(yùn)行效率，通常采用貪婪算法編碼可獲得多基鏈的整數(shù)表示。

算法2貪婪算法

2.2 基于MBNS滑動(dòng)窗口的多標(biāo)量乘快速算法

算法3采用滑動(dòng)窗口算法可以有效降低時(shí)間復(fù)雜度。該算法運(yùn)行在底層元素集合的大數(shù)組上的一個(gè)子列表上，在運(yùn)行整個(gè)列表時(shí)會(huì)進(jìn)行特定操作，動(dòng)態(tài)尋找窗口以減少存儲(chǔ)空間，其中實(shí)際窗口計(jì)算數(shù)小于d。點(diǎn)加的運(yùn)算次數(shù)由多基表示的鏈長和非零位數(shù)決定，也會(huì)隨著窗口寬度w的變化而變化。基于算法3的有限域中窗口寬度及相應(yīng)點(diǎn)加平均運(yùn)算次數(shù)如表2所示，其中表示二元域，E(FP)表示素域分別表示二元域和素域上不同窗口寬度下的平均點(diǎn)加次數(shù)。

表2 基于算法3的有限域窗口寬度及相應(yīng)點(diǎn)加平均運(yùn)算次數(shù)Table 2 The window widths and the average computation number of corresponding point plus in the finite field based on algorithm 3

算法3中假設(shè)基點(diǎn)已知，即定點(diǎn)標(biāo)量乘運(yùn)算，因此無需多次更換預(yù)計(jì)算表，主要計(jì)算賦值階段的運(yùn)算消耗。本文在jmax=3下對(duì)算法性能進(jìn)行分析研究，先對(duì)MBNS表示的每個(gè)窗口進(jìn)行點(diǎn)加操作，然后分別對(duì)i(i=3)個(gè)標(biāo)量求和，算法3在賦值階段所需總的點(diǎn)加運(yùn)算次數(shù)為

2.3 基于交錯(cuò)MBNS滑動(dòng)窗口的多標(biāo)量乘快速算法

基于交錯(cuò)MBNS滑動(dòng)窗口的多標(biāo)量乘快速算法I-MB NS采用w-NAF表示，只需計(jì)算小于2w-1的奇數(shù)項(xiàng)。例如，對(duì)于一個(gè)數(shù)的7-NAF表示，只需計(jì)算介于-63～63的奇數(shù)項(xiàng)，因此其點(diǎn)加運(yùn)算次數(shù)會(huì)減少。首先計(jì)算標(biāo)量kj的NAFw形式，其次進(jìn)行預(yù)處理操作，使用MBNS表示串并計(jì)算出iP1、mP2、的數(shù)值結(jié)果，最后根據(jù)預(yù)處理值，經(jīng)點(diǎn)加和倍點(diǎn)的反復(fù)運(yùn)算操作得到

算法4基于交錯(cuò)MBNS滑動(dòng)窗口的多標(biāo)量乘快速算法

表3 基于算法4的有限域窗口寬度及相應(yīng)點(diǎn)加平均運(yùn)算次數(shù)Table 3 The window widths and the average computation number of corresponding point plus in the finite field based on algorithm 4

3 運(yùn)算效率分析

本文對(duì)Sliding MBNS和I-MBNS算法在jmax=3下進(jìn)行實(shí)驗(yàn)并用Python實(shí)現(xiàn)上述算法。為便于算法性能對(duì)比，Shamir算法［21］和交錯(cuò)NAF算法［22］的窗口大小分別為2 bit和4 bit～8 bit，Sliding MBNS和I-MBNS算法的窗口大小為10 bit～16 bit。表4將Shamir算法、交錯(cuò)NAF算法、Sliding MBNS和I-MBNS算法在二元域（E(F2m)）和素域（E(FP)）上的底層域平均運(yùn)算量進(jìn)行比較，設(shè)置，標(biāo)量長度分別取160 bit、192 bit和230 bit。

表4 算法平均運(yùn)算量比較Table 4 Comparison of average computation amount of algorithms

根據(jù)實(shí)驗(yàn)數(shù)據(jù)分析可知：在二元域上t=160 bit時(shí)，Sliding MBNS算法相比Shamir算法和交錯(cuò)NAF算法運(yùn)算量分別減少了10.00%和1.69%；I-MBNS算法相比Shamir算法和交錯(cuò)NAF算法運(yùn)算量分別減少了13.00% 和4.97%。在素域上t=160 bit時(shí)，Sliding MBNS算法相比Shamir算法運(yùn)算量減少了11.50%，I-MBNS算法相比Shamir算法和交錯(cuò)NAF算法運(yùn)算量分別減少了15.02%和3.11%。Shamir、交錯(cuò)NAF、Sliding MBNS和I-MBNS算法在二元域和素域上的運(yùn)算量對(duì)比結(jié)果如圖1和圖2所示。由圖1和圖2可以看出，無論二元域還是素?cái)?shù)域，Sliding MBNS和I-MBNS算法的運(yùn)算量明顯低于Shamir和交錯(cuò)NAF算法，運(yùn)算效率更高。本文還分析了算法運(yùn)算量與窗口寬度的關(guān)系。以二元域I-MBNS為例，t=160 bit時(shí)不同窗口對(duì)應(yīng)的平均運(yùn)算量如表5所示。

圖1 二元域算法運(yùn)算量對(duì)比結(jié)果Fig.1 Comparison results of algorithm computation amount in binary domain

圖2 素域算法運(yùn)算量對(duì)比結(jié)果Fig.2 Comparison result of algorithm computatuion amount in prime field

表5 t=160 bit時(shí)不同窗口寬度對(duì)應(yīng)的平均運(yùn)算量Table 5 Average computation amount corresponding to different window widths when t=160 bit

由表5可知，不同窗口寬度對(duì)應(yīng)的平均運(yùn)算量不同，并且隨著窗口寬度的不斷增大，平均運(yùn)算量逐漸減少。為能更清晰地顯示兩者之間的變化情況，繪制二元域窗口寬度與平均運(yùn)算量的曲線圖，如圖3所示?？梢钥闯?，當(dāng)t=160 bit時(shí)，隨著I-MBNS算法窗口寬度的不斷增大，平均運(yùn)算量呈下降趨勢。

圖3 二元域窗口寬度與平均運(yùn)算量的關(guān)系Fig.3 The relationship between the window widths and the average computation amount in binary domain

4 結(jié)束語

本文結(jié)合多基數(shù)系統(tǒng)和滑動(dòng)窗口算法，提出一種以2、3、7為基元的多基整數(shù)表示形式及Sliding MBNS和I-MBNS兩種多標(biāo)量乘算法，分析并比較了Sliding MBNS和I-MBNS算法在二元域和素域及不同窗口寬度下的平均運(yùn)算量。實(shí)驗(yàn)結(jié)果表明，Sliding MBNS和I-MBNS算法大幅提升了運(yùn)算效率，且隨著窗口寬度的不斷增加，平均運(yùn)算量呈現(xiàn)下降趨勢，進(jìn)而加速多標(biāo)量乘運(yùn)算及ECC整體實(shí)現(xiàn)。下一步將融合目前主流橢圓曲線密碼體制的硬件實(shí)現(xiàn)，將標(biāo)量乘算法應(yīng)用于網(wǎng)絡(luò)信息安全傳輸中，保證信息傳輸?shù)母咝院桶踩浴?/p>