基于FPGA的多項式基下二進制域ECC點乘設(shè)計

桂金瑤，陳大軍

0 引言

橢圓曲線的實現(xiàn)有軟件和硬件兩種方式，硬件方式更有安全性。最早硬件實現(xiàn)ECC的設(shè)計在GF(2155)上實現(xiàn)了ECC加密算法，加密速度大約為 4× 104bit/s。最早基于 FPGA 實現(xiàn)的 ECC處理器，面積約 5萬門，加密時數(shù)據(jù)吞吐率為1.6× 104bit/s。北京天一集團研制的“天芯一號”高速ECC/RSA密碼算法芯片，基于國內(nèi)可以大規(guī)模生產(chǎn)的0.25um工藝進行設(shè)計。

目前國內(nèi)外對于硬件實現(xiàn)ECC的學(xué)術(shù)成果，主要體現(xiàn)在平衡算法效率和算法所耗費的資源這個過共同的思想。對于ECC加密算法的改進，主要目的就是使改進后的算法更加適用于軟件或者硬件實現(xiàn)，一般情況下，二進制域上的橢圓曲線加密算法適合硬件實現(xiàn)，素數(shù)域上的加密算法適合軟件實現(xiàn)[1]。但是隨著加密算法的改進，國內(nèi)外也出現(xiàn)了很多在素數(shù)域上實現(xiàn)橢圓曲線的加密算法[2]。除了區(qū)分不同有限域以外，對于硬件電路的實現(xiàn)方式上還有 VLSI實現(xiàn)和FPGA實現(xiàn)兩種。這兩種實現(xiàn)方式各有優(yōu)缺點[3]。

為了高效的完成KP的運算，目前國內(nèi)外有很多不同的算法，如 ADD-DOU算法，加減算法，蒙哥馬利算法等。本文采用通過改進的蒙哥馬利點乘算法，通過一系列的狀態(tài)機調(diào)用底層模塊，并且將模逆模塊進行投影映射轉(zhuǎn)換為最少的模乘模塊調(diào)用設(shè)計。根據(jù)NIST推薦的5個二進制有限域163，233，283，409，571。本設(shè)計的ECC加密算法，基于GF(2233) 域上，通過FPGA設(shè)計驗證，在50.3MHZ的頻率下，邏輯單元個數(shù)為25044個，時間和面積復(fù)雜度都有一定程度的優(yōu)勢。

1 算法設(shè)計

1.1 模乘算法設(shè)計

有限域的運算設(shè)計以及實現(xiàn)，橢圓曲線密碼系統(tǒng)在二元有限域上的運算，尤其是模乘運算極為耗費時間和占用資源。二元有限域上基的選取對模乘運算效率有很大影響，目前普遍使用的是多項式基和正規(guī)基。雖然都可以表示乘二進制串的形式，但其對應(yīng)的有限域運算卻是不一樣的，正規(guī)基表示下的元素運算雖然有利于硬件實現(xiàn)，但是當(dāng)m較大時，這種基于查表的運算方式，就很耗時并且占用大量的硬件資源。因此，硬件實現(xiàn)二進制域橢圓曲線標(biāo)量乘法算法時，采用多項式基表示基域是比較理想的。橢圓曲線在有限域內(nèi)的運算主要有模加，模減，模平方，模乘，模逆。逆元素可以通過有限域上的模平方和模乘來實現(xiàn)（可配置ECC算術(shù)模塊的設(shè)計與實現(xiàn)）追求高效的模乘算法中，Montgomery模乘算法無疑是非常有效的?；舅惴ㄊ?1985年 Peter L.Montgomery于1985年提出來的，原有復(fù)雜耗時的除法運算被一系列的簡單移位運算所代替，可以極大的提高模乘運算的效率。從最近的國內(nèi)外最新出現(xiàn)的模乘算法都是從Montgomery算法的基礎(chǔ)上改進得到的。

在本文中，主要是對于二進制域的運算進行研究，GF(2m)是GF(2)的一個擴展，這里的m是擴展的有限域的度。GF(2m)可以被下面的式子來表達，，1≤k≤m。這個多項式是不可約的a可以表示為

其中的系數(shù)ai是二進制域里面的元素。這個系數(shù)可以是0或者1。通過這 樣有效的計算，多項式就可以被儲存和表達為比特流的形式。兩個二進制域的元素 , (2m)a b∈GF可以被定義為兩個多項式系數(shù)的相加，公式1

二進制的加法元素ai＋bi對應(yīng)的就是邏輯的異或操作，對于軟件和硬件都可以很有效簡單的實現(xiàn)。同樣對于模減操作只需要進行一個反轉(zhuǎn)就可以了。

二進制域模乘運算可以分解成兩個步驟，首先假設(shè)兩個操作數(shù)a,b∈GF(2m)，模乘的多項式展開為公式2

其中，第二步要引入一個最簡多項式M，這 個多項式的度必須在小于 m，c0=cmodM，deg(c0)＜m, u,v是二進制域內(nèi)任意的多項式滿足條件u≡u＋vMmodM，為了提高模乘的效率，公式可以變形為tm≡M-TmmodM,因為c的度小于 2m-1，c可以被拆分為兩個多項式c1和c2， deg(c1) ＜m- 1， deg(c2)＜m。c=a*b=c1*tm＋c2此時公式3

因為deg(c1) ＜m- 1，deg(M-tm)＜m， 可 以 得 出deg(c1) ＜ 2m- 2，依次迭代，cj可以被分解為多項式cj,x和cj,y，cj＋1=cj,x*(M-tm)＋cj,y， 直 到cj,x=0 ＜=＞ deg(cj)＜m。迭代出來最小的值取決于取最簡多項式M的度取到最大值的時候。公式4

2 設(shè)計方法與驗證

2.1 模乘模塊設(shè)計

移位操作在軟件實現(xiàn)中極其費時，但是在硬件實現(xiàn)中因為對位的操作很簡單，所有相對容易實現(xiàn)，對于硬件實現(xiàn)的結(jié)構(gòu)，又可分為多項式比特流全串行結(jié)構(gòu)、全并行結(jié)構(gòu)以及串并混合型結(jié)構(gòu)。在全并行結(jié)構(gòu)中，全部的計算過程都必須在一個時鐘周期內(nèi)運行，這對于器件的要求非常嚴(yán)格，因此在硬件環(huán)境受限制的條件下是不合適的。串型結(jié)構(gòu)和并行結(jié)構(gòu)相比，前者面積復(fù)雜度更低，但是運算速度偏慢。混合型結(jié)構(gòu)通常用于均衡速度和面積的復(fù)雜度。如 LSD（最低數(shù)字優(yōu)先）乘法器和MSD（最高數(shù)字優(yōu)先）乘法器。

基域GF(2m)中多項式基表示下元素乘法一般采用先相乘后模約的方法。元素相乘采用從高到低為掃描和低到高位移位相結(jié)合的方法，比較一個2m比特的二進制串。在二元域進行取模運算，實際上就是比較被求模數(shù)的最高位是否為高電平，是則被求模的數(shù)與模進行異或，否則不變，因此，可以將第一位作為控制位，用以做一個二選一電路。一個輸入為為模f(x)，另一個輸入位為低電平，當(dāng)最高位為高電平時，二選一電路輸出為模f(x)，反之為低電平。

2.2 模逆模塊設(shè)計

模逆操作開銷比乘法運算的開銷大得多，為了有效的減少有限域求逆的操作次數(shù)，在進行橢圓曲線點運算的時候需要進行坐標(biāo)系的轉(zhuǎn)換。點運算之前，要先調(diào)用仿真坐標(biāo)到射影坐標(biāo)的轉(zhuǎn)換模塊，將仿真坐標(biāo)系下的點轉(zhuǎn)換到射影坐標(biāo)系下的三維坐標(biāo)。這樣在點運算時只對X、Z坐標(biāo)進行操作，這兩個坐標(biāo)的轉(zhuǎn)換只需要設(shè)計仿真坐標(biāo)中的橫坐標(biāo)的轉(zhuǎn)換，因此，模塊輸入坐標(biāo)是兩維坐標(biāo)中的一個坐標(biāo)，輸出的坐標(biāo)是三維坐標(biāo)中的兩個坐標(biāo)，這只需要寄存器之間的簡單賦值操作即可。

執(zhí)行完標(biāo)量乘法之后，還需要調(diào)用射影坐標(biāo)到仿真坐標(biāo)的轉(zhuǎn)換模塊，將射影坐標(biāo)的坐標(biāo)轉(zhuǎn)換乘仿真坐標(biāo)系的形式，模塊接收到標(biāo)量乘法運算結(jié)束的標(biāo)志以后，將Ready信號置為高電平，之后進行坐標(biāo)的轉(zhuǎn)換。

在模逆運算時需要使能模平方與模乘操作，所以要用一個使能信號與模乘、模平方之間需要一個多路選擇器進行仲裁，以免發(fā)生多驅(qū)動問題。

2.3 點乘設(shè)計與實現(xiàn)

ECC密碼體制內(nèi)運算是有層次性，本設(shè)計采用前文中改進的蒙哥馬利算法。在硬件的總體架構(gòu)設(shè)計中，對于底層的二進制域的計算，采用了基礎(chǔ)運算模塊實現(xiàn)運算，而對于上層的如點加、點倍等操作，以及最后的關(guān)鍵的點乘操作，都是通過一系列的狀態(tài)機調(diào)用其下一層的操作來實現(xiàn)的相關(guān)功能，計算的中間結(jié)果也需要暫存，所以除了控制邏輯與運算組合邏輯之外，還要設(shè)計數(shù)據(jù)存儲單元，用一組三端口的寄存器堆實現(xiàn)。

Kp運算模塊的結(jié)構(gòu)見圖一，在它的組成部分中，有限域運算模塊包括乘法運算器，求逆運算器，加法及平方運算器，負(fù)責(zé)完成有限域上的各種算術(shù)運算功能。移位寄存器為線性反饋寄存器，其中保存運算的元素值。點加和點倍運算為兩個獨立的單元，分別通過狀態(tài)機對有限域運算模塊進行調(diào)度，完成點加和倍點運算，點乘狀態(tài)控制器根據(jù)移位寄存器中存儲的數(shù)值，選擇進行點加或是點倍運算點乘狀態(tài)機在點乘狀態(tài)機外部還有一個計數(shù)器，移位寄存器每移動兩位，計數(shù)器則計數(shù)一次，當(dāng)計數(shù)器輸出值 Q達到一定數(shù)值時，運算結(jié)束。

圖1 KP模塊結(jié)構(gòu)圖

點乘KP模塊的實體描述為：

圖2 點乘測試模塊

綜合上述原理方法，通過采用VHDL語言作為設(shè)計工具，對基域為GF(2233)的橢圓曲線進行了設(shè)計實現(xiàn)，對結(jié)果進行了仿真和綜合，所選器件環(huán)境為 Cyclone系列的EP2C35F484C5,利用 Quartus Ⅱ平臺分析得出時鐘頻率為50.3MHZ，邏輯單元個數(shù)為25044個。表1比較了本設(shè)計和一些設(shè)計在面積上的數(shù)據(jù)，所有設(shè)計都是采用FPGA硬件設(shè)計方案。

表1 FPGA設(shè)計面積比較

3 結(jié)論

在橢圓曲線密碼體制中，有限域上的乘法運算的效率關(guān)系到整個系統(tǒng)的效率，所有重點對其進行了算法上的優(yōu)化，并且把模逆算法轉(zhuǎn)換乘投影坐標(biāo)系下，通過更少次的模乘算法進行了實現(xiàn)。本文依據(jù)蒙哥馬利算法，對其進行了改進，更適合硬件實現(xiàn)，并且消耗的資源更少。通過一系列的狀態(tài)機調(diào)用底層模塊，最終基于FPGA實現(xiàn)了點乘算法，速度和面積消耗和經(jīng)典的實現(xiàn)相比都有相應(yīng)的優(yōu)化。

[1]Min C H, Pyo H C, Hoon K C. High Performance Ellliptic Curve Cryptographic Processor Over GF(2163)[C]//DELTA 2008.4th IEEE International Symposium, 2008:290-295.

[2]Mcivor C, Mcloone M , Mccanny J.Hardware Elliptic Curve Cryptographic Processor Over GF(P)[J].Circuits and Systems:RegularPapers, IEEE Transactions,2006,53(9):1946 -1957.

[3]Gang Chen,Guoqiang Bai, Hongyi Chen.A High-PerfomanceElliptic Curve Cryptographic Processor General Curves Over GF(P) Based on a Systolic Arithmetic Unit[J]. IEEE Transaction on Circuits and Systems, 2007,54(5): 412-416.

[4]William N,Chelton,Mohammed Benaissa. Fast Elliptic Curve Cryptography Cryptography on FPGA[J]. IEEE Transaction on Very Large Scale Integration Systems,2008,16(2): 198-205.

[5]H yun Min Chio,Chun Pyo Hong,Chang Hoon Kim. High Performance Elliptic Curve Cryptographic Process Over GF(2163)[C]//4th IEEE International Symposium on Electronic Design,Application &Test , 2008 :290-295.