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