AES算法中S-box和列混合單元的優(yōu)化及FPGA實(shí)現(xiàn)

　　美國國家標(biāo)準(zhǔn)與技術(shù)局(National Institute of Standard and Technology，NIST)于1997年1月提出發(fā)展AES(Advanced Encryption Standard)加密算法，并于同年9月12日推出AES的早期基本算法。在研究了一系列早期算法之后，Rijndael算法被確定為先進(jìn)加密標(biāo)準(zhǔn)(Advanced Encryption Standard，AES)。由于其較高的保密級(jí)別，AES算法被用來替代DES和3-DES，以適應(yīng)更為嚴(yán)苛的數(shù)據(jù)加密需要。

　　與此同時(shí)，市場(chǎng)迫切需要AES的FPGA和ASIC的硬件解決方案，因?yàn)槠渑c用軟件實(shí)現(xiàn)相比更安全而且更省電。在一些應(yīng)用，如：信用卡，手機(jī)，PDA等中，硬件的復(fù)雜度是影響成本和能耗的一個(gè)非常重要的因素。因此，在加密和解密中都非常需要優(yōu)化AES的主要操作部分。在AES算法中，S-box是惟一的非線性單元，在加密解密，特別是字節(jié)替代和逆字節(jié)替代操作時(shí)需要分別執(zhí)行S-box和逆S-box。建立一個(gè)16×16的S-box，以往通常采用查找表的方式實(shí)現(xiàn)，占用大量硬件資源。因此，對(duì)S-box進(jìn)行優(yōu)化是實(shí)現(xiàn)高效AES的重要步驟。

　　在此首先通過在S-box和逆S-box中共用一個(gè)look-up列表，簡(jiǎn)化非線性單元的復(fù)雜度，然后通過選擇合適的即約多項(xiàng)式，進(jìn)行域GF(28)到GF(24)的同構(gòu)映射，對(duì)S-box的算法進(jìn)行優(yōu)化，并采用組合邏輯電路實(shí)現(xiàn)，使優(yōu)化后的S-box在同等頻率條件下較顯著地減少了硬件資源的消耗。同時(shí)介紹了一種減小列混合(MixColumn)單元硬件復(fù)雜度的方案，可以明顯地減少列混合單元的設(shè)計(jì)面積。

　　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)可以表述為：