AES加密算法的一種優(yōu)化的FPGA實(shí)現(xiàn)方法

隨著密碼分析水平，芯片處理能力和計(jì)算技術(shù)的不斷進(jìn)步，DES的安全強(qiáng)度已經(jīng)難以適應(yīng)新的安全需要，其實(shí)現(xiàn)速度、代碼大小和跨平臺(tái)性均難以繼續(xù)滿足應(yīng)用需求。因此，NIST(美國國家標(biāo)準(zhǔn)與技術(shù)研究所)籌劃AES(高級(jí)數(shù)據(jù)加密標(biāo)準(zhǔn))算法，旨在取代DES，以保護(hù)21世紀(jì)敏感政府信息的新型加密標(biāo)準(zhǔn)。Rijndael算法以其簡潔、高效、安全和原則性的設(shè)計(jì)被接納為AES，并于2001年11月26日正式公布在FIPS(Federal Information ProcessingStandards)出版的FIPS-PUB 197中。作為DES的繼承者，AES自從被接納為標(biāo)準(zhǔn)之日起就已經(jīng)被工業(yè)界、銀行業(yè)和行政部門作為事實(shí)上的密碼標(biāo)準(zhǔn)。

隨著網(wǎng)絡(luò)傳輸速度提升為gigabits數(shù)量級(jí)，業(yè)界對算法的執(zhí)行速度的要求也越來越高，基于軟件的密碼算法便顯得性能不足，需要采用硬件加密的方式，他采用一些特殊的優(yōu)化技術(shù)(如流水線和查找表等)，可極大地提高數(shù)據(jù)的流量并減少密鑰的生成時(shí)間。另外，用硬件實(shí)現(xiàn)加密算法及與之相關(guān)的密鑰生成過程，并且封裝到芯片中，因?yàn)樗麄儾灰妆煌獠抗粽咦x取或更改，會(huì)有較高的物理安全性。因此，基于硬件的密碼算法就受到業(yè)界的普遍關(guān)注。以FPGA為代表的可重構(gòu)硬件以其自身所固有的特點(diǎn)——既具有硬件的安全性和高速性又有軟件的靈活性和易維護(hù)性，已經(jīng)成為分組密碼算法硬件實(shí)現(xiàn)的熱點(diǎn)研究方向。

本文介紹AES加密算法的一種FPGA實(shí)現(xiàn)的方法以及對其加密速度的優(yōu)化處理技巧。

2 AES加密算法簡介

AES是一種迭代分組密碼，采用的是代替／置換網(wǎng)絡(luò)(SPN)。他將明文分組長度固定為128 b，而且僅支持128，196或256 b的密鑰長度，本文僅對密鑰長度為128 b的情況進(jìn)行討論。

AES加密算法的實(shí)現(xiàn)包括密鑰擴(kuò)展過程和加密過程。加密過程又包括一個(gè)作為初始輪的初始密鑰加法(AddRoundKey)，接著進(jìn)行9次輪變換(Round)，最后再使用一個(gè)輪變換(FinalRound)，如圖1所示。

每一次Round均由SubBytes，ShiftRows，MixColumns和AddRoundKey共4個(gè)步驟構(gòu)成，F(xiàn)inalRound包含除MixColumns這一步外的其他3個(gè)步驟，Round結(jié)構(gòu)如圖2所示。

輪變換及其每一步均作用在中間結(jié)果上，將該中間結(jié)果稱為狀態(tài)，可以形象地表示為一個(gè)4*4 B的矩陣。

3 AES加密算法的優(yōu)化

3.1 字節(jié)代換(SubBytes)

步驟SubBytes是Rijndael密碼中惟一的非線形變換。他是一個(gè)磚匠置換，該置換包含一個(gè)作用在狀態(tài)字節(jié)上的S-盒，用SRD表示，他是由字節(jié)在GF(28)域中求其乘法逆并外加一個(gè)仿射變換(仿射變換的作用是復(fù)雜化S-盒的代數(shù)表達(dá)式)實(shí)現(xiàn)，假設(shè)該步的輸入為a，輸出為b，即b=SRD(a)。由于該步驟是一種非線形面向字節(jié)的變換，是將一個(gè)8位二進(jìn)制數(shù)據(jù)轉(zhuǎn)換為另一個(gè)不同的8位二進(jìn)制數(shù)據(jù)，這里要求一一對應(yīng)，并且替換結(jié)果不能超出8位，可以通過構(gòu)造可逆的S-盒來實(shí)現(xiàn)。

根據(jù)字節(jié)代換的要求和特點(diǎn)，具體實(shí)現(xiàn)時(shí)，可以將S-盒用一個(gè)16*16 B的置換表來表示，通過查表即可實(shí)現(xiàn)該步變換，避免了復(fù)雜的乘法運(yùn)算。

3.2 行移變換(ShiftRows)

ShiftRows是線形變換，他和列混合運(yùn)算相互影響，在多輪變換后，使密碼信息達(dá)到充分的混亂，提高非線形度。

行變換是在狀態(tài)的每個(gè)行間進(jìn)行的，是狀態(tài)中的行按照不同的偏移量進(jìn)行循環(huán)左移運(yùn)算，在明文分組長度為128 b，密鑰長度為128 b時(shí)，ShiftRows對狀態(tài)的每行作用如下列表達(dá)式所示：

顯而易見，可以通過對每個(gè)字節(jié)的移位簡單實(shí)現(xiàn)該步變換。

3.3 列混合變換(MixColumns)

MixColumns是線形變換，是以狀態(tài)的列為單位進(jìn)行的操作。假設(shè)該步的一列的輸入為a，輸出為b，MixColumns對狀態(tài)的每列作用如下列表達(dá)式：

上述矩陣乘法為GF(28)有限域中的乘法運(yùn)算，并且有一個(gè)因子為常數(shù)。由于GF(28)有限域中的每一個(gè)元素都能夠?qū)懗?2的不同冪次的和(例如：15=01○+022 ○+024)，因此，乘以任何常數(shù)的乘法都可以通過反復(fù)的乘以02和異或運(yùn)算來實(shí)現(xiàn)。可將矩陣乘法中的常數(shù)因子分解為02的不同冪次和，矩陣乘法轉(zhuǎn)換為與02的乘法和異或運(yùn)算。將GF(28)域中的每一個(gè)元素與02的乘積存儲(chǔ)在一張16*16 B查找表中，記作xtime(?)(例如：02*a=xtime(a))。所以，該步驟可以通過查表和異或運(yùn)算實(shí)現(xiàn)，表達(dá)式如下(假設(shè)該步的一列的輸入為a，輸出為b)：

3.4 密鑰加法(AddRoundKey)

AddRoundKey是將輪密鑰中的各個(gè)字節(jié)與狀態(tài)中的各個(gè)字節(jié)逐位異或，實(shí)現(xiàn)密碼和密鑰的混合。輪密鑰是由初始密鑰通過密鑰擴(kuò)展得到的。

3.5 密鑰擴(kuò)展(ExpandedKey)

以明文分組長度為128 b，密鑰長度為128 b為例，ExpandedKey將初始密碼密鑰(初始密鑰可以形象的排列成一個(gè)4*4 B的矩陣)作為初始密鑰加法的密鑰，以后的各輪輪密鑰是經(jīng)過下列表達(dá)式的密鑰擴(kuò)展函數(shù)得到的(K[i][j]表示初始密鑰狀態(tài)的第i行第j列，W[i][j]表示擴(kuò)展后密鑰狀態(tài)的第i行第j列，Nk表示密鑰分組的列數(shù)，Nr表示輪數(shù)，Nb表示明文分組的列數(shù)，這里Nk=4，Nr=10，Nb=4)：

當(dāng)Nk≤6時(shí)：

其中，SRD(?)是S-盒的置換表，RC(j／Nk)是一個(gè)輪常量，用于消除對稱，可以通過查輪常量的表來得到。

密鑰的選?。旱趇輪的輪密鑰就是由矩陣W中第Nb*i列到Nb*(i+1)-1列給出。

3.6 流水線結(jié)構(gòu)

流水線結(jié)構(gòu)是實(shí)現(xiàn)流程中加入寄存器和相應(yīng)的邏輯電路，將整個(gè)過程劃分為前后相連的多級(jí)實(shí)體，每一級(jí)只完成數(shù)據(jù)處理的一個(gè)步驟，一個(gè)時(shí)鐘周期完成一級(jí)數(shù)據(jù)處理，然后在下一個(gè)時(shí)鐘到來時(shí)將處理后的數(shù)據(jù)傳遞給下一級(jí)；第一組數(shù)據(jù)進(jìn)入流水線后，經(jīng)過一個(gè)時(shí)鐘周期傳遞到第二級(jí)，同時(shí)第二組數(shù)據(jù)進(jìn)入笫一級(jí)，數(shù)據(jù)隊(duì)列依次前進(jìn)。使一個(gè)時(shí)鐘內(nèi)有多個(gè)數(shù)據(jù)塊同時(shí)在各級(jí)中處理。雖然每組數(shù)據(jù)都要經(jīng)過整個(gè)流水線后才能得到最后的計(jì)算結(jié)果，但是作為整個(gè)流水線，每個(gè)時(shí)鐘周期都能計(jì)算出一組結(jié)果，所以平均計(jì)算一組數(shù)據(jù)幾乎只需要一個(gè)時(shí)鐘周期的時(shí)間，大大提高了數(shù)據(jù)處理速度，保證了整個(gè)系統(tǒng)以較高的頻率工作。

流水線技術(shù)通過同時(shí)處理多個(gè)數(shù)據(jù)塊的方法提高吞吐量，其代價(jià)是硬件資源的增加。流水線結(jié)構(gòu)只能用于非反饋加密模式。

4 實(shí)現(xiàn)及仿真

整體的系統(tǒng)結(jié)構(gòu)如圖3所示。圖中粗線代表數(shù)據(jù)線，細(xì)線代表控制線。控制信號(hào)從輸入接口進(jìn)入，數(shù)據(jù)和密鑰通過數(shù)據(jù)總線進(jìn)入，根據(jù)控制模塊來進(jìn)行數(shù)據(jù)傳輸，更換密鑰和加密運(yùn)算。

從第3節(jié)的分析可以看出，AES算法可以通過對SRD表，xtime表和RC表的查詢和通過組合邏輯實(shí)現(xiàn)的移位和異或運(yùn)算來實(shí)現(xiàn)。這些實(shí)現(xiàn)方法代替了繁瑣的乘法運(yùn)算，提高了加密速度。

采用了流水線結(jié)構(gòu)來同時(shí)處理多個(gè)數(shù)據(jù)塊，提高吞吐量。

使用輪函數(shù)完全展開的開環(huán)結(jié)構(gòu)，將輪函數(shù)劃分成4級(jí)流水線，輪函數(shù)中的每一個(gè)步驟都是一級(jí)，并在級(jí)與級(jí)之間加入寄存器暫存中間狀態(tài)的數(shù)據(jù)以消除競爭，從而實(shí)現(xiàn)了輪函教內(nèi)部的完全流水，如圖4所示。

其中，控制信號(hào)sel1，sel2．sel3干sel4分別是每一級(jí)(每一步數(shù)據(jù))處理是否完成的標(biāo)志。

在輪函數(shù)的外部，將每一輪函數(shù)都作為外部流水中的一級(jí)，從而實(shí)現(xiàn)了算法內(nèi)部外部的完全流水結(jié)構(gòu)，如圖5所示。

其中，控制信號(hào)sel0～sel10分別是每一輪數(shù)據(jù)處理是否完成的標(biāo)志。

由于采用流水線結(jié)構(gòu)只能用于非反饋加密模式，所以AES算法的實(shí)現(xiàn)使用的是電碼本模式(ECB)的工作方式。

密鑰擴(kuò)展這一步放在所有加密步驟之前進(jìn)行。再先輸入初始密鑰，然后通過對SRD表和RC表的查詢和通過組合邏輯實(shí)現(xiàn)的移位和異或運(yùn)算完成密鑰的擴(kuò)展，并將結(jié)果存儲(chǔ)在一個(gè)176 B的寄存器中。在密鑰擴(kuò)展完成后再進(jìn)行以后的數(shù)據(jù)加密，在進(jìn)行每一輪的密鑰法時(shí)，將直接在該寄存器中選擇輪密鑰。

針對AFS算法和FPGA的特點(diǎn)，對每一步的處理都采用以字節(jié)為單位的對寄存器進(jìn)行操作的方式。往QuartusII5.0中，用VHDL硬件描述語言實(shí)現(xiàn)了該算法，經(jīng)過仿真，結(jié)果如下：

5 擴(kuò)展及應(yīng)用

迎過FPGA來實(shí)現(xiàn)AES的解密算法(在此僅討論分組長度為128 b，密鑰長度為128 b時(shí)的情況)，同樣可以用查找表和簡單的組合邏輯來實(shí)現(xiàn)?？紤]到使用等價(jià)解密算法沒有多少好處，所以選用直接解密算法，依舊可以采用輪函數(shù)內(nèi)部外部完全流水的流水線技術(shù)來提高解密速度。

注意：

(1)解密算法中的逆字節(jié)代換這一步驟可通過查逆SRD表實(shí)現(xiàn)。

(2)解密算法中的逆行移變換這一步驟可直接將狀態(tài)的每一行循環(huán)右移實(shí)現(xiàn)，如下列表達(dá)式所示：

也可以將狀態(tài)的第二行和第四行互換后進(jìn)行加密算法中的行移變換，然后再將變換后的狀態(tài)的第二行和第四行互換來實(shí)現(xiàn)解密算法中的逆行移變換這一步驟。這樣就利用了加密算法中的行移變換的模塊(此方法僅適用于分組長度為128 b的情況)。

(3)解密算法中的逆列混合變換這一步驟中，由于矩陣乘法的系數(shù)為09，0E，0B，0D，如下列表達(dá)式所示(假設(shè)該步的一列的輸入為a，輸出為b)：

可以通過一個(gè)預(yù)處理步驟和一個(gè)列混合變換步驟來實(shí)現(xiàn)，頇處理步驟如下列表達(dá)式所示(a是一列)：

這樣就利用了加密算法中的列混合變換的模塊。

在同時(shí)支持加解密的模塊中，密鑰擴(kuò)展和密鑰加法的部分可以同時(shí)用于這兩種模式，密鑰擴(kuò)展部分只須輸入對應(yīng)的肌密的初始密鑰后做和加密同樣的密鑰擴(kuò)展，然后按照解密所需要使用的輪密鑰的順序重新排列，存入寄存器等待使用即可，這樣可以節(jié)約資源。

由此，可以將AES的加解密算法統(tǒng)一起來，在一個(gè)FPGA模塊中實(shí)現(xiàn)。通過AVR或ARM等處理器的控制來選擇FPGA是執(zhí)行加密過程還是解密過程以及是否更換新的初始密鑰，形成完整的加解密模塊，可作為單獨(dú)的密碼機(jī)使用或通過各種接口與計(jì)算機(jī)，工控機(jī)等其他主控設(shè)備連接完成對數(shù)據(jù)的加解密。

AES加解密算法可以應(yīng)用于虛擬專用網(wǎng)、SONET、遠(yuǎn)程訪問服務(wù)器、高速ATM、以太路由器、移動(dòng)通信、衛(wèi)星通信、電子金融業(yè)務(wù)等領(lǐng)域，為其提供安全、可靠、快速的解決方案。