|
AES-Rijndael算法是美國(guó)取代DES的新一代分組加密算法標(biāo)準(zhǔn)，也是事實(shí)上的國(guó)際標(biāo)準(zhǔn)。本文在可重構(gòu)平臺(tái)上針對(duì) 128位密鑰長(zhǎng)度AES算法的流水線性能優(yōu)化技術(shù)進(jìn)行了研究，通過對(duì)基本運(yùn)算優(yōu)化、循環(huán)展開、輪內(nèi)流水線、輪間流水線、混合多級(jí)流水線結(jié)構(gòu)優(yōu)化等方法的討論和實(shí)現(xiàn)，對(duì)比不同優(yōu)化方法的優(yōu)缺點(diǎn)及適用環(huán)境。實(shí)驗(yàn)表明，不同結(jié)構(gòu)的設(shè)計(jì)，其加密性能存在很大差異。其中，混合多級(jí)流水線結(jié)構(gòu)的加密性能達(dá)到27．1 Gb／s的速率，為目前國(guó)內(nèi)外相關(guān)研究的較好結(jié)果。 關(guān)鍵詞 高級(jí)加密標(biāo)準(zhǔn) 可重構(gòu)計(jì)算 流水線 結(jié)構(gòu)優(yōu)化 AES-Rijndael算法 1 AES-RijndaeI算法總體結(jié)構(gòu) AES-Rijndael算法是一個(gè)替換一置換網(wǎng)絡(luò)結(jié)構(gòu)的分組密碼算法。它的設(shè)計(jì)基于有限域上的多項(xiàng)式運(yùn)算，密碼算法的主體結(jié)構(gòu)由4部分組成：SubBytes，進(jìn)行S-盒非線性變換；ShiftRows，狀態(tài)矩陣的水平置換；MixCol-umns，執(zhí)行有限域GF(28)上的矩陣乘運(yùn)算；AddRoundK-eys，通過簡(jiǎn)單異或運(yùn)算使子密鑰與狀態(tài)矩陣發(fā)生聯(lián)系。算法經(jīng)過Nr輪變換，將一個(gè)128位明文分組加密成為一個(gè)128位的密文分組。這里Nr是一個(gè)與密鑰長(zhǎng)度相關(guān)的常數(shù)。對(duì)于128位密鑰的情況，Nr的值為 10。除了最后一輪外，其他每一輪加密過程都相同。最后一輪加密中省去了 MixColumns變換，以抵抗某些特殊密碼分析。 2 循環(huán)展開和流水線優(yōu)化 對(duì)于前述AES加密過程的實(shí)現(xiàn)，如圖1(a)所示，我們針對(duì)可重構(gòu)平臺(tái)下4個(gè)變換函數(shù)的實(shí)現(xiàn)方法進(jìn)行了優(yōu)化，優(yōu)化后的加密過程時(shí)鐘頻率達(dá)到了127．9 MHz。這樣，對(duì)于一個(gè)128位明文分組的加密需要11個(gè)時(shí)鐘周期，因此，其加密速率為1．49 Gb／s。這一速率已經(jīng)能滿足絕大多數(shù)應(yīng)用的需要，然而為了滿足一些更高速應(yīng)用的需要，可以通過改變加密處理過程體系結(jié)構(gòu)進(jìn)一步優(yōu)化相應(yīng)設(shè)計(jì)。要提高加密速率，最簡(jiǎn)單的方法是使用循環(huán)展開技術(shù)將迭代加密的結(jié)構(gòu)展開，并將多份加密輪變換電路的輸入輸出首尾相連，如圖1(b)所示。這樣可以節(jié)省寄存器建立延遲和選路器的傳輸延遲時(shí)間，從而加快加密變換處理的速度。然而，這種方法會(huì)消耗大量的邏輯資源，并且性能提高得不多。根據(jù)我們的實(shí)驗(yàn)，循環(huán)展開后的芯片速度比迭代結(jié)構(gòu)增加了17％，然而所消耗的邏輯資源卻是迭代結(jié)構(gòu)的6倍。因此，這一優(yōu)化方法的效率是極其低的；只有在對(duì)性能要求很高，但資源又充分的情況下才能采用。 另外一種優(yōu)化方法是使用流水線技術(shù)。它是將關(guān)鍵執(zhí)行路徑切分為多級(jí)短的執(zhí)行步，并在各執(zhí)行步電路間插入寄存器存儲(chǔ)上一級(jí)執(zhí)行結(jié)果。這樣，雖然關(guān)鍵執(zhí)行路徑?jīng)]有變短，但電路可以在一個(gè)較少的時(shí)鐘周期內(nèi)同時(shí)處理多個(gè)數(shù)據(jù)塊的加密，從而提高了并發(fā)程度，因此，加密速率也就能大大提高。在設(shè)計(jì)加密算法處理流水線的過程中，最常用的是輪間流水線技術(shù)。輪問流水線技術(shù)是將循環(huán)展開結(jié)構(gòu)按各加密輪切分為一系列的流水線，其中每一輪加密變換為一級(jí)。在流水線的各級(jí)之間插入寄存器，寄存器由同步時(shí)鐘來控制，每次時(shí)鐘觸發(fā)，寄存器就保存上一次的變換結(jié)果，同時(shí)將之前保存的結(jié)果送流水線處理部件處理并將結(jié)果保存到下一級(jí)寄存器中，如圖1(c)所示。根據(jù)我們的實(shí)驗(yàn)結(jié)果(見圖3)，輪間流水線結(jié)構(gòu)的設(shè)計(jì)，加密速率是迭代結(jié)構(gòu)的12倍；同時(shí)資源消耗也大量增長(zhǎng)，是迭代結(jié)構(gòu)的7倍。由實(shí)驗(yàn)結(jié)果可見，輪間流水線技術(shù)是一種對(duì)分組加密算法很有效的優(yōu)化技術(shù)。特別是當(dāng)算法中加密輪函數(shù)較為簡(jiǎn)單的情況下，輪間流水線技術(shù)是相當(dāng)適用的；但是，對(duì)于一些輪函數(shù)復(fù)雜，加密輪數(shù)較少的算法，輪問流水線技術(shù)的優(yōu)化效果就不是很突出了。 
Chodowiec等人提出了輪內(nèi)流水線技術(shù)，以優(yōu)化這類加密變換輪較為復(fù)雜的算法。輪內(nèi)流水線將加密輪分割為多級(jí)，在每一級(jí)間插入寄存器，以實(shí)現(xiàn)流水線，如圖2(a)所示。這種方法的優(yōu)點(diǎn)在于所增加的資源消耗很少，僅需多級(jí)寄存器；然而也存在缺點(diǎn)，輪內(nèi)流水線很難平衡各級(jí)間的延遲，而整體時(shí)鐘的頻率只能由最長(zhǎng)流水線的延遲決定。我們的實(shí)驗(yàn)將AES加密函數(shù)按其組成模塊分割為4級(jí)流水線，要將其分為更多級(jí)也是可以做到的，但較為困難，因?yàn)轭愃芐一盒這樣的長(zhǎng)結(jié)構(gòu)很難再分，而它們的延遲將決定總體時(shí)鐘的頻率。
根據(jù)圖3所示實(shí)驗(yàn)結(jié)果，輪內(nèi)流水線結(jié)構(gòu)的執(zhí)行效率比迭代結(jié)構(gòu)的執(zhí)行效率高5倍，而所需資源反而比迭代結(jié)構(gòu)減少11％。經(jīng)分析，輪間流水線結(jié)構(gòu)加入了模塊問寄存器，所需資源應(yīng)該增加，而實(shí)際綜合結(jié)果卻是減少。為此我們?cè)敿?xì)分析了兩模塊中各結(jié)構(gòu)的綜合報(bào)告。從報(bào)告的數(shù)據(jù)看，應(yīng)該是邏輯綜合軟件對(duì)設(shè)計(jì)的優(yōu)化，使得輪間流水線結(jié)構(gòu)所需資源反而減少。
為了達(dá)到極高的加密速度，將輪內(nèi)流水線和輪外流水線結(jié)合使用，設(shè)計(jì)了混和輪內(nèi)外流水線結(jié)構(gòu)�；旌陷唭�(nèi)外流水線結(jié)構(gòu)具有極短的流水線單級(jí)延遲，因而時(shí)鐘頻率可以提高到212．5 MHz。同時(shí)，混合輪內(nèi)外流水線結(jié)構(gòu)能夠在每一時(shí)鐘周期內(nèi)完成一個(gè)數(shù)據(jù)分組的加密，這樣，加密的速度就可以達(dá)到27．1 Gb／s。這一速度是目前有關(guān)AES的高速加密芯片實(shí)現(xiàn)的報(bào)告中數(shù)據(jù)較高的。為了達(dá)到這樣高的加密速度，所需要的資源也是相當(dāng)可觀的。邏輯綜合結(jié)果顯示，完成這一設(shè)計(jì)需要17 887個(gè)邏輯單元，如圖4所示。這相當(dāng)于4塊Xilinx XC2V1000 FPGA的容量。同時(shí)，我們也評(píng)估了各種實(shí)現(xiàn)結(jié)構(gòu)的效率，用速率資源比，即每秒所能進(jìn)行加密的Mb數(shù)除以設(shè)計(jì)所需的邏輯單元數(shù)目得到的比值作為結(jié)構(gòu)的效率。從圖5可以看到，輪內(nèi)循環(huán)結(jié)構(gòu)是最高效的一種設(shè)計(jì)，其比值為3．49；而循環(huán)展開結(jié)構(gòu)效率最低，僅0．12。因此，在邏輯資源相對(duì)有限的條件下，選擇使用輪內(nèi)循環(huán)是比較合適的。
3 結(jié)論 綜上所述，除對(duì)AES加密算法基本運(yùn)算變換的優(yōu)化外，算法的整體實(shí)現(xiàn)結(jié)構(gòu)對(duì)其加密性能的影響是很重要的一個(gè)方面。一般情況下，在對(duì)效率要求不是很高的環(huán)境中，迭代結(jié)構(gòu)實(shí)現(xiàn)簡(jiǎn)單，所需資源最少，因而較為合適；但要達(dá)到更高的加密效率，并且希望實(shí)現(xiàn)代價(jià)較低的情況下，采用輪內(nèi)流水線結(jié)構(gòu)是一個(gè)較為合理的折中方案；只有當(dāng)有大量資源可用并且追求最高的加密性能時(shí)，才有必要采用輪內(nèi)輪間多級(jí)混合流水線結(jié)構(gòu)。 參考文獻(xiàn) 1. NIST Advanced Encryption Standard (AES) 2001 2. Fu Yongzhi.Hao Lin.Yang Rujin Design of An Extremely High Performance Counter Mode AES Reconfigurable Processor 2005 3. Elbirt Adam Reconfigurable Computing for Symmertric-Key Algorithms 2002 4. Pawel Chodowiec Comparison of the Hardware Performance of the AES Candidates Using Reconfigurable Hardware 2002 作者：西南林學(xué)院 付勇智 劉琳 來源：《單片機(jī)與嵌入式系統(tǒng)應(yīng)用》 2009 （6） |
