尤文珠，葛海波

（西安郵電大學電子工程學院，西安 710121）

0 概述

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

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

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

1 相關概念

1.1 橢圓曲線定義

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

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

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

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

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

標量乘運算在實現過程中會調用點加和倍點運算，而點加和倍點運算又會再調用底層有限域算術運算，即標量乘算法的運算效率受底層域運算的影響。表1給出了有限域中相關操作的運算量統(tǒng)計，其中，I表示求逆操作，S和M表示平方和乘法操作。

表1 相關操作的運算量統(tǒng)計Table 1 Statistics of computation amount of related operations

1.2 整數k 的雙基表示

雙基鏈是橢圓曲線標量乘算法的一種加速方法，其中每個正整數n都可表示為2a3b的和或差形式。

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

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

1.3 w-NAF算法

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

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

算法1w-NAF算法

2 多基整數表示方法和多標量乘算法

2.1 多基整數表示方法

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

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

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

算法2貪婪算法

2.2 基于MBNS滑動窗口的多標量乘快速算法

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

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

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

2.3 基于交錯MBNS滑動窗口的多標量乘快速算法

基于交錯MBNS滑動窗口的多標量乘快速算法I-MB NS采用w-NAF表示，只需計算小于2w-1的奇數項。例如，對于一個數的7-NAF表示，只需計算介于-63～63的奇數項，因此其點加運算次數會減少。首先計算標量kj的NAFw形式，其次進行預處理操作，使用MBNS表示串并計算出iP1、mP2、的數值結果，最后根據預處理值，經點加和倍點的反復運算操作得到

算法4基于交錯MBNS滑動窗口的多標量乘快速算法

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

3 運算效率分析

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

表4 算法平均運算量比較Table 4 Comparison of average computation amount of algorithms

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

圖1 二元域算法運算量對比結果Fig.1 Comparison results of algorithm computation amount in binary domain

圖2 素域算法運算量對比結果Fig.2 Comparison result of algorithm computatuion amount in prime field

表5 t=160 bit時不同窗口寬度對應的平均運算量Table 5 Average computation amount corresponding to different window widths when t=160 bit

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

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

4 結束語

本文結合多基數系統(tǒng)和滑動窗口算法，提出一種以2、3、7為基元的多基整數表示形式及Sliding MBNS和I-MBNS兩種多標量乘算法，分析并比較了Sliding MBNS和I-MBNS算法在二元域和素域及不同窗口寬度下的平均運算量。實驗結果表明，Sliding MBNS和I-MBNS算法大幅提升了運算效率，且隨著窗口寬度的不斷增加，平均運算量呈現下降趨勢，進而加速多標量乘運算及ECC整體實現。下一步將融合目前主流橢圓曲線密碼體制的硬件實現，將標量乘算法應用于網絡信息安全傳輸中，保證信息傳輸的高效性和安全性。