AES算法中S-box和列混合單元的優(yōu)化

1 S-box的優(yōu)化設(shè)計(jì)

在AES標(biāo)準(zhǔn)算法中定義了兩個(gè)較大的列表。S-box和逆S-box。將S-box用于兩個(gè)應(yīng)用：字節(jié)替代和密鑰擴(kuò)展。而逆S-box則用于逆字節(jié)替代。這兩個(gè)列表是不相同的，因此必須建立兩個(gè)不同的ROM(256×8 b)，用以存儲(chǔ)這兩個(gè)列表。另外，在AES設(shè)計(jì)中使用平行結(jié)構(gòu)，這就需要用到多個(gè)列表，這樣會(huì)使硬件過于復(fù)雜，需要對(duì)其進(jìn)行優(yōu)化。以下主要對(duì)S-box模塊進(jìn)行結(jié)構(gòu)優(yōu)化。

1.1 S-box和逆S-box的組合

在一個(gè)高速128 b的AES設(shè)計(jì)中，一般需要總共20個(gè)S-box模塊和16個(gè)逆S-box模塊。其中，16個(gè)S-box模塊用于實(shí)現(xiàn)字節(jié)替代的功能，4個(gè)S-box用于實(shí)現(xiàn)密鑰擴(kuò)展的功能，而16個(gè)逆S-box模塊用于實(shí)現(xiàn)逆字節(jié)替代功能。在這種情形下，如果字節(jié)替代和逆字節(jié)替代時(shí)使用不同的列表，就會(huì)占用大量的硬件資源。所以非常需要一種減少硬件復(fù)雜性的方法。

就如AES標(biāo)準(zhǔn)所描述的那樣，S-box的操作過程可以表示為：



因?yàn)閙ultiplicative_inverse(乘法求逆)是一個(gè)相當(dāng)復(fù)雜的方程，最常用的實(shí)現(xiàn)S-box的方法是運(yùn)用look-up列表來由x得到y(tǒng)。等式(1)的逆等式如下：



因?yàn)閙ultiplicative_inverse^-1和multiplicative_inverse是相同的，所以等式(3)可以表述為：



最后，必須找到M^-1，即矩陣M的有限域逆矩陣。由有限域逆矩陣的運(yùn)算方法可知，可以計(jì)算出矩陣M的逆矩陣，命名為M’，如式(5)所示：



在式(1)和式(6)中，只使用了一個(gè)普通的look-up列表，從而將S-box和逆S-box集成，大大減少了字節(jié)替代和逆字節(jié)替代的硬件需求。圖1展示了集成的S-box／逆S-box模塊，可應(yīng)用于AES的加密和解密。



1.2 S-box單元中乘法求逆電路的優(yōu)化

由第1.1節(jié)可知，S-box盒的生成電路由加密仿射電路(實(shí)現(xiàn)out=(in+c)M^-1等式功能)，解密仿射電路(實(shí)現(xiàn)out=in·M+c等式功能)以及乘法求逆電路三個(gè)模塊組成。要減少組合邏輯的復(fù)雜度，需要對(duì)乘法求逆電路進(jìn)行優(yōu)化。下面說明求逆電路的優(yōu)化過程。

S-box硬件實(shí)現(xiàn)時(shí)的主要部件是乘法求逆。在有限域GF(2⁸)上，乘法求逆是一種相當(dāng)復(fù)雜的函數(shù)，直接在域GF(2⁸)上生成S-box盒，組合邏輯復(fù)雜度高，會(huì)使電路中邏輯電路的門數(shù)大大增加。根據(jù)有限域的性質(zhì)，利用域GF(2⁸)與GF[(2⁴)²]的同構(gòu)變換，把GF(2⁸)上的求逆轉(zhuǎn)化在GF[(2⁴)²]上的求逆運(yùn)算，從而生成S-box單元，可以降低邏輯關(guān)系運(yùn)算的復(fù)雜度，優(yōu)化S-box的面積。

所采用有限域GF(2⁸)上的乘法求逆電路模塊優(yōu)化過程如圖2所示。優(yōu)化的乘法求逆過程可表述如下：

(1)通過線性變換T將GF(2⁸)的輸入X映射到域GF(2⁴)上的元素b，c；

(2)構(gòu)建相應(yīng)的域GF(2⁴)的一次多項(xiàng)式，定義域GF(2⁴)上的加法、乘法和求逆運(yùn)算。利用域GF(2⁴)上的加法、乘法和求逆運(yùn)算，得到域GF(2⁴)上元素b，c的逆元素p，q；

(3)構(gòu)建線性變換T^-1，將域GF(2⁴)上的元素p，q映射到域GF(2⁸)上，得到域GF(2⁸)上的元素x的逆元素y=T^-1(p，q)。



由有限域的知識(shí)可知，復(fù)合域GF[(2⁴)²]中每個(gè)元素都可表示為系數(shù)在GF(2⁴)上的一次多項(xiàng)式bx+c。設(shè)定義有限域GF[(2⁴)²]的乘法的二次不可約多項(xiàng)式x²+Ax+B，可驗(yàn)證此時(shí)GF[(2⁴)²]中的任一元素bx+c的乘逆元素是：



式中：(b²B+bcA+c²)^-1是b²B+bcA+c²在GF(2⁴)上的乘法逆元。各部分的邏輯實(shí)現(xiàn)過程可描述如下：

(1)有限域GF(2⁸)到復(fù)合域GF[(2⁴)²]映射。通過GF(2⁸)上的即約多項(xiàng)式p(x)=x²+Ax+B構(gòu)造線性變換T，根據(jù)式(8)將GF(2⁸)的輸入x映射到GF(2⁴)上的元素b，c：



式中：B是GF(2⁴)上的常量元素；T是一個(gè)8×8的矩陣，矩陣的元素是0或1，T矩陣由B的取值決定；A取1，B取8；