分組密碼算法矩陣乘法運算的設(shè)計原理

張學(xué)潤, 徐向紅, 張學(xué)穎

(1. 吉林大學(xué) 農(nóng)學(xué)部公共教學(xué)中心, 長春 130061; 2. 解放軍第230醫(yī)院 信息科, 遼寧 丹東 118000)

密碼算法在軍事、 商業(yè)等領(lǐng)域應(yīng)用廣泛. 目前, 對密碼算法可重構(gòu)運算架構(gòu)的研究已取得許多成果[1-3]. 考慮到硬件實現(xiàn)密碼算法在速度上的優(yōu)勢及在電路面積、 靈活性方面的限制等因素, 要從根本上提高運算電路的實現(xiàn)性能, 必須對密碼算法中的運算進行適當(dāng)?shù)淖儞Q, 使其更適合在密碼算法可重構(gòu)運算電路中運行.

本文結(jié)合分組密碼算法中矩陣乘法運算的操作特點, 基于比特并行有限域乘法運算方法, 提出全比特并行有限域乘法運算的實現(xiàn)原理； 并利用有限域運算法則, 提出適合分組密碼算法中矩陣乘法運算的實現(xiàn)原理. 電路模擬結(jié)果顯示, 據(jù)此原理設(shè)計的電路可靈活、 高效地實現(xiàn)不同算法中的矩陣乘法運算, 進而證明了本文設(shè)計原理的高可用性.

1 矩陣乘法特征分析

分組密碼算法中的矩陣乘法運算就是利用算法給定的乘數(shù)矩陣與算法運行過程中的狀態(tài)矩陣在某個有限域中進行乘法運算, 得到新的狀態(tài)矩陣. 表1列出了分組密碼算法中矩陣乘法的操作特征. 由表1可見, 分組密碼算法為提高矩陣乘法的運算速度, 選取維度較小的有限域乘法作為基本運算單元； 同時為使矩陣乘法運算操作數(shù)據(jù)位寬與密碼算法處理數(shù)據(jù)位寬相匹配, 通常設(shè)計維數(shù)較大的矩陣乘法運算或多個矩陣乘法運算模塊并行運行.

表1 分組密碼算法中矩陣乘法的特征Table 1 Characters of matrix multiplicative of block ciphers

2 設(shè)計原理

由于不同對稱密碼算法中矩陣乘法運算的差別主要體現(xiàn)在基本乘法運算所在有限域的生成多項式不同、 乘法矩陣的維數(shù)不同兩方面, 因此, 矩陣乘法器的實現(xiàn)原理也應(yīng)從上述兩方面考慮.

2.1 全比特并行乘法運算單元

對于維度為k的二元擴域GF(2k), 域多項式f(x)可表示為

f(x)=xk+fk-1xk-1+fk-2xk-2+…+f1x+f0,fi=0,1,i∈[k-1,0];

域中元素：

乘積為

c(α)=a(α)?b(α)modf(α)=ck-1αk-1+ck-2αk-2+…+c1α+c0.

結(jié)合有限域乘法運算原理, 計算a(α),b(α)的乘積c(α)可分為3步完成：

3) 在基域GF(2)中計算乘積項c(α)的系數(shù)值.

可見, 二元擴域上的有限域乘法運算均為在二元域上的比特級運算, 可利用簡單的“與-異或”電路實現(xiàn)； 運算過程中所需的2k-2次乘積項c′(α)的系數(shù), 可通過密碼算法中給出的有限域生成多項式f(x)運算得出.

2.2 2k-2次乘積項系數(shù)的運算

對于二元擴域GF(2k)中元素αk+1的坐標(biāo)可通過元素αk的坐標(biāo)經(jīng)過移位、 異或運算得到[4-5], 即

(1)

依次類推, 有限域乘法運算單元中所需的2k-2次乘積項c′(α)的系數(shù)均可由初始信息conk計算得出：

即

conk+i=(conk+i-1?1)+conk+i-1[k-1]·conk,i∈[2k-2,k+1].

(2)

由式(2)可見, 對于二元擴域全有限域乘法運算單元, 只需將域多項式f(x)的系數(shù)作為初始值conk, 按上述原理依次生成2k-2次乘積項c′(α)的k-2項系數(shù). 因此, 2k-2次乘積項c′(α)系數(shù)的運算同樣可由“與-異或”電路實現(xiàn).

2.3 矩陣乘法運算單元設(shè)計原理

?lu-1+…+tu-1,1?l1+tu-1,0?l0.

(3)

a×bmodf(x)+c×dmodf(x)=(a×b+c×d)modf(x).

(4)

由于對稱密碼算法同一矩陣乘法中的乘法運算都對應(yīng)于同一有限域, 因此可利用式(4)給出的有限域運算性質(zhì)對式(3)進行如下化簡：

即對于參與乘積向量元素計算的u個有限域乘法運算, 先對u個多項式乘法運算結(jié)果分別進行域多項式約減后再將運算結(jié)果相異或運算, 與先將u個多項式乘法運算結(jié)果異或運算后再進行域多項式約減的計算結(jié)果相同. 基于此, 優(yōu)化設(shè)計矩陣乘法運算電路將極大提升其實現(xiàn)性能.

2.4 矩陣乘法運算單元

由表1可知, 不同對稱密碼算法中矩陣乘法所在有限域的生成多項式各不相同, 生成多項式的系數(shù)也不同, 但運算原理一致, 都是利用有限域生成多項式對域中元素坐標(biāo)進行變換, 得到運算結(jié)果. 矩陣乘法運算電路的結(jié)構(gòu)框圖如圖1所示.

圖1 矩陣乘法運算單元框圖Fig.1 Architecture for matrix multiplicative

圖1中: 2k-2次多項式系數(shù)運算電路用于計算多項式約減時所需的系數(shù)； 虛線框標(biāo)識為一個乘積元素運算單元, 用于計算有限域維度較小的乘法運算； 多個乘積元素運算單元通過異或網(wǎng)絡(luò)計算出乘積向量的一個元素, 并可同時計算多個相同維度的有限域乘法運算. 利用本文給出的原理設(shè)計的運算電路可實現(xiàn)表1中所列的分組密碼算法中的矩陣乘法運算.

3 結(jié)果與討論

將上述電路結(jié)構(gòu)利用計算機進行模擬, 并將其實現(xiàn)性能與文獻中已有方案進行對比, 結(jié)果見圖2.

圖2 幾種不同設(shè)計方案的性能比較Fig.2 Performance comparison of matrix multiplicative with other designs

由圖2可見: 文獻[6]中給出的并行實現(xiàn)方式, 電路面積和運算延遲最小, 只能實現(xiàn)一種算法中的矩陣乘法運算, 利用率不高； 文獻[7]利用MSB算法設(shè)計的串行乘法運算單元, 電路延遲較大, 不能滿足密碼算法處理性能的要求； 文獻[8]在文獻[7]的基礎(chǔ)上進行設(shè)計, 在減少電路延遲的同時面積增加較多, 但整體運算速度與本文的設(shè)計方案相比較慢. 同時, 文獻[7-8]中的有限域乘法運算, 將對域多項式系數(shù)和操作數(shù)坐標(biāo)的運算同時進行, 應(yīng)用在矩陣乘法運算電路中時, 無法實現(xiàn)有限域乘法運算間的優(yōu)化, 雖采用了串行實現(xiàn)方式, 但其電路面積仍比本文提出的設(shè)計方案架構(gòu)大.

[1] QU Ying-jie. Concept and Design Principle of Reconfigurable Cipher Coprocessor [J]. Computer Engineering and Applications, 2003(12): 7-9. (曲英杰. 可重構(gòu)密碼協(xié)處理器的概念及其設(shè)計原理 [J]. 計算機工程與應(yīng)用, 2003(12): 7-9.)

[2] YANG Xiao-hui. The Research of Reconfigurable Computing Targeted at Block Cipher Processing [D]: [Master’s Degree Thesis]. Zhengzhou: PLA Information Engineering University, 2007. (楊曉輝. 面向分組密碼處理的可重構(gòu)設(shè)計技術(shù)研究 [D]: [碩士學(xué)位論文]. 鄭州: 解放軍信息工程大學(xué), 2007.)

[3] LIU Ting-ting. Research on the Structure and Special Instruction-Set of a Reconfigurable Stream Cipher Processing System [D]: [Master’s Degree Thesis]. Zhengzhou: PLA Information Engineering University, 2009. (劉婷婷. 序列密碼可重構(gòu)處理系統(tǒng)結(jié)構(gòu)及專用指令集研究 [D]: [碩士學(xué)位論文]. 鄭州: 解放軍信息工程大學(xué), 2009.)

[4] Berk S, Saras E, Koc C K, et al. Constructing Composite Field Representations for Efficient Conversion [J]. IEEE Transactions on Computers, 2003, 52(11): 1391-1398.

[5] HAN Yong-fei, Leong P C, TAN Peng-chong, et al. Fast Algorithms for Elliptic Curve Cryptosystems over Binary Finite Field in Cryptology [C]//ASLACRYPT’99 Proceedings of the International Conference on the Theory and Applications of Cryptology and Information. London: Springer-Verlag, 1999: 75-85.

[6] Reyhani-Masoleh A, Hasan M A. Low Complexity Bit Parallel Architectures for Polynomial Basis Multiplication overGF(2m)[J]. IEEE Transactions on Computers, 2004, 53(8): 945-959.

[7] Kitsos P, Theodoridis G, Koufopavlou O. An Efficient Reconfigurable Multiplier Architecture for Galois Field [J]. Microelectronics, 2003, 34(1): 975-980.

[8] YUAN Dan-shou, RONG Meng-tian. Reconfigurable and Fast Finite Field Multiplier Architecture [J]. Journal of Eleetronies & Information Technology, 2006, 28(4): 717-720. (袁丹壽, 戎蒙恬. 一種可重構(gòu)的快速有限域乘法結(jié)構(gòu) [J]. 電子與信息學(xué)報, 2006, 28(4): 717-720.)