張笑從, 郭 華, 張習(xí)勇, 王 闖, 劉建偉

1. 北京航空航天大學(xué) 軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室, 北京100191

2. 密碼科學(xué)技術(shù)國家重點(diǎn)實(shí)驗(yàn)室, 北京100878

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

4. 北京衛(wèi)星信息工程研究所, 北京100086

1 引言

SM4 分組密碼算法[1]是我國自主設(shè)計(jì)的對稱分組密碼, 為眾多信息系統(tǒng)提供安全、完整的數(shù)據(jù)加密方案. SM4 算法的高效軟件實(shí)現(xiàn)為我國應(yīng)用在安全產(chǎn)品(如IPSec、VPN、SSL、TLS 等)上的密碼算法由國際標(biāo)準(zhǔn)替換為國家標(biāo)準(zhǔn)提供了強(qiáng)有力的支撐, 為SM4 算法廣泛用于政府辦公、公安、銀行、稅務(wù)、電力等自主可控要求高的信息系統(tǒng)提供了可靠的保障. 目前關(guān)于SM4 算法的軟件優(yōu)化實(shí)現(xiàn)方面的相關(guān)工作不多, 多使用查表的方法[2], 但由于代替表規(guī)模相對較大, CPU 在做查表操作時(shí), 表中數(shù)據(jù)在內(nèi)存和cache之間頻繁對換導(dǎo)致查表延時(shí)較大, 且不利于高效并行加/解密多組消息. 此外, 查表法無法抵抗緩存-計(jì)時(shí)側(cè)信道攻擊, 因此在一定程度上制約了SM4 的軟件實(shí)現(xiàn)性能和安全性.

1996 年Intel 推出單指令多數(shù)據(jù)的SSE (Streaming SIMD Extensions) 指令集后, Biham[3]于1997年提出一種新的對稱分組密碼快速軟件實(shí)現(xiàn)方法, 核心思想是將處理器視為以1 比特為單位的單指令多數(shù)據(jù)處理器, 隨后被Matthew Kwan 稱為比特切片(bit slicing)[4].比特切片方法在64 位平臺上實(shí)現(xiàn)了64 組DES 消息的并行加解密, 將邏輯門個(gè)數(shù)從理論上需要的132 個(gè)每比特輸出優(yōu)化到100 個(gè)每比特輸出.之后研究者們對門函數(shù)個(gè)數(shù)進(jìn)一步進(jìn)行了優(yōu)化, 使得標(biāo)準(zhǔn)邏輯門(與、或、非、異或) 和非標(biāo)準(zhǔn)邏輯門均達(dá)到了平均50+ 個(gè)每比特輸出.2011 年Roman Rusakov[5]又將門函數(shù)的個(gè)數(shù)降至平均44 個(gè)邏輯門每比特輸出.比特切片方法可大大提高實(shí)現(xiàn)效率, 也可用于搜索密鑰, 對RISC 和CISC 的指令集平臺均適用, 且具有更好的安全性.

為了提高軟件實(shí)現(xiàn)速度, 國內(nèi)外許多學(xué)者嘗試將采用SIMD (Single Instruction Multiple Dada, 單指令多數(shù)據(jù)) 技術(shù)用于密碼算法的軟件實(shí)現(xiàn).A. Adomnicai 和T. Peyrin[6]給出改進(jìn)的比特切片方法“Fixslicing”,在ARM 和RISC-V 平臺實(shí)現(xiàn)了AES.2012 年Intel 推出高級向量指令集(Advanced Vector Extensions,AVX) 后, 眾多學(xué)者開始研究如何利用AVX 指令集加速對稱分組密碼算法的實(shí)現(xiàn)速度, 尤其是輕量級密碼算法的實(shí)現(xiàn)速度.Seiichi Matsuda 和Shiho Moriai[7]利用AVX 指令集加速切片實(shí)現(xiàn), 給出了輕量級密碼算法面向云端的實(shí)現(xiàn), 將SSE 指令與比特切片方法結(jié)合并應(yīng)用到PRESENT/Piccolo, 使兩者的實(shí)現(xiàn)吞吐量分別達(dá)到4.3 cycle/byte 和4.57 cycle/byte.2013 年,Neves 和Aumasson[8]將AVX2指令應(yīng)用到SHA-3 候選算法BLAKE 上并提高了其實(shí)現(xiàn)性能.最近,郎歡等[9]利用X86 架構(gòu)下的SIMD指令給出了高效的SM4 實(shí)現(xiàn), 他們采用C 語言調(diào)用AVX2 指令接口方式實(shí)現(xiàn), 在并行查表的基礎(chǔ)上, 給出了兩種不同的方法.2014 年Kostas Papapagiannopoulos 等人[10]將比特切片方法修改為nibble 切片方法, 并減少了訪問內(nèi)存, 在AVR 處理器上給出了高效實(shí)現(xiàn).

此外, 研究者們將比特切片方法和其它方法結(jié)合, 對SM4 算法進(jìn)行軟件實(shí)現(xiàn), 也取得了較好的效果.SM4 算法公布不久, Fen Liu 等[11]破解了SM4 算法S 盒的結(jié)構(gòu), 公布了S 盒的代數(shù)表達(dá)式及具體參數(shù)值.之后, Hao Liang 等[12]基于已破解的SM4 中S 盒結(jié)構(gòu), 提出了基于復(fù)合域的SM4 實(shí)現(xiàn)方法, 將S盒的有限域求逆運(yùn)算變換到復(fù)合域中實(shí)現(xiàn), 并在FPGA 上進(jìn)行驗(yàn)證.Jingbin Zhang 等[13]提出了SM4在復(fù)合域中的軟件實(shí)現(xiàn), 使用X86 架構(gòu)普通指令實(shí)現(xiàn), 速率達(dá)到20 Mbps.最近, A. Eldosouky 和W.Saad[14]針對物聯(lián)網(wǎng)應(yīng)用的效率、安全需求改進(jìn)了輕量級密碼算法LED 的比特切片方法, 并在嵌入式處理器ARM Cortex-A53 進(jìn)行了實(shí)現(xiàn)驗(yàn)證.O. Hajihassani 等[15]利用比特切片方法進(jìn)一步提高了高級加密算法AES 的加解密吞吐率.總的來說, 在國密標(biāo)準(zhǔn)SM4 算法的軟件優(yōu)化實(shí)現(xiàn)方法取得了一些進(jìn)展, 但和其他對稱加密算法如AES 相比, SM4 的軟件優(yōu)化實(shí)現(xiàn)仍需進(jìn)一步研究.

本文利用比特切片方法, 結(jié)合支持單指令多數(shù)據(jù)(SIMD) 的AVX2 指令集, 提出了一種SM4 算法的快速軟件優(yōu)化實(shí)現(xiàn)方法, 使用256 位的YMM 寄存器實(shí)現(xiàn)了SM4 算法的256 分組數(shù)據(jù)并行加解密.該方法首先對待加密的明文消息通過SIMD 版本的數(shù)據(jù)編排算法進(jìn)行預(yù)處理; 之后提出了一種改進(jìn)的化簡邏輯表達(dá)式的新方法, 將實(shí)現(xiàn)邏輯表達(dá)式所需的邏輯門電路數(shù)量由3000 降至497; 最后使用反編排算法得到密文.在Intel Core i7-7700HQ(Kabylake)@2.80 GHz 處理器上, 結(jié)合x86 平臺拓展指令集AVX2和上述方法對SM4 算法進(jìn)行軟件實(shí)現(xiàn), 實(shí)現(xiàn)速度達(dá)到了2580 Mbps.相比于傳統(tǒng)的查表實(shí)現(xiàn)(Intel Core i7-5500U(Broadwell-U)@2.40 GHz)、未優(yōu)化的比特切片實(shí)現(xiàn)(Intel Core i7-5500U(Broadwell-U)@2.40 GHz)、SM4 軟件優(yōu)化實(shí)現(xiàn)公開文獻(xiàn)的最佳結(jié)果[9](Intel Core i7-5500U (Broadwell-U) @2.40 GHz), 新方法的實(shí)現(xiàn)效率分別提升了1.8 倍、2.6 倍和43%.綜上所述, 本文主要貢獻(xiàn)如下:

(1) 提出了一種通用的對稱分組密碼算法的軟件優(yōu)化實(shí)現(xiàn)方法, 該方法通用于所有對稱加密算法的快速軟件實(shí)現(xiàn).

(2) 提出的基于比特切片的軟件優(yōu)化實(shí)現(xiàn)方法無需內(nèi)存或高速緩存查表, 因此可抵抗緩存-計(jì)時(shí)側(cè)信道攻擊[16], 從而安全性得到了提升.

(3) 提出的優(yōu)化方法具有較強(qiáng)的通用性.該方法可用于所有對稱加密算法的軟件優(yōu)化實(shí)現(xiàn), 并適用于不同的軟件架構(gòu): 在CISC 架構(gòu)平臺如X86 適合借助SSE、AVX2、AVX512 等拓展指令集實(shí)現(xiàn), 在RISC 架構(gòu)(ARM,RISC-V) 的平臺可使用普通指令集實(shí)現(xiàn).

(4) 新的選擇函數(shù)和搜索算法具有通用性, 可用于一般邏輯函數(shù)的化簡.

本文其余內(nèi)容組織如下: 第2 節(jié)介紹SM4 算法及AVX2 指令; 第3 節(jié)介紹新的選擇函數(shù)及基于選擇函數(shù)的改進(jìn)的搜索算法; 第4 節(jié)介紹SM4 的基于比特切片和AVX 指令的軟件優(yōu)化實(shí)現(xiàn)方法; 第5 節(jié)介紹實(shí)驗(yàn)結(jié)果; 第6 節(jié)總結(jié)全文.

2 預(yù)備知識

2.1 SM4 簡介

對于每個(gè)S 盒的8 位輸入, 前4 位作為行, 后4 位作為列, 輸出即為查找表中對應(yīng)行列所對應(yīng)的值.S 盒如圖2 所示.

圖1 SM4 輪函數(shù)Figure 1 Round function in SM4 algorithm

圖2 SM4 代替表Figure 2 Substitution table in SM4 algorithm

2.2 SIMD 技術(shù)及AVX2 指令集

SIMD (single instruction multiple data) 技術(shù)可實(shí)現(xiàn)同一操作并行處理多組數(shù)據(jù).目前支持SIMD技術(shù)的處理器廠商主要有Intel、AMD、ARM 等.目前大多數(shù)PC 及服務(wù)器采用的是Intel 處理器, 而Intel 處理器中的SSE/AVX 指令集采用的正是SIMD 技術(shù).AVX (Advanced Vector Extensions) 指令集[18]是256-bit 寬向量指令集, 指令操作對象稱為YMM 的256-bit SIMD 寄存器.該寄存器內(nèi)容分為2 個(gè)128-bit lane.AVX 指令操作對象為lanes, 該指令不支持跨越lanes 的操作.

AVX2 指令集是AVX 指令集的擴(kuò)展和改進(jìn), 也稱為Haswell New Instructions, 支持跨越lanes 的操作.AVX2 支持8 道32-bit 整數(shù)異或(vpxor)、移位(vpslld)、置換(vpermd)、查表(vpgatherdd) 等.2013 年Inter 在22 nm Haswell 微架構(gòu)處理器上正式推出AVX2 指令集.表1 給出了部分AVX2 指令,這些指令可用于對稱分組密碼的切片實(shí)現(xiàn).

3 構(gòu)造新的選擇函數(shù)及搜索算法

“選擇函數(shù)”[19]是Mattew 為比特切片方法中簡化實(shí)現(xiàn)S 盒邏輯門電路數(shù)量而提出的一種邏輯函數(shù)表達(dá)形式.選擇函數(shù)的思想為二分法, 每次分得兩個(gè)子函數(shù), 直至最終分解到的子函數(shù)可以直接實(shí)現(xiàn).經(jīng)研究發(fā)現(xiàn), 對于上述特定問題選擇函數(shù)形式比其他常用的標(biāo)準(zhǔn)形式優(yōu)越許多.如上所述, 對于SM4 算法的S 盒, 使用最簡與或形式、最簡或與形式、最簡與或非形式等需要邏輯門數(shù)約為3000, 而使用已知的3個(gè)選擇函數(shù)形式時(shí), 可將邏輯門數(shù)限制在:NSM4= 12+8×(21+22+···+28?2) = 1032.使用本文提出的新的選擇函數(shù)及改進(jìn)的搜索算法, 可進(jìn)一步將邏輯門數(shù)減至497 門.一般來說, 使用的選擇函數(shù)越多,搜索越充分, 越能減少邏輯門數(shù)量.

表1 相關(guān)AVX2 指令總結(jié)Table 1 Summary of relevant AVX2 instructions

本節(jié)首先基于已有的選擇函數(shù)構(gòu)造新的選擇函數(shù), 之后基于新的選擇函數(shù)給出改進(jìn)的搜索算法, 最后介紹如何使用新的選擇函數(shù)及改進(jìn)的搜索算法化簡S 盒的邏輯表達(dá)式.

3.1 選擇函數(shù)簡介

為化簡比特切片方法中實(shí)現(xiàn)S 盒所用的邏輯門電路數(shù)量, Mattew 提出了化簡邏輯門電路的算法及“選擇函數(shù)” 的概念.使用選擇函數(shù), DES 中實(shí)現(xiàn)S 盒的邏輯門電路數(shù)量從平均70 門每比特輸出被約簡到平均45 門每比特輸出.

設(shè)Fo為8 比特邏輯函數(shù), 即Fo(abcdefgh), 從輸入abcdefgh中任選一個(gè)比特, 記為sel, 給出選擇函數(shù)基本形式:

Mattew 指出, 還可使用nand、nor 等非標(biāo)準(zhǔn)邏輯門構(gòu)造更多選擇函數(shù).生成選擇函數(shù)形式的邏輯表達(dá)式過程如下: 從需要實(shí)現(xiàn)的邏輯函數(shù)出發(fā), 進(jìn)行選擇, 逆向生成整個(gè)邏輯電路, 直至最終得到許多2 比特邏輯函數(shù).理論上共有16 種不同的2 比特邏輯函數(shù), 其中有4 個(gè)是平凡的(常量0、1 和直接連接兩個(gè)輸入), 另外12 個(gè)非平凡的邏輯函數(shù)可由兩個(gè)輸入連接12 個(gè)邏輯門實(shí)現(xiàn), 如圖3 所示.每次選擇時(shí)都有上述3 個(gè)選擇函數(shù)形式可以使用, 需要逐個(gè)嘗試以取得較好結(jié)果.對于DES 的6 比特輸入4 比特輸出S盒來說, 先后處理4 個(gè)輸出, 每個(gè)輸出最多需要4 次“選擇”.處理過程中, 對1 個(gè)邏輯函數(shù)做“選擇” 前,可以嘗試直接連接到之前已實(shí)現(xiàn)的中間結(jié)果, 這是化簡的主要實(shí)現(xiàn)方式.

圖3 16 種2 輸入邏輯門的一種實(shí)現(xiàn)Figure 3 Example of 16 logic combinations of two gates

通過對選擇函數(shù)的分析, 我們發(fā)現(xiàn)換入不同邏輯門, 得到的新選擇函數(shù)與原形式可能有不同的子函數(shù), 從而帶來不同的結(jié)果.

針對上述問題, 本文對選擇函數(shù)及其搜索算法進(jìn)行了研究, 給出了9 種實(shí)質(zhì)不同的“選擇函數(shù)” 表達(dá)式, 并改進(jìn)了基于“選擇函數(shù)” 的邏輯門電路生成算法(稱為搜索算法), 以利用9 種“邏輯表達(dá)式” 得到更簡化的S 盒邏輯表達(dá)式.

3.2 構(gòu)造新的選擇函數(shù)及搜索算法

本小節(jié)介紹對“選擇函數(shù)” 的擴(kuò)展和搜索算法的改進(jìn).

3.2.1 構(gòu)造新的選擇函數(shù)

令m表示邏輯函數(shù)輸入的比特?cái)?shù).由于“選擇函數(shù)” 表達(dá)式每次將函數(shù)Fo分解為F1、F2、F3, 每次減少1 比特輸入, 從而保證在有限次(m ?2 次) 選擇后得到可直接實(shí)現(xiàn)的表達(dá)式.對于輸入為m比特的Fo, 可用2m比特表示; 限定F1、F2、F3的輸入為m ?1 比特時(shí), 它們均可用2m?1比特表示, 且F1,F2,F3唯一.

換入非標(biāo)準(zhǔn)邏輯門, 可以找到的所有表達(dá)形式都包含于上述9 種形式之中.

這種遞歸生成“選擇函數(shù)” 的算法處理Fo與notFo可能得到差異較大的結(jié)果, 即Fo與notFo對于“選擇函數(shù)” 生成表達(dá)式的算法來說是兩個(gè)不同的表達(dá)式, 因此應(yīng)分別嘗試.

3.2.2 改進(jìn)搜索算法

下面給出改進(jìn)的搜索算法(算法1). 對40 320×40 320 種輸入輸出排序, 分別調(diào)用此生成算法, 搜索其中邏輯門數(shù)最少的邏輯電路.算法輸入邏輯電路、sel 比特排序和輸出排序, 輸出邏輯電路和邏輯電路的總門數(shù).算法包括5 個(gè)步驟.

注: 改進(jìn)之處在于4 中提供更多選擇函數(shù)形式, 5 是新加入的步驟.

4 SM4 算法的優(yōu)化實(shí)現(xiàn)

本節(jié)首先介紹SM4 算法優(yōu)化實(shí)現(xiàn)方法的總體結(jié)構(gòu), 之后介紹具體的優(yōu)化實(shí)現(xiàn).

4.1 總體實(shí)現(xiàn)

SM4 算法的優(yōu)化實(shí)現(xiàn)包括三部分: 數(shù)據(jù)編排、迭代計(jì)算、數(shù)據(jù)反編排.對于數(shù)據(jù)(反) 編排部分, 主要采用SIMD 技術(shù)實(shí)現(xiàn)轉(zhuǎn)置并優(yōu)化; 對于迭代部分, 主要使用選擇函數(shù)優(yōu)化法優(yōu)化S 盒的邏輯表達(dá)式.具體過程如圖4 所示.

圖4 總體實(shí)現(xiàn)結(jié)構(gòu)Figure 4 Overall structure of implementation

4.1.1 數(shù)據(jù)編排

4.1.5 數(shù)據(jù)反編排

從切片后的 128 組 256 比特?cái)?shù)據(jù)恢復(fù)到 256×128 比特?cái)?shù)據(jù), 需要構(gòu)造比特矩陣轉(zhuǎn)置變換inv_TRANS(), 輸入為128×256 比特, 輸出為256×128 比特.若將輸入第i比特表示為二維數(shù)組M[128][256]的M[i/256][imod256]項(xiàng), 則轉(zhuǎn)置為二位數(shù)組M[256][128]的M[imod256][i/256]項(xiàng).

4.2 AVX2 指令集的的使用

4.2.1 實(shí)現(xiàn)數(shù)據(jù)(反) 編排

數(shù)據(jù)編排中, 對256×128 比特?cái)?shù)據(jù), 分為兩個(gè)比特方陣, 對方陣進(jìn)行比特粒度的轉(zhuǎn)置[20].使用vpor、vpslld、vpxor 等AVX2 指令優(yōu)化實(shí)現(xiàn)轉(zhuǎn)置算法.

數(shù)據(jù)反編排中的128×256 比特?cái)?shù)據(jù)也可分成兩個(gè)比特方陣類似處理.

4.2.2 實(shí)現(xiàn)密鑰編排

若并行加解密的分組使用不同密鑰, 編排方法同數(shù)據(jù)編排, 不需要反編排; 若并行加解密的分組使用相同密鑰, 編排不需要比特粒度轉(zhuǎn)置, 可以將密鑰每一比特復(fù)制為256 比特, AVX2 指令或普通指令均可平凡地實(shí)現(xiàn).

4.2.3 實(shí)現(xiàn)S 盒

使用AVX2 指令集中提供的邏輯指令實(shí)現(xiàn), 具體為vpor, vpand, vpxor, vpnand.指令為三操作數(shù)指令(其中一個(gè)為目的操作數(shù)), 不修改源操作數(shù), 必須選擇16 個(gè)YMM 寄存器作為操作數(shù).需要在內(nèi)存中暫存數(shù)據(jù), 可使用指令vmovdqa、vmovdqu 進(jìn)行數(shù)據(jù)加載、存儲.

4.3 化簡S 盒邏輯表達(dá)式

下面介紹如何使用新的“選擇函數(shù)” 及改進(jìn)的搜索算法化簡S 盒邏輯表達(dá)式.利用上節(jié)給出的9 種選擇函數(shù)表達(dá)式, 可得到9 種改進(jìn)的表達(dá)式.下面以式(1) 為例:

在上述四種處理方式中, 前兩種利用已存在的邏輯門, 無需額外代價(jià); 后兩者基于選擇函數(shù)的遞歸處理在沒有直接可用的邏輯門的情況下使用.

圖5 連接到已存在的邏輯門Figure 5 Appending to generated logic gates

圖6 連接到兩個(gè)邏輯門的組合Figure 6 Appending to combination of two logical gates

圖7 使用選擇函數(shù)公式遞歸生成邏輯電路Figure 7 Generating logical circuit using selection function recursively

圖8 引入可變的Fseed 生成邏輯電路Figure 8 Generating logical circuit via almost arbitrary Fseed

4.4 S 盒實(shí)現(xiàn)結(jié)果比較

表2 列出了使用選擇函數(shù)和未使用選擇函數(shù)時(shí)S 盒實(shí)現(xiàn)中需要的邏輯門電路數(shù)量及實(shí)現(xiàn)時(shí)間.由于AVX2 指令集中數(shù)據(jù)加載存儲指令相對于邏輯操作指令迅速許多, 因此S 盒的實(shí)現(xiàn)時(shí)間大致由邏輯門數(shù)決定.未使用選擇函數(shù)實(shí)現(xiàn)S 盒所需邏輯門數(shù)約為3000 (最簡與或式), 使用9 個(gè)選擇函數(shù)和改進(jìn)的搜索算法所需的邏輯門數(shù)為497.對31 250 Mb 數(shù)據(jù)加密測試結(jié)果顯示, 未使用選擇函數(shù)的實(shí)現(xiàn)時(shí)間為30 秒,使用9 個(gè)選擇函數(shù)和改進(jìn)的搜索算法后, 實(shí)現(xiàn)時(shí)間減少至10.3 秒.

表2 S 盒實(shí)現(xiàn)所需要的邏輯門數(shù)及實(shí)現(xiàn)時(shí)間比較Table 2 Logical gate count and time for implementing S box

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

本節(jié)比較已有公開文獻(xiàn)中關(guān)于SM4 軟件實(shí)現(xiàn)的效率, 包括傳統(tǒng)查表法、SIMD 技術(shù)查表法及比特切片方法.利用C 語言和匯編語言對SM4 算法進(jìn)行優(yōu)化實(shí)現(xiàn), 在相同的硬件環(huán)境中, 比較SM4 算法不同實(shí)現(xiàn)方法的效率.由于PC 端內(nèi)存資源相對豐富, 故對于4 GB、8 GB 內(nèi)存不做區(qū)分; 處理器微架構(gòu)和主頻對性能有較大影響.具體測試環(huán)境如表3 所示.

表4 總結(jié)在不同處理器上SM4 算法采用查表法、選擇函數(shù)優(yōu)化法的軟件實(shí)現(xiàn)性能.評估分組密碼算法軟件實(shí)現(xiàn)性能的指標(biāo)是每秒鐘加/解密的比特?cái)?shù), 即bps.對31 250 Mbit 數(shù)據(jù)進(jìn)行加密測試.表4 的8-32 表示采用8-bit 輸入32-bit 輸出表.

表4 軟件實(shí)現(xiàn)方法在不同處理器上效率對比Table 4 Efficiency of software implementations on different processors

由表4 可以看出, 使用AVX2 指令的并行查表方法比普通查表方法在效率上有明顯提升, 由908 Mbps 到1795 Mbps 提升接近1 倍.未優(yōu)化的比特切片+AVX2 指令方法效率不佳, 而本文的比特切片+AVX 指令+ 選擇函數(shù)優(yōu)化方法在Intel Core i5-6200U(Skylake)@2.40 GHz 和Intel Core i7-7700HQ(Kabylake)@2.80 GHz 分別達(dá)到2387 Mbps 和2580 Mbps, 相對于近似的主頻(2.40 GHz)、微架構(gòu)(Intel Core i7-5500U(Broadwell-U)) 的AVX2 指令并行查表方法有明顯優(yōu)勢.

對于算法所需的內(nèi)存開銷, 普通查表和并行查表需要4 KB 內(nèi)存存放代換表, 對于資源受限的終端并不合適; 而本文的比特切片實(shí)現(xiàn)無需任何額外的內(nèi)存開銷來存儲代換表, 因此所需內(nèi)存開銷為0.此外,查表法在內(nèi)存中存儲代換表并需要在加解密時(shí)訪問對應(yīng)的內(nèi)存, 除了需要額外的內(nèi)存開銷, 還不能抵抗緩存-計(jì)時(shí)側(cè)信道攻擊.本文的軟件優(yōu)化實(shí)現(xiàn)方法不需查表, 因此能夠抵抗該類側(cè)信道攻擊.

下面進(jìn)一步給出對31 250 Mb 數(shù)據(jù)加密測試的詳細(xì)結(jié)果.

表5 軟件實(shí)現(xiàn)方法效率測試Table 5 Test on efficiency of software implementations

由表5 可知, 在Intel Core i5-6200U(Skylake)@2.40 GHz 下, 本文的基于選擇函數(shù)優(yōu)化法的實(shí)現(xiàn)時(shí)間為13.09 秒, 加密效率提升2.04 倍.在Intel Core i7-7700HQ(Kabylake)@2.80 GHz 下, 該方法的實(shí)現(xiàn)時(shí)間為12.11 秒, 加密效率提升2.18 倍.此外, 由表5 可以看出, S 盒計(jì)算占全部計(jì)算約80%, 進(jìn)一步提升效率的關(guān)鍵仍在于優(yōu)化S 盒的實(shí)現(xiàn).

6 總結(jié)

本文基于比特切片方法和SIMD 技術(shù), 提出了一種新的SM4 算法軟件優(yōu)化實(shí)現(xiàn)方法, 并利用X86 平臺的AVX2 指令集給出了高效的實(shí)現(xiàn).新方法首先利用AVX2 指令優(yōu)化了數(shù)據(jù)編排算法, 之后基于選擇函數(shù)提出了更靈活的化簡S 盒邏輯表達(dá)式的算法.在基于選擇函數(shù)的優(yōu)化方法中, 構(gòu)造了新的選擇函數(shù),并基于新的選擇函數(shù)改進(jìn)了搜索算法, 從而將S 盒所使用的門電路數(shù)量從3000 門降至497 門; 在Intel Core i7-7700HQ(Kabylake)@2.80 GHz 環(huán)境下, 同目前公開文獻(xiàn)中SM4 軟件實(shí)現(xiàn)的最快速度1.7 G 相比, 基于選擇函數(shù)的優(yōu)化方法加解密速度提升至2.5 G, 提高了43%.同基于查表的軟件實(shí)現(xiàn)方法相比, 本作品的軟件實(shí)現(xiàn)方法可以抵抗cache 攻擊, 從而提高了算法實(shí)現(xiàn)的安全性.本文提出的新的選擇函數(shù)和搜索算法具有通用性, 可用于其它一般邏輯函數(shù)的化簡.此外, 優(yōu)化方法具有可擴(kuò)展性, 不僅可以從SM4 算法擴(kuò)展至目前所有的對稱加密算法的軟件優(yōu)化實(shí)現(xiàn), 而且可以從X86 平臺的拓展指令集AVX2 實(shí)現(xiàn)擴(kuò)展至利用RISC 指令集在資源受限、安全性要求高的ARM 等嵌入式平臺上實(shí)現(xiàn).