ZUC 算法軟件快速實現(xiàn)*

張宇鵬, 高 瑩,2, 嚴 宇, 劉 翔

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

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

1 引言

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

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

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

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

綜上所述, 本文的主要貢獻如下:

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

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

2 ZUC 算法描述

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

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

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

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

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

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

2.3 比特重組

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

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

2.4 非線性函數(shù)F

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

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

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

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

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

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

3.2 編譯優(yōu)化

3.2.1 提高編譯器自動優(yōu)化等級的方式優(yōu)化程序運行

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

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

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

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

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

3.3 延遲取模

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

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

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

兩個31 比特字a和b模231?1 加法運算c=a+bmod(231?1) 可以通過以下兩步計算實現(xiàn):

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

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

3.4 S 盒合并

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

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

由于小S 盒排布的對稱性, Yu 等人[8]提出將S0和S1兩個小S 盒合并成一個16 比特輸入16比特輸出的大S 盒, 大S 盒的大小為128 KB. 小S 盒合并后, 對于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兩個小S 盒合并后, S 盒的存儲空間變大了, 但查表的次數(shù)和位運算的次數(shù)都減少了.

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

更進一步, 將輸入的高16 比特查表后的移位操作合并到大S 盒中(即將大S 盒中的每個元素左移16 位), 低16 比特的大S 盒不變, 形成兩個大S 盒, 分別記為bigSHigh 和bigSLow. 合并移位操作后,每次S 盒變換都減少了一次移位操作, 但S 盒的存儲空間變大了. 對任意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

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

3.5 使用SIMD 指令集

3.5.1 SIMD 指令集簡介

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

表2 SIMD 指令Table 2 SIMD instruction

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

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

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

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

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

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

3.6 軟件并行方法

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

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

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

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

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

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

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

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

4 實驗及結(jié)果

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

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

CPU: Intel Core i7-8750H.

內(nèi)存: 16 G.

編譯器: 開源的GNU 編譯器gcc.

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

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

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

4.2.1 基準(zhǔn)測試

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

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

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

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

4.2.3 編譯優(yōu)化

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

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

4.2.4 延遲取模

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

表6 延遲取模Table 6 Modulo delay

4.2.5 S 盒合并

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

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

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

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

4.2.6 使用SIMD 指令集

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

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

4.2.7 軟件并行方法

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

表10 軟件并行Table 10 Software parallelism

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

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

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

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

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

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

4.2.10 總結(jié)

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

4.3 組合性能測試

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

表13 組合性能測試Table 13 Combined performance test

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

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

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

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

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

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

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

5 總結(jié)

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