基于GPU的密碼S盒代數(shù)性質(zhì)評(píng)估方法

蔡婧雯，韋永壯*，劉爭(zhēng)紅

（1.廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室（桂林電子科技大學(xué)），廣西桂林 541004；2.廣西無(wú)線寬帶通信與信號(hào)處理重點(diǎn)實(shí)驗(yàn)室（桂林電子科技大學(xué)），廣西桂林 541004）

0 引言

密碼S 盒作為對(duì)稱密碼算法的核心部件，主要提供了必要的非線性變換，其代數(shù)性質(zhì)往往決定著密碼算法的安全強(qiáng)度。伴隨著超級(jí)計(jì)算機(jī)其計(jì)算能力的迅速提升，特別是抵抗未來(lái)的量子計(jì)算攻擊［1］，高強(qiáng)度密碼算法設(shè)計(jì)中對(duì)S 盒的輸入及輸出規(guī)模提出了新的要求，比如基于非線性反饋移位寄存 器（Nonlinear Feedback Shift Register，NFSR）或ARX（Addition-Rotation-XOR）操作部件等方法構(gòu)造出16 比特或32 比特的大狀態(tài)密碼S 盒。美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院（National Institute of Standards and Technology，NIST）發(fā)起輕量級(jí)密碼算法公開征集［2］，最終入圍算法中SPARKLE［3］及GIFT-COFB（COmbined FeedBack）［4］等算法均采用了32 比特或者64 比特大狀態(tài)密碼S 盒。同年，在中國(guó)密碼學(xué)會(huì)舉辦的全國(guó)密碼算法設(shè)計(jì)競(jìng)賽［5］中，徐洪等［6］基于16 級(jí)NFSR 迭代構(gòu)造了16 比特S 盒；田甜等［7］基于NFSR 設(shè)計(jì)了32 比特S 盒；2020 年美洲密碼會(huì)上，Beierle 等［8］基于ARX 結(jié)構(gòu)構(gòu)造了64比特S 盒。注意到，密碼S 盒的安全性與其安全性指標(biāo)息息相關(guān)，傳統(tǒng)安全性指標(biāo)包括差分均勻度［9］、非線性度［10-11］、透明階（Revised Transparency Order，RTO）［12］、飛來(lái)器連接表［13］（Boomerang Connectivity Table，BCT）等。這些指標(biāo)與相應(yīng)的密碼攻擊密切相關(guān)，如差分均勻度、非線性度和透明階分別刻畫了S 盒抵抗差分密碼分析［14］、線性密碼分析［15］及差分功耗攻擊（Differential Power Attack，DPA）［16］的能力。另一方面，對(duì)于n比特輸入及n比特輸出的密碼S 盒，當(dāng)n比較大時(shí)（如n＞15 時(shí)）評(píng)估S 盒的各個(gè)安全性指標(biāo)則較為困難，比如傳統(tǒng)求解密碼S 盒的差分均勻度、非線性度及透明階時(shí)間復(fù)雜度分別約為O（23n）、O（23n）及O(23n·n2)。這些求解因搜索空間大，從而導(dǎo)致花銷時(shí)間太長(zhǎng)等問(wèn)題。如何快速評(píng)估密碼S 盒的代數(shù)性質(zhì)是目前研究的熱點(diǎn)之一。

為了解決計(jì)算資源瓶頸，圖形處理器（Graphics Processing Unit，GPU）應(yīng)運(yùn)而生。GPU 主要應(yīng)用于圖像處理、視頻音頻處理、計(jì)算生物學(xué)等領(lǐng)域上。而利用GPU 解決密碼學(xué)問(wèn)題最早工作是Kedem 等［17］使用PixelFlow 圖像引擎快速破解了UNIX 系統(tǒng)密鑰；Manavski［18］利用計(jì)算統(tǒng)一設(shè)備架構(gòu)（Compute Unified Device Architecture，CUDA）進(jìn)行高級(jí)加密標(biāo)準(zhǔn)（Advanced Encryption Standard，AES）加速；Cheong等［19］在具有Kepler 架構(gòu)上提出了加速分組密碼算法國(guó)際數(shù)據(jù)加密算法（International Data Encryption Algorithm，IDEA），進(jìn)一步提高加密吞吐量；Yeoh 等［20］提出了一種基于GPU 的分支定界算法。如何基于GPU 快速評(píng)估密碼S 盒的安全強(qiáng)度仍有待進(jìn)一步研究。

本文基于CPU-GPU 異構(gòu)結(jié)構(gòu)，對(duì)密碼S 盒的差分均勻度、非線性度及透明階提出求解優(yōu)化方法，實(shí)現(xiàn)多線程并行計(jì)算，提出一種快速求解差分均勻度、非線性度及透明階的方法。測(cè)試結(jié)果表明，與基于中央處理器（Central Processing Unit，CPU）實(shí)現(xiàn)相比，基于CPU-GPU 異構(gòu)結(jié)構(gòu)實(shí)現(xiàn)效率得到大幅度提升。本文方法利用單塊GPU 分別計(jì)算差分均勻度、非線性度及透明階所花銷的時(shí)間與傳統(tǒng)方法相比節(jié)省了90.28%、78.57%、60%。

1 預(yù)備知識(shí)

定義1設(shè)n比特輸入、m比特輸出的S 盒記為S(x)=(f1(x)，f2(x)，…，fm(x))：→，其中fi(x) 為→F2的布爾函數(shù)，記為密碼S 盒的第i個(gè)分量函數(shù)（i=1，2，…，m）。本 文考慮n=m=16 的16 比特S 盒。

定義2差分均勻度［9］。設(shè)n比特輸入、n比特輸出的S盒記為S，對(duì)任意的輸入差分α∈和輸出差分β∈，其中差分對(duì)解的個(gè)數(shù)為：

則差分均勻度定義為：

當(dāng)差分均勻度越小，S 盒的差分分布更均勻，安全性更好。

定義3非線性度［10-11］。一個(gè)n×n的S 盒的非線性度為S 盒的所有分量函數(shù)的非零線性組合中最小的非線性度，即：

定義4透明階（RTO）［12］。對(duì)于任意n比特輸入、n比特輸出的S 盒，該S 盒的透明階記為：

當(dāng)透明階越小時(shí)，抵抗差分功耗攻擊的能力越強(qiáng)，安全性越好。

定義5S 盒的差分概率［21］。對(duì)于一個(gè)n比特輸入、n比特輸出的密碼S 盒，對(duì)于輸入差分α∈和輸出差分β∈，存在差分概率

則稱輸入差分α經(jīng)過(guò)S 盒后將以概率PS(α→β)得到輸出差分β。

定義6S 盒的線性概率［21］。定義一個(gè)S 盒S：→，定義NS(θ，λ)=#{x∈：θ·x=λ·S(x)}構(gòu)造密碼S 盒的線性逼近表，其中，固定輸入掩碼θ∈，得到輸出掩碼λ的概率為：

即固定輸入掩碼θ，輸出掩碼λ，隨機(jī)給定輸入x，則θ·x=λ·S(x)以概率PLS(θ→λ)成立得到。

2 CUDA的并行計(jì)算

2.1 GPU與CUDA

隨著人工智能、大數(shù)據(jù)等計(jì)算領(lǐng)域的不斷發(fā)展，計(jì)算復(fù)雜度越來(lái)越大，圖像處理器（GPU）從幫助CPU 做圖像和圖形運(yùn)算轉(zhuǎn)至海量數(shù)據(jù)處理上，涉及云計(jì)算、生物計(jì)算、天文學(xué)等多個(gè)領(lǐng)域，逐步成為了計(jì)算領(lǐng)域的研究熱點(diǎn)。

由于CPU 與GPU 所應(yīng)用的場(chǎng)景不同，兩者的架構(gòu)大不相同。從圖1 中CPU 與GPU 的架構(gòu)相比可知，CPU 與GPU 有如下區(qū)別：

圖1 CPU與GPU的架構(gòu)區(qū)別Fig.1 Difference between CPU and GPU architectures

1）GPU 采用了若干個(gè)算術(shù)邏輯單元（Arithmetic and Logic Unit，ALU）和超長(zhǎng)的流水線，可以同時(shí)處理多個(gè)線程；然而CPU 擁有少量但很強(qiáng)大的算術(shù)邏輯單元，可以在很少的時(shí)間周期內(nèi)完成運(yùn)算。

2）CPU 具有強(qiáng)大的控制邏輯單元，在運(yùn)算過(guò)程中提供邏輯預(yù)測(cè)能力降低延時(shí)；而GPU 控制能力稍遜色于CPU，運(yùn)算過(guò)程中可以將多個(gè)訪問(wèn)合并成較少的訪問(wèn)。

3）CPU 有大量的緩存空間降低計(jì)算延時(shí)，而GPU 只有少量的緩存空間，與CPU 的緩存空間功能不同，GPU 的緩存空間將線程所需要訪問(wèn)的相同數(shù)據(jù)合并訪問(wèn)動(dòng)態(tài)隨機(jī)存取存儲(chǔ)器。

從以上而可知，CPU 適合于需要較大的緩存空間且復(fù)雜控制邏輯的通信密集型運(yùn)算；GPU 則適合于邏輯分支簡(jiǎn)單、計(jì)算量大的計(jì)算密集型運(yùn)算。另外，從圖2 可以得知，在計(jì)算密集型任務(wù)時(shí)，GPU 所需耗時(shí)占CPU 所需耗時(shí)的22%；而在計(jì)算通信密集的任務(wù)時(shí)，CPU 計(jì)算所需耗時(shí)較少，約為GPU 計(jì)算所需耗時(shí)的30%。在一些具有計(jì)算密集要求且邏輯分支較為簡(jiǎn)單的計(jì)算任務(wù)中，GPU 的處理能力比CPU 具有更大的優(yōu)勢(shì)。

圖2 CPU與GPU任務(wù)耗時(shí)比較Fig.2 Task time consumption comparison of CPU and GPU

GPU 的造價(jià)和功耗與相同計(jì)算能力的CPU 相比，GPU 的造價(jià)和功耗相對(duì)較低。在計(jì)算領(lǐng)域中構(gòu)建CPU 集群的超級(jí)計(jì)算機(jī)，造價(jià)昂貴。根據(jù)摩爾定律可以得知當(dāng)CPU 計(jì)算速度達(dá)到一定程度時(shí)提升空間受限，GPU 的出現(xiàn)滿足了需要計(jì)算大量數(shù)據(jù)而無(wú)法使用巨型計(jì)算機(jī)的用戶需求。

目前應(yīng)用較為廣泛的GPU 并行編程平臺(tái)有CUDA、OpenCL 等。2006 年NVIDIA 公司推出并行開發(fā)平臺(tái)CUDA，支持C、C++、Java、Python 等多種主流編程語(yǔ)言，便于各領(lǐng)域進(jìn)行并行計(jì)算操作。CUDA 使用了具有很強(qiáng)的并行計(jì)算特點(diǎn)的單指令多線程（Single Instruction Multiple Thread，SIMT）的執(zhí)行模型，模型在執(zhí)行過(guò)程中，構(gòu)建CPU 與GPU 異構(gòu)架構(gòu)，其中：CPU 主要負(fù)責(zé)串行計(jì)算工作，完成較為復(fù)雜的邏輯控制及通信密集的運(yùn)算；GPU 主要負(fù)責(zé)并行計(jì)算工作，完成運(yùn)算量大且計(jì)算任務(wù)較為簡(jiǎn)單的計(jì)算密集型工作。經(jīng)過(guò)測(cè)試及多方考量，本文選用CUDA 作為本文的并行開發(fā)平臺(tái)，構(gòu)造CPU-GPU 異構(gòu)架構(gòu)進(jìn)行測(cè)試。

2.2 線程塊的分配

為了發(fā)揮GPU 的最大并行計(jì)算效率，在執(zhí)行內(nèi)核函數(shù)過(guò)程中，需要合理配置線程塊數(shù)量及每塊線程塊中的線程數(shù)量。線程塊的數(shù)目由配置參數(shù)所劃分的網(wǎng)格所決定，通常為32 的倍數(shù)最佳。通過(guò)測(cè)試可知，將線程塊的線程數(shù)量為512時(shí)具有最大的計(jì)算能力。

2.3 并行計(jì)算的影響因素

總結(jié)前文所述的GPU 與CUDA 的計(jì)算特點(diǎn)，影響并行計(jì)算效率的因素可以總結(jié)為以下3 點(diǎn)：

1）減少CPU 與GPU 之間的數(shù)據(jù)傳輸。由于CPU 與GPU使用不同的內(nèi)存空間，CPU 與GPU 在數(shù)據(jù)交換過(guò)程中需要通過(guò)計(jì)算機(jī)總線，造成了額外的時(shí)間花銷，因此在利用GPU 進(jìn)行并行計(jì)算時(shí)，應(yīng)盡量避免減少CPU 與GPU 之間的數(shù)據(jù)傳輸。

2）減少訪問(wèn)GPU 全局內(nèi)存。為了減少內(nèi)存訪問(wèn)產(chǎn)生的時(shí)延和消耗，在GPU 中應(yīng)盡量減少過(guò)多的跳躍式訪問(wèn)，最大限度減少因?qū)PU 內(nèi)存訪問(wèn)而造成的延遲。

3）合理的資源配置。為了提高并行計(jì)算的效率，合理設(shè)置線程塊內(nèi)的線程數(shù)量，最大限度地利用線程處理計(jì)算任務(wù)，減少資源的浪費(fèi)。

3 NBC算法

NBC 算法為中國(guó)密碼學(xué)會(huì)舉辦的全國(guó)密碼算法設(shè)計(jì)競(jìng)賽分組算法［11］第二輪入選算法之一，其采用廣義Feistel 結(jié)構(gòu)［12］，算法加密共有三種模式，具體如表1 所示。

表1 NBC算法的三種模式Tab.1 Three modes of NBC algorithm

本文使用的算法是數(shù)據(jù)分組長(zhǎng)度為128 比特、密鑰長(zhǎng)度為128 比特的NBC 算法。設(shè)第i輪的輸入為Xi=輸出為NBC-128/128 算法結(jié)構(gòu)如圖3 所示。

圖3 八分支的1輪NBC-128/128結(jié)構(gòu)Fig.3 One-round NBC-128/128 structure with 8 branches

NBC-128/128 算法的S 盒采用16 級(jí)NFSR來(lái)構(gòu)造16 比特S 盒，S 盒構(gòu)造圖如圖4 所示。設(shè)S 盒的16 比特的輸入為S0S1…S15，當(dāng)全體內(nèi)部狀態(tài)經(jīng)過(guò)迭代20 輪后形成S 盒輸出。

圖4 NBC-128算法的S盒構(gòu)造Fig.4 S-box structure of NBC-128 algorithm

算法設(shè)計(jì)者稱構(gòu)造出來(lái)的S 盒的差分均勻度Diff（S）=22，非線性度NL（S）=31 982，透明階RTO=15.982 6。

4 基于GPU的16比特密碼S盒代數(shù)性質(zhì)評(píng)估

由于在CPU 下求解差分均勻度、非線性度及透明階的算法效率較低，在本章中，將傳統(tǒng)求解密碼S 盒代數(shù)性質(zhì)評(píng)估方法進(jìn)行優(yōu)化，分別討論基于單GPU 模式和多GPU 模式下將內(nèi)核函數(shù)切片至多線程中，實(shí)現(xiàn)多線程并行化計(jì)算。

4.1 單GPU對(duì)16比特密碼S盒性質(zhì)評(píng)估

根據(jù)共享式內(nèi)存的結(jié)構(gòu)特點(diǎn)和對(duì)S 盒性質(zhì)評(píng)估的求解流程，本文提出了單塊GPU 環(huán)境下的CPU-GPU 異構(gòu)模式，并行架構(gòu)如圖5 所示。

圖5 CPU-GPU異構(gòu)并行流程Fig.5 CPU-GPU heterogeneous parallel flowchart

程序在運(yùn)行時(shí)控制一塊GPU，創(chuàng)建多個(gè)線程共同完成計(jì)算任務(wù)。具體步驟如下所示：

1）檢測(cè)顯卡設(shè)備。函數(shù)cudaSetDevice（）表示檢測(cè)主機(jī)設(shè)備的顯卡個(gè)數(shù)，當(dāng)檢測(cè)到主機(jī)存在可使用的顯卡時(shí)，將對(duì)算法進(jìn)行CUDA 并行計(jì)算做好準(zhǔn)備；

2）讀取數(shù)據(jù)并復(fù)制入GPU。采用cudaMalloc（）函數(shù)在設(shè)備Device 中開辟計(jì)算中所需要參數(shù)的空間。由于GPU 在計(jì)算過(guò)程中，無(wú)法直接讀取CPU 內(nèi)存中的數(shù)據(jù)，故在計(jì)算前需要在設(shè)備Decive 開辟相應(yīng)的空間。

3）當(dāng)Device 中開辟了相應(yīng)的空間大小后，使用cudaMemcpy（）函數(shù)將所需要的參數(shù)S 盒復(fù)制進(jìn)入GPU 內(nèi)。

4）計(jì)算內(nèi)核函數(shù)。偽代碼中存在3 個(gè)不同的內(nèi)核函數(shù)，分別為differenceUniformity（）、degreeOfNolinearity（）及calculateRTO（），其中：differenceUniformity（）為計(jì)算差分均勻度的內(nèi)核函數(shù)；degreeOfNolinearity（）為計(jì)算非線性度的內(nèi)核函數(shù)；calculateRTO（）為計(jì)算透明階的內(nèi)核函數(shù)。

5）在內(nèi)核函數(shù)中，＜＜＜Block，Thread＞＞＞表示在啟動(dòng)內(nèi)核函數(shù)時(shí)，分配Block個(gè)線程組，每個(gè)線程組中分配Thread個(gè)線程，故共分配Block*Thread線程總數(shù)。通過(guò)合理設(shè)置線程組和線程數(shù)量，才能更好地發(fā)揮GPU 的計(jì)算能力。本文使用的是一個(gè)線程處理一個(gè)分組，例如當(dāng)處理100 組數(shù)據(jù)時(shí)，需要在GPU 內(nèi)分配100 個(gè)線程，故本文計(jì)算16 比特S 盒的密碼性質(zhì)中，共需要處理65 536 個(gè)分組數(shù)據(jù)，使用了128 個(gè)線程塊，其中每個(gè)線程塊512 個(gè)線程。

6）檢查并返回結(jié)果。當(dāng)每一個(gè)線程完成了內(nèi)核函數(shù)中的計(jì)算任務(wù)時(shí)，使用cudaGetLastError（）函數(shù)檢查內(nèi)核函數(shù)在計(jì)算過(guò)程中是否存在錯(cuò)誤：若存在錯(cuò)誤，將錯(cuò)誤返回至CPU中；若不存在，利用函數(shù)cudaMemcpy（）將計(jì)算結(jié)果返回至CPU 中，計(jì)算結(jié)束。

求解復(fù)雜度分析如下：

1）由差分均勻度的定義可以得知：針對(duì)n比特輸入、n比特輸出的密碼S 盒，傳統(tǒng)求解差分均勻度需要遍歷輸入差分α∈、輸出差分β∈及x∈三個(gè)變量，時(shí)間復(fù)雜度約為O（23n）。根據(jù)GPU 并行計(jì)算的特性，使用切片技術(shù)對(duì)求解差分均勻度的最外層循環(huán)分解到各個(gè)線程中并行，即除最外層循環(huán)外部分設(shè)為內(nèi)核函數(shù)，此時(shí)求解差分均勻度的時(shí)間復(fù)雜度降低至O（22n）。為了進(jìn)一步提高效率，減少計(jì)算邏輯分支數(shù)，再將遍歷的輸出差分β循環(huán)放置內(nèi)核函數(shù)外，此在GPU 內(nèi)計(jì)算的內(nèi)核函數(shù)的時(shí)間復(fù)雜度將降低至O（2n）。

2）對(duì)求解非線性度及透明階進(jìn)行求解分析。傳統(tǒng)求解非線性度及透明階的時(shí)間復(fù)雜度為O（23n）、O(23n·n2)。利用相同的切片技術(shù)，將求解最外層循環(huán)分解到各個(gè)線程中，求解過(guò)程中利用線程索引對(duì)應(yīng)最外層循環(huán)所遍歷的值，此時(shí)求解非線性度及透明階的時(shí)間復(fù)雜度降低至O（22n）、O(22n·n2)。另外再將一層循環(huán)放在內(nèi)核函數(shù)外，最終GPU 內(nèi)計(jì)算非線性度及透明階的內(nèi)核函數(shù)的時(shí)間復(fù)雜度將降低至O(2n)、O(2n·n2)，與傳統(tǒng)求解方法相比，該方法的時(shí)間復(fù)雜度降低了兩個(gè)指數(shù)級(jí)，節(jié)省了求解時(shí)間花銷。

算法1 測(cè)試主程序。

輸入 S 盒；

輸出 差分均勻度，非線性度，透明階。

4.2 多GPU對(duì)大狀態(tài)S盒性質(zhì)評(píng)估

4.1 節(jié)分析了在CPU-GPU 異構(gòu)計(jì)算結(jié)構(gòu)下，對(duì)16 比特S盒安全性指標(biāo)測(cè)評(píng)比在傳統(tǒng)CPU 計(jì)算下所具有的時(shí)間優(yōu)勢(shì)，在相同的實(shí)驗(yàn)條件下，使用單塊GPU 構(gòu)建的CPU-GPU 異構(gòu)計(jì)算比傳統(tǒng)CPU 計(jì)算時(shí)間節(jié)省90.28%。但對(duì)于n比特輸入、n比特輸出的密碼S 盒，當(dāng)n比較大時(shí)（如n＞15 時(shí)），由于計(jì)算搜索空間大，運(yùn)算量大，單GPU 計(jì)算時(shí)間仍然較長(zhǎng)，故提出在多GPU 環(huán)境下，對(duì)評(píng)估NBC 算法的16 比特S 盒的差分均勻度、非線性度等安全性指標(biāo)方案并行化研究，對(duì)計(jì)算過(guò)程中涉及的數(shù)據(jù)傳輸過(guò)程進(jìn)行研究與優(yōu)化。分析并行化計(jì)算所遇到的瓶頸主要在數(shù)據(jù)傳輸過(guò)程，在結(jié)果保證正確性的基礎(chǔ)上，調(diào)整程序的傳輸方式，由同步傳輸調(diào)整至異步傳輸，且利用多流技術(shù)與異步傳輸相結(jié)合逐步提高加速比。最后通過(guò)實(shí)現(xiàn)分析說(shuō)明基于多GPU 架構(gòu)下對(duì)大狀態(tài)S 盒的安全性指標(biāo)計(jì)算性能。

在使用多GPU 構(gòu)架中，選擇單個(gè)節(jié)點(diǎn)連接到高速串行計(jì)算機(jī)擴(kuò)展總線標(biāo)準(zhǔn)（Peripheral Component Interconnect express，PCIe）總線上，具體架構(gòu)如圖6 所示。程序在運(yùn)行時(shí)使用函數(shù)cudaSetDecice（）對(duì)GPU 設(shè)備組上的各設(shè)備進(jìn)行綁定，使得每個(gè)線程管理一個(gè)GPU，實(shí)現(xiàn)多個(gè)GPU 并行工作。與單GPU 結(jié)構(gòu)相比，多GPU 結(jié)構(gòu)可以開辟更多的線程，運(yùn)算速度得到進(jìn)一步提升。

圖6 多GPU節(jié)點(diǎn)架構(gòu)Fig.6 Multi-GPU node architecture

由于同步傳輸?shù)牟⑿谢?jì)算中，傳輸數(shù)據(jù)占用了大量的時(shí)間。本節(jié)利用多流技術(shù)與異步技術(shù)相結(jié)合，在計(jì)算過(guò)程中使計(jì)算過(guò)程與數(shù)據(jù)傳輸兩個(gè)步驟進(jìn)行重疊，從而減少一部分時(shí)間的開銷。有無(wú)重疊優(yōu)化的時(shí)間開銷對(duì)比如圖7 所示。在無(wú)重疊優(yōu)化時(shí)，由于默認(rèn)只有一個(gè)流隊(duì)列，此時(shí)所有的計(jì)算過(guò)程皆為串行執(zhí)行。先對(duì)數(shù)據(jù)傳輸至GPU 的全局內(nèi)存內(nèi)，傳輸完畢后再進(jìn)行數(shù)據(jù)計(jì)算，等待GPU 內(nèi)的所有線程計(jì)算完畢后再將結(jié)果復(fù)制回CPU 內(nèi)。作為對(duì)比，在使用重疊技術(shù)進(jìn)行時(shí)間優(yōu)化后，當(dāng)一個(gè)流隊(duì)列在計(jì)算部分?jǐn)?shù)據(jù)的同時(shí)，另一個(gè)流隊(duì)列可以對(duì)剩下數(shù)據(jù)進(jìn)行傳輸至GPU 內(nèi)等待計(jì)算。當(dāng)一個(gè)流上的數(shù)據(jù)計(jì)算完畢后，利用另一個(gè)流隊(duì)列傳輸回CPU 內(nèi)，下一個(gè)流隊(duì)列等待數(shù)據(jù)傳輸。計(jì)算與傳輸時(shí)間重疊技術(shù)的優(yōu)化既能保持計(jì)算任務(wù)仍按照串行執(zhí)行，又能掩蓋GPU 與CPU 數(shù)據(jù)傳輸之間所帶來(lái)的大量時(shí)間開銷，從而進(jìn)一步減少程序所需要的執(zhí)行時(shí)間，提高并行效率。

圖7 有無(wú)重疊優(yōu)化的時(shí)間開銷對(duì)比Fig.7 Comparison of time cost with and without overlapping optimization

利用多GPU 對(duì)大狀態(tài)S 盒進(jìn)行評(píng)估過(guò)程具體如下：

1）在CPU 端獲取已有的GPU 設(shè)備數(shù)量和每個(gè)GPU 設(shè)備信息。利用CUDA 中自帶的函數(shù)cudaGetDeviceCount（&ngpus），讀取已有的GPU 設(shè)備數(shù)量，并將GPU 數(shù)量信息存儲(chǔ)在變量ngpus中，可通過(guò)設(shè)備號(hào)dev進(jìn)行選擇使用GPU設(shè)備。

2）在同一節(jié)點(diǎn)上的GPU 設(shè)備構(gòu)成GPU 設(shè)備組，GPU 設(shè)備組內(nèi)的GPU 設(shè)備直接進(jìn)行通信和數(shù)據(jù)傳輸。

3）在CPU 端進(jìn)一步準(zhǔn)備計(jì)算所需要的數(shù)據(jù)集，根據(jù)GPU設(shè)備組的數(shù)量，將數(shù)據(jù)平分至各GPU 設(shè)備上，另外在CPU 端設(shè)置S 盒，在CPU 端將S 盒以結(jié)構(gòu)體的形式傳輸至GPU 設(shè)備組中對(duì)應(yīng)的常量存儲(chǔ)區(qū)中，S 盒參數(shù)都在對(duì)應(yīng)的GPU 設(shè)備運(yùn)行過(guò)程中將會(huì)被核函數(shù)多次調(diào)用。

4）在CPU 端設(shè)置循環(huán)遍歷所有的GPU 設(shè)備，將GPU 設(shè)備組中的GPU 分別置于對(duì)應(yīng)并行流上，通過(guò)對(duì)工作流在不同時(shí)間下的操作和阻塞實(shí)現(xiàn)GPU 設(shè)備的異步，設(shè)置CUDA 工作流Steam 的異步操作隱藏了部分訪問(wèn)延遲和實(shí)現(xiàn)了任務(wù)的并發(fā)執(zhí)行，減少了數(shù)據(jù)處理時(shí)間。

5）明確每個(gè)核函數(shù)分配的變量和變量空間，利用函數(shù)cudaMemory（）將數(shù)據(jù)以異步方式傳輸至GPU 設(shè)備組中對(duì)應(yīng)的GPU 上。

6）為了確保核函數(shù)運(yùn)行時(shí)有較好的性能，延用上一節(jié)對(duì)GPU 的線程數(shù)分配，使用了128 個(gè)線程組，其中每個(gè)線程組512 個(gè)線程，共計(jì)65 536 個(gè)線程數(shù)。

7）核函數(shù)完成線程配置后，數(shù)據(jù)根據(jù)“分而治之”思想，將輸入數(shù)據(jù)劃分成多個(gè)子集分別復(fù)制。由于每個(gè)問(wèn)題都是獨(dú)立的，所以分別安排在不同的并行流中進(jìn)行計(jì)算，不同的流之間輸出傳輸于另一個(gè)流的核計(jì)算進(jìn)行重疊。

8）當(dāng)線程中循環(huán)遍歷完所有的塊，完成內(nèi)核函數(shù)Kernel的計(jì)算后，利用重疊流的思想保證每個(gè)線程計(jì)算后優(yōu)先傳輸至CPU 內(nèi)。

9）當(dāng)所有線程都計(jì)算完畢后，CPU 端對(duì)GPU 設(shè)備組的各GPU 設(shè)備返回的結(jié)果進(jìn)行統(tǒng)一歸總，并按照規(guī)定的格式進(jìn)行輸出。

算法2 多GPU 測(cè)試主程序。

輸入 S 盒；

輸出 差分均勻度，非線性度，透明階。

5 測(cè)試與結(jié)果分析

5.1 測(cè)試環(huán)境

本文實(shí)驗(yàn)環(huán)境所使用的CPU 為Intel Xeon Silver 4210 2.20 GHz；GPU 為NVIDIA Quadro RTX 8000；在多GPU 環(huán)境下，共使用4 塊相同型號(hào)的GPU，且顯卡型號(hào)為NVIDIA Quadro RTX 8000；操作系統(tǒng)為Ubuntu 18.04.4 LTS，64 bits；編程環(huán)境為CUDA 7.0、GCC 7.5.0。本實(shí)驗(yàn)的CPU 代碼用的C 語(yǔ)言進(jìn)行編寫，GPU 代碼用CUDA C 進(jìn)行編寫。

5.2 測(cè)試結(jié)果

本次測(cè)試是針對(duì)NBC-128/128 算法的16 比特S 盒分別進(jìn)行差分均勻度、非線性度和透明階運(yùn)算，其中測(cè)試可得NBC 算法的差分均勻度為Diff（S）=22，非線性度為NL=31 982，透明階RTO=15.982 6，運(yùn)行時(shí)間如圖8 所示。

圖8 對(duì)比CPU、單塊GPU及多塊GPU下的運(yùn)行時(shí)間Fig.8 Comparison of running time under CPU，single GPU and multi-GPU

通過(guò)以上實(shí)驗(yàn)結(jié)果表明，在相同的實(shí)驗(yàn)條件下，使用GPU 測(cè)試16 比特S 盒差分均勻度所用時(shí)間比在CPU 測(cè)試16比特S 盒所用時(shí)間約減少90.28%；使用GPU 測(cè)試16 比特S盒的非線性度所用時(shí)間比在CPU 測(cè)試16 比特S 盒所用時(shí)間約減少78.57%；使用GPU 測(cè)試16 比特S 盒透明階所用時(shí)間比在CPU 測(cè)試16 比特S 盒所用時(shí)間約減少60%。實(shí)驗(yàn)結(jié)果證明使用GPU 測(cè)試大比特S 盒性質(zhì)所消耗時(shí)間明顯少于使用CPU 測(cè)試大比特S 盒性質(zhì)所用的時(shí)間。在使用多GPU 并行計(jì)算的架構(gòu)下，在相同實(shí)驗(yàn)條件下，使用多GPU 測(cè)試差分均勻度所用時(shí)間比單GPU 測(cè)試所用時(shí)間約減少99.52%；使用多GPU 測(cè)試非線性度所用時(shí)間比單GPU 測(cè)試所用時(shí)間約減少91.67%；使用多GPU 測(cè)試透明階所用時(shí)間比單GPU 測(cè)試所用時(shí)間約減少78.13%，使用多塊GPU 并行計(jì)算的計(jì)算速率明顯高于單塊GPU 計(jì)算速率。

通過(guò)密碼S 盒的差分概率定義可知，當(dāng)輸入尺寸n比較大時(shí)（如n＞15 時(shí)），需要遍歷輸入差分α∈、輸出差分β∈及x∈三個(gè)變量，所以求解差分概率所需的時(shí)間復(fù)雜度約為O（23n）。類似地，當(dāng)求解線性概率時(shí)，同樣需要遍歷3 個(gè)變量，分別是輸入掩碼θ、輸出掩碼λ及輸入x，即時(shí)間復(fù)雜度也約為O（23n）。注意到，利用切片技術(shù)對(duì)差分概率及線性概率的計(jì)算過(guò)程可以分解到各個(gè)線程中并行計(jì)算。因而，求解差分概率及線性概率與求解差分均勻度方法類似，預(yù)計(jì)所花銷的時(shí)間大致相當(dāng)，限于篇幅，本文不再贅述。

6 結(jié)語(yǔ)

本文基于CPU-GPU 結(jié)構(gòu)，結(jié)合差分均勻度、非線性度等計(jì)算特征，將內(nèi)核函數(shù)利用切片技術(shù)拆分至多線程上，實(shí)現(xiàn)多線程并行計(jì)算，并由此提出快速評(píng)估密碼S 盒代數(shù)性質(zhì)新方法。在單塊GPU 及4 塊GPU 環(huán)境下對(duì)NBC-128/128 密碼算法的S 盒進(jìn)行差分均勻度、非線性度及透明階3 個(gè)性質(zhì)計(jì)算，實(shí)驗(yàn)結(jié)果證實(shí)：與基于CPU 的實(shí)現(xiàn)環(huán)境相比，基于單塊GPU 所構(gòu)建的CPU-GPU 架構(gòu)的實(shí)現(xiàn)效率得到了顯著的提升，即計(jì)算差分均勻度、非線性度及透明階分別節(jié)省了90.28%、78.57%、60%的時(shí)間。下一步的研究工作可以考慮針對(duì)32 比特、64 比特等大狀態(tài)的密碼S 盒，基于CPU-GPU 結(jié)構(gòu)進(jìn)行安全性評(píng)估。