徐勁松,王志新,嚴(yán)迎建
(解放軍信息工程大學(xué) 電子技術(shù)學(xué)院,河南 鄭州450004)
橢圓曲線密碼體制 (ECC)是一種基于代數(shù)曲線的公開密碼體制,需要進(jìn)行高強(qiáng)度的密碼學(xué)運(yùn)算,而通用處理器在運(yùn)算性能上有明顯的局限性,難以滿足實(shí)際應(yīng)用需求。因此,一般使用硬件加速的方法來(lái)實(shí)現(xiàn)ECC。傳統(tǒng)的硬件加速方法是用專用集成電路實(shí)現(xiàn)ECC算法,對(duì)特定的ECC算法進(jìn)行硬件優(yōu)化來(lái)獲得高性能,這種方法處理速度快,但只能針對(duì)特定ECC算法,可配置性和可擴(kuò)展性十分欠缺,且成本較高。目前專用指令集處理器 (ASIP)作為一種新的硬件加速方案,得到了廣泛的研究[1-3],出現(xiàn)了多款各具特色的ECC專用指令集處理器[4-6]。本文設(shè)計(jì)了一款能實(shí)現(xiàn)多種ECC算法的ASIP,能夠完成160~576-bit二元域和素?cái)?shù)域上的有限域運(yùn)算。
ASIP設(shè)計(jì)通常分為4個(gè)關(guān)鍵步驟:應(yīng)用分析、體系結(jié)構(gòu)設(shè)計(jì)、代碼綜合和硬件綜合[7]。本文對(duì)此4個(gè)關(guān)鍵步驟進(jìn)行了細(xì)化與擴(kuò)展,采用了軟硬件協(xié)同的方法設(shè)計(jì)了一款專用指令ECC處理器,具體流程如圖1所示。設(shè)計(jì)采用自頂向下的設(shè)計(jì)方法,從系統(tǒng)驗(yàn)證、RTL硬件仿真和FPGA硬件原型測(cè)試3個(gè)不同的層次對(duì)處理器的設(shè)計(jì)工作進(jìn)行了驗(yàn)證。
設(shè)計(jì)一款ECC專用指令處理器,要綜合考慮不同ECC算法的對(duì)性能、面積、功耗等參數(shù)的需求,對(duì)軟硬件進(jìn)行合理地劃分,硬件方面主要進(jìn)行處理器指令集體系結(jié)構(gòu)(ISA)模型設(shè)計(jì),包含指令設(shè)計(jì)、寄存器設(shè)計(jì)等;軟件方面主要進(jìn)行ECC算法程序設(shè)計(jì)以及與處理器配套的軟件開發(fā)、調(diào)試工具的設(shè)計(jì),包括指令集模擬器 (ISS)、匯編器等。ISS、匯編器不僅可以作為處理器的開發(fā)、調(diào)試工具,而且還可以作為處理器的仿真器來(lái)使用。系統(tǒng)設(shè)計(jì)完成后需要對(duì)處理器進(jìn)行系統(tǒng)驗(yàn)證,并根據(jù)仿真結(jié)果重新對(duì)軟硬件進(jìn)行劃分,調(diào)整處理器體系結(jié)構(gòu),優(yōu)化指令集,修改寄存器堆大小,使系統(tǒng)滿足設(shè)計(jì)需求和約束。系統(tǒng)驗(yàn)證通過(guò)后可進(jìn)行硬件RTL設(shè)計(jì),將匯編程序編譯后的機(jī)器碼作為激勵(lì),對(duì)電路結(jié)構(gòu)進(jìn)行仿真,并進(jìn)行優(yōu)化。RTL仿真通過(guò)后,建立FPGA硬件模型,對(duì)整個(gè)系統(tǒng)進(jìn)行完備性驗(yàn)證。
圖1 處理器設(shè)計(jì)流程
橢圓曲線有加密、解密、數(shù)字簽名、簽名認(rèn)證等多種應(yīng)用協(xié)議,定義的有限域通常采用素?cái)?shù)域和二元域,且運(yùn)算長(zhǎng)度可變。為了滿足ECC多種運(yùn)算形式的需要,結(jié)合硬件的約束,對(duì)軟硬件進(jìn)行了劃分,采用了硬件實(shí)現(xiàn)ECC底層運(yùn)算,軟件實(shí)現(xiàn)ECC算法流程的形式。
ECC各種應(yīng)用協(xié)議都以點(diǎn)加、倍點(diǎn)以及點(diǎn)乘運(yùn)算規(guī)則為基礎(chǔ),具有層次性[8],如表1所示。上層算法可以通過(guò)調(diào)用下層的算法來(lái)實(shí)現(xiàn),點(diǎn)乘運(yùn)算可以由多次調(diào)用點(diǎn)加和倍點(diǎn)操作完成,而點(diǎn)加、倍點(diǎn)運(yùn)算則可以通過(guò)調(diào)用有限域上的模運(yùn)算而實(shí)現(xiàn),包括模加/減、模約減、模乘、模平方及模逆等運(yùn)算。在此基礎(chǔ)上,增加了移位、邏輯運(yùn)算、比較等指令,從而構(gòu)成了處理器的運(yùn)算指令。此外還設(shè)計(jì)了數(shù)據(jù)傳輸指令、控制指令、配置指令等,共4大類指令。其中配置指令為運(yùn)算單元重構(gòu)而設(shè)計(jì)。
表1 ECC算法層次結(jié)構(gòu)
ECC算法具有計(jì)算密集型的特點(diǎn),而且在調(diào)用有限域上的模運(yùn)算來(lái)實(shí)現(xiàn)點(diǎn)加、倍點(diǎn)運(yùn)算的過(guò)程中,有限域上的模運(yùn)算操作存在較大數(shù)據(jù)并行性[9]。超長(zhǎng)指令字(VLIW)體系結(jié)構(gòu)是目前常用的一種指令級(jí)并行處理方案[10],廣泛地應(yīng)用于DSP等計(jì)算密集型的處理器設(shè)計(jì)。VLIW結(jié)構(gòu)中硬件提供若干個(gè)運(yùn)算單元,各運(yùn)算單元可并行執(zhí)行處理器指令,通過(guò)編譯器靜態(tài)分析程序中指令的依賴關(guān)系將可并行的指令一起發(fā)射執(zhí)行,把通常由硬件實(shí)現(xiàn)的功能交由軟件實(shí)現(xiàn)。VLIW一次發(fā)射的最大指令條數(shù)由處理器內(nèi)部運(yùn)算單元的數(shù)量決定,運(yùn)算單元越多,其對(duì)應(yīng)的寄存器結(jié)構(gòu)就越復(fù)雜。因此,運(yùn)算單元的個(gè)數(shù)需要根據(jù)處理器應(yīng)用范圍來(lái)合理設(shè)置,做到成本與效率的平衡。
由于ECC底層運(yùn)算指令較少,基于有限域操作的各種ECC算法流程比較固定,其運(yùn)算流程的數(shù)據(jù)并行性可利用編寫匯編代碼的形式手動(dòng)挖掘。因此,處理器采用VLIW結(jié)構(gòu)可簡(jiǎn)化硬件設(shè)計(jì),使處理器能夠達(dá)到較高的并行性能。
在各種ECC算法中,點(diǎn)乘是最主要的運(yùn)算,決定了ECC算法的實(shí)現(xiàn)效率。設(shè)計(jì)對(duì) Double-and-Add、m-ary、Montgomery、窗口NAF、固定基窗口、固定基的Comb等多種點(diǎn)乘調(diào)度算法進(jìn)行了數(shù)據(jù)相關(guān)性分析,研究了運(yùn)算單元數(shù)量對(duì)運(yùn)算速度、資源消耗的影響,計(jì)算出不同并行度下時(shí)間開銷與資源開銷,表2列出了不同并行度下Montgomery點(diǎn)乘算法一輪迭代的時(shí)間與資源開銷。
表2 不同并行度下Montgomery點(diǎn)乘算法的時(shí)間和資源開銷
從表2可以看出,用4個(gè)運(yùn)算單元的時(shí)間和資源的開銷分別是用2個(gè)運(yùn)算單元的1/2和2倍。同時(shí)由于運(yùn)算過(guò)程中的數(shù)據(jù)相關(guān)性約束,當(dāng)運(yùn)算單元增加時(shí),并不能減少時(shí)間開銷。
在現(xiàn)代高性能的微處理器設(shè)計(jì)過(guò)程中,設(shè)置適當(dāng)?shù)拇鎯?chǔ)空間為處理器中的多條指令流提供充足和連續(xù)的數(shù)據(jù),成為提高處理器性能的關(guān)鍵。存儲(chǔ)容量的大小從根本上影響著各運(yùn)算處理單元之間的數(shù)據(jù)交互速度,在某種程度上也決定了處理器的靈活性和性能提升空間。這里根據(jù)ECC運(yùn)算數(shù)據(jù)占用空間的大小,設(shè)計(jì)了兩類寄存器:
(1)靜態(tài)配置寄存器:主要存儲(chǔ)模數(shù)/不可約多項(xiàng)式、運(yùn)算長(zhǎng)度、有限域類型、模乘運(yùn)算常數(shù)、功能單元的模式等。這類數(shù)據(jù)所需存儲(chǔ)容量較小,且一旦算法確定,數(shù)據(jù)一般不會(huì)發(fā)生變化,因此寄存器端口設(shè)置、尋址模式比較簡(jiǎn)單。
(2)通用寄存器:主要存儲(chǔ)外部輸入,橢圓曲線相關(guān)的常數(shù)值,計(jì)算過(guò)程中的臨時(shí)數(shù)據(jù),輸出的數(shù)據(jù)等。這類數(shù)據(jù)需要較大的存儲(chǔ)容量,主要是運(yùn)算過(guò)程中的臨時(shí)數(shù)據(jù),且某些數(shù)據(jù)在運(yùn)算完畢后,就很少再次使用,可以直接覆蓋,因此寄存器端口設(shè)置、尋址模式比較復(fù)雜。對(duì)應(yīng)設(shè)計(jì)中的4個(gè)功能單元,將通用數(shù)據(jù)寄存器分成4組,每組設(shè)有1個(gè)寫端口,2個(gè)讀端口;支持直接尋址、增量尋址、寄存器間接尋址等尋址模式。通過(guò)對(duì)ECC算法進(jìn)行統(tǒng)計(jì),可以確定通用數(shù)據(jù)寄存器的容量。表3列出了二元域上部分坐標(biāo)系下點(diǎn)加/倍點(diǎn)運(yùn)算所需要的最大儲(chǔ)存容量,其中Len表示模運(yùn)算的數(shù)據(jù)位寬。
表3 不同坐標(biāo)系下存儲(chǔ)容量需求
依據(jù)上面的設(shè)計(jì),處理器的結(jié)構(gòu)圖如圖2所示,主要有控制單元、接口單元及數(shù)據(jù)通路等3部分組成??刂茊卧饕瓿芍噶畲嫒?、指令譯碼、指令存儲(chǔ)器地址生成等過(guò)程中的信號(hào)生成工作,負(fù)責(zé)協(xié)調(diào)處理器內(nèi)部指令和外部用戶命令的正確執(zhí)行。接口單元?jiǎng)t主要完成外部指令/命令及運(yùn)算數(shù)據(jù)的輸入以及運(yùn)算結(jié)果的輸出。數(shù)據(jù)通路是ECC處理器的數(shù)據(jù)執(zhí)行部分,包含F(xiàn)U0~FU3共4個(gè)可并行執(zhí)行的功能單元、通用向量寄存器堆、靜態(tài)配置寄存器、回寫單元等4個(gè)主要部分。4個(gè)功能單元是處理器執(zhí)行指令運(yùn)算的核心,其功能是可配置的,由靜態(tài)配置寄存器提供必要的配置參數(shù),來(lái)完成不同參數(shù)下的運(yùn)算處理。
圖2 ECC專用指令處理器整體結(jié)構(gòu)
軟硬件協(xié)同驗(yàn)證[11-12]是一種在硬件設(shè)計(jì)確認(rèn)制造之前,驗(yàn)證軟件能在設(shè)計(jì)硬件上正確運(yùn)行的過(guò)程,需要軟硬件同時(shí)進(jìn)行設(shè)計(jì)驗(yàn)證,及時(shí)在硬件和軟件之間交換需要的數(shù)據(jù)。由于ECC專用指令集處理器規(guī)模龐大、結(jié)構(gòu)復(fù)雜,為了確保設(shè)計(jì)的正確性,需要從系統(tǒng)驗(yàn)證、RTL硬件仿真和FPGA硬件原型測(cè)試等不同層次對(duì)處理器的設(shè)計(jì)工作進(jìn)行驗(yàn)證。
系統(tǒng)驗(yàn)證是處理器設(shè)計(jì)過(guò)程中不可或缺的重要環(huán)節(jié),進(jìn)行系統(tǒng)驗(yàn)證就是在系統(tǒng)仿真驗(yàn)證平臺(tái)上運(yùn)行算法程序的過(guò)程。系統(tǒng)級(jí)驗(yàn)證一方面用來(lái)驗(yàn)證算法的正確性以及該算法在硬件結(jié)構(gòu)上實(shí)現(xiàn)的可行性,另一方面用來(lái)對(duì)處理器的設(shè)計(jì)空間進(jìn)行探索研究[13],例如修改功能單元設(shè)置,優(yōu)化指令集,調(diào)整寄存器堆容量等。
算法程序設(shè)計(jì)根據(jù)處理器的體系結(jié)構(gòu),對(duì)ECC算法進(jìn)行并行調(diào)度算法研究,充分挖掘運(yùn)算流程的數(shù)據(jù)并行性,用設(shè)計(jì)的專用指令編寫并行調(diào)度算法作為目標(biāo)程序代碼。仿真驗(yàn)證平臺(tái)主要是指用C++進(jìn)行對(duì)系統(tǒng)的功能和性能進(jìn)行描述,建立系統(tǒng)中處理器的虛擬原型;通過(guò)匯編器、調(diào)試器和仿真器來(lái)模擬處理器體系結(jié)構(gòu),實(shí)現(xiàn)算法程序的驗(yàn)證。在本設(shè)計(jì)中,仿真器主要通過(guò)ISS來(lái)實(shí)現(xiàn)。ISS建立了處理器的ISA模型,通過(guò)模擬每條指令在目標(biāo)處理器上的執(zhí)行效果來(lái)模擬目標(biāo)機(jī)程序[14],能滿足處理器在指令精確級(jí)的仿真驗(yàn)證,同時(shí)配合匯編器、調(diào)試器,能夠?qū)崿F(xiàn)處理器配套的軟件開發(fā)工具。
系統(tǒng)驗(yàn)證的過(guò)程如圖3所示。算法程序經(jīng)過(guò)匯編器編譯得到二進(jìn)制指令文件,將該文件輸入到ISS,對(duì)系統(tǒng)進(jìn)行驗(yàn)證。在驗(yàn)證過(guò)程中,通過(guò)ISS可以查看目標(biāo)處理器的內(nèi)部狀態(tài),例如寄存器、程序計(jì)數(shù)器值等。將輸出結(jié)果與Certicom Research提供的 測(cè)試向 量文件 Test Vectors for SEC1比對(duì),可以驗(yàn)證算法是否正確以及硬件設(shè)計(jì)是否可行,同時(shí)可以根據(jù)驗(yàn)證過(guò)程中的一些統(tǒng)計(jì)數(shù)據(jù),對(duì)系統(tǒng)進(jìn)行調(diào)整。
圖3 系統(tǒng)驗(yàn)證過(guò)程
在系統(tǒng)驗(yàn)證過(guò)程中,采用了ISS逐條模擬用戶指令的形式,只能夠提供精確到指令邊界的處理器狀態(tài),無(wú)法確定處理器在每個(gè)時(shí)鐘周期的狀態(tài)。因此,在系統(tǒng)級(jí)驗(yàn)證通過(guò)之后,有必要進(jìn)行軟件代碼與硬件RTL代碼的協(xié)同仿真驗(yàn)證,通過(guò)RTL硬件仿真,來(lái)觀察電路運(yùn)行的時(shí)序,做到時(shí)鐘周期精確級(jí)的仿真。
進(jìn)行RTL硬件仿真,需要將系統(tǒng)級(jí)設(shè)計(jì)的ISA模型以硬件描述語(yǔ)言的形式表示出來(lái),同時(shí)編寫RTL仿真驗(yàn)證的測(cè)試文件。測(cè)試文件調(diào)用與匯編程序相對(duì)應(yīng)二進(jìn)制文件,作為RTL仿真中的測(cè)試向量,通過(guò)ModelSim對(duì)系統(tǒng)進(jìn)行硬件代碼仿真驗(yàn)證,如圖4所示。同時(shí)將ModelSim的輸出結(jié)果與系統(tǒng)驗(yàn)證得到的結(jié)果進(jìn)行比對(duì),以確保RTL描述與ISA模型的設(shè)計(jì)一致。
圖4 RTL仿真過(guò)程
在RTL硬件仿真中,只對(duì)設(shè)計(jì)的RTL硬件描述代碼進(jìn)行仿真,它無(wú)法確定設(shè)計(jì)真實(shí)的物理實(shí)現(xiàn)與設(shè)計(jì)描述之間的區(qū)別,和硬件實(shí)際工作狀態(tài)還有很大的差別。FPGA硬件原型測(cè)試將通過(guò)RTL硬件仿真的RTL代碼經(jīng)過(guò)綜合,下載到FPGA系統(tǒng)中,利用FPGA系統(tǒng)為處理器提供硬件環(huán)境,使硬件工作狀態(tài)更真實(shí),速度更快[15]。
這里采用基于Altera公司EP3SL340H1152C3N芯片的DE3開發(fā)板,PC機(jī)通過(guò)USB接口發(fā)送命令,控制器作為開發(fā)板上的控制邏輯,通過(guò)USB接口接收命令,并對(duì)命令進(jìn)行解析后傳給ECC處理器,處理器根據(jù)命令對(duì)數(shù)據(jù)進(jìn)行ECC運(yùn)算處理,并將最終的運(yùn)算結(jié)果存儲(chǔ)到ECC處理器中或?qū)?shù)據(jù)通過(guò)USB接口傳回PC機(jī)。如圖5所示。
圖5 FPGA驗(yàn)證系統(tǒng)組成框架
本文提出了一種軟硬件協(xié)同設(shè)計(jì)方法,完成了不同設(shè)計(jì)階段的仿真驗(yàn)證,并使用該方法設(shè)計(jì)了一款專用指令ECC處理器。該處理器可配置性強(qiáng)、速度快、靈活性高,能夠完成160~576bit二元域和素?cái)?shù)域上的有限域運(yùn)算,能實(shí)現(xiàn)多種ECC應(yīng)用協(xié)議,在不同的應(yīng)用條件下具有良好的適應(yīng)性。使用DC工具,采用SIMC 0.18μm CMOS工藝標(biāo)準(zhǔn)單元庫(kù),對(duì)所設(shè)計(jì)的ECC處理器進(jìn)行邏輯綜合,在4ns的約束條件下,處理器規(guī)模達(dá)到了225.89萬(wàn)門,最高時(shí)鐘頻率可以達(dá)到250MHz。
[1]Kimmo Puusaari.Application specific instruction set processor microarchitecture for UTMS-FDD cell search [C].Tampere:Proceedings International Symposium on System-on-Chip,2005:46-49.
[2]SHEN Bilong,ZHAO Peng,CHEN Xucan,et al.Research and realization on analysis method of application features faced instruction set design of specific processor [J].Computer Engineering & Science,2009,31 (A01):115-119 (in Chinese).[沈弼龍,趙鵬,陳旭燦,等.面向?qū)S锰幚砥髦噶罴O(shè)計(jì)的應(yīng)用特征分析方法研究與實(shí)現(xiàn) [J].計(jì)算機(jī)工程與科學(xué),2009,31 (A01):115-119.]
[3]REN Kun,YAN Xiaolang,SUN Lingling.An ASIP compiler design and implementation [J].Journal of Circuits and Systems,2009,14 (6):59-62 (in Chinese). [任坤,嚴(yán)曉浪,孫玲玲.ASIP編譯器設(shè)計(jì)和實(shí)現(xiàn) [J].電路與系統(tǒng)學(xué)報(bào),2009,14 (6):59-62.]
[4]LAI Jyuyuan,HUANG Chihtsun.Elixir:high-throughput cost-effective dual-field processors and the design framework for elliptic curve cryptography [J].IEEE Transaction on VeryLarge Scale Integration Systems,2008,16 (11):1567-1580.
[5]Tim Guneysu,Christof Paar.Ultra high performance ECC over NIST primes on commercial FPGAs [C].Berlin,Heidelberg:Proceeding Sof the 10th International Workshop on Cryptographic Hardware and Embedded Systems,2008:62-78.
[6]CAI Liang,DAI Zibin,CHEN Lu.Design and implementation of general ECC coprocessor [J].Computer Engineering,2009,34 (4):140-142 (in Chinese). [蔡亮,戴紫彬,陳璐.一種通用ECC協(xié)處理器的設(shè)計(jì)與實(shí)現(xiàn) [J].計(jì)算機(jī)工程,2009,34 (4):140-142.]
[7]YANG Jun.Research on application specific instruction set processor (ASIP)architecture design [D].Hefei:University of Scinece and Technology of China,2006 (in Chinese). [楊君.專用指令集處理器 (ASIP)體系結(jié)構(gòu)設(shè)計(jì)研究 [D].合肥:中國(guó)科學(xué)技術(shù)大學(xué),2006.]
[8]ZHANG Jun.Research on technology of application specific instruction and reconfigurable unit of Eliptic curve cryptography processor [D].Zhengzhou:PLA Information Engineering U-niversity,2010 (in Chinese).[張軍.ECC處理器專用指令與可重構(gòu)單元設(shè)計(jì)技術(shù)研究 [D].鄭州:解放軍信息工程大學(xué),2010.]
[9]CAI Liang.Research and design of the dual-field ECC coprocessor architecture [D].Zhengzhou:PLA Information Engineering University,2008 (in Chinese).[蔡亮.雙域ECC協(xié)處理器體系結(jié)構(gòu)研究與設(shè)計(jì) [D].鄭州:解放軍信息工程大學(xué),2008.]
[10]SHEN Zheng,SUN Yihe.Architecture design of simultaneous multithreading VLIW DSP [J].Acta Electronica Sinica,2010,38 (2):352-358 (in Chinese). [沈鉦,孫義和.一種支持同時(shí)多線程的 VLIW DSP架構(gòu) [J].電子學(xué)報(bào),2010,38 (2):352-358.]
[11]ZHAO Gang,HOU Ligang,LIU Yuan.Methodology of SoC design using hardware/software cosimulation [J].Microelectronics & Computer,2006,23 (6):24-26 (in Chinese).[趙剛,侯立剛,劉源.基于SoC設(shè)計(jì)的軟硬件協(xié)同驗(yàn)證方法學(xué) [J].微電子學(xué)與計(jì)算機(jī),2006,23 (6):24-26.]
[12]BAO Hua,HONG Yi,GUO Erhui.Design of HW/SW coverification platform for SoC [J].Computer Engineering,2009,35 (8):271-273 (in Chinese). [鮑華,洪一,郭二輝.面向SoC的軟硬件協(xié)同驗(yàn)證平臺(tái)設(shè)計(jì) [J].計(jì)算機(jī)工程,2009,35 (8):271-273.]
[13]SHAO Yang,LIU Hongjin,HE Xing.A system level methodology for ASIP design [J].Microelectronics & Computer,2007,24 (7):102-104 (in Chinese). [邵洋,劉鴻瑾,何星.專用指令集處理器系統(tǒng)級(jí)設(shè)計(jì)方法 [J].微電子學(xué)與計(jì)算機(jī),2007,24 (7):102-104.]
[14]YAN Yingjian,YE Jiansen,LIU Junwei.VLIW processor ISA modeling and aided software optimization technology [J].Computer Engineering and Design,2009,30 (11):2727-2729(in Chinese).[嚴(yán)迎建,葉建森,劉軍偉.VLIW處理器ISA建模與輔助軟件優(yōu)化技術(shù) [J].計(jì)算機(jī)工程與設(shè)計(jì),2009,30 (11):2727-2729.]
[15]WANG Peidong,LI Fengwei,YANG Juncheng.Hardware/Software coverification solution integrated FPGA and ISS [J].Computer Engineering and Application,2009,45 (30):73-74(in Chinese).[王培東,李鋒偉,楊俊成.一種融合FPGA和ISS技術(shù)的軟硬件協(xié)同驗(yàn)證方法 [J].計(jì)算機(jī)工程與應(yīng)用,2009,45 (30):73-74.]