??? 摘 要： 在橢圓曲線密碼體制" title="橢圓曲線密碼體制">橢圓曲線密碼體制(ECC)中，有限域GF(2m)上模乘運(yùn)算是最基本的運(yùn)算，加速模乘運(yùn)算是提高ECC算法性能的關(guān)鍵。針對(duì)不同不可約多項(xiàng)式廣泛應(yīng)用的現(xiàn)狀，提出了一種通用GF(2m)模乘加速器設(shè)計(jì)方案。該加速器通過(guò)指令調(diào)度的方式，能快捷地完成有限域上模乘運(yùn)算。實(shí)現(xiàn)結(jié)果表明，該設(shè)計(jì)完全適用于智能卡等應(yīng)用要求。
??? 關(guān)鍵詞： 有限域; 橢圓曲線密碼體制; 模乘運(yùn)算; 快速實(shí)現(xiàn)
?
??? Neal Koblitz和V.S.Miller在公鑰密碼理論中引入橢圓曲線群，提出了橢圓曲線密碼體制ECC（Elliptic Curve Cryptography）。隨著傳統(tǒng)公鑰密碼體制受到大數(shù)分解和并行處理技術(shù)的日益嚴(yán)峻的挑戰(zhàn)，ECC便以最強(qiáng)的單比特安全性、曲線參數(shù)的更多可選性等優(yōu)點(diǎn)得到了人們?cè)絹?lái)越多的重視，其中基于GF(2m)上的橢圓曲線密碼體制的設(shè)計(jì)與實(shí)現(xiàn)是研究的熱點(diǎn)之一。針對(duì)ECC應(yīng)用現(xiàn)狀，本文提出一種通用GF(2m)模乘加速器結(jié)構(gòu)（密鑰擴(kuò)展范圍：160≤m≤400）并對(duì)其快速實(shí)現(xiàn)。
1 算法及加速器結(jié)構(gòu)設(shè)計(jì)
??? 橢圓曲線密碼系統(tǒng)運(yùn)算層次如圖1所示。由圖1可知，模乘運(yùn)算是ECC中最基本的運(yùn)算之一，且模平方和模逆運(yùn)算都可以轉(zhuǎn)化為模乘運(yùn)算操作。因此，快速實(shí)現(xiàn)模乘加速器具有很強(qiáng)的應(yīng)用價(jià)值。對(duì)于有限域GF(2m)中的元素，一般有正規(guī)基表" title="基表">基表示和多項(xiàng)式基表示兩種形式。采用不同基表示，雖然都可以表示成二進(jìn)制數(shù)串的形式，但其對(duì)應(yīng)的有限域中的運(yùn)算卻不一樣。模乘加速器采用正規(guī)基表示基域元素時(shí)，很容易進(jìn)行平方和指數(shù)運(yùn)算，但是實(shí)現(xiàn)面積較大，也不具有通用性，這是因?yàn)檎?guī)基通常選取最優(yōu)正規(guī)基(ONB)，而最優(yōu)正規(guī)基的存在是有條件的?？紤]到一般的有限域元素最直接、最常用的表達(dá)式是多項(xiàng)式的形式，且具有通用性。因此，本文提出的模乘加速器設(shè)計(jì)是基于一般不可約多項(xiàng)式的。
?
1.1 有限域GF(2m)上模乘運(yùn)算
??? 基域GF(2m)上多項(xiàng)式基表示下的模乘運(yùn)算從處理方式上大體可以分為全串行、全并行、串并" title="串并">串并結(jié)合三種類型，且對(duì)應(yīng)三種不同的快速設(shè)計(jì)方案。全串行模乘加速器是最簡(jiǎn)單的一種設(shè)計(jì)方案，完成一次GF(2m)上模乘運(yùn)算至少需要m個(gè)時(shí)鐘周期" title="時(shí)鐘周期">時(shí)鐘周期，運(yùn)算效率相對(duì)較低。由于其實(shí)現(xiàn)面積小，因此通常應(yīng)用于資源受限環(huán)境。全并行模乘加速器可以用一個(gè)時(shí)鐘周期完成運(yùn)算，但是其電路規(guī)模和m2成正比，所以當(dāng)遇到較大m時(shí)，其面積和功耗將會(huì)急劇增大。串并結(jié)合模乘加速器是一種比較現(xiàn)實(shí)的設(shè)計(jì)方案，在設(shè)計(jì)該加速器之前需要選取一個(gè)合理的數(shù)字大小(digit-size)。若選取數(shù)字大小為g，則完成一次GF(2m)上模乘運(yùn)算需[(m+1)/g]個(gè)時(shí)鐘周期。在綜合考慮效率、規(guī)模和功耗等各種因素情況下，本文模乘加速器將采用數(shù)字大小為8的串并結(jié)合加速器設(shè)計(jì)方案。若記
??? 
則其算法描述如下：
??? 
??? 在上述算法步驟①中，V1的計(jì)算實(shí)際上只需將P(x)邏輯左移g bit，然后再模約不可約多項(xiàng)式F(x)即可。在快速實(shí)現(xiàn)時(shí)，該操作是在一個(gè)時(shí)鐘周期內(nèi)完成的。其原理如圖2所示，其中L&R表示邏輯左移1bit后模約不可約多項(xiàng)式操作。
?
?
??? 
????若記LeftShift(g)為邏輯左移1位，則對(duì)于任意k（0
??? 因此，在上述算法步驟②中，V2的計(jì)算類似于V1的計(jì)算。只是在最后結(jié)果輸出時(shí)要考慮乘數(shù)的作用，該部分對(duì)應(yīng)在硬件結(jié)構(gòu)上就是m×g個(gè)與門(mén)和m×(g-1)個(gè)異或門(mén)，其原理如圖3所示，其中bit(j)表示m bit數(shù)據(jù)的第j bit(0≤j
?
?
??? 在模乘加速器片選信號(hào)有效時(shí)，計(jì)算V1的邏輯電路和計(jì)算V2的邏輯電路在同一時(shí)鐘周期內(nèi)是并行工作的，并且時(shí)鐘延遲相當(dāng)，計(jì)算結(jié)果在下個(gè)時(shí)鐘上升沿到來(lái)時(shí)得到。
1.2 通用GF(2m)模乘加速器結(jié)構(gòu)設(shè)計(jì)
??? 結(jié)合上述原理和方法，本文提出的通用GF(2m)模乘加速器架構(gòu)如圖4所示。
?
??? 該加速器支持定義在GF(2m)和160≤m≤400上的模乘和模加運(yùn)算。分為邏輯控制單元" title="控制單元">控制單元、運(yùn)算邏輯單元和寄存器三個(gè)模塊。邏輯控制單元主要對(duì)運(yùn)算邏輯單元及各個(gè)寄存器讀寫(xiě)進(jìn)行控制。根據(jù)外部指令OC內(nèi)容的不同，它控制加速器完成不同的操作。指令與操作之間的對(duì)應(yīng)關(guān)系如表1所示。
?
??? 運(yùn)算邏輯單元主要包括乘運(yùn)算邏輯和模約邏輯，在邏輯控制單元控制下每個(gè)時(shí)鐘周期完成8bit模乘運(yùn)算，并且在[(m+1)/8]個(gè)時(shí)鐘周期后將運(yùn)算結(jié)果送入結(jié)果寄存器。寄存器模塊主要保存運(yùn)算數(shù)據(jù)，在進(jìn)行模乘運(yùn)算時(shí)，在當(dāng)前時(shí)鐘周期內(nèi)，被乘數(shù)寄存器和不可約多項(xiàng)式寄存器中的數(shù)據(jù)是一次性讀入到運(yùn)算邏輯，而乘數(shù)寄存器中的數(shù)據(jù)只有高8位被讀入，同時(shí)乘數(shù)寄存器邏輯左移8位等待下一個(gè)時(shí)鐘周期的到來(lái)。
??? 對(duì)于基于橢圓曲線離散對(duì)數(shù)問(wèn)題(ECDLP)的公鑰加密體制，只有當(dāng)私鑰長(zhǎng)度至少為160bit時(shí)，才能達(dá)到理想中的安全強(qiáng)度。因此，通用模乘加速器應(yīng)用時(shí)要解決其接口問(wèn)題。該加速器引腳定義如表2所示。
?
??? 需要說(shuō)明的是，為了使該加速器適合不可約多項(xiàng)式的任意選取，在設(shè)計(jì)乘運(yùn)算邏輯和模約邏輯時(shí)應(yīng)考慮到各種不可約多項(xiàng)式的情況。如果選取特殊的不可約多項(xiàng)式：三項(xiàng)式或五項(xiàng)式、全一式(AOP)，則加速器規(guī)模將有所減小，效率將有所提高，但是達(dá)不到通用的目的。這也是本文選取一般不可約多項(xiàng)式的原因。
2 實(shí)現(xiàn)和結(jié)果分析
??? 采用VHDL語(yǔ)言作為設(shè)計(jì)工具，對(duì)上述加速器進(jìn)行了設(shè)計(jì)實(shí)現(xiàn)。使用ModelSim軟件對(duì)實(shí)現(xiàn)結(jié)果進(jìn)行功能仿真，保證了功能設(shè)計(jì)的正確性。利用Quartus II軟件平臺(tái)，選擇器件環(huán)境為CycloneII EP2C35F672C6完成通用加速器的邏輯綜合和時(shí)序仿真，并經(jīng)過(guò)FPGA開(kāi)發(fā)環(huán)境驗(yàn)證，邏輯綜合所得性能參數(shù)如表3所示。其中，標(biāo)量乘速度是在頻率為50.17MHz時(shí)鐘驅(qū)動(dòng)下，加速器配合微控制器（MCU）工作時(shí)的應(yīng)用評(píng)估。
?
參考文獻(xiàn)
[1] ?吳永一，李慶，曾曉洋．具有防御功耗攻擊性能的雙域橢圓曲線密碼處理器設(shè)計(jì)[J]．小型微型計(jì)算機(jī)系統(tǒng)，2006，27(12)：2321-2325．
[2] ?蔣林，章倩苓，謝曉燕．基于GF(2n)的ECC協(xié)處理器芯片設(shè)計(jì)[J].微電子學(xué)與計(jì)算機(jī)，2003，(9)：50-54．
[3] ?DAILEY D V, PAAR C. Efficient arithmetic in finite field ?extensions with application in elliptic curve cryptography[J]. Journal of Cryptology, 2001,14(3):153-176．
[4] ?Standard specifications for public key cryptography[S].?IEEE P1363-2000, August 2000．
[5] ?KOBLITZ N. Elliptic curve cryptosystems[J]. Mathematics of Computation, 1987,48(177)：203-209．