基于CUDA的高性能對稱密碼算法實(shí)現(xiàn)技術(shù)研究

◆楊海云 張梓鋅 隆 昆 段博坤

?

基于CUDA的高性能對稱密碼算法實(shí)現(xiàn)技術(shù)研究

◆楊海云 張梓鋅 隆 昆 段博坤

(中國民航大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 天津 300300)

在大數(shù)據(jù)和云計(jì)算應(yīng)用與日俱增的今天，很多的應(yīng)用服務(wù)器面臨著執(zhí)行大量計(jì)算稠密的加密挑戰(zhàn)。CUDA作為NVIDIA推出的一種并行計(jì)算平臺和編程模型，能夠利用現(xiàn)有的顯卡資源，以低成本的方式提升加密性能。在NVIDIA Geforce 940M 上設(shè)計(jì)并實(shí)現(xiàn)了并行的AES和SM4算法，與傳統(tǒng)的CPU實(shí)現(xiàn)方式進(jìn)行對比，AES最高可以獲得92.70%的加密效率提升和13.69倍的加速比，SM4最高可以獲得98.41%的加密效率提升和62.92倍的加速比。

CUDA；并行計(jì)算；對稱密碼算法；加速比

0 引言

在當(dāng)今諸多的網(wǎng)絡(luò)應(yīng)用中，數(shù)據(jù)加密必不可少。伴隨著大數(shù)據(jù)時(shí)代的到來，加密效率已經(jīng)成為一個(gè)不容忽視的問題。同時(shí)，計(jì)算機(jī)正在從只使用CPU的“中央處理”向CPU與GPU并用的“協(xié)同處理”發(fā)展。CUDA[1]作為NVIDIA公司推出的一種并行編程計(jì)算框架，有效利用GPU的計(jì)算能力，提高了計(jì)算速度。本文將先以基于CUDA的AES和SM4算法[2]為實(shí)踐基礎(chǔ)，研究GPU計(jì)算對于這兩種常用加密算法的性能提升，進(jìn)一步探索基于CUDA的對稱密碼算法設(shè)計(jì)實(shí)現(xiàn)的一般性方法。

1 CUDA簡介

CUDA（Compute Unified Device Architecture，統(tǒng)一計(jì)算設(shè)備架構(gòu)）是一種由NVIDIA推出的通用并行計(jì)算架構(gòu)，該架構(gòu)使GPU 能夠解決復(fù)雜的計(jì)算問題。它包含了CUDA指令集架構(gòu)以及GPU內(nèi)部的并行計(jì)算引擎，開發(fā)人員可以使用C語言來為CUDA架構(gòu)編寫程序。它要求計(jì)算機(jī)的顯卡必須支持CUDA技術(shù)，然后安裝CUDA開發(fā)環(huán)境即可使用C語言進(jìn)行編程。

2 AES和SM4算法簡介

2.1 AES算法

AES（Advanced Encryption Standard，高級加密標(biāo)準(zhǔn)）是由美國國家標(biāo)準(zhǔn)技術(shù)研究所在2001年發(fā)布的一種對稱加密算法，目前，AES算法已然成為對稱密鑰加密中最流行的算法之一。

作為一種分組加密算法，AES的分組長度為128bit，密鑰長度有三種可選取值：128bit、192bit和256bit。加密時(shí)首先將明文切割成為128bit的分組，每個(gè)分組首先進(jìn)行密鑰相加，其次按照密鑰長度加密不同的輪數(shù)。每一輪中有四層，分別為字節(jié)替換（SubBytes，使用Sbox進(jìn)行非線性替換）、行移位（ShiftRows，對每行分別進(jìn)行0，1，2，3字節(jié)的循環(huán)移位，達(dá)到字內(nèi)混淆）、列混合（MixColumns，線性變換每列以混淆數(shù)據(jù)）、密鑰相加（AddRoundKey，對輪密鑰和狀態(tài)進(jìn)行異或運(yùn)算，進(jìn)行盲化）。需要注意的是，最后一輪不包括列混合層。加密對應(yīng)輪數(shù)后，即完成了一個(gè)分組的加密變換。對其余分組也進(jìn)行這樣的操作，組合每個(gè)分組的加密結(jié)果，便完成了整個(gè)明文的加密[3]。

2.2 SM4算法

SM4是由中國國家商用密碼管理辦公室2006年發(fā)布的一種Feistel結(jié)構(gòu)的分組密碼算法，分組長度和密鑰長度均為128bit。加解密算法與密鑰擴(kuò)展算法都采用32輪非線性迭代結(jié)構(gòu)。對加密流程中涉及的參數(shù)做出如下定義：

加密密鑰：

輪密鑰由加密密鑰擴(kuò)展而來，表示為：

系統(tǒng)參數(shù)：

為字，固定參數(shù)：

為字，輪函數(shù)F為：

輸出為：

則：

定義反序變換R為：

整個(gè)加密的流程圖如圖1所示。

圖1 SM4加密流程圖

3 基于CUDA的SM4和AES算法設(shè)計(jì)與實(shí)現(xiàn)

通過上面對SM4和AES的算法介紹可以看出，對稱密碼算法的主要特點(diǎn)是：明文加密前需要按照分組長度進(jìn)行切塊，各個(gè)明文分組加密過程沒有影響。這個(gè)特點(diǎn)是算法并行實(shí)現(xiàn)的理論基礎(chǔ)所在。傳統(tǒng)的加密程序?qū)⒚魑淖x取與切塊、密鑰擴(kuò)展、分組加密，加密結(jié)果整合這四個(gè)步驟統(tǒng)一放在CPU上處理，而CUDA提供了一個(gè)低成本的并行計(jì)算平臺，可以將分組加密這個(gè)最耗費(fèi)時(shí)間和計(jì)算資源的步驟放在GPU上。CPU要做的只是明文讀取與切塊、密鑰擴(kuò)展、加密結(jié)果整合這三個(gè)計(jì)算量比較小的步驟，這樣便大大節(jié)省了CPU的計(jì)算資源。

GPU的計(jì)算線程集中在每一block（線程塊）上，計(jì)算執(zhí)行時(shí)加載到流處理器上運(yùn)行[4,5]。所以并發(fā)度與流處理器的個(gè)數(shù)和每個(gè)線程塊中所能容納的最大線程數(shù)目有直接關(guān)系。本實(shí)驗(yàn)使用的顯卡為NVIDIA Geforce 940M，流處理器有3個(gè)，每個(gè)線程塊的最大線程數(shù)目為1024，即每個(gè)線程塊最大可以讓1024個(gè)明文分組執(zhí)行加密運(yùn)算。GPU的啟動(dòng)參數(shù)計(jì)算方法如下：

設(shè)明文分組個(gè)數(shù)為n，線程塊數(shù)目為p，每個(gè)線程塊中啟動(dòng)的線程數(shù)目為q，則：

if(n/3>1024)

p=n/1024

q=1024

else

p=3

q=n/3

然后使用0號線程對共享內(nèi)存中的S盒等一些必要數(shù)據(jù)參數(shù)進(jìn)行初始化，從1號線程開始進(jìn)行加密，對于單個(gè)線程來說，它們執(zhí)行一個(gè)分組的完整加密流程，每個(gè)block中的各個(gè)線程互不干擾，計(jì)算各自的加密結(jié)果。最后使用線程ID將它們的計(jì)算結(jié)果收集起來，得到最終的加密結(jié)果[6]。

在CUDA程序設(shè)計(jì)中，將CPU稱為主機(jī)端，GPU稱為設(shè)備端[7,8]。通過上面的分析可知，無論是AES，還是SM4。明文文件的讀取，密鑰擴(kuò)展，加密結(jié)果整合都應(yīng)該在主機(jī)端完成，只有分組加密在設(shè)備端。圖2總結(jié)了實(shí)現(xiàn)并行AES和SM4的算法的主要思想。

圖2 基于CUDA的SM4和AES算法設(shè)計(jì)框圖

4 實(shí)驗(yàn)

4.1 測試方案與步驟

為了比較傳統(tǒng)的CPU加密和GPU加密時(shí)間，在表1的配置環(huán)境下我們設(shè)計(jì)出如下的測試方案：

第一步：準(zhǔn)備1MB， 4MB，8MB，10MB，15MB，20MB，30MB，50MB，100MB的10個(gè)文件。

第二步：分別將這10個(gè)文件用傳統(tǒng)的AES和SM4算法加密20次，計(jì)算并記錄平均加密時(shí)間。

第三步：分別將這10個(gè)文件用并行的AES和SM4算法加密20次，計(jì)算并記錄平均加密時(shí)間。

第四步：整理實(shí)驗(yàn)數(shù)據(jù)，計(jì)算加密效率與加速比。

定義加密效率S為：

定義加速比r為：

表1 實(shí)驗(yàn)環(huán)境配置

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

按照上面的實(shí)驗(yàn)步驟，分別可以得到AES算法和SM4算法串行與并行的加密時(shí)間。計(jì)算對應(yīng)數(shù)據(jù)的加速比和加密效率。AES算法的實(shí)驗(yàn)數(shù)據(jù)如表2所示，加速比變化趨勢見圖3。SM4算法的實(shí)驗(yàn)數(shù)據(jù)如表3所示，加速比變化趨勢如圖4所示。

表2 AES算法加密數(shù)據(jù)統(tǒng)計(jì)表

表3 SM4算法加密數(shù)據(jù)統(tǒng)計(jì)表

圖3 AES算法性能分析圖表

圖4 SM4算法性能分析圖表

4.3 實(shí)驗(yàn)結(jié)論

通過表3的數(shù)據(jù)可以看出，就AES算法而言，加密1MB的小文件，基于CUDA的并行AES算法要比傳統(tǒng)CPU加密快11倍，效率提升達(dá)到91.28%，伴隨著文件大小逐步增加到100M，加速比與加密效率也穩(wěn)步提升，加密效率峰值達(dá)到92.70%，加速比達(dá)到13.60倍。結(jié)合表4與SM4算法進(jìn)行縱向?qū)Ρ龋琒M4算法的效率提升平均在98%，文件大小在100MB時(shí)加密效率達(dá)到98.41%，加速比達(dá)到峰值62.92倍。

實(shí)驗(yàn)數(shù)據(jù)表明，基于CUDA的SM4和AES可以以低成本的方式獲得很高的效率提升。是否可以將這種設(shè)計(jì)方法推廣到其他的對稱密碼算法呢？SM4和AES算法的一個(gè)重要的共同特征就是分組加密。各個(gè)明文分組之間互不干涉的進(jìn)行著一次加密流程，可以發(fā)現(xiàn)，這也是對稱密碼算法的特征。需要找出的是每次加密中重復(fù)且互不影響的部分，使用GPU上的線程來計(jì)算這部分內(nèi)容，然后將運(yùn)行結(jié)果返回CPU進(jìn)行整理。這樣就可將對稱密碼算法使用CUDA來重新設(shè)計(jì)，節(jié)省了CPU有限的計(jì)算資源，充分發(fā)揮了GPU閑置的計(jì)算能力，提高密碼算法的效率。

5 結(jié)束語

本文以解決大量數(shù)據(jù)加密為出發(fā)點(diǎn)，提出了基于CUDA的加密算法實(shí)現(xiàn)方法，通過對常用加密算法AES和SM4實(shí)驗(yàn)，數(shù)據(jù)表明，SM4算法最高加速比和效率可以達(dá)到98%和62.92倍。說明這種設(shè)計(jì)思路是合理的，可以推廣到其他的對稱加密算法。

[1]NVIDIA Corporation. CUDA Technology[OL].

[2]國家密碼管理局.國家密碼管理局公告第23號.[EB/OL].http://www.sca.gov.cn/app-zxfw/zxfw/bzgfcx.jsp.

[3]馬小婷等譯.深入淺出密碼學(xué)[M].北京:清華大學(xué)出版社，2012.

[4]劉金碩等著.基于CUDA的并行程序設(shè)計(jì)[M].北京:科學(xué)出版社，2014.

[5]方民權(quán)等著.GPU編程與優(yōu)化[M].北京:科學(xué)出版社， 2016.

[6]李大為，趙旭鑫，武萌. SM4密碼算法的高速流水線實(shí)現(xiàn)[J].電子器件，2007.

[7]蘇統(tǒng)華，李東等譯.CUDA并行程序設(shè)計(jì) GPU編程指南[M].北京:機(jī)械工業(yè)出版社，2014.

[8]趙開勇，汪朝輝，程亦超等譯.大規(guī)模并行處理器編程實(shí)戰(zhàn)(第二版)[M].北京:清華大學(xué)出版社，2013.

大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練項(xiàng)目（項(xiàng)目編號：IECAUC2017044）。