橢圓曲線加密的硬件實(shí)現(xiàn)

 摘 要： 橢圓曲線加密是一種目前已知的所有公鑰密碼體制中能夠提供最高比特強(qiáng)度的一種公鑰體制。在FPGA實(shí)現(xiàn)橢圓曲線加密系統(tǒng)時，基于GF(2)的多項(xiàng)式有限域中的乘法、求逆運(yùn)算是其中的兩大難點(diǎn)。本文提供了一種橢圓曲線加密的FPGA實(shí)現(xiàn)的結(jié)構(gòu)，著重討論了基于GF(2)的多項(xiàng)式有限域中的乘法、求逆運(yùn)算的實(shí)現(xiàn)，并與軟件實(shí)現(xiàn)的性能進(jìn)行了比較。

關(guān)鍵詞： FPGA；多項(xiàng)式有限域；橢圓曲線加密系統(tǒng)

加密的安全性
從數(shù)論的角度來說，任何公鑰密碼系統(tǒng)都建立在一個NP(無法處理的問題)的基礎(chǔ)上，即對于特定的問題，沒有辦法找到一個多項(xiàng)式時間算法求解該問題。一般求解此類問題的算法都是指數(shù)時間或者亞指數(shù)時間，例如現(xiàn)在常用的RSA算法就是基于大整數(shù)因式分解問題的難解性。經(jīng)過近三十多年的研究，RSA算法雖然并不存在多項(xiàng)式時間的算法，但是可以找到亞指數(shù)時間的算法，目前其密鑰長度必須大于1024位才能保證信息傳遞的安全，而橢圓曲線加密系統(tǒng) (Elliptic Curve Cryptosystem—ECC) 是目前已知的所有公鑰密碼體制中能夠提供最高比特強(qiáng)度 (Strength-Per-Bit) 的一種公鑰體制，只需要160的密鑰就可以達(dá)到1024位RSA算法提供的安全等級。其根據(jù)是有限域上的橢圓曲線上的點(diǎn)群中的離散對數(shù)問題(ECDLP)，許多密碼專家認(rèn)為它是指數(shù)級的難度。因此對于橢圓曲線加密系統(tǒng)來說，這一點(diǎn)從計(jì)算量、處理速度、存儲空間和通信帶寬等角度分析，橢圓曲線加密系統(tǒng)都有很大的優(yōu)勢。IEEE已經(jīng)制定的公鑰加密算法標(biāo)準(zhǔn)P1363就是基于ECC算法的。現(xiàn)在密碼學(xué)界普遍認(rèn)為它將替代RSA成為通用的公鑰密碼算法，目前已成為研究的熱點(diǎn)，是很有前途的研究方向。

圖2 密鑰、數(shù)據(jù)交換

圖4 橢圓曲線加密系統(tǒng)FPGA電路模塊框圖

圖5 驗(yàn)證系統(tǒng)結(jié)構(gòu)

橢圓曲線加密體制
橢圓曲線
引進(jìn)Non-supersingular橢圓曲線Weierstrass方程E:Y2+XY=X3+aX2+c其中a,c∈GF(2k),c≠0。為簡化以后的運(yùn)算，引進(jìn)z使X=x/z；Y=y/z，則橢圓曲線方程化為E:y2z+xyz=x3+ax2z+cz3，定義(x, y, z)=λ(x, y, z)?？梢钥闯霎?dāng)z≠0，(X, Y)和(x, y, z)相對應(yīng)，當(dāng)z=0可以理解為沿y軸趨向無窮遠(yuǎn)，定義為無窮遠(yuǎn)點(diǎn)O。則橢圓曲線上所有的點(diǎn)外加無窮遠(yuǎn)點(diǎn)構(gòu)成的集合構(gòu)成一個Abel群，O是單位元(零元)。在橢圓曲線E上定義了兩種點(diǎn)運(yùn)算：點(diǎn)運(yùn)算和點(diǎn)運(yùn)算。
1) 橢圓曲線上點(diǎn)運(yùn)算定義為：設(shè)P=( x1, y1, 1)∈E，Q=( x2, y2, 1) ∈E，-P=( x1, y1+ x1, 1), 當(dāng)Q≠-P時 PQ=(x3, y3, z3) 則
當(dāng)P≠Q時：
其中A=(x2z1+x1),B=(y2z1+y1), C=A+B,D=A2(A+a2z1)z1BC
當(dāng)P=Q時：
其中
2) 橢圓曲線上的點(diǎn)運(yùn)算定義為：設(shè)P=(x1, y1, 1)∈E，(ltlt-1...l0)2是整數(shù)l的二進(jìn)制表示形式，lP=PPAP=Q且Q∈E。
利用上面的點(diǎn)運(yùn)算，得點(diǎn)算法實(shí)現(xiàn)如圖1所示。定義l=logpQ，若P的周期很大，則利用l、P求Q是比較容易的，但利用P、Q求l是很難處理的，這就是ECDLP，橢圓曲線加密就是建立在這個難題之上。
加密體制
在Diffe-Hellman公鑰系統(tǒng)體制中，具體的橢圓曲線、曲線上點(diǎn)P及P的周期大素?cái)?shù)N都是公開信息。
A和B要進(jìn)行通訊，首先得到橢圓曲線E、點(diǎn)P及素?cái)?shù)N。然后用戶A將[1,N-1]中隨機(jī)選取的整數(shù)a作為私鑰，A將KpubA=aP作為自己的公鑰傳送給用戶B，與此同時B將 [1,N-1]中隨機(jī)選取的整數(shù)b作為私鑰，并將KpubB=bP作為自己的公鑰傳送給A。A、B各自將自己的私鑰點(diǎn)乘于對方傳過來的公鑰得到KAB，這樣就完成了密鑰的交換過程。當(dāng)用戶A需要將待傳數(shù)據(jù)m傳送給用戶B時，A利用m和KAB生成Em，當(dāng)用戶B得到Em后，利用密鑰交換過程自己生成的KAB和從用戶A處得到的加密數(shù)據(jù)Em生成數(shù)據(jù)m。見圖2。

橢圓加密體制實(shí)現(xiàn)
迄今所投入使用的橢圓加密系統(tǒng)中，絕大部分的密鑰長度都比較短，一般集中在30~60位，這是因?yàn)樵谲浖?shí)現(xiàn)時，由于軟件執(zhí)行速率所限，密鑰長度比較大(≥160)的橢圓加密系統(tǒng)的速率將達(dá)不到使用要求。與此同時，在硬件實(shí)現(xiàn)時，密鑰長度比較大的橢圓加密系統(tǒng)將耗費(fèi)大量的硬件資源。隨著橢圓加密算法研究的深入和可編程邏輯器件的快速發(fā)展，利用可編程邏輯器件實(shí)現(xiàn)橢圓加密系統(tǒng)已經(jīng)是一個可能的選擇，下面將介紹一種實(shí)現(xiàn)方案，并且用軟、硬件分別實(shí)現(xiàn)。
根據(jù)以上橢圓加密體制的要求，設(shè)計(jì)出圖3的加密系統(tǒng)結(jié)構(gòu)圖，其中橢圓加密系統(tǒng)參數(shù)接口獲取與加密有關(guān)的橢圓的基本參數(shù)，如私鑰、橢圓曲線、橢圓曲線上的給定點(diǎn)等。橢圓曲線乘法控制部分主要負(fù)責(zé)如何計(jì)算乘法結(jié)果，會大量調(diào)用PP和PQ來實(shí)現(xiàn)乘法功能；而PP和PQ通過有限域加法、乘法和求逆的調(diào)用得到結(jié)果。
軟件模型驗(yàn)證
軟件實(shí)現(xiàn)的主要目的是為硬件實(shí)現(xiàn)建立驗(yàn)證模型，整個軟件的結(jié)構(gòu)如圖3所示。在軟件驗(yàn)證系統(tǒng)實(shí)現(xiàn)的過程中，有限域上的加法是異或操作。有限域上的乘法和求逆是關(guān)鍵點(diǎn)，必須預(yù)先考慮到硬件實(shí)現(xiàn)時的資源消耗，需要高效的算法。在此系統(tǒng)中使用了復(fù)合域GF((2n)m)帶來的特殊性，可以高效、快速的實(shí)現(xiàn)乘法和求逆運(yùn)算。
* GF(2n)上的乘法：A(y)×B(y)=C(Y)modQ(y)，Q(y)為既約多項(xiàng)式。常用的有： Paar-Rosner乘法器、Mastrovito乘法器、Massey-Omura乘法器、Hasan-Bhargava乘法器等，此處介紹兩種選擇：
1) 當(dāng)n比較小時可用查表法實(shí)現(xiàn)，設(shè)ω為Q(y)=0的本原根，則F2n={0,ω,Aω2n-1}，利用查表法取得A、B的級次數(shù)a、b，C的級次c=a+b，再次利用查表法由c得C。在本系統(tǒng)中就使用了此法實(shí)現(xiàn)GF(2n)上的乘法。
2) 當(dāng)n比較大時，利用查表法資源消耗太大，難以承受，可利用C=Z×B(n比較大時)，Z是由A(y),Q(y)確定的矩陣，其中：

* 復(fù)合有限域的乘法：以GF((24)2)為例，利用GF(24)上的乘法和加法可以構(gòu)造出GF(28)的乘法。子域GF(24)的本原多項(xiàng)式為Q(y)=y4+y+1，第二個子域的本原多項(xiàng)式為R(z)=z3+z+ω14，其中ω是GF(24)的基底元素，滿足Q(ω)=0。域中兩個元素的乘法[a0+a1z]×[b0+b1z]可以表示為：

這樣GF((24)2)在復(fù)合域上的乘法就可以通過GF(24)上的有限域的數(shù)學(xué)運(yùn)算而得到。
* 復(fù)合有限域的逆運(yùn)算：復(fù)合有限域GF((2n)m)中的元素A的逆為：
其中
可以觀察到Ar屬于子域GF(2n)中的元素，可以較容易的求取(Ar)-1的值。
FPGA硬件實(shí)現(xiàn)
軟件化的實(shí)現(xiàn)方法開發(fā)時間短，但是其加密速度比較慢，妨礙了橢圓曲線加密的實(shí)用性。FPGA的方法綜合了軟件的靈活性和硬件的安全性，提供了比軟件化方法優(yōu)越的速度，和傳統(tǒng)的ASIC實(shí)現(xiàn)相比，可編程器件由于其高度的靈活性，更適合于密碼學(xué)的應(yīng)用領(lǐng)域。
在軟件模型的基礎(chǔ)上，我們針對FPGA硬件的特性對模型進(jìn)行了優(yōu)化。根據(jù)橢圓曲線加密算法的要求，對加密系統(tǒng)進(jìn)行模塊化設(shè)計(jì)，每個模塊獨(dú)立完成其各自功能，模塊之間進(jìn)行相互數(shù)據(jù)交換以及時序控制，達(dá)到加密功能。圖4是橢圓曲線加密系統(tǒng)FPGA實(shí)現(xiàn)的電路模塊框圖。
其中，橢圓曲線加密控制系統(tǒng)模塊是整個系統(tǒng)的核心。當(dāng)Ready為True時，系統(tǒng)讀入初始數(shù)據(jù)并且控制RAM進(jìn)行初始數(shù)據(jù)的存儲。在運(yùn)算過程中，該模塊根據(jù)數(shù)據(jù)源對選擇器進(jìn)行控制循環(huán)，進(jìn)行PP=R和PQ=R運(yùn)算，獲得最后結(jié)果，然后通過Out_Ready信號對結(jié)果進(jìn)行輸出；選擇器模塊根據(jù)控制系統(tǒng)模塊提供的指令對PP=R模塊和PQ=R模塊進(jìn)行控制，并且提供相應(yīng)的實(shí)時數(shù)據(jù)流；PP=R模塊和PQ=R模塊利用對有限域上的加法和乘法運(yùn)算進(jìn)行時序控制求出橢圓曲線上點(diǎn)的加法運(yùn)算，將直接影響到整個系統(tǒng)的速度性能，因此必須對有限域上的加法和乘法運(yùn)算設(shè)計(jì)合理的輸入輸出數(shù)據(jù)流，以達(dá)到高效率的運(yùn)算速率。各種存儲器模塊根據(jù)不同的指令分別存放系統(tǒng)的初始值、運(yùn)算過程中的中間值以及系統(tǒng)運(yùn)算結(jié)果。
綜合以上各種因素，我們選擇了XILINX 公司的VirtexII器件，ISE 4.1作為開發(fā)平臺，VHDL作為開發(fā)語言。由于168位的橢圓曲線加密算法的計(jì)算量比較大，所以在FPGA實(shí)現(xiàn)的時候，布線是個值得考慮的因素。對于FPGA器件的選擇應(yīng)考慮到布線資源，Virtex 系列提供的布線資源比較豐富。在Modelsim上進(jìn)行仿真后得到性能指標(biāo)為：在40MHz時鐘驅(qū)動下第一次加密或者解密時需要初始的建立時間，明文或者密文的輸出需要2ms左右，其后的明文或者密文的輸出大約為25Mbps。可以看出，這是一個比較高的速率，可以應(yīng)用于很多場合。
應(yīng)用系統(tǒng)驗(yàn)證
橢圓加密硬件實(shí)現(xiàn)后，必須在實(shí)際系統(tǒng)中得到驗(yàn)證。我們特地構(gòu)造了串口加密實(shí)驗(yàn)板