摘 要:介紹了一種適用于較小面積應(yīng)用場合AES密碼算法的實(shí)現(xiàn)方案。結(jié)合該算法的特點(diǎn)，在常規(guī)輪變換中提出一種加/解密列混合變換集成化的硬件結(jié)構(gòu)設(shè)計，通過選擇使用同一個模塊，可以實(shí)現(xiàn)加密和解密中的線性變換，既整合了部分加/解密硬件結(jié)構(gòu)，又節(jié)約了大量的硬件資源。仿真與綜合結(jié)果表明，加/解密運(yùn)算模塊面積不超過25 000個等效門，有效地減小了硬件實(shí)現(xiàn)面積，同時該設(shè)計方案也滿足實(shí)際應(yīng)用性能的需求。關(guān)鍵詞:AES算法; 復(fù)合域算法;輪變換; 加/解密硬件結(jié)構(gòu)

中圖分類號:TN918-33文獻(xiàn)標(biāo)識碼:A

文章編號:1004-373X(2010)16-0010-04

Hardware Implementation of AES Cipher Algorithm

WANG Ze-kun1，CHEN Song-tao2

(1. Huaxia College， Wuhan University of Technology，Wuhan 430223，China;2. Fiberhome Co. Ltd.， Wuhan 430223，China)

Abstract: An implementation of AES cipher algorithm for limited area application is introduced. In the normal round transformation， the combination of addroundkey transformation and (Inv) MixColumns transformation is presented for eliminating the difference between encryption and decryption in hardware architecture， and linear transformation is achieved when data is encrypted or decrypted in the certain condition choice. Simulation and synthesis results show that the encryption and decryption operation modules are no more than 25k gates， and can reduce the size of the hardware implementation more effectively. The design can meet the requirements in performance.

Keywords: AES algorithm; composite field arithmetic;round transformation; encryption and decryption hardware architecture

0 引 言

密碼模塊是安全保密系統(tǒng)的重要組成部分，其核心任務(wù)就是加/解密數(shù)據(jù)。目前，分組密碼算法AES以其高效率、低開銷、實(shí)現(xiàn)簡單等特點(diǎn)被廣泛應(yīng)用于密碼模塊的研制。隨著計算機(jī)信息技術(shù)和超大規(guī)模集成電路技術(shù)的成熟與發(fā)展，通過硬件來實(shí)現(xiàn)密鑰模塊的內(nèi)部運(yùn)作，可保證在外界無密鑰的明文流動，能夠?qū)崿F(xiàn)真正意義上的保密。此外，硬件實(shí)現(xiàn)還具有高速、高可靠性等特點(diǎn)。目前許多AES算法的硬件實(shí)現(xiàn)采用基于RAM查找表方式來實(shí)現(xiàn)算法中最關(guān)鍵的SubBytes部分。本文采用復(fù)合域來實(shí)現(xiàn)SubBytes部分的求逆運(yùn)算，以便于采用組合邏輯減小面積[1]。同時采用加/解密運(yùn)算中列變換的部分電路進(jìn)行復(fù)用，從而進(jìn)一步節(jié)省實(shí)現(xiàn)面積。這樣可以使AES密碼應(yīng)用于RFID系統(tǒng)，IC卡等面積要求較小的場合。

1 AES算法簡介

AES算法是一種迭代型分組密碼，其分組長度和密鑰長度均可變，各自可以獨(dú)立指定為128 b，192 b，256 b[2-3]。本文主要討論分組長度和密鑰長度為128 b的情況。AES算法是將輸入的明文(或密文)分成16個字節(jié)，在第一個Add Round Keys變換后進(jìn)入10輪迭代。迭代過程的前9輪完全相同，依次經(jīng)過字節(jié)代替(substitute bytes)、行移位(shift rows)、列混合(mixcolumns)、輪密鑰加(add round keys)，最后一輪則跳過了列混合(mix columns)。解密過程與加密過程類似，但執(zhí)行順序與描述內(nèi)容有所不同，因此AES算法的加解密運(yùn)算需要分別實(shí)現(xiàn)。

2 AES算法的硬件設(shè)計

根據(jù)AES算法的原理和基本結(jié)構(gòu)，將整個AES算法模塊分成4個相對獨(dú)立的子模塊:接口模塊、控制單元模塊、加解密運(yùn)算模塊、密鑰擴(kuò)展模塊。本文所設(shè)計的密碼算法不包括密鑰發(fā)生器，所用的密鑰通過接口模塊由外部輸入，加解密運(yùn)算后的數(shù)據(jù)經(jīng)輸出接口輸出[4]。AES算法模塊的總體結(jié)構(gòu)如圖1所示。

2.1 接口模塊的設(shè)計

輸入接口模塊的主要任務(wù)是:將數(shù)據(jù)傳送到加解密運(yùn)算模塊，將外部輸入的密鑰傳送到密鑰擴(kuò)展模塊。由于明文和密鑰輸入都是128位，將導(dǎo)致整個模塊的輸入/輸出過多，占用太多資源，考慮到本文的設(shè)計主要應(yīng)用于對面積要求較小的場合使用，如RFID系統(tǒng)中數(shù)據(jù)的傳輸[5]，即每次傳輸?shù)臄?shù)據(jù)是64位，故采用4個32位寄存器，在時鐘的控制下每次輸入1組32位，通過4個時鐘周期可得到128位的數(shù)據(jù)，可以有效減少資源的占用。輸出接口模塊的作用是將128位的解密運(yùn)算結(jié)果輸出，同樣也采取32位分4組輸出的方法。

圖1 AES算法模塊的總體結(jié)構(gòu)框圖

2.2 控制模塊的設(shè)計

控制模塊的主要任務(wù)是實(shí)現(xiàn)加/解密運(yùn)算模塊與密鑰擴(kuò)展模塊工作的啟動?？刂颇K在時鐘脈沖控制下，產(chǎn)生控制加/解密模塊中字節(jié)替代、行移位、列混合、密鑰加各部分工作信號?？捎?個兩狀態(tài)的狀態(tài)機(jī)實(shí)現(xiàn)控制。當(dāng)新的數(shù)據(jù)或密鑰輸入時，通過狀態(tài)機(jī)的信號可判斷上次加/解密運(yùn)算是否完成。如果狀態(tài)機(jī)信號處于忙狀態(tài)，說明加解密運(yùn)算正在進(jìn)行，需要等待;如果信號處于空閑狀態(tài)，說明加解密運(yùn)算已經(jīng)完成，可以啟動加解密運(yùn)算模塊與密鑰擴(kuò)展模塊，將數(shù)據(jù)和密鑰分別輸入到加解密運(yùn)算模塊與密鑰擴(kuò)展模塊中，開始新一組數(shù)據(jù)的加解密運(yùn)算。

2.3 加解密運(yùn)算模塊的設(shè)計

AES算法的輪變換特點(diǎn)使之在硬件實(shí)現(xiàn)時可以有多種方式[6]:串行方式，輪變換可采用組合邏輯實(shí)現(xiàn);在10輪迭代過程中，前一輪結(jié)果可直接作為下一輪的輸入;并在1個周期內(nèi)完成1個分組運(yùn)算，使吞吐量達(dá)到最佳狀態(tài)。但需要大量的存儲器資源和組合邏輯資源支持，一般的FPGA芯片難以滿足容量的需求，而且時鐘頻率非常低;基本迭代反饋方式，所有迭代只用1個輪變換模塊，10個時鐘周期完成1個分組運(yùn)算，資源占用較少;輪內(nèi)流水線方式，在輪變換中插入寄存器，將每輪運(yùn)算分成多個操作段，每個時鐘完成1個操作段，其優(yōu)點(diǎn)是可以提高算法運(yùn)行的時鐘頻率。但輪內(nèi)各級流水部件不能同時執(zhí)行，因此增加了算法運(yùn)行的時鐘數(shù)目。輪內(nèi)流水線級數(shù)越多，時鐘數(shù)目也越多，雖然算法仿真頻率可以達(dá)到很高，但吞吐量并沒有明顯提高。

綜上比較可知，本文AES算法的硬件實(shí)現(xiàn)的目的是盡量減少資源的占用，使面積盡可能減小。故采用基本迭代反饋工作方式設(shè)計。

2.3.1 SubBytes( )和InvSubBytes( )的設(shè)計

字節(jié)代替是整個AES硬件實(shí)現(xiàn)中最為重要的變換，在加解密運(yùn)算模塊及密鑰擴(kuò)展模塊中字節(jié)代替是主要的運(yùn)算過程。因此，字節(jié)代替的硬件設(shè)計決定了整個AES算法硬件實(shí)現(xiàn)的速度和面積。字節(jié)代替可以通過查找表和算術(shù)運(yùn)算的方式[7]得到。傳統(tǒng)的AES算法使用查找表方法實(shí)現(xiàn)字節(jié)代替，可以提高求逆速度，但由于該變換輸入的數(shù)據(jù)為8位，加密和解密所用的替換字節(jié)表不同，因此需要的選擇器和寄存器數(shù)量較多，硬件實(shí)現(xiàn)面積較大，故主要用于高速AES的實(shí)現(xiàn)。算術(shù)運(yùn)算的方式在硬件設(shè)計上表現(xiàn)為組合邏輯，采用算術(shù)運(yùn)算的方式實(shí)現(xiàn)則會降低硬件設(shè)計的復(fù)雜度，減小面積[8]。

2.3.2 ShiftRows( )和InvShiftRows( )的設(shè)計

行移位變換作用在中間態(tài)的行上，將狀態(tài)中的行按不同的偏移量進(jìn)行循環(huán)移位。加密運(yùn)算中間態(tài)的0～3行，分別向右循環(huán)移動0，1，2，3個字節(jié)。該操作僅是將數(shù)據(jù)按字節(jié)進(jìn)行移動，硬件實(shí)現(xiàn)時只需在布線上進(jìn)行調(diào)整，基本不占硬件資源。

解密過程只是行移位的逆變換，即分別向左循環(huán)移動0，1，2，3個字節(jié)。同樣，該操作也僅將數(shù)據(jù)按字節(jié)移動。如果有字節(jié)的位置改變，只需在布線上進(jìn)行修改。

2.3.3 MixColumns( )和InvMixColumns( )的設(shè)計

MixColumns( )變換以矩陣中的列為單位，將每列看作一個GF(28)域上的四階多項(xiàng)式，將多項(xiàng)式乘以c(x)/d(x)并對x4+1取模。其中c(x)為:

c(x)={03}x3+{01}x2+{01}x+{02}(1)

在相應(yīng)的解密過程中:

d(x)={0B}x3+{0D}x2+{09}x+{0E}(2)

同樣對x4+1取模。

為了降低整個模塊的復(fù)雜度，考慮將加解密運(yùn)算中列混合變換的部分電路進(jìn)行復(fù)用，對比加解密運(yùn)算所乘的多項(xiàng)式，可以發(fā)現(xiàn){03}x可以用({02}x)⊕x表示，同理:

{0B}x={08}x⊕{02}x⊕x

{0D}x={08}x⊕{04}x⊕x

{09}x={08}x⊕x(3)

{0E}x={08}x⊕{04}x⊕{02}x⊕x

因此，{02}x可以作為一個基本單元，由于在GF(28)域內(nèi)，{02}x mod m(x)，x∈GF(28)

m(x)=x8+x4+x3+x+1(4)

這樣:

{02}x={x7x6x5x4x3x2x1x0}⊕

{0，0，0，x7，x7，0，x7，x7}(5)

由于0⊕xi=xi，式(8)只需要4個異或門就可實(shí)現(xiàn)。將該單元記為xtime( )函數(shù)。其硬件結(jié)構(gòu)如圖2所示。加密時所取的系數(shù)較小{01，02，03}，所以只需經(jīng)過一次xtime( )單元，便將乘法運(yùn)算轉(zhuǎn)換為移位操作和加法運(yùn)算的復(fù)合。

而解密時，Mixcolumns( )的系數(shù)是{09，0B，0E，0D}，實(shí)現(xiàn)這些乘法顯然比加密時需要更多的時間。由式(3)可知，InvMixcolumns( )也可用xtime ( )函數(shù)與異或門實(shí)現(xiàn)。這樣，就可以實(shí)現(xiàn)加/解密列混合變換電路的復(fù)用，從而節(jié)約電路面積，提高解密運(yùn)算速度[9]。

圖2 xtime( )的硬件結(jié)構(gòu)

2.3.4 密鑰加AddRoundKey( )的設(shè)計

在AES算法中，加法用異或操作實(shí)現(xiàn)。密鑰加是中間狀態(tài)的每一字節(jié)按位與輪密鑰進(jìn)行異或操作，加法的逆運(yùn)算也用異或操作，所以可采用逐位異或操作實(shí)現(xiàn)加解密運(yùn)算的AddRoundkey( )。AddRoundkey( )的逆運(yùn)算是其自身。因此本文在常規(guī)輪中把加密時的密鑰加、列混合變換和解密時的密鑰加、列混合變換集成為同一模塊，通過加解密信號的選擇，實(shí)現(xiàn)加解密運(yùn)算的列變換和密鑰加功能。這樣可消除加解密硬件結(jié)構(gòu)的差異，同時也可降低輪密鑰處理的復(fù)雜度。

2.4 密鑰擴(kuò)展模塊的設(shè)計

輪密鑰的產(chǎn)生是AES 加解密運(yùn)算的基礎(chǔ)，密鑰擴(kuò)展模塊的作用就是產(chǎn)生除了初始密鑰本身之外的10 個輪密鑰，分別用于10輪加解密運(yùn)算。

加密運(yùn)算采用密鑰內(nèi)部擴(kuò)展的方式，即加密運(yùn)算與密鑰擴(kuò)展并行完成[10]。這一過程，每一輪變換都要和相應(yīng)密鑰擴(kuò)展輪次生成的子密鑰進(jìn)行異或，因此需使用狀態(tài)機(jī)控制加密運(yùn)算和密鑰擴(kuò)展的同步，否則會發(fā)生混亂。需要指出，使用內(nèi)部擴(kuò)展方式可以提高整個加密運(yùn)算速度。而解密運(yùn)算采用外部擴(kuò)展方式，即密鑰擴(kuò)展完之后再進(jìn)行解密運(yùn)算，因?yàn)榻饷苓\(yùn)算使用的初始密鑰是密鑰擴(kuò)展生成的最后一輪子密鑰。

3 仿真測試與結(jié)果

根據(jù)前述設(shè)計思路和優(yōu)化措施， 系統(tǒng)采用Mentor公司專門為各邏輯器件制造廠商設(shè)計的第三方專用仿真工具M(jìn)odelSim 6.0進(jìn)行功能仿真，給出了最后的功能仿真圖。

3.1 加密運(yùn)算的仿真測試

一次完整的加密操作，需要12個時鐘周期。其中，10個周期用于10個輪循環(huán)變換，1個時鐘周期用于初始的密鑰擴(kuò)展，1個時鐘周期用于密文的輸出。加密運(yùn)算的功能測試仿真波形如圖3所示。

圖3 加密運(yùn)算的功能仿真結(jié)果

從圖3給出的加密運(yùn)算功能仿真結(jié)果可以看出，加密運(yùn)算與密鑰擴(kuò)展過程是并行進(jìn)行。當(dāng)“rst”變?yōu)榈碗娖?，“l(fā)d”變?yōu)楦唠娖綍r，明文3243f6a8885a308d313198-a2e0370734與密鑰2b7e151628aed2a6abf7158809cf4f3c分別同時加載到加解密運(yùn)算模塊與密鑰擴(kuò)展模塊中;在下一個時鐘周期，密鑰擴(kuò)展模塊生成1輪子密鑰，等待加密輪變換中的密鑰加操作。當(dāng)完成1次加密過程后，“done”信號變?yōu)楦唠娖?，同時輸出密文3925841d02dc09fbdc-118597196a0632。從圖3中同時也可以看出，密鑰擴(kuò)展模塊總是提前一個時鐘周期生成下一輪的子密鑰，這樣可以保證密鑰擴(kuò)展與加密運(yùn)算同時進(jìn)行而不會發(fā)生錯亂，并且還可提高加密速度，節(jié)約資源占用和減少面積。使用DC進(jìn)行綜合和優(yōu)化后，加密運(yùn)算模塊面積不超過20 000個等效門，其中組合邏輯面積為14 264門，非組合邏輯面積為3 878門。

3.2 解密運(yùn)算的仿真測試

在解密過程中，完成一次解密操作同樣需要12時鐘周期。其中，10個周期用于10個輪循環(huán)變換，1個時鐘周期用于初始密鑰的加載，1個時鐘周期用于密文的輸出。在解密過程中，本文采用在解密之前所生成的10輪子密鑰，因?yàn)榻饷艹跏夹枰淖用荑€是密鑰擴(kuò)展得到的最后一輪子密鑰，而最后一輪需要的子密鑰是密鑰擴(kuò)展的初始密鑰。如圖4所示。

解密過程與密鑰擴(kuò)展過程不是同步的，當(dāng)“kld”為高電平時，從第1個時鐘周期開始，便將初始密鑰2b7e151628aed2a6abf7158809cf4f3c輸入到密鑰擴(kuò)展模塊中，之后經(jīng)過10個時鐘周期生成10輪子密鑰，并存儲到寄存器中。當(dāng)“l(fā)d”為高電平時，密文3925841-d02dc09fbdc118597196a0632開始加載到解密模塊中，經(jīng)過10個時鐘周期將解密的密文輸出，同時“done”信號變?yōu)楦唠娖?，表示解密過程結(jié)束，并輸出明文3243f6a8885a308d313198a2e0370734。

圖4 解密運(yùn)算的功能仿真測試結(jié)果

對比圖3與圖4仿真測試結(jié)果可知，加解密運(yùn)算的功能正確，即解密運(yùn)算能夠正確地解出加密運(yùn)算的密文。

解密運(yùn)算模塊使用DC進(jìn)行綜合和優(yōu)化后面積不超過25 000個等效門。其中組合邏輯面積為10 495門，非組合邏輯面積為14 142門。由于密鑰擴(kuò)展與解密過程不是同步進(jìn)行，占用了寄存器存儲解密過程所需的10輪子密鑰，所以非組合邏輯面積比加密運(yùn)算模塊大。但需要指出，由于加/解密運(yùn)算模塊部分電路采用復(fù)用的方法實(shí)現(xiàn)，所以整個加/解密運(yùn)算模塊的實(shí)際總面積比沒有復(fù)用時減小。

4 結(jié) 語

根據(jù)設(shè)計思路和優(yōu)化措施， 本文使用Verilog硬件描述語言實(shí)現(xiàn)AES密碼算法， 并在ModelSim 6.0工具下進(jìn)行仿真，證明本文設(shè)計的正確性。為了更進(jìn)一步做比較，證明本文設(shè)計思路的合理性和優(yōu)化措施的有效性，同樣采取未優(yōu)化的設(shè)計方案實(shí)現(xiàn)了該算法，通過在DC中進(jìn)行綜合、布線，兩相比較， 優(yōu)化后的設(shè)計比優(yōu)化前節(jié)省了22%的邏輯單元，處理速度提高了13%。

參考文獻(xiàn)

[1]黃小苑，戴紫彬.基于FPGA的AES算法芯片設(shè)計實(shí)現(xiàn)[J].微電子學(xué)與計算機(jī)，2005，22(8):62-64.

[2]DAEMEN Joan， RIJMEN Vincent.高級加密標(biāo)準(zhǔn)(AES)算法:Rijndael的設(shè)計[M].谷大武， 徐勝波，譯.北京:清華大學(xué)出版社，1996.

[3]盧開澄.計算機(jī)密碼學(xué):計算機(jī)網(wǎng)絡(luò)中的數(shù)據(jù)保密與安全[M].北京:清華大學(xué)出版社，1998.

[4]夏宇聞.Verilog數(shù)字系統(tǒng)設(shè)計教程[M].北京:北京航空航天大學(xué)出版社，2003.

[5]Joint Technical Committee. ISO/IEC 14443 (Part1-Part4)identification cards-contactless integrated circuit(s) cards – Proximity cards[S]. [2001-07-15].http://webstore.jec.ch/preview.

[6]MORIOKA S， SATOH A. An optimized S-box circuit architecture for low power AES design[C]//Proc. of CHES.[S.l.]: CHES， 2003: 172-186.

[7]陳俊，王晶，曾曉洋，等.低復(fù)雜度先進(jìn)密碼算法的VLSI實(shí)現(xiàn)[J].計算機(jī)工程，2007，33(4):143-145.

[8]吳亞聯(lián)，段斌.AES密碼計算構(gòu)件的設(shè)計及應(yīng)用[J].計算機(jī)工程，2005，31(21):181-186.

[9]蔡宇東，沈海斌，嚴(yán)曉浪.AES算法的高速實(shí)現(xiàn)[J].微電子與計算機(jī)，2004，20(1):83-85.

[10]武玉華，李艷俊，周玉坤，等.基于FPGA的AES-128密碼算命實(shí)現(xiàn)研究[J].微計算機(jī)信息，2007，23(25):53-54.