桂金瑤，陳大軍

0 引言

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

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

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

1 算法設(shè)計(jì)

1.1 模乘算法設(shè)計(jì)

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

在本文中，主要是對于二進(jìn)制域的運(yùn)算進(jìn)行研究，GF(2m)是GF(2)的一個(gè)擴(kuò)展，這里的m是擴(kuò)展的有限域的度。GF(2m)可以被下面的式子來表達(dá)，，1≤k≤m。這個(gè)多項(xiàng)式是不可約的a可以表示為

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

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

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

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

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

2 設(shè)計(jì)方法與驗(yàn)證

2.1 模乘模塊設(shè)計(jì)

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

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

2.2 模逆模塊設(shè)計(jì)

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

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

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

2.3 點(diǎn)乘設(shè)計(jì)與實(shí)現(xiàn)

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

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

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

點(diǎn)乘KP模塊的實(shí)體描述為：

圖2 點(diǎn)乘測試模塊

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

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

3 結(jié)論

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