基于N 進(jìn)制位權(quán)下NAF 的橢圓曲線(xiàn)標(biāo)量乘算法

趙增

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

0 引言

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

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

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

1 相關(guān)知識(shí)介紹與分析

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

橢圓曲線(xiàn)上的點(diǎn)群的運(yùn)算可以概括的分為兩層，即底層的點(diǎn)加與倍點(diǎn)運(yùn)算和上層的點(diǎn)乘運(yùn)算。

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

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

文獻(xiàn)[8]在公式（3）的基礎(chǔ)上提出直接計(jì)算4P，8P，16P的公式。文獻(xiàn)[9]在此基礎(chǔ)上給出了直接計(jì)算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。

而文獻(xiàn)[10]給出了直接計(jì)算3P，5P，3kP，5kP的計(jì)算方法。

2 基于N進(jìn)制位權(quán)的非相鄰形式的橢圓曲線(xiàn)標(biāo)量乘的快速算法

2.1 正整數(shù)展開(kāi)成N進(jìn)制位權(quán)的非相鄰形式

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

（1）N進(jìn)制位權(quán)的非相鄰形式定義及性質(zhì)

定義1數(shù)制中的一個(gè)m位整數(shù)k，在數(shù)k的任意編碼位置處都有相應(yīng)的與其對(duì)應(yīng)的單位權(quán)值，我們把這一單位權(quán)值稱(chēng)為與其位置對(duì)應(yīng)的位權(quán)。

例如，一個(gè)8位十六進(jìn)制編碼的整數(shù)k，其編碼為F1010E01。整數(shù)k的第0位處的數(shù)值為1，其位置相應(yīng)的權(quán)值為160，此位置處代表的數(shù)據(jù)為 ，此時(shí)把整數(shù)k的第0位記成K0，把K0相應(yīng)的權(quán)值稱(chēng)為K0位權(quán)。

性質(zhì)（N進(jìn)制位權(quán)的非相鄰形式的性質(zhì)）令k是一個(gè)正整數(shù)。

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

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

●NBW-NAF(k)的長(zhǎng)度最多比k的N進(jìn)制形式的長(zhǎng)度大1。

●NBW-NAF(k)的長(zhǎng)度最多比k的N進(jìn)制形式的長(zhǎng)度小1。

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

上橢圓曲線(xiàn)的點(diǎn)乘NP運(yùn)算公式。

（2）正整數(shù)展開(kāi)成N進(jìn)制位權(quán)的非相鄰形式的構(gòu)造過(guò)程

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

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

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

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

算法1正整數(shù)展開(kāi)成N進(jìn)制位權(quán)的非相鄰形式的算法

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

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

2.2 基于N進(jìn)制位權(quán)的非相鄰形式的橢圓曲線(xiàn)標(biāo)量乘的快速算法的實(shí)現(xiàn)

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

算法2基于N進(jìn)制位權(quán)的非相鄰形式的橢圓曲線(xiàn)標(biāo)量乘的快速算法

輸出：輸出橢圓曲線(xiàn)密碼體制中點(diǎn)乘的值，即kP

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

3 算法分析與仿真實(shí)驗(yàn)

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

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

（1）算法的終止

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

（2）算法的正確性

算法的正確性證明：

由N進(jìn)制位權(quán)的非相鄰形式的性質(zhì)可得，算法1一定可以把正整數(shù)k轉(zhuǎn)化為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)的基礎(chǔ)上，又由定理2和算法2的第11步到第13步可得NBW-NAF算法的橢圓曲線(xiàn)點(diǎn)群上的點(diǎn)乘運(yùn)算可以表示為：

由公式（5）的可得NBW-NAF算法計(jì)算點(diǎn)乘kP的運(yùn)算是正確的。

3.2 仿真實(shí)驗(yàn)

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

表1 橢圓曲線(xiàn)參數(shù)設(shè)置表

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

表2 不同算法點(diǎn)乘運(yùn)算比較表

4 結(jié)語(yǔ)

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