基于FPGA的橢圓曲線密碼二進(jìn)制域運(yùn)算實現(xiàn)

沈慶偉，宛星斌，高莉

（安徽建筑大學(xué)電子與信息工程學(xué)院，合肥230601）

0 引言

橢圓曲線在代數(shù)學(xué)和幾何學(xué)上已經(jīng)廣泛研究了150多年之久，有著豐富的理論積累，1985年，Koblitz和Miller將橢圓曲線引入密碼學(xué)，橢圓曲線密碼體制（Elliptic Curve Cryptosystem，ECC）就此誕生[1]。

在目前眾多使用廣泛的公鑰密碼體制之中，ECC被認(rèn)為是每比特提供加密強(qiáng)度最高的一種密碼體制。這說明在相同的安全性能條件下，ECC大大縮短了密鑰長度。從安全性、計算速度、存儲空間來看，ECC擁有著非常好的應(yīng)用前景

ECC與RSA、ELGamal等公鑰密碼相比，具有抗攻擊性強(qiáng)，CPU占用少，內(nèi)容使用少，網(wǎng)絡(luò)消耗低，加密速度快和硬件實現(xiàn)面積更小的特點，是其他公鑰密碼系統(tǒng)所不能比的。由于ECC的安全性和優(yōu)勢可以廣泛應(yīng)用于電子信息通信、smart cards和無線傳感網(wǎng)絡(luò)終端。這些領(lǐng)域不僅要求具有高級別的安全性，還要具有較快的運(yùn)算速度和較小的存儲空間，ECC滿足了這些條件。在當(dāng)今信息安全鄰域中ECC占據(jù)重要的位置。隨著無線傳感器網(wǎng)絡(luò)技術(shù)和物聯(lián)網(wǎng)技術(shù)飛速的發(fā)展，在無線傳感器網(wǎng)絡(luò)和物聯(lián)網(wǎng)內(nèi)部信息傳輸加密與解密ECC也發(fā)揮著重要的作用。

ECC實現(xiàn)主要分為硬件實現(xiàn)和軟件實現(xiàn)。隨著通信技術(shù)的發(fā)展第五代移動通信技術(shù)（5G）已成為全球研發(fā)的熱點[2]，這意味著實現(xiàn)密碼體制需要更快的運(yùn)算速度和更高的安全性能，面對這些需求，ECC硬件實現(xiàn)相比軟件實現(xiàn)具有的發(fā)展前景與優(yōu)勢。那么，實現(xiàn)ECC運(yùn)算的硬件具有重大意義。由于二進(jìn)制域上橢圓曲線運(yùn)算更適合于硬件實現(xiàn)，后面將介紹二進(jìn)制域上的ECC運(yùn)算的硬件實現(xiàn)。

FPGA（現(xiàn)場可編程門陣列）往往被人們稱為可編程的“萬能芯片”，是現(xiàn)在比較流行的硬件設(shè)計和開發(fā)芯片[3]。理論上，如果擁有規(guī)模足夠大門電路，F(xiàn)PGA可以通過編程實現(xiàn)任意芯片的邏輯功能，F(xiàn)PGA的核心優(yōu)點是可編程靈活性高、開發(fā)周期短、并行計算可編程效率高。使用FPGA實現(xiàn)ECC二進(jìn)制域上的運(yùn)算，不僅提高其運(yùn)算速度，而且設(shè)計開發(fā)便捷。

本文介紹了ECC二進(jìn)制域上的運(yùn)算的硬件設(shè)計，選取了NIST推薦的K-163曲線，實現(xiàn)有限域運(yùn)算單元實現(xiàn)二進(jìn)制域下多項式基模加、模乘、模平方、模逆運(yùn)算。完成RTL代碼設(shè)計，在Vivado 2017.4軟件平臺下實現(xiàn)仿真。

1 有限域理論

1.1 有限域的基本概念

域是一類代數(shù)結(jié)構(gòu)，它擁有著豐富優(yōu)良的運(yùn)算性質(zhì)，而且應(yīng)用非常的廣泛[4]。例如實數(shù)域R、有理數(shù)Q、復(fù)數(shù)域C。這些都屬于域，域是代數(shù)結(jié)構(gòu)定義了加法（減法）和乘法（除法），滿足下列四則運(yùn)算的基本規(guī)律（交換律、結(jié)合律、分配律）。

a+b=b+a

a·b=b·a

a+b+c=a+(b+c)

a·b·c=a·(b·c)

a·(b+c)=a·b+a·c

(b+c)·a=b·a+c·a

在組合設(shè)計、編碼理論、密碼學(xué)和計算機(jī)等許多領(lǐng)域中，有限域具有重要的地位。

有限域又叫伽羅華域，設(shè)(F，+，?)是域，如果F是有限集，則稱F為有限域。對于素數(shù)p和正整數(shù)n，若有限域F的元素個數(shù)是pn，那么稱有限域的特征為p，可將F記為Fpn或GF(pn)。對于有限域F中任意元素α。

pα=α+α+α+...+α=0

1.2 二進(jìn)制域的表示方法

二進(jìn)制域GF(2n)表示方法有三種，多項式表示法[5]、多項式根的表示法和生成元表示法三種。這里介紹后面所用的方法多項式表示法，多項式表示法相對比較容易理解，硬件上實現(xiàn)也比較簡單。

多項式表示法：

構(gòu)造多項式域的數(shù)域為F2={0，1}，已知多項式集合：

設(shè)既約多項式（不可約多項式）為：

則GF(2n)=GF2[x]g(x)關(guān)于模g(x)的同余加法和乘法構(gòu)成域。

二進(jìn)制域GF(2n)在編碼理論扮演著重要的角色，而在數(shù)字計算機(jī)和數(shù)據(jù)傳輸或是存儲系統(tǒng)中同樣得到了普遍運(yùn)用。例如GF(23)=x5+x3+x+1，等價于比特串00101011。

NIST推薦的K-163、K-233、K-409等橢圓曲線，其二進(jìn)制域分別為GF(2163)、GF(2233)、GF(2409)，既約多項式分別為g(x)=x163+x7+x6+x3+1、g(x)=x233+x74+1，g(x)=x409+x87+1。后面的章節(jié)針對GF(2163)分析多項式基模加、模乘、模平方、模逆運(yùn)算。

2 二進(jìn)制域GF(2n)運(yùn)算分析

2.1 模加

設(shè)有限域為GF(2n)，其既約多項式為g(x)=xn+，域中元素有，C(x)=為運(yùn)算結(jié)果。

模加的運(yùn)算比較容易實現(xiàn)，在硬件設(shè)計中模加只需要按位異或即可。

2.2 模乘

設(shè)有限域為GF(2n)，其既約多項式為g(x)=xn+，域中元素有，C(x)=為運(yùn)算結(jié)果。

模乘運(yùn)算：

在二進(jìn)制域乘法除法過程的加法和減法是沒有進(jìn)位的模2計算，按位異或即可。

2.3 模平方

設(shè)有限域為 GF(2n)，其既約多項式為，域中元素有為運(yùn)算結(jié)果。模平方可以看作模乘的一個特例。

2.4 模逆

設(shè)有限域為GF(2n)，其既約多項式為g(x)=xn+，域中元素有A(x)=

由費(fèi)馬小定理[6]得：

這樣就把模逆運(yùn)算轉(zhuǎn)變?yōu)槟３诉\(yùn)算。

3 二進(jìn)制域GF(2n)算法模塊設(shè)計

3.1 加法模塊

設(shè)有限域為 GF(2n)，其既約多項式為，域 中 元 素 有為運(yùn)算結(jié)果。

輸入：(an-1...a1，a0)，(bn-1...b1，b0)

輸出：(cn-1...c1，c0)

步驟：

模加模塊設(shè)計圖如圖1所示。

3.2 乘法模塊

模乘運(yùn)算分為兩個部分，第一部分計算乘法部分，第二部分計算模既約多項式（不可約多項式）部分。由于在計算乘法的過程中是的n位的數(shù)被擴(kuò)展為2n-1位數(shù)，所以必須模上n+1位的數(shù)使得運(yùn)算結(jié)果在規(guī)定的域中。在乘法和求模的過程中，由于是多項式系數(shù)的運(yùn)算，運(yùn)算過程是沒有進(jìn)位的，加法和減法計算都是按位異或運(yùn)算。

圖1模加模塊

使用全并行計算方法實現(xiàn)，全并行計算算方法乘法部分和模既約除法器設(shè)計如下所示。

設(shè)有限域為 GF(2n)，其既約多項式為，域中元素有為運(yùn)算結(jié)果。

乘法算法部分：

輸入：A=(an-1...a1，a0)，B=(bn-1...b1，b0)

輸出：D=(d2n-2...d1，d0)

步驟：

d0=a0?b0

d1=a1?b0b1

d2=a2?

d3=a3?

...

dn-1=an-1?

...

d2n-5=an-1?bn-4d2n-4=an-1?bn-3

d2n-3=an-1?bn-2

d2n-2=an-1?bn-1

end

乘法器內(nèi)部結(jié)構(gòu)如圖2所示。

模既約除法器算法部分：

輸入：D=(d2n-2...d1，d0)，G=（1，gn-1...g1，g0)

輸出：C=(cn-1...c1，c0)

步驟：

將D用D1:D2兩段形式拼接

for j從1到D2的位數(shù)

if D1>G

則D1=D1^G

圖2乘法器內(nèi)部結(jié)構(gòu)

D1:D2左移一位

end

C=D1

end

模既約除法器設(shè)計圖如圖3所示。圖4為除法器中AXOR模塊的內(nèi)部結(jié)構(gòu)。

3.3 模逆模塊

上文介紹將模逆運(yùn)算用費(fèi)馬小定理轉(zhuǎn)換為模乘運(yùn)算，A-1=A2n-2，從公式上看計算模逆需要進(jìn)行大量的乘法運(yùn)算且運(yùn)算復(fù)雜的相當(dāng)大，根據(jù)文獻(xiàn)[5]提供的改進(jìn)算法如下，以n=163為例。

A22-1←A?A?A

A24-1←(A22-1)22?A22-1

A25-1←(A24-1)2?A

A210-1←(A25-1)25?A25-1

A220-1←(A210-1)210?A210-1

A240-1←(A220-1)220?A220-1

A280-1←(A240-1)240?A240-1

A281-1←(A280-1)2?A

A2162-1←(A281-1)281?A281-1

A2163-1←(A2162-1)2

這個算法成功的降低模乘運(yùn)算的復(fù)雜度。

圖3模既約除法器

圖4 AXOR模塊內(nèi)部結(jié)構(gòu)

4 結(jié)果仿真

根據(jù)前面文章對二進(jìn)制域運(yùn)算的設(shè)計與分析，二進(jìn)制域運(yùn)算核心是模加和模乘，使用Vivado 2017.4針對Xilinx Artix-7的FPGA設(shè)計模加和模乘RTL代碼，完成功能仿真。選用NIST推薦的K-163曲線，其二進(jìn)制域為GF(2163)，既約多項式為g(x)=x163+x7+x6+x3+1，實現(xiàn)163位操作數(shù)的運(yùn)算[7]。

模加：隨機(jī)選取兩個163位二進(jìn)制數(shù)其十六進(jìn)制表示如下：

A=163’

H6ced3df50d18ec55f1513da742ae2e2e287b40312

B=163’

H0e23aa6c3ede1026160969ccb8abd37e4725df218

運(yùn)算結(jié)果C如圖5所示。

C=163’

H62ce979933c6fc73e758546bfa05fd506f5e9f10a

圖5模加仿真圖

模乘：隨機(jī)選取兩個163位二進(jìn)制數(shù)其十六進(jìn)制表示如下：

A=163’

H6ced3df50d18ec55f1513da742ae2e2e287b40312

B=163’

H0e23aa6c3ede1026160969ccb8abd37e4725df218

運(yùn)算結(jié)果C如圖6所示。

圖6模乘仿真圖

C=163’

H2f9d5e8718f1f758cec6c9c04bc4ffcd5a286e181

5 結(jié)語

本文主要介紹對橢圓曲線密碼體制中二進(jìn)制有限域上的運(yùn)算設(shè)計與實現(xiàn)。本文從硬件編程角度設(shè)計出模既約除法器，并給出了一種較為簡單的實現(xiàn)方法。二進(jìn)制有限域上的運(yùn)算是橢圓曲線密碼體制的重要方面，實現(xiàn)二進(jìn)制有限域上的運(yùn)算為橢圓曲線運(yùn)算層和密碼協(xié)議層奠定基礎(chǔ)。接下來的研究工作是優(yōu)化運(yùn)算模塊的設(shè)計及提高模乘運(yùn)算的效率，實現(xiàn)參數(shù)可調(diào)整的橢圓曲線密碼系統(tǒng)設(shè)計。