名稱:橢圓曲線加密的硬體實現
摘要：橢圓曲線加密是一種目前已知的所有公鑰密碼體制中能夠提供最高比特強度的一種公鑰體制。在FPGA實現橢圓曲線加密系統時，基於GF(2)的多項式有限域中的乘法、求逆運算是其中的兩大難點。本文提供了一種橢圓曲線加密的FPGA實現的結構，著重討論了基於GF(2)的多項式有限域中的乘法、求逆運算的實現，並與軟體實現的性能進行了比較。
加密的安全性
從數論的角度來說，任何公鑰密碼系統都建立在一個NP(無法處理的問題)的基礎上，即對於特定的問題，沒有辦法找到一個多項式時間演算法求解該問題。一般求解此類問題的演算法都是指數時間或者亞指數時間，例如現在常用的RSA演算法就是基於大整數因式分解問題的難解性。經過近三十多年的研究，RSA演算法雖然並不存在多項式時間的演算法，但是可以找到亞指數時間的演算法，目前其密鑰長度必須大於1024位才能保證信息傳遞的安全，而橢圓曲線加密系統 (Elliptic Curve Cryptosystem—ECC)是目前已知的所有公鑰密碼體制中能夠提供最高比特強度 (Strength-Per-Bit)的一種公鑰體制，只需要160的密鑰就可以達到1024位RSA演算法提供的安全等級。其根據是有限域上的橢圓曲線上的點群中的離散對數問題(ECDLP)，許多密碼專家認為它是指數級的難度。因此對於橢圓曲線加密系統來說，這一點從計算量、處理速度、存儲空間和通信帶寬等角度分析，橢圓曲線加密系統都有很大的優勢。IEEE已經制定的公鑰加密演算法標準P1363就是基於ECC演算法的。現在密碼學界普遍認為它將替代RSA成為通用的公鑰密碼演算法，目前已成為研究的熱點，是很有前途的研究方向。
圖1點演算法實現
圖2密鑰、數據交換
圖3橢圓曲線加密系統結構圖
圖4橢圓曲線加密系統FPGA電路模塊框圖
圖5驗證系統結構
橢圓曲線加密體制
橢圓曲線
引進Non-supersingular橢圓曲線Weierstrass方程E:Y2+XY=X3+aX2+c其中a,c∈GF(2k),c≠0。為簡化以後的運算，引進z使X=x/z；Y=y/z，則橢圓曲線方程化為E:y2z+xyz=x3+ax2z+cz3，定義(x, y, z)=λ(x, y, z)。可以看出當z≠0，(X, Y)和(x, y, z)相對應，當z=0可以理解為沿y軸趨向無窮遠，定義為無窮遠點O。則橢圓曲線上所有的點外加無窮遠點構成的集合構成一個Abel群，O是單位元(零元)。在橢圓曲線E上定義了兩種點運算：點運算和點運算。
1)橢圓曲線上點運算定義為：設P=( x1, y1, 1)∈E，Q=( x2, y2, 1)∈E，-P=( x1, y1+ x1, 1),當Q≠-P時 PQ=(x3, y3, z3)則
當P≠Q時：
其中A=(x2z1+x1),B=(y2z1+y1), C=A+B,D=A2(A+a2z1)z1BC
當P=Q時：
其中
2)橢圓曲線上的點運算定義為：設P=(x1, y1, 1)∈E，(ltlt-1...l0)2是整數l的二進位表示形式，lP=PPAP=Q且Q∈E。
利用上面的點運算，得點演算法實現如圖1所示。定義l=logpQ，若P的周期很大，則利用l、P求Q是比較容易的，但利用P、Q求l是很難處理的，這就是ECDLP，橢圓曲線加密就是建立在這個難題之上。
加密體制
在Diffe-Hellman公鑰系統體制中，具體的橢圓曲線、曲線上點P及P的周期大素數N都是公開信息。
A和B要進行通訊，首先得到橢圓曲線E、點P及素數N。然後用戶A將[1,N-1]中隨機選取的整數a作為私鑰，A將KpubA=aP作為自己的公鑰傳送給用戶B，與此同時B將 [1,N-1]中隨機選取的整數b作為私鑰，並將KpubB=bP作為自己的公鑰傳送給A。A、B各自將自己的私鑰點乘於對方傳過來的公鑰得到KAB，這樣就完成了密鑰的交換過程。當用戶A需要將待傳數據m傳送給用戶B時，A利用m和KAB生成Em，當用戶B得到Em后，利用密鑰交換過程自己生成的KAB和從用戶A處得到的加密數據Em生成數據m。見圖2。
橢圓加密體制實現
迄今所投入使用的橢圓加密系統中，絕大部分的密鑰長度都比較短，一般集中在30~60位，這是因為在軟體實現時，由於軟體執行速率所限，密鑰長度比較大(≥160)的橢圓加密系統的速率將達不到使用要求。與此同時，在硬體實現時，密鑰長度比較大的橢圓加密系統將耗費大量的硬體資源。隨著橢圓加密演算法研究的深入和可編程邏輯器件的快速發展，利用可編程邏輯器件實現橢圓加密系統已經是一個可能的選擇，下面將介紹一種實現方案，並且用軟、硬體分別實現。
根據以上橢圓加密體制的要求，設計出圖3的加密系統結構圖，其中橢圓加密系統參數介面獲取與加密有關的橢圓的基本參數，如私鑰、橢圓曲線、橢圓曲線上的給定點等。橢圓曲線乘法控制部分主要負責如何計算乘法結果，會大量調用PP和PQ來實現乘法功能；而PP和PQ通過有限域加法、乘法和求逆的調用得到結果。
軟體模型驗證
軟體實現的主要目的是為硬體實現建立驗證模型，整個軟體的結構如圖3所示。在軟體驗證系統實現的過程中，有限域上的加法是異或操作。有限域上的乘法和求逆是關鍵點，必須預先考慮到硬體實現時的資源消耗，需要高效的演算法。在此系統中使用了複合域GF((2n)m)帶來的特殊性，可以高效、快速的實現乘法和求逆運算。
* GF(2n)上的乘法：A(y)×B(y)=C(Y)modQ(y)，Q(y)為既約多項式。常用的有： Paar-Rosner乘法器、Mastrovito乘法器、Massey-Omura乘法器、Hasan-Bhargava乘法器等，此處介紹兩種選擇：
1)當n比較小時可用查表法實現，設ω為Q(y)=0的本原根，則F2n=0,ω，Aω2n-1，利用查表法取得A、B的級次數a、b，C的級次c=a+b，再次利用查表法由c得C。在本系統中就使用了此法實現GF(2n)上的乘法。
2)當n比較大時，利用查表法資源消耗太大，難以承受，可利用C=Z×B(n比較大時)，Z是由A(y),Q(y)確定的矩陣，其中：
*複合有限域的乘法：以GF((24)2)為例，利用GF(24)上的乘法和加法可以構造出GF(28)的乘法。子域GF(24)的本原多項式為Q(y)=y4+y+1，第二個子域的本原多項式為R(z)=z3+z+ω14，其中ω是GF(24)的基底元素，滿足Q(ω)=0。域中兩個元素的乘法[a0+a1z]×[b0+b1z]可以表示為：
這樣GF((24)2)在複合域上的乘法就可以通過GF(24)上的有限域的數學運算而得到。
*複合有限域的逆運算：複合有限域GF((2n)m)中的元素A的逆為：
其中
可以觀察到Ar屬於子域GF(2n)中的元素，可以較容易的求取(Ar)-1的值。
FPGA硬體實現
軟體化的實現方法開發時間短，但是其加密速度比較慢，妨礙了橢圓曲線加密的實用性。FPGA的方法綜合了軟體的靈活性和硬體的安全性，提供了比軟體化方法優越的速度，和傳統的ASIC實現相比，可編程器件由於其高度的靈活性，更適合於密碼學的應用領域。
在軟體模型的基礎上，我們針對FPGA硬體的特性對模型進行了優化。根據橢圓曲線加密演算法的要求，對加密系統進行模塊化設計，每個模塊獨立完成其各自功能，模塊之間進行相互數據交換以及時序控制，達到加密功能。圖4是橢圓曲線加密系統FPGA實現的電路模塊框圖。
其中，橢圓曲線加密控制系統模塊是整個系統的核心。當Ready為True時，系統讀入初始數據並且控制RAM進行初始數據的存儲。在運算過程中，該模塊根據數據源對選擇器進行控制循環，進行PP=R和PQ=R運算，獲得最後結果，然後通過Out_Ready信號對結果進行輸出；選擇器模塊根據控制系統模塊提供的指令對PP=R模塊和PQ=R模塊進行控制，並且提供相應的實時數據流；PP=R模塊和PQ=R模塊利用對有限域上的加法和乘法運算進行時序控制求出橢圓曲線上點的加法運算，將直接影響到整個系統的速度性能，因此必須對有限域上的加法和乘法運算設計合理的輸入輸出數據流，以達到高效率的運算速率。各種存儲器模塊根據不同的指令分別存放系統的初始值、運算過程中的中間值以及系統運算結果。
綜合以上各種因素，我們選擇了XILINX公司的VirtexII器件，ISE 4.1作為開發平台，VHDL作為開發語言。由於168位的橢圓曲線加密演算法的計算量比較大，所以在FPGA實現的時候，布線是個值得考慮的因素。對於FPGA器件的選擇應考慮到布線資源，Virtex系列提供的布線資源比較豐富。在Modelsim上進行模擬后得到性能指標為：在40MHz時鐘驅動下第一次加密或者解密時需要初始的建立時間，明文或者密文的輸出需要2ms左右，其後的明文或者密文的輸出大約為25Mbps。可以看出，這是一個比較高的速率，可以應用於很多場合。
應用系統驗證
橢圓加密硬體實現后，必須在實際系統中得到驗證。我們特地構造了串口加密實驗板進行驗證，整個驗證系統的結構如圖5所示。經過實際系統驗證，證明上述橢圓加密體制硬體實現是成功的。
結語
公鑰密碼體制由於其運算和時間複雜性較高，通常用於密鑰管理、密鑰交換、數字簽名和認證等涉及信息較少的場合。目前，被廣泛使用的仍是DES、RSA這樣陳舊的演算法，演算法的更新不僅可以使本來的密碼戶獲得更好的性能，而且還可以使IC卡、手機等本來難以實現密碼演算法的領域可以使用密碼技術來保證信息安全。
橢圓曲線密碼體制(ECC)正在以其更短的密鑰和理論上更高的強度引起業界的重視，而橢圓曲線密碼體制(ECC)的硬體實現也將是公鑰密碼體制中的一個聚焦點。本文雖然已經為將來的工作打下了良好的基礎，在以下幾個方面還有大量的工作需要做。首先是可編程邏輯器件的發展，以後必然出現能提供更大門數，能提供更快速率的器件；其次是橢圓曲線密碼體制本身的改進；最後是有限域數學運算的硬體實現演算法的進一步改良。隨著以上各個方面的發展，將能提供更長密鑰和更快的數據速率的硬體實現，為國民經濟和社會發展提供更快更安全的加密系統。
