基于N 進制位權下NAF 的橢圓曲線標量乘算法

趙增

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

0 引言

橢圓曲線密碼體制（Elliptic Curve Cryptography，ECC）被Miller[1]和Koblitz[2]分別的獨立提出以來，受到密碼學科研工作者的廣泛關注和高度重視。ECC與其他公開的密碼體制對比，它擁有自己的優(yōu)點，例如運算效率高、安全等級相同時ECC所需密鑰長度短、ECC所需的帶寬少等。這些優(yōu)點促使ECC能在安全領域得到廣泛應用和研究。在當今信息化，大數(shù)據(jù)的時代，信息安全關乎重大，如何更迅速使得信息加密與解密也至關重要，因此ECC運算效率的提高也是該領域研究者的研究熱點。

在有限域Fq上橢圓曲線上的標量乘（點乘）是實現(xiàn)ECC加解密的關鍵步驟，這直接影響到ECC的運算效率。有個大的整數(shù)k和有限域Fq上橢圓曲線上的一個基點P，所謂的橢圓曲線上的標量乘就是計算kP。為了提高橢圓曲線密碼體制的運算效率，可以從有限域Fq上橢圓曲線上的標量乘著手。以前的研究者提出了二進制方法、NAF方法、Montgomery標量乘、Frobenius標量乘和固定基窗口方法等[3-5]。但是以上的算法要么是基于正整數(shù)k的分解方式，要么是基于底層域的減少點加與倍點上的求逆次數(shù)，這兩種方式從而來提高橢圓曲線上點乘的運算效率。沒有用這兩種方式交互融合，互相促進的方式來提升橢圓曲線上點乘的運算效率。

針對以上問題，本文提出了一種基于N進制位權的非相鄰形式的橢圓曲線標量乘的快速算法（簡稱為NBW-NAF算法）。NBW-NAF算法在實現(xiàn)過程中利用預計算生成預置表，通過查詢預置表使得算法的在進行多次點乘運算時效率得到提升。又由本文新提出的N進制位權的非相鄰形式的特點，這種編碼方式比常規(guī)二進制的編碼的位數(shù)更短，而且結合非相鄰形式的特點，極大減少了NBW-NAF算法主要循環(huán)步驟中的點加和N倍點的運算次數(shù)，從而使得NBW-NAF算法擁有更高的運算效率。

1 相關知識介紹與分析

本節(jié)對橢圓曲線上的點群的運算的概念進行介紹，之后對現(xiàn)有的個別方法進行舉例分析，提出有待改進的方向。

橢圓曲線上的點群的運算可以概括的分為兩層，即底層的點加與倍點運算和上層的點乘運算。

對于底層的點加與倍點運算，由于在不同的特征的有限域Fq上的橢圓曲線的點加與倍點運算有少許差異，篇幅有限，本節(jié)只介紹在特征等于2的有限域上的點加與倍點運算的情況。其他情形查考文獻[6]。

其中a,b∈F2m，其判別式b≠0，其無窮遠點記為∞。對于任意的Q=(x2,y2),P≠±Q其上的點加公式P+Q=(x3,y3)為：

文獻[8]在公式（3）的基礎上提出直接計算4P，8P，16P的公式。文獻[9]在此基礎上給出了直接計算2sP，1≤s≤m的公式。令2sP=(xs,ys)，P=(x0,y0)即得公式：其 中 cs= δ2,as=λ2+δλ,bs=as-14+δλxs而 δ=as-1cs-1,λ=as-12+bs-1cs-1,初始值 a0=x0,b0=y0，c0=1。

而文獻[10]給出了直接計算3P，5P，3kP，5kP的計算方法。

2 基于N進制位權的非相鄰形式的橢圓曲線標量乘的快速算法

2.1 正整數(shù)展開成N進制位權的非相鄰形式

為了提高橢圓曲線上的計算點乘kP的效率，先把整數(shù)k轉換成N進制，之后用N進制位權的非相鄰形式來表示整數(shù)k，即下文中的算法1來實現(xiàn)。

（1）N進制位權的非相鄰形式定義及性質

定義1數(shù)制中的一個m位整數(shù)k，在數(shù)k的任意編碼位置處都有相應的與其對應的單位權值，我們把這一單位權值稱為與其位置對應的位權。

例如，一個8位十六進制編碼的整數(shù)k，其編碼為F1010E01。整數(shù)k的第0位處的數(shù)值為1，其位置相應的權值為160，此位置處代表的數(shù)據(jù)為 ，此時把整數(shù)k的第0位記成K0，把K0相應的權值稱為K0位權。

性質（N進制位權的非相鄰形式的性質）令k是一個正整數(shù)。

●K一定存在N進制位權的非相鄰形式，并記為NBW-NAF(k)。

●NBW-NAF(k)在k的所有帶符號形式中具有最少的非零位。

●NBW-NAF(k)的長度最多比k的N進制形式的長度大1。

●NBW-NAF(k)的長度最多比k的N進制形式的長度小1。

定理1對于任意正整數(shù)N和已知橢圓曲線上某一基點P，我們一定可以推導出直接進行計算在有限域F2m

上橢圓曲線的點乘NP運算公式。

（2）正整數(shù)展開成N進制位權的非相鄰形式的構造過程

由N進制位權的非相鄰形式的定義，其中沒有任意連續(xù)相鄰的不同位權處的數(shù)值是非零的，并且每一位權處的數(shù)值不大于■■N22。因此在把正整數(shù)k轉化為NBW-NAF(k)的算法中有如下的步驟。

首先，利用進制轉換把正整數(shù)k轉換成N進制，即，用k除以N，得到整數(shù)商和余數(shù)，記錄余數(shù)，之后，用k減去余數(shù)從而整除N得到的整數(shù)來更新原來的整數(shù)k的值，再用新得到的整數(shù)k除以N，得到新一輪的商和余數(shù)，如此反復，直到最后k迭代成0為止。即算法1中第2步～第8步中得到的(N_Ki,…,N_K1,N_K0)就是正整數(shù)k的N進制表達式。

之后，對正整數(shù)k的 N進制表達式(N_Ki,…,N_K1,N_K0)從右到左執(zhí)行更新分離算法使得任意相鄰位權處的非零數(shù)不相鄰。即算法1中第11步到第18步，每次處理2個位權位置處的數(shù)值。

最后，經(jīng)過前兩個步驟之后得到的返回數(shù)(Kl-1,…,K1,K0)即為正整數(shù)k的N進制位權的非相鄰形式。其偽代碼如算法1所示。

算法1正整數(shù)展開成N進制位權的非相鄰形式的算法

輸入：輸入正整數(shù)k，選用k的N進制形式中的N（N＞1）

輸出：代表正整數(shù)k的 NBW-NAF(k),即表示為：(Kl-1,…,K1,K0)

2.2 基于N進制位權的非相鄰形式的橢圓曲線標量乘的快速算法的實現(xiàn)

由于N進制位權的非相鄰形式中每一位置處的位權和其相鄰處的位權差值不再是2倍關系，所以橢圓曲線密碼體制中的倍點公式不能直接用到現(xiàn)在的N進制位權的非相鄰形式的橢圓曲線點乘運算中。在特征為2的有限域F2m上的橢圓曲線上的點乘，我們可以有定理1推出直接進行計算NP的公式。在此基礎上，我們結合算法1得到的正整數(shù)展開成N進制位權的非相鄰形式進行展開，從而得到計算有限域F2m的橢圓曲線上的點乘。如下算法2所示。

算法2基于N進制位權的非相鄰形式的橢圓曲線標量乘的快速算法

輸出：輸出橢圓曲線密碼體制中點乘的值，即kP

1. 調(diào)用正整數(shù)展開成N進制位權的非相鄰形式的算法，并把輸入?yún)?shù)k，N傳遞給此算法。此算法返回k的NBW-NAF（k），即：(Kl-1,…,K1,K0)

3 算法分析與仿真實驗

首先對NBW-NAF算法進行理論證明與分析，然后把NBW-NAF算法與其他相關算法進行對比。為了比較的公平性與合理性，本文對實驗中的單位進行了統(tǒng)一的歸一化處理。

3.1 NBW-NAF算法的正確性分析

（1）算法的終止

對于算法1的步驟（2）到步驟（8），由于正整數(shù)k是有限的，所以算法1可以跳出while循環(huán)，由步驟（9）可知m是有限的，所以算法1的步驟（11）到步驟（18）也會執(zhí)行完，因此算法1也一定會終止。同理算法2也一定會終止。

（2）算法的正確性

算法的正確性證明：

由N進制位權的非相鄰形式的性質可得，算法1一定可以把正整數(shù)k轉化為NBW-NAF(k)。由算法1中第2步～第8步可知(N_Ki,…,NK1,NK0)=k，又由第11步到第18步可知(N_Ki,…,NK1,NK0)=(Kl-1,…,K1,K0)，所以k=(Kl-1,…,K1,K0)=NBW-NAF(k)。在k=(Kl-1,…,K1,K0)=NBW-NAF(k)的基礎上，又由定理2和算法2的第11步到第13步可得NBW-NAF算法的橢圓曲線點群上的點乘運算可以表示為：

由公式（5）的可得NBW-NAF算法計算點乘kP的運算是正確的。

3.2 仿真實驗

為了到達實驗的公平性與合理性，采用的是NIST推薦的橢圓曲線[11]定義在有限域F2m，橢圓曲線方程為：y2+xy=x3+ax2+b，基點為P(Px,Py)，其中階數(shù)為n，該橢圓曲線的參數(shù)設置見表1。以0x開頭的數(shù)據(jù)代表16進制數(shù)據(jù)。

表1 橢圓曲線參數(shù)設置表

為了進行合理公平的比較，我們?yōu)槠溥x擇了共同的實驗環(huán)境，其設置2.6GHz的i7處理器，8GB的內(nèi)存空間。我們選擇的編程工具是Visual Studio 2015，編程語言是C++。隨機生成6組256位隨機正整數(shù)。然后用這6組正整數(shù)與基為P(Px,Py)做點乘。下表2列出不同算法件的對比結果。由表2得NBW-NAF算法在N=2的情況下與二進制NAF算法的效率相當，在N＞2效率提高了26.91%～31.72%。

表2 不同算法點乘運算比較表

4 結語

本文提出了一種基于N進制位權下非相鄰形式的橢圓曲線標量乘算法：NBW-NAF算法。該算法結合了N進制位權下非相鄰形式下的優(yōu)勢與多進制下算法移位操作需要多倍點運算的優(yōu)勢，使得整體運算中求逆的次數(shù)大大減少，又通過查詢預置表，從而有效減少了運算過程中的時間開銷。本文對NBW-NAF算法的可行性、正確性分析證明以及效率分析驗證進行了詳細的描述。仿真實驗表明，與其他同類算法對比,NBW-NAF算法具有更高的運算效率。