低成本AES加解密集成設計

劉松 夏樹村

該文提出一種有效的基于內容可尋址存儲器（CAM）的S/S-1盒查找表的實現方法，可以應用于AES的加密和解密運算，與基于RAM的S/S-1盒查找表相比，其復雜性顯著降低。同時還提出一種關鍵路徑上只有5個異或門延遲的列/逆列混合復用的硬件結構,大大節省了芯片面積。

AES；內容可尋址存儲器；S/S-1盒；列/逆列混合

1.引言

隨著AES算法的推廣，其應用的范圍越來越廣泛。一般的硬件實現方案都是采用并行運算的形式，雖然提供了很高的數據吞吐率，但是資源消耗卻很大，這就使得AES在便攜設備等對硬件開銷要求苛刻的領域中的應用受到限制。

為了能夠高效、低成本的實現AES算法，本文提出一種新穎的基于內容可尋址存儲器（CAM）的S/S-1盒查找表方法，僅使用一個查找表就可以實現AES的加密和解密運算。與基于RAM的S/S-1盒查找表相比，這種存儲器的復雜性顯著地降低。同時還提出一種低復雜度的硬件結構來實現列/逆列混合變換，使得解密過程能夠充分利用加密的硬件資源，進一步有效地減少了芯片面積。

本文組織結構如下：第2節簡要介紹AES算法；第3節重點介紹基于CAM的S/S-1盒查找表的體系結構，并與單獨實現S盒與S-1盒查找表的方法進行比較；第4節詳細介紹列/逆列混合的優化設計；第5節總結全文。

2.AES算法

AES是一種對稱分組密碼算法，其分組長度和密鑰長度均可變，支持任意組合的128bit、192bit和256bit的分組長度和密鑰長度。根據不同的密鑰長度，AES的圈數分別為10、12和14。數據分組被分割成字節陣列，每一次運算都是面向字節的運算。基本的輪運算包括：字節代替/逆字節代替、行移位/逆行移位、列混合/逆列混合和圈密鑰加。

無論進行加密或解密運算，數據分組首先與初始密鑰進行異或，然后進行N-1圈迭代輪運算，其中 取決于密鑰長度，最后一圈進行除列/逆列混合之外的其它三個變換。

字節代替變換是一個關于字節的非線性變換，將狀態中的每一個字節非線性地變換為另一個字節，代替表（S盒）是可逆的，且由兩個可逆變換復合而成。首先，將每一個字節變換為有限域中的乘法逆，規定00變換到其自身；其次，將上一步的結果在上做仿射變換。

逆字節代替變換是字節代替變換的逆變換。首先對每一個字節在上做仿射變換的逆變換，然后返回其在有限域中的乘法逆元素。

行移位變換就是加密時將一個狀態的第 行循環左移 個字節，解密時循環右移 個字節即為逆行移位變換。

列混合變換對一個狀態逐列進行變換，它將一個狀態的每一列視為有限域GF(2^8)上的一個多項式且與一個固定多項式相乘。

加密時的列混合變換可表示為：解密時的逆列混合變換為：

圈密鑰加就是簡單地將一個圈子密鑰按位異或到一個狀態上。圈子密鑰按順序取自擴展密鑰，擴展密鑰由初始密鑰經過擴展后得到。

3.字節代替的優化設計

內容可尋址存儲器（CAM）具有固有的并行性，允許并行地存取和比較存儲器中的內容。本節提出一種新穎的基于CAM的查找表來執行S盒與S-1盒的查表操作。通過比較說明這種實現方法比使用兩個單獨的S盒與S-1盒查找表的復雜性顯著降低。

A.內容可尋址存儲器（CAM）

內容可尋址存儲器（CAM）[2]是一種并行模式的匹配電路，能同時搜索存儲器中的所有內容，并返回匹配數值的存儲地址。CAM被視為一種并行處理器，用來加速實現圖像處理和數據庫搜索等應用。

CAM除擁有傳統的存儲器如RAM的讀寫功能外，還具有一種特殊的功能，它能夠并行地比較其中存儲的數據和數據線上的數據，返回滿足比較條件的地址。

本文設計了一個8bit的CAM來實現S/S-1盒查找表。圖1所示為CAM單元第bit的邏輯電路。在查找內容前，將匹配信號（match）復位為1。圖中，連接數據線連接數據線。可知，。如果，則那么匹配信號接地，即=0。否則那么=1。進行寫操作時，地址線被激活，通過數據線，數據被寫入CAM單元中（數據被存儲在和中）。進行讀操作時，選取相應的地址線，通過數據線獲得存儲器中的內容。

B.基于CAM的S/S-1盒查找表

AES加密過程定義了一個S盒查找表，包含8bit的256個置換值。解密過程同樣也定義了一個S-1盒。我們提出一種新穎的基于CAM的S/S-1盒查找表的體系結構。

在CAM單元陣列中，用地址線來表示S盒的輸入，存儲的數據作為其輸出值。每行為8bit，共有256行。在配置時將查找表的初始值加載到CAM中。當進行S盒查表操作時，選擇相應的地址線，通過數據線讀出數值。例如，要找到字節{00}的置換值，地址線00被激活，通過數據線可以讀出輸出值為{63}。當進行S-1盒查表操作時，將使用CAM的搜索功能。例如，為了找到字節{63}的逆置換值，將63裝入比較寄存器，開始并行搜索。CAM將匹配數值63，并返回相應的地址{00}，于是可以使用{00}作為{63}的逆置換值。這樣，S盒與S-1盒就可以通過一個查找表來實現，顯著降低了查找表的復雜性，大大節省了芯片面積。

圖2為本文提出的基于CAM的S/S-1盒查找表的體系結構。在圖2中，有一個8bit的比較寄存器，用來存儲被比較的數據，通過數據線與CAM相連。我們注意到，被比較的數據被連接到數據線時是取反的，這是由于CAM單元的邏輯結構所致。如果數據與CAM中的相匹配，相應的匹配信號變為1，匹配標記（match flag）被標注。CAM的相應地址線可以通過地址譯碼器來獲得，返回一個8bit的地址值。

與使用兩個查找表來實現S盒與S-1盒的方法相比，基于CAM的S/S-1盒查找表的復雜性顯著降低。表1比較了基于RAM和CAM實現方式的存儲空間的復雜性，可以看出在加解密過程中，使用一個基于CAM的查找表，比RAM方式實現的S/S-1盒查找表減少了25%的硬件資源。

表1不同的查找表實現方式的資源比較

4.列/逆列混合的優化設計

AES中定義了x乘,即用x乘以一個多項式，可以用字節內左移一位和緊接著的一個與“1b”的按位異或來實現，記為。

可將上式統一表示為：

的電路結構如圖3所示。

利用，對加密的列混合變換進行化簡：

顯然，化簡后的列混合變換的關鍵路徑僅為3個異或門延遲。

對解密的逆列混合變換來說，我們設計了和兩個模塊[3]，分別為：

的電路結構分別如圖4、5所示，均為2個異或門延遲。

圖4結構圖圖5結構圖

由此，逆列混合變換可化簡為：

可見，逆列混合的實現可以利用列混合的電路結構，降低了結構的復雜性，而且通過共享部分硬件資源，有效地減少了芯片面積。如此一列狀態需要（3+6+9?+8?）?=364個2輸入異或門，其關鍵路徑上的延遲為5個異或門，如圖6所示。

如上提出的結構只是完成字節的列/逆列混合變換，要實現整個列/逆列混合變換，首先要集成4個字節列/逆混合模塊，組成一個新的字列/逆列混合模塊，如圖7所示。然后再集成4個字列/逆列混合模塊，組成一個128bit的分組列/逆列混合模塊。圖8即為并行分組列/逆列混合模塊，其中ed為模式選擇信號，ed=1時進行列混合變換，ed=0時進行逆列混合變換。

5.結論

本文提出了一種新穎的基于內容可尋址存儲器（CAM）的AES S/S-1盒的實現方法，將S盒與S-1盒的置換結合成一個查找表，可以同時應用于加密和解密運算，與RAM方式實現的S/S-1盒查找表相比，其復雜性顯著降低，面積大幅度減少。通過對列/逆列混合變換的化簡，在逆列混合變換中復用了列混合變換，使得AES的解密過程能夠充分利用加密的硬件資源，進一步地節約了芯片面積，降低了成本。

[1]“Advanced Encryption Standard (AES)”Federal Information Processing Standards Publication 197, Nov. 26, 2001.

[2]Hua Li.”A New CAM Based S/S-1-Box Look-up Table in AES”.Circuits and Systems.ISCAS 2005.IEEE International Symposium on.pp.4634-4636.Vol.05.2005.05

[3]陳俊，王晶，曾曉洋，韓軍.低復雜度先進密碼算法的VLSI實現[J]計算機工程.2007.33