劉松 夏樹村

該文提出一種有效的基于內(nèi)容可尋址存儲(chǔ)器（CAM）的S/S-1盒查找表的實(shí)現(xiàn)方法，可以應(yīng)用于AES的加密和解密運(yùn)算，與基于RAM的S/S-1盒查找表相比，其復(fù)雜性顯著降低。同時(shí)還提出一種關(guān)鍵路徑上只有5個(gè)異或門延遲的列/逆列混合復(fù)用的硬件結(jié)構(gòu),大大節(jié)省了芯片面積。

AES；內(nèi)容可尋址存儲(chǔ)器；S/S-1盒；列/逆列混合

1.引言

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

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

本文組織結(jié)構(gòu)如下：第2節(jié)簡要介紹AES算法；第3節(jié)重點(diǎn)介紹基于CAM的S/S-1盒查找表的體系結(jié)構(gòu)，并與單獨(dú)實(shí)現(xiàn)S盒與S-1盒查找表的方法進(jìn)行比較；第4節(jié)詳細(xì)介紹列/逆列混合的優(yōu)化設(shè)計(jì)；第5節(jié)總結(jié)全文。

2.AES算法

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

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

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

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

行移位變換就是加密時(shí)將一個(gè)狀態(tài)的第 行循環(huán)左移 個(gè)字節(jié)，解密時(shí)循環(huán)右移 個(gè)字節(jié)即為逆行移位變換。

列混合變換對(duì)一個(gè)狀態(tài)逐列進(jìn)行變換，它將一個(gè)狀態(tài)的每一列視為有限域GF(2^8)上的一個(gè)多項(xiàng)式且與一個(gè)固定多項(xiàng)式相乘。

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

圈密鑰加就是簡單地將一個(gè)圈子密鑰按位異或到一個(gè)狀態(tài)上。圈子密鑰按順序取自擴(kuò)展密鑰，擴(kuò)展密鑰由初始密鑰經(jīng)過擴(kuò)展后得到。

3.字節(jié)代替的優(yōu)化設(shè)計(jì)

內(nèi)容可尋址存儲(chǔ)器（CAM）具有固有的并行性，允許并行地存取和比較存儲(chǔ)器中的內(nèi)容。本節(jié)提出一種新穎的基于CAM的查找表來執(zhí)行S盒與S-1盒的查表操作。通過比較說明這種實(shí)現(xiàn)方法比使用兩個(gè)單獨(dú)的S盒與S-1盒查找表的復(fù)雜性顯著降低。

A.內(nèi)容可尋址存儲(chǔ)器（CAM）

內(nèi)容可尋址存儲(chǔ)器（CAM）[2]是一種并行模式的匹配電路，能同時(shí)搜索存儲(chǔ)器中的所有內(nèi)容，并返回匹配數(shù)值的存儲(chǔ)地址。CAM被視為一種并行處理器，用來加速實(shí)現(xiàn)圖像處理和數(shù)據(jù)庫搜索等應(yīng)用。

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

本文設(shè)計(jì)了一個(gè)8bit的CAM來實(shí)現(xiàn)S/S-1盒查找表。圖1所示為CAM單元第bit的邏輯電路。在查找內(nèi)容前，將匹配信號(hào)（match）復(fù)位為1。圖中，連接數(shù)據(jù)線連接數(shù)據(jù)線?？芍?，。如果，則那么匹配信號(hào)接地，即=0。否則那么=1。進(jìn)行寫操作時(shí)，地址線被激活，通過數(shù)據(jù)線，數(shù)據(jù)被寫入CAM單元中（數(shù)據(jù)被存儲(chǔ)在和中）。進(jìn)行讀操作時(shí)，選取相應(yīng)的地址線，通過數(shù)據(jù)線獲得存儲(chǔ)器中的內(nèi)容。

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

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

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

圖2為本文提出的基于CAM的S/S-1盒查找表的體系結(jié)構(gòu)。在圖2中，有一個(gè)8bit的比較寄存器，用來存儲(chǔ)被比較的數(shù)據(jù)，通過數(shù)據(jù)線與CAM相連。我們注意到，被比較的數(shù)據(jù)被連接到數(shù)據(jù)線時(shí)是取反的，這是由于CAM單元的邏輯結(jié)構(gòu)所致。如果數(shù)據(jù)與CAM中的相匹配，相應(yīng)的匹配信號(hào)變?yōu)?，匹配標(biāo)記（match flag）被標(biāo)注。CAM的相應(yīng)地址線可以通過地址譯碼器來獲得，返回一個(gè)8bit的地址值。

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

表1不同的查找表實(shí)現(xiàn)方式的資源比較

4.列/逆列混合的優(yōu)化設(shè)計(jì)

AES中定義了x乘,即用x乘以一個(gè)多項(xiàng)式，可以用字節(jié)內(nèi)左移一位和緊接著的一個(gè)與“1b”的按位異或來實(shí)現(xiàn)，記為。

可將上式統(tǒng)一表示為：

的電路結(jié)構(gòu)如圖3所示。

利用，對(duì)加密的列混合變換進(jìn)行化簡：

顯然，化簡后的列混合變換的關(guān)鍵路徑僅為3個(gè)異或門延遲。

對(duì)解密的逆列混合變換來說，我們設(shè)計(jì)了和兩個(gè)模塊[3]，分別為：

的電路結(jié)構(gòu)分別如圖4、5所示，均為2個(gè)異或門延遲。

圖4結(jié)構(gòu)圖圖5結(jié)構(gòu)圖

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

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

如上提出的結(jié)構(gòu)只是完成字節(jié)的列/逆列混合變換，要實(shí)現(xiàn)整個(gè)列/逆列混合變換，首先要集成4個(gè)字節(jié)列/逆混合模塊，組成一個(gè)新的字列/逆列混合模塊，如圖7所示。然后再集成4個(gè)字列/逆列混合模塊，組成一個(gè)128bit的分組列/逆列混合模塊。圖8即為并行分組列/逆列混合模塊，其中ed為模式選擇信號(hào)，ed=1時(shí)進(jìn)行列混合變換，ed=0時(shí)進(jìn)行逆列混合變換。

5.結(jié)論

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

[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]陳俊，王晶，曾曉洋，韓軍.低復(fù)雜度先進(jìn)密碼算法的VLSI實(shí)現(xiàn)[J]計(jì)算機(jī)工程.2007.33