Edwards 曲線快速標(biāo)量乘算法的改進(jìn)與FPGA 實(shí)現(xiàn)*

高獻(xiàn)偉 明嬌嬌 張 磊 董秀則 張青川

1. 北京電子科技學(xué)院，北京市 100070；

2. 農(nóng)產(chǎn)品質(zhì)量安全追溯技術(shù)及應(yīng)用國家工程實(shí)驗(yàn)室(北京工商大學(xué))，北京市 100048

引言

公鑰密碼思想是由W.Diffie 和M.E.Hellman在1976 年提出的，隨著社會信息化的快速發(fā)展，人們對系統(tǒng)安全性要求越來越高，這點(diǎn)使得公鑰密碼的應(yīng)用也越來越廣泛。 RSA 是公鑰密碼體系中應(yīng)用最廣的一種公鑰密碼體制，但是，現(xiàn)在計(jì)算機(jī)的計(jì)算能力越來越高，RSA 變得越來越不安全，很容易就被第三方攻 破。 所以，對于RSA 密碼體制來說，若想要增強(qiáng)其安全強(qiáng)度，就必須不斷地增加密鑰長度，但是密鑰長度的增加所帶來的問題就是加解密速度特別慢，而且占用的存儲空間也比較大，這不但使得密碼體制效率低下，資源利用率也很低。

橢圓曲線密碼(Elliptic Curves Cryptography，ECC)體制是在1985 年由Miller[1]和Koblitz[2]分別提出來的。 研究表明，在安全性相同的情況下，ECC 的密鑰長度較短[3]。 例如，160 位密鑰的ECC 相當(dāng)于1024 位的RSA 的安全性[4]。 因?yàn)镋CC 的密鑰的長度比較短，所以ECC 在工程實(shí)現(xiàn)加密和解密時(shí)的速度比較快，并且節(jié)省資源，適合用在移動通信、智能卡等系統(tǒng)中。 因此，密碼學(xué)中熱衷于研究橢圓曲線的學(xué)者越來越多。Edwards[5]在2007 年為橢圓曲線引入了一種新的形式:x2＋y2＝c2(1 ＋dx2y2)，并且提出，如果一個(gè)域的特征不等于2，則該域上的橢圓曲線與該域或其擴(kuò)域上的Edwards 曲線等價(jià)。 Edwards曲線最大的優(yōu)點(diǎn)是點(diǎn)加運(yùn)算和倍點(diǎn)運(yùn)算的公式相同，所以其運(yùn)算規(guī)則比較簡單。 這個(gè)特點(diǎn)使得Edwards 曲線能夠天然有效地抵抗側(cè)信道攻擊[6]，進(jìn)而使得加密系統(tǒng)更加安全。 文獻(xiàn)[7]全面分析了Edwards 曲線上的點(diǎn)運(yùn)算規(guī)則，結(jié)果表明，Edwards 曲線上的運(yùn)算效率比其他形式的橢圓曲線效率更高。 如今對Edwards 曲線的研究也取得了一些優(yōu)秀的成果，例如，文獻(xiàn)[8]設(shè)計(jì)了一款加密處理器，該處理器是基于Edwards 曲線的，然后將該處理器設(shè)計(jì)于無源射頻識別(Radio Frequency Identification，RFID)標(biāo)簽，能夠很好的到達(dá)RFID 標(biāo)簽的要求。 文獻(xiàn)[9]對于標(biāo)量乘法的研究中提出馬爾科夫點(diǎn)加-倍點(diǎn)鏈能夠抵抗簡單能量攻擊。 文獻(xiàn)[10]采用串行和并行兩種算法，分別對標(biāo)量乘法進(jìn)行了測試，還有一些學(xué)者對二進(jìn)制Edwards 曲線的硬件設(shè)計(jì)進(jìn)行了測試[11][12]。 研究發(fā)現(xiàn)，Edwards 曲線是橢圓曲線中實(shí)現(xiàn)效率更好的一種曲線，而且其安全性也比其他曲線更高。 因此，Edwards 曲線成為橢圓曲線領(lǐng)域的研究熱點(diǎn)。

標(biāo)量乘是橢圓曲線密碼體制中的核心運(yùn)算，其運(yùn)算速度嚴(yán)重制約著整個(gè)密碼體系的實(shí)現(xiàn)效率。 Edwards 曲線作為一種新型橢圓曲線，其上的標(biāo)量乘算法研究較少，最常見的是采用二進(jìn)制計(jì)算方法，如文獻(xiàn)[10]中工程實(shí)現(xiàn)采用從左向右算法和從右向左算法。 該方法將標(biāo)量k 表示為二進(jìn)制形式，通過判斷每一位上的數(shù)值執(zhí)行相應(yīng)的點(diǎn)加和倍點(diǎn)運(yùn)算，此算法雖然比較簡單，但是運(yùn)算效率并不高。 文獻(xiàn)[13]中通過對倍點(diǎn)公式進(jìn)行變形設(shè)計(jì)了一種連續(xù)倍點(diǎn)算法，采用該算法來計(jì)算標(biāo)量乘能夠有效降低模逆運(yùn)算的次數(shù)。但是該算法是在仿射坐標(biāo)下設(shè)計(jì)的，不能用于其他坐標(biāo)系中，而且模逆運(yùn)算是模運(yùn)算中最耗時(shí)的運(yùn)算，算法最后一步仍然需要計(jì)算模逆運(yùn)算，因此，標(biāo)量乘運(yùn)算速度仍然受到制約。 為了提高Edwards 曲線上標(biāo)量乘的計(jì)算效率，本文針對標(biāo)量乘算法進(jìn)行研究，主要通過研究標(biāo)量k 的有效表示來減少點(diǎn)運(yùn)算的調(diào)用次數(shù)，從而提高標(biāo)量乘的運(yùn)算速度。

本文首先詳細(xì)地介紹了仿射坐標(biāo)系下和標(biāo)準(zhǔn)射影坐標(biāo)系下的Edwards 曲線上的點(diǎn)運(yùn)算規(guī)則以及一種Edwards 曲線上快速標(biāo)量乘(scalar multiplication on Edwards curve， EDSM)算法[14]，然后從標(biāo)量k 的表示形式上對該算法進(jìn)行了改進(jìn)，經(jīng)過計(jì)算得出改進(jìn)算法運(yùn)算效率優(yōu)于原算法，最后，將設(shè)計(jì)的算法在現(xiàn)場可編程門陣列(Field Programmable Gate Array， FPGA)上仿真實(shí)現(xiàn)，結(jié)果表明本文所提出的標(biāo)量乘算法能夠取得較好的運(yùn)算效率。

1 Edwards 曲線及其基本運(yùn)算

1.1 仿射坐標(biāo)下的Edwards 曲線

2007 年，Edwards 提出了特征不為2 的域K上橢圓曲線的一種新形式，定義如下:

其中，c，d ∈K，c，d ≠0，且cd4≠1，稱(1)式為Edwards 曲線，該曲線上的運(yùn)算規(guī)則簡單。研究表明，如果域的特征不等于2，那么其上的橢圓曲線雙有理等價(jià)于該域或者其擴(kuò)域上的Edwards 曲線。

更深一步研究發(fā)現(xiàn):任何特征不為2 的域上的橢圓曲線都能夠轉(zhuǎn)換為該域上c ＝1 的曲線，即(1)式簡化為

Edwards 曲線上的點(diǎn)對于加法運(yùn)算構(gòu)成加法群。 其中單位元為(0，1)， - P1＝(- x1，y1)，令P1＝(x1，y1) 和P2＝(x2，y2)，P1＋P2＝P3＝(x3，y3)，點(diǎn)加公式為:

當(dāng)P1＝P2時(shí)，公式(3)仍然成立，此時(shí)只要將其中的x2和y2分別替換為x1和y1，即為倍點(diǎn)公式:

令I(lǐng)，M，S 分別域K 上的求逆、乘法與平方運(yùn)算，則根據(jù)文獻(xiàn)[15]可知，I，M，S 之間的等價(jià)關(guān)系為I ＝10M，S ＝0.8M；令D 表示乘以d 的運(yùn)算，加法和減法運(yùn)算可以忽略不計(jì)，則點(diǎn)加公式(3)的計(jì)算量為2I ＋5M ＋1D ＝25M ＋1D，倍點(diǎn)公式(4)的計(jì)算量為2I ＋1M ＋3S ＋1D ＝23.4M＋1D。

1.2 標(biāo)準(zhǔn)射影坐標(biāo)下的Edwards 曲線

為了避免Edwards 曲線加法公式中耗時(shí)的求逆運(yùn)算，采用標(biāo)準(zhǔn)射影坐標(biāo)形式，將曲線方程表示為:

其上的(X1:Y1:Z1) 對應(yīng)于仿射坐標(biāo)下的點(diǎn)(X1/Z1，Y1/Z1)，Z1≠0。 單位元是(0:c:1)，(X1:Y1:Z1) 的逆是(-X1:Y1:Z1)。 令P1＝( X1:Y1:Z1) ，P1＝ ( X2:Y2:Z2) ，P3＝P1＋P2＝( X3:Y3:Z3) ，則點(diǎn)加公式為:

設(shè)有寄存器R1，R2，R3存儲X1，Y1，Z1，寄存器R4，R5，R6存儲X2，Y2，Z2，僅使用兩個(gè)臨時(shí)的寄存器R7，R8。 最終結(jié)果X3，Y3，Z3放在寄存器R1，R2，R3中，上述點(diǎn)加計(jì)算過程如下:

R3←R3·R6；R7←R1＋R2；R8←R4＋R5；R1←R1·R4；R2←R2·R5；R7←R7·R8；R7←R7-R1；R7←R7- R2；R7←R7·R3；R8←R1·R2；R8←d·R8；R2←R2-R1；R2←R2·R3；R3←R23；R1←R3-R8；R3←R3＋R8；R2←R2·R3；R3←R3·R1；R1←R1·R7；R3←cR3.

同樣地，設(shè)有寄存器R1，R2，R3存儲X1，Y1，Z1，寄存器R4，R5，R6存儲X2，Y2，Z2， 僅使用兩個(gè)臨時(shí)的寄存器R7，R8。 最終結(jié)果X3，Y3，Z3放在寄存器R1，R2，R3中，則倍點(diǎn)公式的計(jì)算過程如下所示:

由此可以看出，使用該倍點(diǎn)公式來計(jì)算X3，Y3，Z3的計(jì)算量為3M ＋4S ＋3C ＋6a。

1.3 Edwards 曲線上的快速標(biāo)量乘算法

標(biāo)量乘法是橢圓曲線上的關(guān)鍵運(yùn)算，其運(yùn)算速度影響著整個(gè)ECC 的運(yùn)算效率。 因此，研究如何加快標(biāo)量乘法的運(yùn)算速度對于ECC 來說很重要。

標(biāo)量乘kP 是指計(jì)算k 個(gè)P 相加的結(jié)果，其中k 為整數(shù)，P 為橢圓曲線上的一個(gè)點(diǎn)，則計(jì)算標(biāo)量乘法kP 的過程為:

根據(jù)公式(8)，如果要計(jì)算5P，則先計(jì)算兩次倍點(diǎn)運(yùn)算得到4P，然后再計(jì)算4P ＋P， 即由點(diǎn)加運(yùn)算得出5P 的結(jié)果。 橢圓曲線密碼算法結(jié)構(gòu)圖如圖1 所示，按照不同的層次來劃分橢圓曲線系統(tǒng)，可以分為4 層，分別為協(xié)議層、橢圓曲線層、點(diǎn)運(yùn)算層和有限域運(yùn)算層，由圖中可以看出，標(biāo)量乘法調(diào)用群運(yùn)算層中的點(diǎn)加運(yùn)算和倍點(diǎn)運(yùn)算，而點(diǎn)加運(yùn)算和倍點(diǎn)運(yùn)算調(diào)用底層有限域上的模加、模減、模乘和模逆運(yùn)算。 若要提高標(biāo)量乘法的運(yùn)算速度，第一個(gè)方面是提高底層有限域上的基本運(yùn)算，第二個(gè)方面是提高群運(yùn)算層上的點(diǎn)運(yùn)算速度，標(biāo)量乘法是通過調(diào)用點(diǎn)加和倍點(diǎn)運(yùn)算實(shí)現(xiàn)的，因此，減少點(diǎn)加和倍點(diǎn)的運(yùn)算次數(shù)可以有效提高標(biāo)量乘法的運(yùn)算速度。 眾所周知標(biāo)量k 的長度越短，點(diǎn)加和倍點(diǎn)的調(diào)用次數(shù)越少，本文首先引入了一種新的標(biāo)量乘運(yùn)算算法EDSM[14]，然后針對該算法進(jìn)行了改進(jìn)，改進(jìn)方案是將標(biāo)量k 表示為四進(jìn)制形式，并且給出了在四進(jìn)制下標(biāo)量乘法的實(shí)現(xiàn)算法，最后用Verilog HDL 語言對算法進(jìn)行描述，通過FPGA 仿真實(shí)現(xiàn)，給出改進(jìn)后算法的運(yùn)算速度。

首先介紹一種Edwards 曲線上的快速標(biāo)量乘算法EDSM 算法[14]。 計(jì)算標(biāo)量乘kP，k 是域K 上的任意一個(gè)整數(shù)， P 為Edwards 曲線上的點(diǎn)， 將 k 表 示 成 三 進(jìn) 制 形 式， 即 k ＝(kl-1kl-2…k1k0)，其中ki∈{0，1，2}。

算法1:EDSM 算法

輸入:k 和P，l 為k 的三進(jìn)制表示位數(shù)

輸出:kP

在算法1 中，循環(huán)語句執(zhí)行一次時(shí)，只需要計(jì)算一次倍點(diǎn)和一次點(diǎn)加，若忽略加減法運(yùn)算且c ＝1，則倍點(diǎn)的運(yùn)算量是3M ＋4S，點(diǎn)加的運(yùn)算量是10M ＋1S ＋1D。 因此，執(zhí)行一次循環(huán)語句總共需要的運(yùn)算量是13M ＋5S ＋1D，如果假定標(biāo)量k 的二進(jìn)制長度l′ ＝256，則由計(jì)算可以得出標(biāo)量k 的三進(jìn)制表示長度為l ＝(log2/log3)·l′≈162， 因此可得，算法1 中計(jì)算標(biāo)量乘法的EDSM 算法平均每比特的運(yùn)算量為[(9M ＋1S ＋1D) ＋(3M ＋4S) ＋(162 - 2)(13M ＋5S ＋1D)]/256 ≈8.17M ＋3.15S ＋0.63D。 其中，算法1 中步驟1 計(jì)算初始值時(shí)，點(diǎn)加運(yùn)算可以采用混合點(diǎn)加運(yùn)算，其運(yùn)算量為9M ＋1S ＋1D，而在循環(huán)體內(nèi)采用標(biāo)準(zhǔn)射影坐標(biāo)下的運(yùn)算，因此采用普通點(diǎn)加運(yùn)算即可，倍點(diǎn)運(yùn)算的計(jì)算量是3M ＋4S，因此倍點(diǎn)運(yùn)算相比點(diǎn)加運(yùn)算來說，計(jì)算量少一些。

2 標(biāo)量乘算法的改進(jìn)

一個(gè)整數(shù)用三進(jìn)制表示和四進(jìn)制表示時(shí)，它們的位數(shù)是不同的，如果用四進(jìn)制來表示標(biāo)量k，那么相比于三進(jìn)制來說， k 的長度會縮短20%左右。 在橢圓曲線標(biāo)量乘法中，標(biāo)量k 的長度決定著調(diào)用ECC 上點(diǎn)加運(yùn)算和倍點(diǎn)運(yùn)算的次數(shù)，如果k 的長度越短，則調(diào)用次數(shù)越少，相應(yīng)的標(biāo)量乘法的計(jì)算量就會減少。

2.1 Edwards 曲線上快速標(biāo)量乘算法的改進(jìn)

為了提高ECC 上標(biāo)量乘法的運(yùn)算速度，將k表示成四進(jìn)制形式，即k ＝(kl-1kl-2…k1k0)， 其中ki∈{0，1，2，3}。 改進(jìn)算法如下所示。

算法2:EDSM 算法改進(jìn)

輸入:k 和P，l 為k 的四進(jìn)制表示位數(shù)輸出:kP

因此，當(dāng)算法2 中輸入標(biāo)量k 和Edwards 曲線上的點(diǎn)P 后，其輸出的Q0即為標(biāo)量乘法kP 的值。 下面給出算法的正確性證明:

當(dāng)l ＝1 時(shí)，Q0＝k0P，for 循環(huán)語句不執(zhí)行，結(jié)論顯然成立。

當(dāng)l ＝2 時(shí)，即k ＝k1k0＝k1×4 ＋k0，初值Q0＝k1P，Q1＝(k1＋1)P。 for 循環(huán)語句執(zhí)行一次，此時(shí)i ＝0，ki＝k0，有以下四種情況。

執(zhí)行parallel do 語句，由k0＝0 有: Q0＝2(Q0＋Q2)＝2(k1P ＋k1P)＝4 ×k1P，Q1＝4Q1＋P ＝4 × k1P ＋P；最后輸出Q0＝4 × k1P 成立；

執(zhí)行parallel do 語句，由k0＝1 有:Q0＝4Q0＋P ＝4 × k1P ＋P，Q1＝2(Q1＋Q3) ＝2((k1＋1)P ＋k1P)＝4 × k1P ＋2P；最后輸出Q0＝4 ×k1P ＋P，成立；

執(zhí)行parallel do 語句，由k0＝2 有: Q0＝2(Q0＋Q2)＝2((k1＋1)P ＋k1P) ＝4 × k1P ＋2P，Q1＝4Q1-P ＝4(k1＋1)P-P ＝4×k1P ＋3P；最后輸出Q0＝4 × k1P ＋2P，成立；

執(zhí)行parallel do 語句，由k0＝3 有:Q0＝4Q0- P ＝4(k1＋1)P -P ＝4 ×k1P ＋3P，Q1＝4Q1＝4(k1＋1)P ＝4 × k1P ＋4P；最后輸出Q0＝4 ×k1P ＋3P，成立。

對于l ＞2 的情況，同樣可以用數(shù)學(xué)歸納法來證明。 假設(shè)當(dāng)l ＝n 時(shí)成立，證明l ＝n ＋1 時(shí)是否成立。 當(dāng)l ＝n ＋1 時(shí)，即k ＝knkn-1…k1，根據(jù)假設(shè)，for 循環(huán)執(zhí)行n 次后輸出Q0＝knkn-1…k1P，Q1＝(knkn-1…k1＋1)P。 同理，當(dāng)i ＝0，k0有四種取值，即等于0、1、2 或3，根據(jù)上述辦法可知，無論k0為何值，最后算法求出的Q0就是Q0＝knkn-1…k0P 的值，所以，當(dāng)l ＝n ＋1 時(shí)成立。

綜上，根據(jù)數(shù)學(xué)歸納法可知，算法是正確的。

2.2 效率分析

在算法2 中，第一步計(jì)算初值時(shí)， ki的取值有四種，分別為0，1，2，3。 當(dāng)ki取0 時(shí)，初值不用計(jì)算；當(dāng)ki取1 時(shí)，Q0＝P，Q1＝2P，需要進(jìn)行一次倍點(diǎn)運(yùn)算；當(dāng)ki取2 時(shí)，Q0＝2P，Q1＝3P，需要計(jì)算一次倍點(diǎn)和一次點(diǎn)加；當(dāng)ki取3 時(shí)，Q0＝3P，Q1＝4P，需要計(jì)算兩次倍點(diǎn)和一次點(diǎn)加。在循環(huán)體內(nèi)，當(dāng)ki取不同值時(shí)，Q0和Q1之間互不相關(guān)，可以在FPGA 中并行計(jì)算。 因此，執(zhí)行一次循環(huán)運(yùn)算最多需要計(jì)算兩次倍點(diǎn)運(yùn)算和一次點(diǎn)加運(yùn)算。

下面分析當(dāng)ki取不同值時(shí)，算法中計(jì)算Q0和Q1的平均運(yùn)算量。

ki＝0 時(shí)，Q0和Q1平均運(yùn)算量為[(13M＋5S＋1D)＋2(3M＋4S)＋10M＋1S＋1D]/2≈14.5M＋7S＋1D。 同樣地，當(dāng)分別計(jì)算ki＝1，2，3 時(shí)，計(jì)算Q0和Q1的平均運(yùn)算量分別為14.5M＋7S＋1D，14.5M＋7S＋1D，11M＋8.5S＋0.5D。 設(shè)ki＝0，1，2，3 出現(xiàn)概率相同，并且隨機(jī)出現(xiàn)，則算法2 中計(jì)算Q0和Q1的平均運(yùn)算量為[3(14.5M＋7S＋1D)＋(11M＋8.5S＋0.5D)]/4≈13.62M＋7.37S＋0.88D。 假定k的二進(jìn)制長度l′＝256，那么其四進(jìn)制表示長度l ＝(log2/log4)·l′＝128，由于在算法2 中，步驟1 計(jì)算初值時(shí)，ki＝0，1，2，3，因此需要計(jì)算兩次倍點(diǎn)運(yùn)算和一次點(diǎn)加運(yùn)算。 雖然在單次循環(huán)中比算法1多計(jì)算了一次倍點(diǎn)運(yùn)算，但是算法2 中標(biāo)量k 的長度變短了。 通過上述分析可以得出，算法2 中改進(jìn)的EDSM 算法平均每比特的運(yùn)算量為[(9M＋1S＋1D)＋2(3M＋4S)＋(128-2)(13.62M＋7.37S＋0.88D)]/256≈6.76M＋3.66S＋0.44D。

2.3 算法比較

表1 給出Edwards 曲線中不同算法的平均每比特的計(jì)算量比較，前三種算法的計(jì)算量參考文獻(xiàn)[14]。 使用基本二進(jìn)制算法計(jì)算標(biāo)量乘法時(shí)，無論是采用從左向右計(jì)算還是從右向左計(jì)算，在標(biāo)量k(假設(shè)k 是t 比特的數(shù))中0 和1 均衡情況下，兩種算法都需要進(jìn)行t/2 次點(diǎn)加運(yùn)算和t 次倍點(diǎn)運(yùn)算。 因此，當(dāng)標(biāo)量k 為256 位數(shù)時(shí)，平均每比特的計(jì)算量為[(256/2)(10M ＋1S ＋1D) ＋256(3M ＋4S)]/256 ＝8M ＋4.5S ＋0.5D。

文獻(xiàn)[16]利用連續(xù)倍點(diǎn)算法給出仿射坐標(biāo)系下標(biāo)量乘法的計(jì)算算法， 由于仿射坐標(biāo)系下需要計(jì)算復(fù)雜的模逆運(yùn)算，因此計(jì)算量較大，通過計(jì)算可得，其每比特的計(jì)算量為12.42M ＋1.89S ＋0.32D。 文獻(xiàn)[17]中也是采用四進(jìn)制來表示標(biāo)量k，然后根據(jù)k 的形式給出計(jì)算標(biāo)量乘法的算法。 但是標(biāo)量乘算法中計(jì)算Q0和Q1不能并行計(jì)算，Q1的值依賴于Q0。 而本文標(biāo)量乘算法中計(jì)算Q0和Q1時(shí)互相獨(dú)立，可以并行計(jì)算，從而提高標(biāo)量乘法的運(yùn)算效率。 算法中的點(diǎn)加都采用混合點(diǎn)加，表中(S，D) 表示相對于M的比例，即(1，1) 表示1S ＝1M，1D ＝1M；(0.8，0.5) 表示1S ＝0.8M，1D ＝0.5M；(0.8，0) 表示1S ＝0.8M，1D ＝0M。

表1 Edwards 曲線上各種標(biāo)量乘算法每比特計(jì)算量比較Table 1 Comparison of calculation amount per bit of various scalar multiplication algorithms on Edwards curve

通過表1 中不同算法的計(jì)算量可以看出，本文改進(jìn)后的算法每比特計(jì)算量比其他算法的計(jì)算量都低，在(S，D)比例分別為(1，1)、(0.8，0.5)、(0.8，0)的情況下，改進(jìn)后的算法比改進(jìn)的蒙哥馬利方法計(jì)算速度提高了35.8%、28.4%、21.5%，比EDSM 算法的計(jì)算速度提高了9.1%、10.0%、9.4%。

2.4 不同進(jìn)制效率分析

標(biāo)量乘法是ECC 上的核心運(yùn)算，本文對于標(biāo)量乘法的研究主要通過縮短標(biāo)量k 的長度來減少點(diǎn)運(yùn)算的調(diào)用次數(shù)，進(jìn)而提高標(biāo)量乘法的運(yùn)算速度。 用不同的進(jìn)制數(shù)表示標(biāo)量k 時(shí)，其長度是不一樣的，當(dāng)采用三進(jìn)制表示標(biāo)量k 時(shí)，其長度為162，當(dāng)采用四進(jìn)制表示標(biāo)量k 時(shí)，其長度為128，長度縮短了約20%。 根據(jù)上述計(jì)算結(jié)果可知，標(biāo)量k 采用四進(jìn)制后的運(yùn)算速度比三進(jìn)制僅提高了10%左右。 雖然四進(jìn)制長度比三進(jìn)制短，但是在四進(jìn)制形式標(biāo)量乘算法中計(jì)算Q0和Q1時(shí)，相比三進(jìn)制形式需要多做一次倍點(diǎn)運(yùn)算。也就是說，如果采用五進(jìn)制或者其他進(jìn)制，雖然標(biāo)量k 的長度會變短，但同時(shí)也會需要計(jì)算更多的點(diǎn)加或倍點(diǎn)運(yùn)算，導(dǎo)致計(jì)算量增加。 而且標(biāo)量k 表示的進(jìn)制數(shù)越多，需要的存儲空間會越大，效率反而會降低。

3 標(biāo)量乘的FPGA 實(shí)現(xiàn)與分析

為了更好地驗(yàn)證本文所設(shè)計(jì)標(biāo)量乘算法的實(shí)現(xiàn)效率，利用FPGA 并行計(jì)算的特點(diǎn)對設(shè)計(jì)的算法進(jìn)行仿真實(shí)現(xiàn)，下面給出具體分析。

3.1 標(biāo)量乘算法的FPGA 實(shí)現(xiàn)

模加/減法器用于計(jì)算兩個(gè)整數(shù)相加或者相減，然后對運(yùn)算結(jié)果進(jìn)行取模，即計(jì)算z ＝(x ±y)modp。 為了方便頂層文件調(diào)用，本文對于模加運(yùn)算和模減運(yùn)算的FPGA 實(shí)現(xiàn)采用可以同時(shí)具備模加/減的結(jié)構(gòu)[18]。 如果要在電路中實(shí)現(xiàn)既能進(jìn)行模加運(yùn)算又可以進(jìn)行模減運(yùn)算，就需要在算法中設(shè)置一個(gè)控制位，然后根據(jù)該控制位的取值來決定進(jìn)行模加運(yùn)算還是模減運(yùn)算。

模乘器采用文獻(xiàn)[19]中基于進(jìn)位存儲加法(Carry-Save Adder，CSA)的Montgomery 模乘器，該模乘器將傳統(tǒng)的串行結(jié)構(gòu)改進(jìn)為串并混合結(jié)構(gòu)，改進(jìn)后的Montgomery 模乘器能夠在一個(gè)時(shí)鐘周期內(nèi)進(jìn)行多次CSA 迭代運(yùn)算，這樣就可以降低一次模乘的時(shí)鐘個(gè)數(shù)，從而提高了模乘的運(yùn)算速度。 以256 比特的數(shù)據(jù)為例，當(dāng)選取一個(gè)周期進(jìn)行16 次迭代時(shí)，完成一次模乘僅僅需要0.22μs。

模逆運(yùn)算采用二進(jìn)制下的擴(kuò)展歐幾里德算法[18]，該算法可以計(jì)算z ＝xy-1modp。 歐幾里德模逆算法中除法運(yùn)算不能被FPGA 綜合，但是，二進(jìn)制下的擴(kuò)展歐幾里德算法對歐幾里得模逆算法進(jìn)行了擴(kuò)充，并且避免了除法運(yùn)算，因此，采用該算法進(jìn)行模逆運(yùn)算在時(shí)間上有很大的優(yōu)勢。

標(biāo)量乘算法的FPGA 實(shí)現(xiàn)時(shí)，本文選取Edwards 曲線x2＋y2＝1 ＋(121665/121666)x2y2，p＝2255- 19。 曲線上的點(diǎn)為P ＝(xp，yp)。 采用Verilog HDL 硬件語言對算法進(jìn)行代碼描述，并使用Modelsime 10.2c 進(jìn)行功能仿真。 仿真驗(yàn)證成功后，使用Synopsys 公司的Synplify Pro 編譯器進(jìn)行綜合，綜合實(shí)現(xiàn)是基于FPGA 硬件實(shí)現(xiàn)平臺，選用Xilinx Virtex5 XC5VLX20T 芯片。 選取素域上256 位的數(shù)據(jù)進(jìn)行測試，測試數(shù)據(jù)如下所示:

d ＝256′D37095705934669439343138083508754565189542113879843219016388785533085940283555；

k ＝256′HFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551；

先將k 表示為四進(jìn)制形式，如下所示:

k ＝33333333333333330000000000000000333333333333333333333333333333332330321233222 231221301132132201033032321302230023330120302111101；

x1＝256′H216936D3CD6E53FEC0A4E231FDD6DC5C692CC7609525A7B2C9562D608F25D51A；

y1＝256H′6666666666666666666666666666666666666666666666666666666666666658.

仿真結(jié)果和綜合后的器件頻率分別如圖2 和3 所示:

在仿真圖2 中，當(dāng)start ＝1 時(shí)對應(yīng)的時(shí)間為80ns，當(dāng)done ＝1 時(shí)對應(yīng)的時(shí)間為1456780ns，所以，采用改進(jìn)后的EDSM 算法計(jì)算一次標(biāo)量乘需要的時(shí)鐘個(gè)數(shù)為「1456780-80■/40 ＝36418。 由圖3 中可知，標(biāo)量乘綜合后的器件頻率為98.1MHz，因此，通過計(jì)算可得，完成一次標(biāo)量乘需要的時(shí)間為0.37ms。

3.2 性能對比分析

為了說明本文設(shè)計(jì)的標(biāo)量乘算法能取得比較好的效率，下面從完成一次256 位標(biāo)量乘所需要的時(shí)鐘個(gè)數(shù)、器件的時(shí)鐘頻率、運(yùn)算時(shí)間和資源消耗進(jìn)行分析。 表2 列舉了不同文獻(xiàn)的標(biāo)量乘運(yùn)算比較，如下所示:

在表2 中，為了公平合理地進(jìn)行對比，所有文獻(xiàn)都是選用Xilinx FPGA 作為仿真實(shí)現(xiàn)的硬件平臺，并且都是針對256 位數(shù)據(jù)的標(biāo)量乘運(yùn)算進(jìn)行研究。 文獻(xiàn)[20]采用的是基于Karatsuba-Ofman 算法的兩級流水線。 通過提出的乘法結(jié)構(gòu)，設(shè)計(jì)了一種基于改進(jìn)的Barret 模塊化乘法算法的256 位模塊化乘法器。 在模塊化乘法器上，完成了標(biāo)量乘法的調(diào)度。 文獻(xiàn)[20]的時(shí)鐘頻率最低，資源占用中還使用了芯片內(nèi)部的64 個(gè)18×18 的乘法器。 明顯本文設(shè)計(jì)的算法在運(yùn)算時(shí)間上更短，且本文不占用芯片內(nèi)部任何乘法器。文獻(xiàn)[21]中采用新型并行模塊化乘法算法，通過合并四個(gè)并行乘法器單元可以在電路級別進(jìn)行優(yōu)化，文中仿真平臺選用了兩種，分別為Xilinx Virtex4 和Xilinx Virtex6，為了公平合理的對比，本文選用Xilinx Virtex4 芯片進(jìn)行綜合，結(jié)果表明，本文在計(jì)算標(biāo)量乘運(yùn)算中，不僅資源占用較少，運(yùn)算時(shí)間也比文獻(xiàn)[21]降低了60%。文獻(xiàn)[22]中標(biāo)量乘法中采用全字乘法器，該乘法器所需的時(shí)鐘周期比較少，仿真是在Xilinx Virtex2 中進(jìn)行實(shí)現(xiàn)的，和本文進(jìn)行對比，其運(yùn)算速度不如本文的的高，占用資源上不僅使用了63020 個(gè)查找表，還額外使用了128 個(gè)18×18 的乘法器。 文獻(xiàn)[23]對于標(biāo)量乘的研究是基于高基Montgomery 模乘流水化陣列結(jié)構(gòu)，然后給出計(jì)算標(biāo)量乘法的硬件結(jié)構(gòu)。 為了便于比較，本文選用和文獻(xiàn)[23]一樣的仿真平臺Xilinx Virtex5，雖然本文的時(shí)鐘頻率不如文獻(xiàn)[23]高，使用的查找表數(shù)量也比文獻(xiàn)[23]多，但是本文運(yùn)算時(shí)間少，速度提高了一倍左右，而且文獻(xiàn)[23]中還用到了芯片內(nèi)部38 個(gè)DSP 模塊，本文并沒有占用芯片內(nèi)部的DSP 模塊，因此，本文具有更好的可移植性，對于其他硬件平臺也適用。

表2 本文標(biāo)量乘運(yùn)算性能與其他文獻(xiàn)性能的對比Table 2 Comparison of performance of scalar multiplication operation in this paper with that of other literatures

4 結(jié)語

Edwards 曲線是一種新型橢圓曲線，相比于傳統(tǒng)的曲線來說，目前針對Edwards 曲線的研究很少，尤其在硬件實(shí)現(xiàn)方面寥寥無幾。 但是，Edwards 曲線自身特點(diǎn)比其他曲線有很好的優(yōu)勢，研究Edwards 曲線對于橢圓曲線密碼體制來說有重大的意義。 本文針對EDSM 算法進(jìn)行了改進(jìn)，將標(biāo)量k 表示為四進(jìn)制的形式來減少k 的長度，從而降低點(diǎn)加運(yùn)算和倍點(diǎn)運(yùn)算的調(diào)用次數(shù)，以此來減少標(biāo)量乘法的運(yùn)算量，通過FPGA 仿真實(shí)現(xiàn)得出，本文算法不但能夠提高標(biāo)量乘法的運(yùn)算速度，而且具有良好的可移植性。