張宇鵬, 高 瑩,2, 嚴(yán) 宇, 劉 翔

1. 北京航空航天大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院, 北京 100191

2. 空天網(wǎng)絡(luò)安全工業(yè)和信息化部重點(diǎn)實(shí)驗(yàn)室, 北京 100191

1 引言

ZUC 算法(即ZUC-128 序列密碼算法) 是我國(guó)自主設(shè)計(jì)的密碼算法, 也是我國(guó)第一個(gè)成為國(guó)際商業(yè)密碼標(biāo)準(zhǔn)的國(guó)產(chǎn)密碼算法. 2011 年9 月, 在第三代合作伙伴計(jì)劃(3GPP) 組織的第53 次會(huì)議上, 基于ZUC 密碼算法的數(shù)據(jù)加密算法EEA3 和認(rèn)證算法EIA3 成為3GPP LTE 標(biāo)準(zhǔn)[1]. 2020 年4 月, 在國(guó)際標(biāo)準(zhǔn)化組織ISO 的工作組會(huì)議上, ZUC 算法成為ISO/IEC 國(guó)際標(biāo)準(zhǔn)[2], 進(jìn)入標(biāo)準(zhǔn)發(fā)布階段. ZUC 算法是我國(guó)商用密碼的重要組成部分, 主要用于通信領(lǐng)域的數(shù)據(jù)機(jī)密性和完整性保護(hù)工作. 2018 年, 為了適應(yīng)5G 通信的需求, ZUC 算法研制組研制了“ZUC-256 流密碼算法”, 從128 比特密鑰升級(jí)到256 比特密鑰,升級(jí)版的算法與ZUC-128 算法高度兼容, 可提供消息加密和認(rèn)證[3].

在優(yōu)化ZUC 算法實(shí)現(xiàn)、提高工作效率方面,國(guó)內(nèi)外學(xué)者已經(jīng)在軟件和硬件方面做出了很多嘗試. 總體來(lái)說(shuō), 在ZUC 算法的硬件實(shí)現(xiàn)方面取得的速度令人滿意, Zhang 等人[4]使用一種新的展開(kāi)架構(gòu)將ZUC算法在ASIC 上的實(shí)現(xiàn)速度提高到100 Gbps. 但是, 由于ZUC 算法的設(shè)計(jì)結(jié)構(gòu)所限, ZUC 算法在軟件實(shí)現(xiàn)速度遠(yuǎn)遠(yuǎn)不如硬件速度. 在ZUC 算法標(biāo)準(zhǔn)報(bào)告[5]中, 提到了一種利用移位和與運(yùn)算實(shí)現(xiàn)模231?1的加法和乘法的快速運(yùn)算方法. Avanzi 等人[6]提出用延遲取模的方法提高LFSR 的實(shí)現(xiàn)效率. 李建鵬等人[7]使用優(yōu)化函數(shù)調(diào)用過(guò)程和優(yōu)化執(zhí)行過(guò)程的方法, 減少了訪存時(shí)的沖突, 并減少了運(yùn)行時(shí)取模運(yùn)算的次數(shù). Yu 等人[8]使用延遲取模、滑動(dòng)窗口和將S 盒合并的方式, 結(jié)合使用SIMD 指令集, 將ZUC 算法的軟件實(shí)現(xiàn)速度提高到3.34 Gbps. Drucker 等人[9]利用了S 盒和AES 密碼中的S 盒的同構(gòu), 將S 盒的查表改為利用AES 擴(kuò)展指令進(jìn)行運(yùn)算, 將S 盒運(yùn)算變成恒定時(shí)間完成.

本文在前人工作的基礎(chǔ)上, 綜合利用已有的軟件優(yōu)化方法, 提出了一種ZUC 算法的軟件實(shí)現(xiàn)的高效組合方法. 我們嘗試過(guò)的主要方法有: (1) 優(yōu)化函數(shù)的調(diào)用過(guò)程; (2) 編譯器優(yōu)化技術(shù); (3) 使用延遲取模的方式減少取模次數(shù); (4) 通過(guò)合并S 盒的方式減少訪存次數(shù); (5) 利用SIMD 指令集實(shí)現(xiàn)LFSR 的多輪計(jì)算; (6) 將算法分兩個(gè)線程運(yùn)行; (7) 使用循環(huán)數(shù)組的方式優(yōu)化LFSR 的移位操作; (8) 使用查表的方式實(shí)現(xiàn)了線性變換L.

通過(guò)分析觀察發(fā)現(xiàn), 這些方法中, 有些方法只在理論中有效, 但是實(shí)際使用的過(guò)程中, 并不能減少軟件的運(yùn)行時(shí)間; 有些方法單獨(dú)使用時(shí)可以提高效率, 但是當(dāng)同其它的優(yōu)化方式共同使用的時(shí)候, 其反而會(huì)起到反作用. 我們通過(guò)嘗試組合不同的優(yōu)化方式, 得到了一種比較高效的軟件優(yōu)化組合方法, 在Intel Core i7-8750H@2.20 GHz 處理器上, 生成長(zhǎng)密鑰流時(shí), 軟件運(yùn)行速度可以達(dá)到4.22 Gbps. 和已有的最新結(jié)果3.34 Gbps 相比速度提高26%. 將該組合方法應(yīng)用到ZUC-256 密碼算法時(shí), 密鑰流產(chǎn)生速度可達(dá)到4.19 Gbps.

綜上所述, 本文的主要貢獻(xiàn)如下:

(1) 提出了一種高效的軟件實(shí)現(xiàn)優(yōu)化組合方式, 使得ZUC 算法的軟件實(shí)現(xiàn)速度達(dá)到4.22 Gbps. 和已有的最新結(jié)果3.34 Gbps 相比速度提高26%.

(2) 本方法可以完全應(yīng)用于ZUC-256 算法的軟件快速實(shí)現(xiàn). 使用該方法優(yōu)化ZUC-256 算法, 密鑰流產(chǎn)生速度可以達(dá)到4.19 Gbps.

2 ZUC 算法描述

2.1 ZUC 算法結(jié)構(gòu)

ZUC 算法邏輯上分為三層. 上層是16 級(jí)線性反饋移位寄存器, 包含16 個(gè)31 比特寄存器變量. 中層為比特重組. 下層為非線性函數(shù)F. ZUC 算法的結(jié)構(gòu)圖如圖1 所示.

圖1 ZUC 算法結(jié)構(gòu)圖Figure 1 ZUC algorithm structure chart

ZUC 算法以128 比特的初始密鑰k和128 比特的初始向量iv 作為輸入, 在密鑰字輸出階段, 每運(yùn)行一個(gè)節(jié)拍, 依次調(diào)用比特重組、F函數(shù)、LFSR 工作模式, 并產(chǎn)生一個(gè)32 比特的密鑰字Z.

2.2 線性反饋移位寄存器(LFSR)

LFSR 有2 種運(yùn)行模式: 初始化模式和工作模式. LFSR 在初始化模式下接收一個(gè)31 比特字u,u是由非線性函數(shù)F的32 比特輸出W通過(guò)舍棄最低位比特得到, 即u=W ?1. LFSR 的初始化模式計(jì)算過(guò)程如下:

2.3 比特重組

比特重組從LFSR 的寄存器單元中抽取128 比特組成4 個(gè)32 比特字X0,X1,X2,X3. 比特重組的計(jì)算過(guò)程如下:

其中下標(biāo)H和L分別表示高16 比特和低16 比特.

2.4 非線性函數(shù)F

F包含2 個(gè)32 比特的記憶單元變量R1和R2.F的輸入為3 個(gè)32 比特字X0,X1,X2, 輸出為一個(gè)32 比特字W, 計(jì)算過(guò)程如下:

其中S為32 比特的S 盒變換,由4 個(gè)小的8×8 的S 盒并置而成,即(S0,S1,S2,S3),其中S0=S2,S1=S3.L1和L2為32 比特線性變換, 定義如下:

其中?為循環(huán)左移.

3 優(yōu)化方法

3.1 調(diào)用優(yōu)化

3.1.1 使用inline 函數(shù)的方式優(yōu)化函數(shù)調(diào)用

在ZUC 算法的密鑰輸出階段, 每運(yùn)行一個(gè)節(jié)拍, 需要依次調(diào)用比特重組、F函數(shù)、LFSR 工作模式這3 個(gè)函數(shù), 并產(chǎn)生一個(gè)32 比特的密鑰字. 頻繁的函數(shù)調(diào)用會(huì)大量消耗?？臻g. 為了避免函數(shù)調(diào)用過(guò)程中額外的開(kāi)銷, 可以在函數(shù)定義前加上inline, 使其成為內(nèi)聯(lián)函數(shù), 函數(shù)的代碼被放入符號(hào)表中, 可以解決頻繁調(diào)用的函數(shù)大量消耗棧空間的問(wèn)題, 使程序運(yùn)行速度得到明顯提升.

3.1.2 使用宏定義的方式優(yōu)化函數(shù)調(diào)用

與使用inline 一樣, 使用宏定義函數(shù)可以使函數(shù)在程序中直接被替換, 而這一切使用預(yù)處理器實(shí)現(xiàn),沒(méi)有了參數(shù)壓棧、代碼生成等一系列的操作. 因此實(shí)現(xiàn)效率高, 速度提升很明顯.

3.1.3 使用寄存器優(yōu)化程序訪存

對(duì)于函數(shù)中頻繁使用的變量, 可以定義為寄存器變量, 即將其存儲(chǔ)在寄存器中, 省去了內(nèi)存與CPU 的數(shù)據(jù)交換過(guò)程, 使取值速度得到提高. 但是由于寄存器有限, 并不是所有變量都能定義為寄存器變量.

3.2 編譯優(yōu)化

3.2.1 提高編譯器自動(dòng)優(yōu)化等級(jí)的方式優(yōu)化程序運(yùn)行

使用gcc 進(jìn)行編譯, 優(yōu)化等級(jí)選擇O3. 在該等級(jí)下, 編譯器會(huì)對(duì)代碼的分支、表達(dá)式、常量來(lái)進(jìn)行優(yōu)化, 加入寄存器的使用, 同時(shí)還會(huì)進(jìn)行分支預(yù)測(cè): 對(duì)循環(huán)每一層的預(yù)測(cè), 以便于將循環(huán)拆分, 可以提高執(zhí)行效率. 編譯器還會(huì)試圖用已有的值來(lái)代替未知的值, 并且還會(huì)用加代替乘(因?yàn)檫\(yùn)算器的特性, 乘法十分復(fù)雜耗時(shí)). 在該命令下, 程序運(yùn)行速度得到極大提升.

3.2.2 使用編譯器對(duì)于Core i7 處理器的本地運(yùn)行性能進(jìn)行優(yōu)化

使用gcc 進(jìn)行編譯時(shí)加入-march=native 命令, 在編譯程序時(shí), 借助參數(shù)傳遞的方法, 使用與系統(tǒng)CPU 相匹配的gcc 參數(shù), 編譯出的程序就是為系統(tǒng)CPU 而進(jìn)行特定優(yōu)化過(guò)的, 因而執(zhí)行速度和效率都會(huì)是最好. 該方法在優(yōu)化等級(jí)O3 的基礎(chǔ)上, 使程序速度進(jìn)一步提升.

3.2.3 使用編譯器展開(kāi)循環(huán)的方式進(jìn)行優(yōu)化

程序中存在大量的循環(huán), 因此在使用gcc 編譯時(shí)加入-funroll-loops 命令, 對(duì)程序中的循環(huán)進(jìn)行展開(kāi).這樣做一是減少了對(duì)循環(huán)沒(méi)有直接貢獻(xiàn)的計(jì)算, 比如循環(huán)計(jì)數(shù)變量的計(jì)算, 分支跳轉(zhuǎn)指令的執(zhí)行等; 二是提供了進(jìn)一步利用機(jī)器特性進(jìn)行的優(yōu)化的機(jī)會(huì).

3.3 延遲取模

LFSR 的工作模式中, 新的s16計(jì)算方式如下式所示:

為了防止中間結(jié)果的溢出, 上式總共進(jìn)行了5 次模乘和5 次模加. ZUC 算法官方文檔給出了模加和模乘的快速實(shí)現(xiàn)方式如下.

當(dāng)其中一個(gè)字具有較低的漢明重量時(shí), 兩個(gè)31 比特字模231?1 可以通過(guò)31 比特的循環(huán)移位和模231?1 加法運(yùn)算實(shí)現(xiàn). 例如計(jì)算abmod(231?1), 其中b=2i+2j+2k, 則有:

兩個(gè)31 比特字a和b模231?1 加法運(yùn)算c=a+bmod(231?1) 可以通過(guò)以下兩步計(jì)算實(shí)現(xiàn):

Avanzi 等人[6]提出將LFSR 中的5 次模加和5 次模乘改為普通的加法和乘法, 最后再對(duì)結(jié)果進(jìn)行兩次模運(yùn)算, 同時(shí)為了防止中間結(jié)果的溢出, 使用64 比特的整型變量存儲(chǔ)中間結(jié)果. 計(jì)算過(guò)程如下所示:

通過(guò)延遲取模, LFSR 每輪的模運(yùn)算次數(shù)由10 次降低到了2 次.

3.4 S 盒合并

S 盒變換的結(jié)構(gòu)如圖2 所示, 可以看出, S 盒變換輸入32 比特輸出32 比特, 其中又由4 個(gè)8 比特輸入8 比特輸出的小S 盒組成, 即S0S1S0S1, 小S 盒的大小為0.5 KB. 對(duì)于S 盒變換的任意32 比特輸入A=A0A1A2A3(A0,A1,A2,A3均為8 比特), 有:

圖2 S 盒變換Figure 2 S-box substitution

由于小S 盒排布的對(duì)稱性, Yu 等人[8]提出將S0和S1兩個(gè)小S 盒合并成一個(gè)16 比特輸入16比特輸出的大S 盒, 大S 盒的大小為128 KB. 小S 盒合并后, 對(duì)于S 盒變換的任意32 比特輸入A=A0A1A2A3(A0,A1,A2,A3均為8 比特), 有:

合并后的S 盒變換結(jié)構(gòu)如圖3 所示.

圖3 合并后的S 盒變換Figure 3 S-box substitution after merging

如表1 所示, 將S0,S1兩個(gè)小S 盒合并后, S 盒的存儲(chǔ)空間變大了, 但查表的次數(shù)和位運(yùn)算的次數(shù)都減少了.

表1 S 盒合并前后對(duì)比Table 1 Comparison of S-box before and after combination

更進(jìn)一步, 將輸入的高16 比特查表后的移位操作合并到大S 盒中(即將大S 盒中的每個(gè)元素左移16 位), 低16 比特的大S 盒不變, 形成兩個(gè)大S 盒, 分別記為bigSHigh 和bigSLow. 合并移位操作后,每次S 盒變換都減少了一次移位操作, 但S 盒的存儲(chǔ)空間變大了. 對(duì)任意32 比特輸入A=A0A1A2A3(A0,A1,A2,A3均為8 比特), 有:

高位S 盒合并移位后的S 盒變換結(jié)構(gòu)圖如圖4 所示.

圖4 合并移位操作的S 盒變換Figure 4 S-box substitution of merging shift operation

實(shí)驗(yàn)結(jié)果: 在測(cè)試中, 合并S 盒后速度加快, 但是使用兩個(gè)大S 盒速度反而有所下降, 這可能是由于兩個(gè)大S 盒占用空間過(guò)大, 導(dǎo)致緩存命中率降低, 最終我們使用的是將S 盒合并為一個(gè)大S 盒.

3.5 使用SIMD 指令集

3.5.1 SIMD 指令集簡(jiǎn)介

SIMD(單指令多數(shù)據(jù)) 指令集支持向量化的數(shù)據(jù)并行, 一個(gè)指令可以同時(shí)操作多個(gè)數(shù)據(jù). 本文使用的AVX 及AVX2 指令集最多可支持256 比特寬的向量. SIMD 指令集主要包括與、或、異或、左移、右移等邏輯運(yùn)算, 加、減、乘、除、絕對(duì)值等算數(shù)運(yùn)算以及比較、加載或存儲(chǔ)等. 本文用到的SIMD 指令如表2 所示.

表2 SIMD 指令Table 2 SIMD instruction

3.5.2 在線性反饋移位寄存器中使用SIMD 指令集

考慮在LFSR 中一次性生成4 個(gè)新的si, 表達(dá)式如下所示:

在生成新的si前,s0,s1,··· ,s15均已知, 而s16,s17,s18,s19每一項(xiàng)的計(jì)算均依賴前一項(xiàng)計(jì)算的結(jié)果. 因此我們將最后五項(xiàng)的計(jì)算進(jìn)行并行處理, 在處理完并行部分后, 再依次處理不可并行的部分, 依次生成s16,s17,s18,s19.

由于使用了延遲取模的方法, 中間變量需要用64 位的變量存儲(chǔ), 因此使用256 位寬的寄存器去存儲(chǔ)四個(gè)表達(dá)式中操作相同的數(shù)據(jù), 如下所示:

其中,s16尚未計(jì)算, 先設(shè)為0. 之后我們就可以使用一個(gè)指令對(duì)多個(gè)數(shù)據(jù)同時(shí)進(jìn)行加法和移位, 減少操作次數(shù). 使用SIMD 指令集的并行部分如下所示:

最后處理必須串行的部分, 依次計(jì)算s16,s17,s18,s19, 如下所示:

3.6 軟件并行方法

使用多線程的方法嘗試并行處理數(shù)據(jù). 考慮到LFSR 和BR 與F函數(shù)的獨(dú)立性, 建立兩個(gè)線程: 一個(gè)線程運(yùn)行LFSR, 另一個(gè)線程運(yùn)行BR 和F函數(shù). 通過(guò)共享變量ready 保證兩個(gè)線程的同步; 使用高性能的自旋鎖, 通過(guò)線程的忙式等待保證對(duì)ready 訪問(wèn)的互斥性.

但是, 由于線程運(yùn)行的每一輪時(shí)間過(guò)于短暫, 自旋鎖的獲取和釋放時(shí)間實(shí)際上占了很大一部分, 導(dǎo)致速度反而有了明顯的下降. 因此, 在單組數(shù)據(jù)內(nèi)部軟件多線程并行的方法不可用.

3.7 使用循環(huán)數(shù)組的方式優(yōu)化LFSR 的循環(huán)移位

在LFSR 部分, 每一輪都是以16 次賦值結(jié)束的. 通過(guò)觀察我們發(fā)現(xiàn), 每一輪進(jìn)行的都是移位操作, 真正被“改變” 的只有一個(gè)31 比特?cái)?shù). 因此, 我們用循環(huán)數(shù)組實(shí)現(xiàn)移位寄存器, 使用頭來(lái)尋址, 將每輪的16次賦值改為了對(duì)隊(duì)頭的賦值以及隊(duì)頭的后移, 有效地減少了賦值操作, 提高了程序運(yùn)行效率.

3.8 使用查表的方式實(shí)現(xiàn)L 變換

對(duì)于線性變換L的任意32 比特輸入A, 記為A=A0A1A2A3, 其中Ai為8 比特, 由于變換L的線性性質(zhì), 有:

因此, 對(duì)于每個(gè)線性變換Li, 可以提前計(jì)算好Li(A0?24),Li(A1?16),Li(A2?8),Li(A3) 的值,生成四個(gè)8 比特輸入32 比特輸出的表LiBoxj, 每張表的大小為256×32 bits. 這樣, 線性變換Li的實(shí)現(xiàn)就由位運(yùn)算變?yōu)榱怂拇尾楸斫Y(jié)果的異或, 即:

實(shí)驗(yàn)結(jié)果: 在實(shí)際實(shí)現(xiàn)過(guò)程中發(fā)現(xiàn),L變換的兩種實(shí)現(xiàn)方法速度提升不大, 可能是因?yàn)樗拇螌ぶ? 訪存用時(shí)較多, 但是改用兩個(gè)16 bits 數(shù)查表又會(huì)導(dǎo)致單次尋址時(shí)間增加, 導(dǎo)致速度下降.

4 實(shí)驗(yàn)及結(jié)果

4.1 實(shí)驗(yàn)環(huán)境和測(cè)試數(shù)據(jù)的選擇

使用Dell g3 3579 筆記本作為測(cè)試環(huán)境.

CPU: Intel Core i7-8750H.

內(nèi)存: 16 G.

編譯器: 開(kāi)源的GNU 編譯器gcc.

系統(tǒng)測(cè)試方案: 對(duì)于每一種對(duì)方案的改進(jìn), 測(cè)試方案分為兩步, 首先, 使用算法標(biāo)準(zhǔn)中的測(cè)試樣例對(duì)于算法的正確性進(jìn)行驗(yàn)證, 然后, 生成大量的密鑰流對(duì)于算法的性能進(jìn)行驗(yàn)證. 4.2 節(jié)在驗(yàn)證了算法正確性的基礎(chǔ)上, 對(duì)算法的性能進(jìn)行了測(cè)試.

測(cè)試使用的數(shù)據(jù)量: 每次生成128 比特密鑰流, 循環(huán)生成20 M (20 971 520) 輪作為一次測(cè)試.

4.2 單個(gè)優(yōu)化方法

4.2.1 基準(zhǔn)測(cè)試

對(duì)不做任何優(yōu)化的ZUC 算法進(jìn)行性能測(cè)試, 測(cè)試結(jié)果如表3 所示.在基準(zhǔn)測(cè)試中, 程序平均用時(shí)3491 ms. 平均運(yùn)行速率為733 Mbps.

表3 基準(zhǔn)測(cè)試Table 3 Benchmark

4.2.2 優(yōu)化函數(shù)調(diào)用過(guò)程

優(yōu)化ZUC 算法的函數(shù)調(diào)用過(guò)程, 并對(duì)性能進(jìn)行測(cè)試, 測(cè)試結(jié)果如表4 所示. 在優(yōu)化函數(shù)的調(diào)用過(guò)程后, 程序平均用時(shí)3013 ms, 加密速度能夠達(dá)到850 Mbps.

4.2.3 編譯優(yōu)化

對(duì)ZUC 算法進(jìn)行編譯優(yōu)化, 并測(cè)試性能, 結(jié)果如表5 所示, 程序平均運(yùn)行時(shí)間為1231 ms, 平均加密速度為2079 Mbps.

表5 編譯優(yōu)化Table 5 Compile optimization

4.2.4 延遲取模

使用延遲取模的方法對(duì)ZUC 算法的LFSR 進(jìn)行優(yōu)化, 并測(cè)試性能, 結(jié)果如表6 所示. 使用延遲取模之后, 程序平均運(yùn)行時(shí)間為2371 ms, 平均加密速度為1080 Mbps.

表6 延遲取模Table 6 Modulo delay

4.2.5 S 盒合并

將非線性函數(shù)F內(nèi)的兩個(gè)S 盒合并, 并測(cè)試性能, 結(jié)果如表7 和表8 所示.

表7 S 盒合并— 1 個(gè)大S 盒Table 7 S-box merge – 1 large S-box

表8 S 盒合并— 2 個(gè)大S 盒Table 8 S-box merge – 2 large S-boxes

將非線性函數(shù)F中的兩個(gè)S 盒整合成一個(gè)大S 盒之后, 程序平均運(yùn)行時(shí)間為3282 ms. 平均運(yùn)行速度為780 Mbps. 進(jìn)一步地, 將大S 盒進(jìn)行移位操作, 形成2 個(gè)大S 盒之后, 程序平均運(yùn)行時(shí)間3400 ms,平均運(yùn)行速度753 Mbps, 可以發(fā)現(xiàn), 使用一個(gè)大S 盒的優(yōu)化效果更好.

4.2.6 使用SIMD 指令集

在LFSR 中使用SIMD 指令集, 并測(cè)試性能, 結(jié)果如表9 所示. 使用SIMD 的方式優(yōu)化LFSR 后, 程序平均運(yùn)行時(shí)間為2732 ms, 平均運(yùn)行速度為937 Mbps.

表9 使用SIMD 指令集Table 9 Using SIMD instruction

4.2.7 軟件并行方法

使用基于多線程的優(yōu)化方案對(duì)ZUC 進(jìn)行軟件并行, 并測(cè)試性能, 結(jié)果如表10 所示. 在使用了線程同步之后, 程序的平均運(yùn)行時(shí)間達(dá)到19 959 ms, 相比于基準(zhǔn)測(cè)試, 速度大幅下降.

表10 軟件并行Table 10 Software parallelism

4.2.8 使用循環(huán)數(shù)組實(shí)現(xiàn)LFSR 的循環(huán)移位

使用循環(huán)數(shù)組實(shí)現(xiàn)LFSR 的循環(huán)移位, 并測(cè)試性能, 結(jié)果如表11 所示. 使用循環(huán)數(shù)組的方式來(lái)優(yōu)化LFSR 的循環(huán)移位后, 程序平均運(yùn)行時(shí)間為3051 ms, 平均運(yùn)行速度為839 Mbps.

表11 循環(huán)數(shù)組實(shí)現(xiàn)LFSR 的循環(huán)移位Table 11 Using cyclic array to realize cyclic shift of LFSR

4.2.9 使用查表的方式實(shí)現(xiàn)兩個(gè)L變換

使用查表的方式實(shí)現(xiàn)非線性函數(shù)F中的兩個(gè)L變換, 并測(cè)試性能, 結(jié)果如表12 所示. 將兩個(gè)線性變換用查表代替之后, 平均運(yùn)行時(shí)間為3620 ms, 平均運(yùn)行速度為707 Mbps. 相對(duì)于基準(zhǔn)測(cè)試速度略有下降.

表12 查表實(shí)現(xiàn)L 變換Table 12 Using look up table to realize L transformation

4.2.10 總結(jié)

本節(jié)嘗試使用各種基本的優(yōu)化方式對(duì)ZUC 算法進(jìn)行優(yōu)化, 其中被證明有效的優(yōu)化方式為優(yōu)化函數(shù)的調(diào)用過(guò)程, 使用編譯器進(jìn)行優(yōu)化, 合并兩個(gè)S 盒, 使用SIMD 指令集對(duì)于LFSR 進(jìn)行優(yōu)化, 使用循環(huán)數(shù)組方式的LFSR. 被證明無(wú)效的方式為使用多線程的方式優(yōu)化ZUC 算法, 使用查表的方式優(yōu)化線性變換L.

4.3 組合性能測(cè)試

組合性能測(cè)試中, 我們將不同的優(yōu)化方式進(jìn)行組合, 以達(dá)到更高的速度. 在下面的組合速度測(cè)試中, 使用“調(diào)用” 表示優(yōu)化函數(shù)的調(diào)用過(guò)程, 使用“編譯” 表示編譯器優(yōu)化, 使用“循環(huán)數(shù)組” 表示利用循環(huán)數(shù)組實(shí)現(xiàn)LFSR 的循環(huán)移位, 使用“S” 表示將兩個(gè)S 盒合并為一個(gè)大S 盒, 使用“SIMD” 表示使用SIMD 指令集優(yōu)化LFSR. 測(cè)試的結(jié)果如表13 所示. 各種優(yōu)化方式的有效性如表14 所示.

表13 組合性能測(cè)試Table 13 Combined performance test

表14 各種優(yōu)化方式的有效性Table 14 Effectiveness of various optimization methods

在將優(yōu)化方式進(jìn)行組合的過(guò)程中, 在使用了優(yōu)化函數(shù)的調(diào)用過(guò)程和編譯器優(yōu)化之后, 我們發(fā)現(xiàn)再使用循環(huán)數(shù)組的方式對(duì)于LFSR 進(jìn)行優(yōu)化的話, 反而會(huì)拖慢程序的運(yùn)行效率, 因此在后面的組合優(yōu)化過(guò)程中,不再使用循環(huán)數(shù)組的方式對(duì)于LFSR 進(jìn)行優(yōu)化, 在使用了優(yōu)化函數(shù)的調(diào)用過(guò)程, 編譯優(yōu)化, 延遲取模之后,對(duì)于合并S 盒和SIMD 優(yōu)化的處理過(guò)程中, 我們發(fā)現(xiàn)使用這兩種方式都可以使速度得到提高, 但是同時(shí)使用這兩種方法的優(yōu)化效果反而不如僅僅使用合并S 盒的優(yōu)化方式. 最終, 我們的實(shí)驗(yàn)結(jié)果是使用優(yōu)化函數(shù)的調(diào)用過(guò)程、編譯器優(yōu)化、延遲取模、合并S 盒可以獲得最快的密鑰流生成速度.

4.4 加密數(shù)據(jù)測(cè)試

加密數(shù)據(jù)測(cè)試的結(jié)果如表15 所示, 在加密數(shù)據(jù)測(cè)試中, 每初始化一次密鑰加密64 KB 數(shù)據(jù)獲得了最快的速度, 最快的速度是0.849 bits/cycle. 數(shù)據(jù)較短時(shí), 隨著單次加密數(shù)據(jù)的變長(zhǎng). 速度提升的原因是初始化在運(yùn)行中所占的時(shí)間變少. 但是觀察到隨著數(shù)據(jù)的加長(zhǎng), 速度有些下降, 這可能是存儲(chǔ)數(shù)據(jù)的內(nèi)存過(guò)長(zhǎng)導(dǎo)致緩存命中率下降導(dǎo)致的. 在密鑰流生成測(cè)試中沒(méi)有出現(xiàn)類似的現(xiàn)象是因?yàn)槊荑€流生成的過(guò)程中, 循環(huán)覆蓋存儲(chǔ)密鑰流的內(nèi)存, 沒(méi)有使用很長(zhǎng)的內(nèi)存區(qū)域.

表15 加密數(shù)據(jù)測(cè)試Table 15 Data encryption test

4.5 ZUC-256 應(yīng)用測(cè)試

考慮到ZUC-256 算法與ZUC-128 算法在結(jié)構(gòu)上具有高度的相似性, 我們使用的優(yōu)化方法可以方便地應(yīng)用于ZUC-256 算法的軟件優(yōu)化工作. 我們將經(jīng)過(guò)測(cè)試效果較好的優(yōu)化函數(shù)調(diào)用和變量存取、編譯優(yōu)化、延遲取模和兩個(gè)S 盒合并應(yīng)用到ZUC-256 算法的實(shí)現(xiàn)中, 進(jìn)行了推廣測(cè)試, 測(cè)試的平均運(yùn)行時(shí)間596 ms, 平均運(yùn)行速度4.19 Gbps.

5 總結(jié)

本文對(duì)于ZUC 算法的軟件實(shí)現(xiàn)嘗試了8 種優(yōu)化方法, 分別是優(yōu)化函數(shù)的調(diào)用過(guò)程、編譯器優(yōu)化、通過(guò)延遲取模的方法優(yōu)化LFSR、通過(guò)合并兩個(gè)S 盒的方式來(lái)減少訪存的次數(shù)、利用SIMD 指令集實(shí)現(xiàn)LFSR 的多輪計(jì)算、將算法分為兩個(gè)線程執(zhí)行、使用循環(huán)數(shù)組的方式優(yōu)化LFSR、使用查表的方式實(shí)現(xiàn)線性變換L. 其中, 將算法分為兩個(gè)線程進(jìn)行執(zhí)行的方式, 由于線程的同步開(kāi)銷過(guò)大, 速度明顯下降, 使用查表的方式實(shí)現(xiàn)線性變換L也會(huì)使速度下降. 除此之外, 其他的方法單獨(dú)使用時(shí)是有效的. 然后, 我們將各種優(yōu)化方式進(jìn)行整合, 在最終實(shí)現(xiàn)中, 我們使用了效果較好的優(yōu)化函數(shù)調(diào)用和變量存取、編譯優(yōu)化、延遲取模和合并兩個(gè)S 盒, 最終使用ZUC 算法生成長(zhǎng)密鑰流的實(shí)現(xiàn)速度可以達(dá)到4.22 Gbps. 將該方法應(yīng)用到ZUC-256 算法中, 生成密鑰流速度可以達(dá)到4.19 Gbps. 實(shí)驗(yàn)源代碼見(jiàn)https://github.com/zzz136454872/ZUC_software_optimization.