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