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