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