基于A結(jié)E構(gòu)S 共享和多級(jí)流水線的加密算法的研究

王 群

（青島科技大學(xué)信息學(xué)院 山東 青島 266061）

2000年10月，美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)局（NIST）選擇了兩位比利時(shí)研究者Daemen和Rijmen提出的Rijndael算法，即AES（高級(jí)加密標(biāo)準(zhǔn)）。它具有128bits的分組長(zhǎng)度，三種可選的密鑰長(zhǎng)度，即128bits、196bits和 256bits。

AES可以抵抗所有設(shè)計(jì)中已知的攻擊方法，具有較高的安全強(qiáng)度。文中闡述了AES算法的原理，并對(duì)其加解密模塊進(jìn)行優(yōu)化，提出了一種基于結(jié)構(gòu)共享和多級(jí)流水線的AES算法實(shí)現(xiàn)方案，并重點(diǎn)闡述了實(shí)現(xiàn)過(guò)程。

1 AES算法介紹

AES算法是一種迭代分組算法，采用128bits的分組長(zhǎng)度，三種可選密鑰長(zhǎng)度128bits，192bits和256bits。對(duì)于不同的密鑰長(zhǎng)度，所需的加解密輪數(shù)不同。本文主要討論分組長(zhǎng)度和密鑰長(zhǎng)度128bits的情況。

整個(gè)加密過(guò)程包括11輪迭代。其中Round0只有Add Round Key操作。Round1-Round9具有完全相同的操作， 依次經(jīng)過(guò) SubBytes、Shift Rows、Mix Columns和Add Round Key四種操作。Round10只包括 SubBytes、Shift Rows和 Add Round Key 三種操作。解密過(guò)程是加密過(guò)程的逆過(guò)程。關(guān)于AES算法的詳細(xì)描述見(jiàn)參考文獻(xiàn)[1]。

2 加解密模塊的結(jié)構(gòu)共享

2.1 字節(jié)變換（SubBytes）

當(dāng)前實(shí)現(xiàn)字節(jié)變化的方法有兩種：一是有限域運(yùn)算的方法；一是查找表的方法。前者運(yùn)算復(fù)雜，后者容易實(shí)現(xiàn)，并且運(yùn)行速度更快，但是硬件開(kāi)銷較大?？紤]到可以利用FPGA自帶的Block RAM資源，在設(shè)計(jì)中采用了查找表的實(shí)現(xiàn)方式。

如果將用于加密的Sbox表和用于解密的Inverse Sbox表同時(shí)存放在FPGA的Block RAM中，會(huì)造成RAM資源的大量消耗。為降低硬件資源的消耗，設(shè)計(jì)中采用重新配置的方法。加密時(shí)一次性加載16個(gè)Sbox表，而在解密時(shí)，對(duì)存放這些Sbox表的RAM重新寫(xiě)入Inverse Sbox表的數(shù)據(jù)。

2.2 行移位（Shift Rows）

本文采用128bits并行算法，行移位變換可按照移位的方向和字節(jié)數(shù)連線，幾乎不占用硬件資源和產(chǎn)生延時(shí)，然后通過(guò)選通器選擇正向或逆向行移位變換。

2.3 列混合（Mix Columns）/逆列混合（InvMix Columns）

根據(jù)算法原理，列混合變換就是輸入狀態(tài)矩陣與一個(gè)系數(shù)矩陣相乘。

列混合變換表示為：

逆列混合變換表示為：

逆列混合變換的系數(shù)矩陣與列混合變換的系數(shù)矩陣存在如下關(guān)系：

因此，在實(shí)現(xiàn)逆列混合變換時(shí)，只需在列混合變換之前先執(zhí)行個(gè)邏輯電路。將列混合變換和逆列混合變換進(jìn)行整合，使得列混合電路可以復(fù)用于解密過(guò)程中，并由選擇器來(lái)實(shí)現(xiàn)加密/解密操作，實(shí)現(xiàn)了硬件資源的共享。

3 流水線結(jié)構(gòu)的設(shè)計(jì)

3.1 AES算法實(shí)現(xiàn)流水線的可行性

第一，AES算法加解密過(guò)程的核心是10次輪操作，前一輪操作的輸出即為下一輪操作的輸入。第二，AES算法每次對(duì)一個(gè)128bits的數(shù)據(jù)塊進(jìn)行編碼，當(dāng)采用ECB工作模式時(shí)，前后進(jìn)行編碼的數(shù)據(jù)塊間不存在相關(guān)性。由于上述特點(diǎn)，AES算法完全能夠以流水線的形式實(shí)現(xiàn)。

3.2 兩類典型的流水線結(jié)構(gòu)

AES算法的流水線結(jié)構(gòu)分為輪內(nèi)流水線結(jié)構(gòu)和輪間流水線結(jié)構(gòu)兩種。輪內(nèi)流水線結(jié)構(gòu)就是把在一個(gè)時(shí)鐘周期內(nèi)欲完成的運(yùn)算劃分為若干子運(yùn)算，采用寄存器輸出模式。輪間流水線結(jié)構(gòu)就是在相鄰的兩輪加解密模塊之間加入寄存器，每個(gè)時(shí)鐘周期各加解密模塊都有一次輸出，從而實(shí)現(xiàn)輪間流水線設(shè)計(jì)。

輪內(nèi)流水線結(jié)構(gòu)被很多人討論并使用，這種結(jié)構(gòu)既可縮短延時(shí)路徑，提高時(shí)鐘頻率，又可使各子運(yùn)算同時(shí)進(jìn)行。但是這種結(jié)構(gòu)增加了控制的復(fù)雜度同時(shí)占用大量的存儲(chǔ)單元，對(duì)于FPGA實(shí)現(xiàn)來(lái)說(shuō)將是很大的負(fù)擔(dān)。另一方面，這種結(jié)構(gòu)雖然能提高仿真頻率，但是系統(tǒng)吞吐量并沒(méi)有明顯的提高。因此，本設(shè)計(jì)采用輪間流水線結(jié)構(gòu)。

3.3 AES算法的5級(jí)流水線設(shè)計(jì)

傳統(tǒng)的AES算法流水線為10級(jí)流水線結(jié)構(gòu)或2級(jí)流水線結(jié)構(gòu)。這兩種設(shè)計(jì)結(jié)構(gòu)都存在弊端。10級(jí)流水線結(jié)構(gòu)能夠最大限度的利用流水線技術(shù)，提高系統(tǒng)的運(yùn)行速度，但是要耗用大量FPGA的邏輯單元和存儲(chǔ)單元；而2級(jí)流水線結(jié)構(gòu)設(shè)計(jì)，雖然占用FPGA資源較少，但是沒(méi)有有效的利用好流水線技術(shù)。本文提出的5級(jí)流水線結(jié)構(gòu)是上述兩種設(shè)計(jì)結(jié)構(gòu)的折中方案，能夠最大限度的利用FPGA資源來(lái)實(shí)現(xiàn)流水線設(shè)計(jì)，從而提高系統(tǒng)運(yùn)行速度。

具體實(shí)現(xiàn)為將原來(lái)的0-10輪循環(huán)迭代結(jié)構(gòu)進(jìn)行分解。第0輪只是實(shí)現(xiàn)了Add Round Key操作，可以使用單獨(dú)的“異或電路”加以實(shí)現(xiàn)。將剩下的1-10輪通過(guò)2輪一組，組內(nèi)循環(huán)的方式設(shè)計(jì)為5級(jí)流水線結(jié)構(gòu)。如圖1所示。

圖1 AES算法5級(jí)流水線結(jié)構(gòu)

由于1-9輪的運(yùn)算模式與第10輪存在不同，因此將第9輪和第10輪作為一組在控制上要使用不同的控制信號(hào)。通過(guò)狀態(tài)機(jī)來(lái)對(duì)兩輪的控制信號(hào)賦不同的值。而1-8輪的的運(yùn)算模式是相同的，即其控制信號(hào)也是相同的。因此前4組流水線可以使用一組固定的控制值。

本設(shè)計(jì)是組內(nèi)循環(huán)與輪間流水相結(jié)合的模式，必須要解決好輸入的問(wèn)題，即要協(xié)調(diào)好來(lái)自上一級(jí)流水線的輸入數(shù)據(jù)與本級(jí)流水線循環(huán)反饋的數(shù)據(jù)，使系統(tǒng)正常工作。這里通過(guò)設(shè)計(jì)一個(gè)2選1（MUX2_1）選擇器來(lái)實(shí)現(xiàn)。選擇器的使能信號(hào)也是由狀態(tài)機(jī)來(lái)實(shí)現(xiàn)。

輪密鑰的匹配輸入問(wèn)題。由于每級(jí)流水線包括兩次加/解密的運(yùn)算，而每次加/解密運(yùn)算所需的輪密鑰各不相同。要實(shí)現(xiàn)此操作就必須為每級(jí)流水線設(shè)置一個(gè)寄存器堆。寄存器堆中存放兩次加/解密運(yùn)算所需的不同輪密鑰。對(duì)輪密鑰的選擇也是由狀態(tài)機(jī)來(lái)實(shí)現(xiàn)。

4 結(jié)束語(yǔ)

本文提出了一種基于結(jié)構(gòu)共享和多級(jí)流水線的AES算法實(shí)現(xiàn)方案。字節(jié)變換采用可重構(gòu)設(shè)計(jì)，用同一組RAM資源在加解密時(shí)，分別加載Sbox表數(shù)據(jù)和Inverse Sbox表數(shù)據(jù)，節(jié)約了RAM資源。通過(guò)在列混合變換之前執(zhí)行個(gè)邏輯電路（PreInvmix），來(lái)實(shí)現(xiàn)逆列混合變換。從而實(shí)現(xiàn)了逆列混合變換與列混合變換的結(jié)構(gòu)共享。采用5級(jí)流水線結(jié)構(gòu)設(shè)計(jì)，實(shí)現(xiàn)了芯片面積的節(jié)省和系統(tǒng)工作頻率的提高。

［1］Federal Information Processing Standard (FIPS)for the Advanced Encryption Standard[J].FIPS-197.November 26,2001.

［2］武玉華，李艷俊，周玉坤.基于FPGA的AES_128密碼算法實(shí)現(xiàn)研究[J].微計(jì)算機(jī)信息，2007（2）.

［3］李雪梅，路而紅，歐海文.AES算法的快速硬件設(shè)計(jì)與實(shí)現(xiàn)[J].電子技術(shù)應(yīng)用，2006（5）.

［4］吳曉成，高琳.AES IP Core的一種高速流水線實(shí)現(xiàn)方法[C].西安電子科技大學(xué)學(xué)術(shù)年會(huì)，2007.