使用FPGA實(shí)現(xiàn)AES算法的優(yōu)化設(shè)計(jì)

信息安全是計(jì)算機(jī)科學(xué)技術(shù)的熱點(diǎn)研究領(lǐng)域，數(shù)據(jù)加密則是信息安全的重要手段。隨著可編程技術(shù)的飛速發(fā)展及高速集成電路的不斷出現(xiàn)，采用FPGA實(shí)現(xiàn)加密算法已受到越來越廣泛的關(guān)注和重視。與傳統(tǒng)的軟件加密方法相比，硬件加密的優(yōu)點(diǎn)是：（1）安全性好，不易被攻擊；（2）計(jì)算速度快，效率高；（3）成本低，性能可靠。加密系統(tǒng)中體現(xiàn)數(shù)據(jù)傳輸速度的一個(gè)重要性能指標(biāo)是數(shù)據(jù)吞吐量，計(jì)算公式為：（數(shù)據(jù)長度M/時(shí)鐘個(gè)數(shù)N）×?xí)r鐘頻率F。提高數(shù)據(jù)吞吐量是改善加密系統(tǒng)性能的關(guān)鍵，也是加密算法硬件實(shí)現(xiàn)技術(shù)的重要內(nèi)容。

AES算法作為DES算法的替代者應(yīng)用非常廣泛，其硬件實(shí)現(xiàn)方法已有不少討論，主要是通過提高算法頻率來提高吞吐量。但是在實(shí)際運(yùn)行中，為了保證整個(gè)加密系統(tǒng)的穩(wěn)定性，通常全局時(shí)鐘頻率較低，不可能達(dá)到算法的仿真頻率，如PCI接口電路時(shí)鐘頻率只有33MHz，因此實(shí)際數(shù)據(jù)吞吐量仍然較低。本文根據(jù)AES算法的結(jié)構(gòu)特點(diǎn)及硬件系統(tǒng)的特點(diǎn)，提出一種快速的AES算法IP核設(shè)計(jì)方法。該方法采用優(yōu)化設(shè)計(jì)輪函數(shù)和流水線技術(shù)，在較低的系統(tǒng)時(shí)鐘頻率下，通過減少分組運(yùn)算時(shí)鐘數(shù)目來獲得更高的吞吐量和更快的傳輸速度。

1 AES算法

AES是美國國家標(biāo)準(zhǔn)與技術(shù)研究所（NIST）提出的高級(jí)加密標(biāo)準(zhǔn)。2000年10月，NIST宣布將比利時(shí)人Joan Daemen和Vicent Rijinen提交的Rijndael算法作為高級(jí)加密標(biāo)準(zhǔn)（AES）。該算法設(shè)計(jì)簡單，與公鑰密碼算法不同，沒有復(fù)雜的乘法運(yùn)算，易于實(shí)現(xiàn)，靈活性強(qiáng)，輪函數(shù)良好的并行特性有利于硬件設(shè)計(jì)與實(shí)現(xiàn)。AES算法是一種迭代型分組密碼，其分組長度和密鑰長度均可變，各自可以獨(dú)立指定為128bit、192bit、256bit。本文主要討論分組長度和密鑰長度為128bit的情況。

AES算法是將輸入的明文（或密文）分成16個(gè)字節(jié)，在第一個(gè)Add Round Keys變換后進(jìn)入10輪迭代。前9輪完全相同，依次經(jīng)過字節(jié)代替（Substitute Bytes）、行移位（Shift Rows）、列混合（Mix Columns）、輪密鑰加（Add Round Keys），最后一輪則跳過了Mix Column。解密過程與加密過程類似，但執(zhí)行順序與描述內(nèi)容有所不同，因此AES算法的加解密過程需要分別實(shí)現(xiàn)。圖1給出了AES算法的加解密過程。

2 AES算法優(yōu)化設(shè)計(jì)

2.1 硬件選擇

Cyclone器件是Altera公司推出的成本最低的SRAM工藝FPGA，容量為2 910～20 060個(gè)邏輯單元（LE）和多達(dá)288kbit的M4K memory block。每個(gè)LE都有一個(gè)四輸入的LUT查找表、可編程寄存器和具有進(jìn)位選擇能力的進(jìn)位鏈，可實(shí)現(xiàn)任何四輸入變量的函數(shù)，能夠進(jìn)行大量邏輯運(yùn)算，非常適合作為加密算法的硬件載體。設(shè)計(jì)中所使用的開發(fā)工具是QuartusII4.2，F(xiàn)PGA芯片選擇Cyclone器件的EP1C12Q240C8，基于Verilog HDL語言實(shí)現(xiàn)。

2.2 密鑰擴(kuò)展單元優(yōu)化設(shè)計(jì)

密鑰擴(kuò)展是將初始密鑰作為種子密鑰，經(jīng)過字節(jié)代換、字節(jié)移位、輪常數(shù)計(jì)算、字異或等過程，計(jì)算產(chǎn)生10輪迭代子密鑰。有文獻(xiàn)提出計(jì)算密鑰時(shí)密鑰擴(kuò)展和加密過程同步執(zhí)行，這樣做會(huì)節(jié)約FPGA的存儲(chǔ)器資源。但筆者認(rèn)為在算法運(yùn)行過程中，擴(kuò)展密鑰進(jìn)程始終運(yùn)行會(huì)增加FPGA芯片的動(dòng)態(tài)功耗。另外，AES算法解密運(yùn)算是從最后一輪子密鑰開始，只有擴(kuò)展出所有子密鑰才能啟動(dòng)解密運(yùn)算，因此制約了解密過程的實(shí)現(xiàn)。通常情況下初始密鑰不會(huì)頻繁改變，加/解密多包數(shù)據(jù)時(shí)可共享密鑰擴(kuò)展結(jié)果，同時(shí)由于Cyclone器件存儲(chǔ)器資源豐富，為存放子密鑰提供了足夠的空間。因此本文采用更普遍的做法，將所有子密鑰擴(kuò)展后保存在RAM中，使用時(shí)依次從RAM中讀取。這種方式不受加解密實(shí)現(xiàn)過程的限制，靈活性強(qiáng)，非常適合于加密算法的FPGA實(shí)現(xiàn)。

從RAM中讀取子密鑰需要時(shí)間，為了避免算法第一個(gè)Add Round Key過程帶來的延時(shí)，可以將第一組子密鑰（初始密鑰）和最后一組子密鑰（解密過程第一組子密鑰）在寫入RAM的同時(shí)，分別保存在兩組寄存器中。如圖2所示，加/解密時(shí)直接利用寄存器結(jié)果進(jìn)入算法第一輪迭代，保證算法在10個(gè)時(shí)鐘內(nèi)完成10輪迭代，從而減少Add Round Key的時(shí)間。

保存密鑰雖然多占用了約256個(gè)寄存器資源，但這樣做更易于實(shí)現(xiàn)算法的流水線操作，對(duì)提高整體性能有很大幫助。

2.3 輪函數(shù)優(yōu)化設(shè)計(jì)

優(yōu)化輪函數(shù)設(shè)計(jì)，減少輪函數(shù)的延時(shí)，是提高算法時(shí)鐘頻率的關(guān)鍵。本文通過對(duì)輪函數(shù)中Substitute Byte、Shift Row和Mix Column變換進(jìn)行優(yōu)化來提高算法的時(shí)鐘頻率。

輪函數(shù)中Substitute Byte（S-Box）是對(duì)一個(gè)字節(jié)的非線性操作。使用Verilog HDL描述S-Box通常有兩種方法：（1）使用case語句進(jìn)行行為描述，綜合后占用LE資源；（2）使用FPGA中的存儲(chǔ)器資源。AES算法的S-Box是一個(gè)8入8出的查找表，如果用LE實(shí)現(xiàn)，則在Cyclone芯片中每個(gè)S-Box需要208個(gè)LE，AES算法的并行運(yùn)算需要32個(gè)S-Box，共6656個(gè)LE，不但占用大量的硬件資源，而且使結(jié)構(gòu)復(fù)雜，增加了延時(shí)。而用存儲(chǔ)器資源實(shí)現(xiàn)S-Box，不需占用其他硬件資源，并且可以減少延時(shí)，是個(gè)很好的選擇。本文即采用這種方法，并充分利用器件資源：Cyclone器件中每個(gè)memory block可以設(shè)計(jì)為一個(gè)256×16bit的ROM，將加/解密過程的S-Box設(shè)計(jì)在同一個(gè)ROM內(nèi)，加密S-Box內(nèi)容置于ROM的前8bit，解密S-Box內(nèi)容置于ROM的后8bit，這樣可以使memory block的數(shù)目比分別使用ROM設(shè)計(jì)時(shí)減少一半，大幅提高了資源利用率。Shift Row的硬件實(shí)現(xiàn)非常簡單，只是連線操作。為了進(jìn)一步降低由于連線引起的延時(shí)，將Substitute Byte與Shift Row合為一體，使兩部分延時(shí)僅取決于S-Box的ROM。Mix Column變換被定義為系數(shù)在有限域GF（28）上的四次多項(xiàng)式矩陣乘法，輸入列向量（X0，X1，X2，X3），輸出列向量（Y0，Y1，Y2，Y3），加密過程是在GF（28）上乘以01、02、03，解密過程相對(duì)復(fù)雜，是在GF（28）上乘以09、0E、0B、0D。為了簡化設(shè)計(jì)以便于FPGA實(shí)現(xiàn)，可將矩陣乘法展開并整理，得到以下結(jié)果：

加密Mix Column：

解密Mix Column：

式中a是對(duì)一個(gè)字節(jié)的變換函數(shù)，其Verilog HDL描述為：

a={b［6：0］，1′b0}^（8′h1b&{8}）；

經(jīng)過整理，簡化了Mix Column實(shí)現(xiàn)過程，節(jié)約了硬件資源。Add Round Key只是簡單的異或，占用資源較少。優(yōu)化設(shè)計(jì)后輪函數(shù)的最大延時(shí)僅8.6ns，為提高整個(gè)設(shè)計(jì)的時(shí)鐘頻率提供了保障。

3 AES算法的快速實(shí)現(xiàn)

3.1 AES算法的硬件實(shí)現(xiàn)方式

AES算法的輪操作特點(diǎn)使得其硬件實(shí)現(xiàn)可以有多種方式：（1）串行運(yùn)算：輪函數(shù)用組合邏輯實(shí)現(xiàn)，10輪迭代過程直接相連，前一輪結(jié)果直接作為下一輪的輸入，1個(gè)時(shí)鐘周期內(nèi)完成一個(gè)分組運(yùn)算，吞吐量可以達(dá)到最佳狀態(tài)。（2）基本迭代：采用反饋模式，所有迭代只用一個(gè)輪函數(shù)，10個(gè)時(shí)鐘周期完成一個(gè)分組運(yùn)算。（3）輪內(nèi)流水線：在每一個(gè)輪函數(shù)中插入寄存器，將一輪運(yùn)算分成多個(gè)操作段，每個(gè)時(shí)鐘完成一個(gè)操作段，這種方式被很多人討論并使用，其優(yōu)點(diǎn)是可以提高算法運(yùn)行的時(shí)鐘頻率。

在以上幾種AES算法實(shí)現(xiàn)方式中，方式（1）由于10個(gè)輪函數(shù)同時(shí)工作，不但需要大量的寄存器資源和組合邏輯資源的支持，而且還增加了延時(shí)，一般的FPGA芯片難以滿足容量的要求，時(shí)鐘頻率也非常低，所以這種方法不適合加密算法的硬件實(shí)現(xiàn)。方式（2）實(shí)現(xiàn)簡單，資源占用較少，但每個(gè)分組運(yùn)算時(shí)間比較長，吞吐量仍然相對(duì)較低。在方式（3）中，由于加密算法的輪操作特點(diǎn)使得輪內(nèi)各級(jí)流水部件不能同時(shí)執(zhí)行，增加了算法運(yùn)行的時(shí)鐘數(shù)目。輪內(nèi)流水線級(jí)數(shù)越多，時(shí)鐘數(shù)目也越多。雖然算法仿真頻率可以達(dá)到很高，但由于受硬件加密系統(tǒng)全局時(shí)鐘的影響，吞吐量并沒有明顯提高。

在對(duì)以上算法的幾種實(shí)現(xiàn)方式進(jìn)行分析后，本文基于流水線技術(shù)，提出一種更快速的AES算法的FPGA實(shí)現(xiàn)方案。該方案即使在全局時(shí)鐘頻率較低的情況下，也能獲得很高的吞吐量。

3.2 流水線設(shè)計(jì)

AES算法結(jié)構(gòu)簡單，只需要邏輯運(yùn)算和查找表運(yùn)算。筆者通過優(yōu)化設(shè)計(jì)輪函數(shù)，使得基本迭代方式下的時(shí)鐘頻率遠(yuǎn)高于PCI接口的時(shí)鐘頻率33MHz。本文在滿足算法時(shí)鐘頻率的基礎(chǔ)上，通過降低算法分組數(shù)據(jù)的處理時(shí)間來提高吞吐量。具體做法是：采用兩級(jí)輪外流水線，將AES算法的10輪迭代過程分為前后兩個(gè)操作段，每個(gè)操作段可作為一級(jí)流水線，在操作段內(nèi)部，每輪之間以反饋（FB）方式完成5輪基本迭代，前一個(gè)操作段結(jié)束后，將結(jié)果直接送入第二個(gè)操作段，同時(shí)去處理下一個(gè)分組數(shù)據(jù)，兩個(gè)操作段互不影響，并行執(zhí)行?？紤]到實(shí)際應(yīng)用中數(shù)據(jù)總線寬度（如PCI總線）通常為32位，這里將AES算法IP核的數(shù)據(jù)寬度設(shè)置為32位，4個(gè)時(shí)鐘輸入/輸出一個(gè)分組數(shù)據(jù)。為了與每一級(jí)流水線5輪迭代過程相匹配，在輸入/輸出分組數(shù)據(jù)的第5n個(gè)時(shí)鐘內(nèi)執(zhí)行一輪空操作，使得輸入明文數(shù)據(jù)、輸出密文結(jié)果、第一級(jí)流水線和第二級(jí)流水線四步操作同時(shí)執(zhí)行，從而實(shí)現(xiàn)圖3所示的流水線過程。在得到第一個(gè)分組結(jié)果后，每5個(gè)時(shí)鐘就會(huì)產(chǎn)生一個(gè)分組結(jié)果，從外部看起來，完成一個(gè)分組僅需要5個(gè)時(shí)鐘。

3.3 實(shí)驗(yàn)結(jié)果與性能分析

將設(shè)計(jì)在QuartusⅡ4.2軟件中綜合，仿真最高頻率為78.38MHz，完全可以滿足較低全局時(shí)鐘頻率的要求。整個(gè)系統(tǒng)設(shè)計(jì)采用33MHz時(shí)鐘，實(shí)驗(yàn)測(cè)試結(jié)果表明，吞吐量已達(dá)到810Mbps。如果提高全局時(shí)鐘頻率，則吞吐量會(huì)超過1Ｇbps。

根據(jù)AES算法的特點(diǎn)及硬件加密系統(tǒng)的特點(diǎn)，給出了AES算法IP核的快速硬件設(shè)計(jì)方案。采用流水線技術(shù)和優(yōu)化設(shè)計(jì)，在較低頻率下，可以獲得很高數(shù)據(jù)吞吐量，使加密算法的FPGA實(shí)現(xiàn)過程不再是傳輸速度的瓶頸。整個(gè)設(shè)計(jì)具有很強(qiáng)的實(shí)用性，運(yùn)行穩(wěn)定，且效果良好。對(duì)于AES算法分組長度和密鑰長度為192bit和256bit的情況，由于分組長度不同，執(zhí)行輪數(shù)有所增加。要實(shí)現(xiàn)流水線操作并在資源使用和吞吐量方面達(dá)到較好的效果，還需要進(jìn)一步優(yōu)化設(shè)計(jì)，這也是今后研究的方向。