??? 摘 要： 在橢圓曲線密碼體制" title="橢圓曲線密碼體制">橢圓曲線密碼體制(ECC)中，有限域GF(2m)上模乘運算是最基本的運算，加速模乘運算是提高ECC算法性能的關鍵。針對不同不可約多項式廣泛應用的現(xiàn)狀，提出了一種通用GF(2m)模乘加速器設計方案。該加速器通過指令調度的方式，能快捷地完成有限域上模乘運算。實現(xiàn)結果表明，該設計完全適用于智能卡等應用要求。
??? 關鍵詞： 有限域; 橢圓曲線密碼體制; 模乘運算; 快速實現(xiàn)
?
??? Neal Koblitz和V.S.Miller在公鑰密碼理論中引入橢圓曲線群，提出了橢圓曲線密碼體制ECC（Elliptic Curve Cryptography）。隨著傳統(tǒng)公鑰密碼體制受到大數(shù)分解和并行處理技術的日益嚴峻的挑戰(zhàn)，ECC便以最強的單比特安全性、曲線參數(shù)的更多可選性等優(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="基表">基表示和多項式基表示兩種形式。采用不同基表示，雖然都可以表示成二進制數(shù)串的形式，但其對應的有限域中的運算卻不一樣。模乘加速器采用正規(guī)基表示基域元素時，很容易進行平方和指數(shù)運算，但是實現(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)實的設計方案，在設計該加速器之前需要選取一個合理的數(shù)字大小(digit-size)。若選取數(shù)字大小為g，則完成一次GF(2m)上模乘運算需[(m+1)/g]個時鐘周期。在綜合考慮效率、規(guī)模和功耗等各種因素情況下，本文模乘加速器將采用數(shù)字大小為8的串并結合加速器設計方案。若記
??? 
則其算法描述如下：
??? 
??? 在上述算法步驟①中，V1的計算實際上只需將P(x)邏輯左移g bit，然后再模約不可約多項式F(x)即可。在快速實現(xiàn)時，該操作是在一個時鐘周期內完成的。其原理如圖2所示，其中L&R表示邏輯左移1bit后模約不可約多項式操作。
?
?
??? 
????若記LeftShift(g)為邏輯左移1位，則對于任意k（0
??? 因此，在上述算法步驟②中，V2的計算類似于V1的計算。只是在最后結果輸出時要考慮乘數(shù)的作用，該部分對應在硬件結構上就是m×g個與門和m×(g-1)個異或門，其原理如圖3所示，其中bit(j)表示m bit數(shù)據的第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]個時鐘周期后將運算結果送入結果寄存器。寄存器模塊主要保存運算數(shù)據，在進行模乘運算時，在當前時鐘周期內，被乘數(shù)寄存器和不可約多項式寄存器中的數(shù)據是一次性讀入到運算邏輯，而乘數(shù)寄存器中的數(shù)據只有高8位被讀入，同時乘數(shù)寄存器邏輯左移8位等待下一個時鐘周期的到來。
??? 對于基于橢圓曲線離散對數(shù)問題(ECDLP)的公鑰加密體制，只有當私鑰長度至少為160bit時，才能達到理想中的安全強度。因此，通用模乘加速器應用時要解決其接口問題。該加速器引腳定義如表2所示。
?
??? 需要說明的是，為了使該加速器適合不可約多項式的任意選取，在設計乘運算邏輯和模約邏輯時應考慮到各種不可約多項式的情況。如果選取特殊的不可約多項式：三項式或五項式、全一式(AOP)，則加速器規(guī)模將有所減小，效率將有所提高，但是達不到通用的目的。這也是本文選取一般不可約多項式的原因。
2 實現(xiàn)和結果分析
??? 采用VHDL語言作為設計工具，對上述加速器進行了設計實現(xiàn)。使用ModelSim軟件對實現(xiàn)結果進行功能仿真，保證了功能設計的正確性。利用Quartus II軟件平臺，選擇器件環(huán)境為CycloneII EP2C35F672C6完成通用加速器的邏輯綜合和時序仿真，并經過FPGA開發(fā)環(huán)境驗證，邏輯綜合所得性能參數(shù)如表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．