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