解文博，韋永壯*，劉爭紅

（1.廣西密碼學與信息安全重點實驗室（桂林電子科技大學），廣西桂林 541004；2.廣西無線寬帶通信與信號處理重點實驗室（桂林電子科技大學），廣西桂林 541004）

0 引言

圖形處理器（Graphic Processing Unit，GPU）的架構與中央處理器（Central Processing Unit，CPU）不同，相對于CPU 來說，GPU 的線程更多，帶寬更高，延遲更低，更適合并行計算，并且計算速度也要明顯高于CPU 的計算速度。GPU 設計之初是用于圖形圖像處理，但隨著GPU 的發(fā)展，它被不斷地用于大數據、多并行的計算。計算統(tǒng)一設備架構（Compute Unified Device Architecture，CUDA）是NVDIA 發(fā)布的并行計算平臺和接口模型，支持C、C++等多種編程語言，使得GPU并行計算變得更為容易，是目前最受歡迎的應用編程接口之一。

利用GPU 解決密碼學問題的最早工作是Kedem 等［1］和Olano 等［2］使用Pixel Flow 圖像引擎快速破解了UNIX 系統(tǒng)的密鑰，這使得原本用于解決圖像處理問題的GPU 開始用于密碼學問題。Cook等［3］第一次嘗試對對稱密碼算法使用GPU進行優(yōu)化，于2006 年利用OpenGL 實現了高級加密標準（Advanced Encryption Standard，AES）；但由于軟件的不足和硬件的限制，GPU 比CPU 的性能提升僅有2.3%。2007 年Manavski等［4］第一次利用CUDA進行AES算法的加速，在顯卡NVIDIA Geforce 8800GTX 上實現了128 位的AES 算法，加密8 MB 的數據，加密吞吐量可以達到8.28 Gb/s。2009 年Chu等［5］利用GPU 的強大計算能力來降低網絡編碼和同態(tài)哈希的計算成本，他們通過在GPU 上實現網絡編碼和同態(tài)哈希函數（Homomorphic Hashing Function，HHF），所得結果比CPU 上計算速度提高顯著，這種實現方式可以為防御分布式系統(tǒng)中的污染攻擊提供解決方案。Li 等［6］于2012 年提出在GPU 上AES 的電子密碼本（Electronic CodeBook，ECB）模式和密文分組鏈接（Cipher Block Chaining，CBC）模式的實現，通過將T 盒分配在共享存儲器上并采用每個線程處理16 字節(jié)的粒度，使得GPU 運行速度比CPU 快50 倍。Cheong 等［7］在2015 年在具有Kepler 架構的NVIDIA GTX 690 上提出加速分組密碼IDEA（International Data Encryption Algorithm）、Blowfish 和Threefish的技術，對于三個算法分別實現了90.3 Gb/s、50.82 Gb/s 和83.71 Gb/s 的加密吞吐量。2017 年，Abdelrahman 等［8］提出了使用不同粒度值在三種不同的GPU 架構上的AES-128 算法（ECB 模式）實現。他們的實驗結果表明，使用NVIDIA GTX 1080（Pascal）、NVIDIA GTX TITAN X（Maxwell）和GTX 780（Kepler）GPU 架構，吞吐率分別達到277 Gb/s、201 Gb/s 和78 Gb/s。同年，Ma 等［9］在CBC 模式下實現了AES解密，他們對基于GPU 的不同參數設置下的實現進行了全面分析，這些參數包括：輸入數據的大小、每個塊的線程數、內存分配的方式和并行粒度。最終GPU 上的最優(yōu)性能是CPU 上的112 倍。2020 年，Yeoh 等［10］提出一種基于GPU 的快速搜索密碼學算法差分特性的分支定界算法，文章針對TRIFLE-BC-128 算法，利用中間相遇方法與GPU 相結合，所得結果與基于CPU 的方法相比，搜索效率提高了約58 倍。綜上可知，關于分組密碼在GPU 上的快速實現研究較多的是對AES 的優(yōu)化，作為Beierle 等［11］新推出的分組密碼算法SKINNY 雖與AES結構類似，都是代換-置換網絡（Substitution-Permutation Network，SPN）結構，但由于采用新型設計理念，具有安全性好、使用靈活等優(yōu)點，特別適合在微控制器和軟件上快速實現，備受業(yè)界廣泛關注，所以對其快速并行實現是目前亟待解決的問題。

本文基于Linux 系統(tǒng)下的CUDA 平臺，通過分析SKINNY算法的特性，對該算法的ECB 和計數器（Counter，CTR）模式進行并行加速，在數據量達到64 MB 的加密環(huán)境下分析測試了GPU 并行算法的性能，并對基于CPU 實現和基于GPU 實現的SKINNY 算法進行了時間、加速效率、加速比和吞吐量的分析。

1 SKINNY算法

1.1 算法簡介

SKINNY 算法是一種新的輕量級密碼算法，該算法加密分組為64 和128 位的明文數據，可以使用64、128、192、256 和384 位的密鑰來加密。本文快速實現的算法是數據分組長度為128 位、密鑰長度為256 位的SKINNY 算法，簡記為SKINNY-256。SKINNY 算法的操作是在二維數組上執(zhí)行的，該數組的初始狀態(tài)如式（1）所示：

SKINNY-256的輪函數由以下5個操作組成，分別是：

1）字節(jié)替換（SubCells，SC）：通過S 盒將一個字節(jié)替換為另一個字節(jié)。

2）輪加常數（AddConstants，AC）：狀態(tài)矩陣異或輪常數。

3）輪加密鑰（AddRoundTweakey，ART）：輪密鑰的第一行、第二行和狀態(tài)矩陣相應的位置異或。

4）行移位（ShiftRows，SR）：簡單的位移。矩陣從第0 行到第3行，依次循環(huán)移動0、1、2、3個字節(jié)。

5）列混淆（MixColumns，MC）：狀態(tài)矩陣與二進制矩陣相乘。

SKINNY 的加密輪函數過程如圖1 所示，由48 個輪函數迭代而成，解密過程相似。密鑰編排算法可參考文獻［11］。

圖1 SKINNY算法加密輪函數Fig.1 Encryption round function of SKINNY algorithm

1.2 SKINNY加密模式的選擇

分組密碼常用的工作模式有5 種［12-14］，分別是：電子密碼本（ECB）模式、計數器（CTR）模式、密碼塊鏈接（CBC）模式和密碼反饋（Cipher FeedBack，CFB）模式及輸出反饋（Output FeedBack，OFB）模式。

1.2.1 模式比較

表1列出了5種加密模式的并行特性［6］：ECB、CTR模式都支持并行計算，因為它們的每個單個分組都可以獨立加密；而其他三種模式不支持，因為它們的分組輸入都與前一段的輸出有一定關系，具有串行特性。本文SKINNY 算法實現選擇的是可以并行實現的ECB 模式和CTR 模式。接下來對ECB和CTR這兩種模式進行簡單介紹。

表1 加密模式比較［6］Tab.1 Comparison of encryption modes［6］

1.2.2 電子密碼本（ECB）模式

在ECB 模式下，數據會被分組獨立進行加密。這種加密模式加密方便，應用廣泛。此模式的表達式如式（2）所示：

其中：i=1，2，…，n；P表示輸入的明文；C表示輸出的密文。

1.2.3 計數器（CTR）模式

計數器模式有一個自增的連續(xù)值，將這個自增值用密鑰進行加密，加密之后的中間值與明文進行異或，得到密文，相當于一次一密。此模式的加密方式快速簡單，可靠安全，但它容易遭受攻擊者的攻擊。此模式的表達式如式（3）所示：

其中：R={0，1，…，2(|P|-1)}；i=1，2，…，n。

2 CUDA加速SKINNY

2.1 SKINNY的并行優(yōu)化

SKINNY 的每一輪的操作如圖2 所示，ai，j表示輸入明文，TKk，j表示輪密鑰。

圖2 SKINNY算法的輪變換Fig.2 Round transformation of SKINNY algorithm

為了得到更好的實現性能，本文將5 個步驟進行化簡合并成為一個公式，如式（4）所示，然后將其前4 個表分別定義為T表，兩組輪密鑰矩陣合并定義為TK，輪常數矩陣定義為C。

最終的表達式化簡為4 個T表和5 個異或運算，如式（5）所示，這樣可以避免大量的邏輯計算。

其中：i，j=0，1，2，3；k=0，1。輪常數C只影響輸入矩陣的第一列；輪密鑰TK只影響輸入矩陣的前兩行。

2.2 并行粒度

并行粒度的設計會影響算法的實現效果，所以在設計并行粒度時要遵循兩個原則：1）提高分配線程的利用率；2）減少各線程間的通信開銷［15］。并行粒度的設計一般分為兩種：一種為細粒度，一個GPU 線程處理16 字節(jié)分組中的4 字節(jié)，如圖3所示；另一種稱為粗粒度處理，一個線程處理16個字節(jié)的分組，如圖4 所示。在細粒度實現中，它可以調度更多線程增大吞吐量，但是線程之間的通信開銷也隨之增大。在粗粒度實現中，單個線程處理一個獨立的SKINNY 分組，GPU 上的線程無須同步，并且每個線程都獨立運行，從而減少了通信時間。通過實驗對比發(fā)現，粗粒度的設計方式要優(yōu)于細粒度。

基于以上分析，將SKINNY 的并行粒度設計為“每個線程一個分組”，也就是說每個線程處理16 字節(jié)的數據。數據被分為多個16字節(jié)矩陣，這些矩陣由GPU 同步執(zhí)行。在這種情況下，每個GPU 線程可以獨立完成，因為不同線程的矩陣不具有相互依賴性，線程間不用相互等待。

圖3 細粒度并行方案Fig.3 Fine-grained parallel scheme

圖4 粗粒度并行方案Fig.4 Coarse-grained parallel scheme

2.3 內存分配

CUDA 的內存分配策略非常重要，因為CUDA 具有5種不同的內存［16］，每種內存的特性在一定程度上相互不同。內存分配策略的不同會對性能帶來明顯的影響。

2.3.1 明文內存分配

輸入明文被分為幾個互相獨立的塊進行加密。本文使用的是一個線程處理一個分組，例如，當處理1 000個分組，就需要1 000個GPU線程。因為明文數量較大，所以將整體明文存儲到全局內存中。每個線程獲得16 個字節(jié)的數據后，將會暫存在線程的寄存器中，寄存器對于各個線程是私有的，即彼此無法互相訪問。所有線程完加密后，再將數據從GPU 內存中取回。

2.3.2T表內存分配

T表本質上是查找表，在線程間是只讀數據，用戶可以通過它們快速實現部分加密操作。每個線程在每一輪加密操作中都需要隨機訪問T表。因此，本文需要將T表提前加載到GPU 的內存中。根據這些屬性，將T表分配到CUDA 常量內存中。另一種分配方案是將T表分配到共享內存中，但是此種分配方式會存在一些問題，即存儲體沖突，如果多個地址請求落在相同的內存存儲體時，就會發(fā)生存儲體沖突，導致請求被重復執(zhí)行。

2.3.3 輪密鑰內存分配

密鑰的保密性和密鑰的長度是保證密碼的安全性的基礎。在SKINNY 算法的實現中，每一輪加密都需要密鑰異或操作。CUDA 的每個線程都需要輸入不同的輪密鑰。在這種情況下，本文將輪密鑰放入常量存儲器中，所有線程在常量內存中共享輪密鑰。

2.4 線程數的分配

每個GPU 塊中線程數的數量也會影響運行性能。每個塊的線程數如何分配，存在一些原則。在分配時一個塊的線程數最好是32的倍數，因為連續(xù)的線程會以32個為一組組成一個線程束（warp），同一warp 里的線程會對不同的數據執(zhí)行相同的指令。而如果線程數不是32的倍數，GPU 會將不足32的線程的warp 補全，造成資源的浪費。本文使用的設備的一個塊最大線程數為1 024，設置線程數不能超過其最大值，雖然說一個塊中的線程越多越能隱藏延遲，但是這樣會使每個線程可以使用的資源變少，考慮到所用的其他資源：共享內存、寄存器等，為了達到更好的性能，決定每塊分配512 個線程。

綜上所述，最終的分配方案如表2 所示?；贕PU 實現的SKINNY 算法加密部分流程如圖5 所示，解密部分與加密相似。

圖5 SKINNY算法并行流程Fig.5 Parallel flowchart of SKINNY algorithm

表2 GPU變量分配方案Tab.2 GPU variable allocation scheme

3 實驗與結果分析

3.1 實驗環(huán)境

本實驗所使用的CPU 為：Inter Xeon E5-2643 v4 @3.40 GHz；GPU：GeForce GTX TITAN X，內存為32 GB，全局內存為12 GB；操作系統(tǒng)為：Ubuntu 18.04.2 LTS，64 bit；編程環(huán)境為：CUDA 10.1，GCC 7.5.0。本實驗的CPU 代碼用的C 語言編寫，GPU代碼用CUDA C編寫。

3.2 實驗結果

實驗操作是對相同大小的明文分別進行基于CPU 和GPU 的加密運算，明文大小從16 B 開始二倍遞增到64 MB，記錄運行的時間和吞吐量。為了降低實驗誤差，每種規(guī)格的明文均運行10 次，取平均值。用加速效率和加速比來作為衡量算法性能提升的指標，加速效率表示并行程序的運行效率的提升情況，加速效率S的定義如式（6）所示；加速比表示并行程序對比串行程序的性能提升，加速比E的定義如式（7）所示。

其中：TC表示CPU串行加密時間；TG表示GPU并行加密時間。

3.2.1 SKINNY算法ECB模式的實驗結果與分析

SKINNY 算法的ECB 模式在CPU 和GPU 上運行的效果的對比以及吞吐量的變化趨勢如表3和圖6所示。從表3和圖6可以看出：隨著輸入數據的倍速增長，基于CPU 的SKINNY 算法的運行時間也倍速增長，而基于GPU 的該算法的運行時間卻以緩慢的速度增長。隨著明文數據增到16 MB 左右，加速比和加速效率達到峰值。并且隨著輸入數據的增大，基于GPU 的吞吐量增幅明顯，而CPU 吞吐量相對穩(wěn)定，增幅不大。GPU 吞吐量的峰值出現在明文大小在16 MB 左右時，此后吞吐量趨于穩(wěn)定。對于ECB 模式來說，加速比峰值可達671，加速效率峰值可達99.85%。

圖6 SKINNY_ECB加密串行和并行吞吐量對比Fig.6 Throughput of SKINNY_ECB（CPU vs.GPU）

表3 SKINNY_ECB實現性能比較（CPU對比GPU）Tab.3 SKINNY_ECB implementation performance comparison（CPU vs.GPU）

3.2.2 SKINNY算法CTR模式的實驗結果與分析

SKINNY 算法的CTR 模式在CPU 和GPU 上運行的效果的對比以及吞吐量的變化趨勢如表4和圖7所示。

表4 SKINNY_CTR實現性能比較（CPU對比GPU）Tab.4 SKINNY_CTR implementation performance comparison（CPU vs GPU）

圖7 SKINNY_CTR加密串行和并行吞吐量對比Fig.7 Throughput of SKINNY_CTR（CPU vs.GPU）

它的增長與變化曲線與ECB 模式類似，但CTR 模式的實現速度要稍快于ECB 模式的實現速度。CTR 和ECB 模式最大的區(qū)別在于CTR 有一個16字節(jié)的計數器counter，每次加密counter 加1，所以加密速度更快。它的加速比和加速效率峰值也都出現在明文數據輸入為16 MB 左右，其中加速比最高可達765，加速效率最高可達99.87%。

3.3 實驗討論

綜合兩種加密模式的分析，發(fā)現當輸入明文大小在16 B～64 B 時，加速比要小于1，說明基于CPU 的性能要優(yōu)于GPU。因為數據量太小，GPU開啟的線程數少，無法通過線程級并行來隱藏延遲；也說明一個線程的GPU 并行運算的時間效果遠沒有單線程CPU 好。但是，當輸入明文變大，例如16 MB，基于GPU 的性能要明顯優(yōu)于CPU，當處理大量數據時，GPU 可以通過多個線程之間的亂序執(zhí)行和多個線程間的靈活切換來隱藏延遲，從而提高吞吐量。

也就是說：當輸入明文大小較?。ㄐ∮?4 B）時，基于CPU的性能要好于GPU 性能；但是，當輸入明文大小變大（64 B 及以上）時，GPU 的性能要比CPU 好得多，GPU 在性能方面比CPU 優(yōu)勢顯著。雖然當可并行化數據的大小越來越大時，GPU 的性能就可以得到充分利用，但GPU 的性能并不能無限得到提升，由于受到GPU 自身硬件條件的限制，它的速度提升也是有邊界的，比如當輸入明文超過2 MB 時，吞吐量增長趨于平穩(wěn)，執(zhí)行時間開始呈線性增長。由圖4～5可以得出，并行GPU的吞吐量變化大致分為三個階段：16 B～128 KB吞吐量為指數增長，128 KB～4 MB 吞吐量為線性增加，4 MB 及以上吞吐量增加趨于穩(wěn)定。

3.4 實驗結果對比

文獻［17］報告了ECB 模式下SKINNY 不同版本的在OpenCL 中的并行實現，他們的優(yōu)化方法是分別對加密算法的分布操作進行優(yōu)化，但是沒有提及線程塊的配置、存儲方式選擇等問題。相較于文獻［17］的ECB 模式下的SKINNY-256 并行實現，本文基于GPU 實現并行算法的最高吞吐量是其1.29倍。并且由于AES 是目前主流的密碼算法，且AES-256 和SKINNY-256具有相同的明文分組和密鑰分組長度，還將本文的實驗結果與文獻［18］關于ECB模式下的AES-256加速的并行算法進行對比，對比結果表明：本文的結果有2.55 倍的性能提升。具體比較如表5 所示。這說明，本文采用的方法對SKINNY 的ECB 模式在GPU 下能有效地發(fā)揮其并行計算能力。本文通過將SKINNY 的5 個加解密步驟進行組合形成1個整體表達式，使得SKINNY 的實現只需要4 個T表查找和5個XOR 運算，減少了代碼數量、降低了內存占用面積，提高了并行性；采用粗粒度的并行方式即“每個線程一個分組”用于線程調度，避免了線程間的頻繁數據交互；線程塊數的設置非定值而是隨明文大小和線程數個數變化，其計算公式為：明文總數/每塊線程數/分組大小，有助于提高并行性能。同時本文還對CTR 模式在GPU 下的實現方法進行了探究，針對CTR 模式與ECB 模式的不同，將CTR 模式特有的計數器初始值存儲到寄存器中，其他操作與ECB 模式基本相似，結果發(fā)現CTR模式的并行也可以在GPU上充分發(fā)揮其并行計算能力。

表5 不同算法的吞吐量比較Tab.5 Throughput comparison of different algorithms

4 結語

本文基于GPU 下的CUDA 編程模型，利用SKINNY-256算法的結構和特點，提出其ECB 和CTR 模式的并行優(yōu)化方案。實驗結果表明，對于SKINNY 算法的ECB 和CTR 模式，當處理數據在16 MB 及以上時，GPU 加速效率可以達到99.85%和99.87%，加速比分別可達到671 和765。進一步的研究工作可以考慮對其他分組密碼算法如國密SM4 進行GPU 下的并行加速。