基于GPU的密文分组随机链接加密模式的研究*

2015-03-27吴伟民李坚锐林志毅

计算机工程与科学 2015年1期

关键词：明文密文密钥

吴伟民, 李坚锐,林志毅

(广东工业大学计算机学院，广东广州 510006)

基于GPU的密文分组随机链接加密模式的研究*

吴伟民, 李坚锐,林志毅

(广东工业大学计算机学院，广东广州 510006)

大部分传统的分组加密模式不能有效应用于GPU上。分析传统加密工作模式，结合GPU并行计算的要求提出一种满足GPU执行要求的、高效的、安全的分组加密模式——密文分组随机链接加密模式(RCBC)。该模式不但执行效率高，并且增加了破解难度。实验结果表明，在CPU_GPU上采用RCBC的密码算法在处理数据时，呈现出高效的处理能力。

GPU；数据加密；工作模式

1 引言

自1999年NVIDIA发布第一款GPU(Graphic Processing Unit)以来，GPU的发展一直保持很高的速度，随着以CUDA(Compute Unified Device Architecture)为代表的GPU通用计算API(Application Programming Interface)的普及，GPU在计算机中的作用将更为重要，GPU的含义已经从图形处理器扩展为通用处理器(General Purpose Unit)。利用GPU的强大计算能力，能为大数据的处理提供新的解决方案[1]。

随着信息时代的发展，数据安全也越显重要，其中对数据进行保护的重要手段是进行加密，但是在明文与密文的转换过程中，需要大量的运算。当对大量数据加解密时，对CPU提出较高的要求。因此，将加密解密过程中最耗时间的部分交给GPU完成，能有效提高加密的效率。国内外对运用GPU加速密码算法做了大量研究，朱兴锋[2]提出基于GPU的高效IDEA加密算法的实现，Addison W[3]提出AES在GPU上的实现，随后叶剑等人[4]也提出基于GPU的AES快速实现，以上研究都表明GPU能对密码算法进行有效加速。但是，它们都是针对具体的分组密码算法而言的，缺少对CPU_GPU协处理下分组密码工作模式的深入描述。

分组密码工作模式是利用分组密码解决实际问题的密码方案，好的模式可以弥补分组密码的缺陷，不好的工作模式可能带来隐患。大部分传统分组加密模式不能有效应用于GPU上。虽然电子密码本ECB(Electronic Codebook)模式能在保持密码学特征的同时易于并行实现，但众所周知，ECB对分组重放等攻击缺乏高强度的抵御能力[5]，所以对于大数据量的加密更适合采用其它模式，其中密码分组链拉CBC(Cipher-Block Chaining)是最为常用的工作模式，但由于其串行的特性，无法有效应用于并行体制上。殷新春[6,7]在CBC基础上提出并行的PCBC(Parallel CBC)模式，通过模运算实现块间的并行，但其安全性依赖于对n的保密，并且缺乏灵活性，运用该模式难以发挥GPU与CPU协处理的优势。而关于CPU_GPU下的分组密码模型研究少之又少。因此，本文在CBC的基础上，根据CPU_GPU协处理下的各自特征提出分组随机链接模式RCBC(RandomCipher-BlockChaining)。

2 相关知识

2.1 GPU编程

现代的图像处理器(GPU)把数据并行计算引入到几乎每台计算机中。这些处理器有能力加速很多应用程序，而不仅仅局限于实时渲染。其中，GPU的编程模型与CPU的编程模型完全不同，GPU使用的是SIMT模型，该编程模型的主要目标之一是高效计算。SIMT的好处是无需开发者费力把数据凑成合适的矢量长度，同时SIMT允许每个线程有不同的分支。在这种编程模型中，对数据流的连续操作便是程序，当对一个处理器编程时，将以更加结构化的方式访问存储器。而由于在一个流元素上的计算不会影响其他元素的计算，所以保证了这种数据的并行性。模型所给予的数据并行性使得GPU的处理速度能比串行处理器快很多。文献[1]给出了GPU编程的参考内容。

2.2 分组密码模式

(1)分组密码(BlockCipher)是一种对称密钥密码[8]，它的特点是将明文分为多个等长的组，并用相同的密钥对每组分别进行加密与解密，其中典型的加密算法有DES和AES等，不同的分组密码算法又可以配合不同的工作模式。

(2)电子密码本(ECB)是使用分组密码的最简单方式，加密方式为:yt=Ekey(xi)，对应解密过程为:xi=Dkey(yi)。各组可以独立进行加解密而不相互干涉。ECB可以在GPU上完美地执行，但是ECB过于简单，不能很好地隐藏明文的模式，所以夏春林等人[9]在GPU上实现AES时，采用改进的ECB模式，在进行密码运算前采用序列消除明文中相同的数据区域。

(3)密码分组链接(CBC)是一种基于反馈机制的分组模式。前一个分组的加密结果被反馈到当前分组的加密中。具体如下，从一个初始加密参数项IV开始，定义y0=IV，然后使用下式构造y1～yt:

yi=Ekey(xi⊕yi-1),i≥1

(1)

解密过程:

y0=IV,xi=Dkey(yi)⊕yi-1,i≥1

(2)

简单地来说，每一组被用来修改下一组的加密，每组的密文不仅依赖于产生它的明文组，而且依赖于前面所有的明文分组。虽然CBC增加了密文复杂程度，使得攻击难以实施，但是由于该模式中组与组间存在数据相关性，导致无法并行处理各组。因此，将应用CBC模式的密码算法运行于GPU环境下，其效率极低，本文实验章节将给出相关数据。

(4)其他模式。输出反馈OFB(Output Feed Back)以及密码反馈CFB(Cipher Feed Back)与CBC类似，这些模式为了增加密码的安全性均在组与组之间形成依赖关系，从而无法在并行机制下实现，文献[10]给出了相关描述及近年来的研究现状。

3 密文分组随机链接加密模式设计与实现

RCBC是在CBC加密模式的基础上，针对CPU_GPU协处理的特征，在CPU上运用伪随机算法产生随机的链接表(Tr)及向量表(TIV)，再将大量需处理的数据传入GPU中进行快速加密，发挥CPU与GPU的各自优势。

3.1 拆分

与传统的分组加密模式相同，明文以及密文进行加解密前都需要进行分组，每组大小为64位或者128位。设想把每组当作是单独的节点，那么CBC可以看作成链式结构的模型，其特性是后一个节点依赖于前一个节点。前后节点的依赖性决定了CBC只能串行地处理，因此对链式结构进行拆分至关重要。规律性地切断原节点间的关系，生成多个分链，并且各个分链使用独立的VI加密参数项作为新的输入，使分链间相互独立，从而分链能被并行处理。

若拆分后分链的长度均为K，则称该种拆分方式为等长拆分。当K=1时，拆分的CBC模式与ECB模式的差异在于VI加密参数项的输入。如图1所示，是将原来的链式等长地拆分成三个节点为一个分链的例子。

Figure 1 Isometric splitting

通过拆分，使得CBC满足了并行计算的要求，同时有效地防止了错误的扩散和传播。需注意的是，使用过短的等长拆分方式，明文中重复的内容在密文中会有所体现，仍难以抵抗相关攻击[11]。因此，本文采用非等长及随机的拆分方式，并用以下方式实现。

3.2 随机链接

RCBC采用非等长的拆分，即拆分后的分链长短各异，避免等长拆分所产生的规律性。但是，这会导致各分链计算规模大小不一致的问题，为了保证并行时任务完成时间相近，避免短板效应带来的影响，分链中节点数目必须得到有效限制。设分链的最大链接节点数为Kmax(Kmax> 0)，通过设定分链中的节点数必须小于或等于Kmax来限制分链中拥有的节点，解决由于并行计算粒度粗细差异而产生的效益问题。由定义可知，当Kmax越小，分链的平均长度也越小，利于整体的并行计算。

为了增加该方案的复杂性，组成分链的节点成员是随机产生的，分链中的节点在原链式中可以是连续的或者是间隔的，这取决于具体采用的链接规则。本文采用随机链接表(Tr)实现具体的链接规则，根据随机链接表决定节点间链接关系，并约定采用连续的节点作为分链成员。具体如下，从多组初始加密参数项IV开始，定义y0=IV0,…,yk=IVk(k为未知量)，然后使用下式构造y1～yt:

yi=Ekey(xi⊕R),i≥1

(3)

R=Tr(i)=yi-1orIVk

(4)

解密过程:

y0=IV0,xi=Dkey(yi)⊕R,i≥1

(5)

R=Tr(i)=yi-1orIVk

(6)

随机链接表与链接规则的对应关系如图2所示，设定Kmax=3。随机链接表中第一个1表示明文第1组为单独一个分链，接下来的2表示明文第2、3组为第二个分链成员。根据随机链接表对拆分出分链，如此类推下去，直到将i组成员分到各分链中。

Figure 2 Rules for random grouping

对于随机链接表的产生，本文选取混沌映射来实现。其中，Logistic[12]映射生成混沌序列已广泛应用于密码学中，其安全性及效率已得到许多研究的证实。如图3所示，将密钥及附加参数作为输入，结合Logistic映射在CPU上生成随机链接表(Tr)及分链初始向量表(TIV)。

Figure 3 Generate Tr and TIV

其中对于Tr及TIV的大小，将通过分组总数i、Kmax及阈值L计算出来。设定分组密码每组m位，当i≦2L时，则所需Tr及TIV的大小设定为：sizeof(Tr)=(i/Kmax/m)* 2Kmax；sizeof(TIV)=i/(Kmax/2)，其中以m位为一单位。当i>2L，则设定所需Tr及TIV的大小为：sizeof(Tr)=(2L/Kmax/m)* 2Kmax；sizeof(TIV)=2L/(Kmax/2)，通过阀值L控制Tr及TIV的大小，避免处理大数据块时过度膨胀。同时，周期性变换使用TIV及Tr，从而满足RCBC的输入要求。

3.3 CPU_GPU上的实现

在CPU_GPU上实现应用RCBC的密码算法，其具体步骤如下：

(1)程序初始阶段，通过主机(CPU)读入明文、附加参数以及密钥，明文进行划分补齐，密钥进行位数检测。密钥及附加参数结合Logistic映射，生成所需随机链接表(Tr)及初始向量表(TIV)。

(2)主机(CPU)计算明文、Tr及TIV所需空间，向设备(GPU)申请内存。将数据从主机(CPU)内存复制到设备(GPU)内存。

(3)根据Tr以及组数(i)计算产生分链数M。再根据分链数M分配所需的线程块以及线程块中的线程数，其中需满足：

M≤线程块 × 线程块中的线程

(7)

(4)配置核函数(kernel)参数，执行核函数。将产生大于或等于M个线程副本，对数据进行并行加密处理。其中每个线程对应一个拆分后的分链。

(5)并行计算过程中，各个线程在TIV读取独立的IV，再对Tr进行查询，计算出分链首地址，以及对应分链的节点数，得到待处理的数据，将数据交给密码算法Ekey(x)完成具体加密工作。

(6)等待GPU完成所有分链的处理，将处理后的结果传回主机(CPU)中，完成RCBC模式下CPU_GPU协处理的加密过程。

对于分组加密算法而言，解密的过程与加密的过程是相对应的，此处的关键在于保证Tr及TIV在加解密算法前后的一致性。

4 安全性分析

对RCBC可能的攻击方法大致有四种：

(1)Vaudenay S[13]对CBC实施的填补攻击;

(2)逐组破解分组密码得到明文；

(3)通过攻击分组密码找出分链的链接规则；

(4)对密钥及附加参数进行穷举，直到找到有意义的明文或与得到的密文相符合。

对上面的攻击方法进行可行性分析。

对于第(1)种攻击，其依据在于 CBC模式需填补位数使加密长度为分组长度的倍数。利用该弱点，攻击者尝试填补数据，并向语言机询问结果，从而对CBC进行破解[13]。但是，对于RCBC而言，由于各分链间是相互独立的，并且各分链的IV均不同,所以对于攻击者而言，最多只能分析出拥有末端分组的分链内容，不可能通过该方式获得整个明文内容。

对于第(2)种攻击，攻击者只能够使用穷举密钥的方法进行破译，对于ECB而言，攻击者只需要找到一个密钥，使得它对每一组密文解密后的结果有意义，即可破解该密码。但是，对于RCBC而言，由于每个分链使用了不同的初始向量，而分链内采用CBC，使得每组明文并不单单依赖于密钥，所以对一组密文的破译不能对整个RCBC构成威胁，这种攻击等同于猜想明文，显然毫无意义。

对于第(3)种攻击，由于链接规则的产生依赖于混沌映射，使其具有很强的随机性。同时，攻击者无法获取更多由同一IV输入所加密的明文/密文对，攻击者只能用穷举的方法找出链接规则。当链长为N，Kmax=k时，链接的方式达k×N！种，N>256时，其数量级已达到2256。以1 Mb大小的文件为例，64位为一组，其链长为1.25×105，假设Kmax=4，即便攻击者得到了密钥，而在不知链接规则的情况下，对信息进行强力攻击，至少需要2128的计算量，按照每微秒加密一百万次的运算能力，需要用时5.9×1030年，而随着N的变大，可选择的链接规则也随之膨胀。因此，在链接规则保密的情况下，攻击者对较大数据进行攻击显得无力。

对于第(4)种攻击，假设攻击者已得知伪随机函数来生成链接规则，则在总链长足够长及Kmax够大的情况下，可以通过增大混沌映射输入参数(P)的位数来保障其安全性。具体做法是将P作为附加的伪密钥与原密钥结合，假设P的位数为 512位，密钥key的位数为64位，将其结合，使得密钥空间达2576。以目前的计算水平来看，已经完全能够抵抗穷举攻击了。而随着计算技术的进步，P的位数也能随之增大，使得计算水平的发展不对RCBC构成过大的威胁，因此对于RCBC来说，即使攻击者拥有计算能力很强的计算机，仍难以快速地进行暴力破解。

5 性能分析

5.1 测试环境

硬件：CPU 为Intel Core(TM) i3 3.30 GHz，4 GB内存，GPU为GTX250 650 MHz 516 MB显存，128个流处理器。

软件：Windows7系统，Visual Studio 2010，CUDA Toolkit 4.0。

5.2 测试结果

本文进行了两个性能对比实验，一个是在CPU环境下，CBC及RCBC的对比实验。另一个是RCBC在CPU环境及CPU_GPU环境上的对比实验。实验结果如表1～表2所示，其中，加密算法采用AES，Kmax取值为3,阈值L取值为18。表2中GPU的计算时间包括数据从CPU到GPU所花的时间。

Table 1 Comparison of CBC and RCBC on CPU

Table 2 Implementation of RCBC on CPU and CPU_GPU

通过观察表1可以看出，进行数据量较小的加密时，AES_RCBC的吞吐量显然低于AES_CBC，这是由于RCBC需要产生Tr及TIV导致的，但随着数据的增大，AES_RCBC的吞吐量与AES_CBC的吞吐量相差无几。说明了RCBC应用于大数据量处理时，其随机性的增加及随机的处理方式并不会对性能造成影响。

通过观察表2可以看出，在处理大量数据时，RCBC在CPU及CPU_GPU上有着明显的差异，运用RCBC的AES算法在CPU_GPU上的执行时间更快，当输入加密文件的大小为512 MB时，速度达到了85.3 M/s，这时AES_RCBC_CPU_GPU上的处理速度是AES_RCBC_CPU上的4.2倍。在CPU_GPU下，密码算法有明显的加速。

本文还测量了应用CBC的AES算法在GPU上的性能，其吞吐量维持在0.8 M/s左右，与采用RCBC的AES在CPU_GPU的性能相差甚远。另外，将AES替换成其他主流分组密码算法重复以上实验，实验数据表明，采用RCBC的DES、Camellia及IDEA均能达到4倍左右的加速。

以上实验表明了应用RCBC的密码算法能在GPU上有效运行，且根据 Amdahl 定律可知，当数据量不大时，加速效果并不明显；而随着数据量的增大，产生Tr、TIV所需时间与数据在CPU_CPU之间的传输时间所占用的比例越来越小，从而加速效果越来越明显。

6 结束语

本文对现有分组加密模式进行研究分析，在CBC的基础上，结合CPU_GPU各自特征需要，提出了新的密文分组工作模式。通过非等长拆分及增加随机性，使CBC能应用于GPU上，同时数据相关性的切断有效地防止了错误的扩散，并能抵御CBC所不能抵御的填补攻击。最后，在CUDA环境下实现了RCBC，结果表明该模式拥有良好的性能，特别是在处理大数据时，表现出了较强的处理能力。

[1] Zhang Shu,Chu Yan-li.GPU performance computing-CUDA[M].Beijing:China Water Power Press,2009.(in Chinese)

[2] Zhu Xing-feng. Design and implementation of efficient IDEA encryption algorithm based on CUDA[J]. Computer and Modernization, 2011(12):48-52.(in Chinese)

[3] Addison W.AES encryption and decryption on the GPU [M].GPU Gems 3 GPU Computing, NY:Microsoft Research,2007.

[4] Ye Jian,Li Li-xin.Fast implementation of AES based on GPU [J]. Computer Engineering and Design, 2010,31(2):256-259.(in Chinese)

[5] Zhang Ji-li, Dong Xi-wei, Xu Shao-wen. Security defect of block cipher mode—ECB mode[J]. Science& Technology Information, 2007(28):341:343.(in Chinese)

[6] Yin Xin-chun,Chen Wei-he,Xie Li.Parallel processing model of the block cipher[J].MINI-MICRO SYSTEMS, 2005,26(4):601-603. (in Chinese)

[7] Yin Xin-chun.Research on parallel cipher[D]. Nanjing:Nanjing University, 2003.(in Chinese)

[8] Fen Deng-guo. Status quo and trend of cryptography[J]. Journal of China Institute of Communications,2002,23(5):18-25. (in Chinese)

[9] Xia Chun-lin, Zhou De-yun, Zhang Kun. CUDA based high-efficiency implementation of AES algorithm[J]. Application Research of Computers, 2013,30(6):1097-1910. (in Chinese)

[10] Wu Wen-ling, Feng Deng-guo. The state-of-art of research on block cipher mode of operation[J].Chinese Journal of Computers,2006,29(1):21-34.(in Chinese)

[11] Li Chao, Sun Bing, Li Rui-lin. Attack method and examples analysis of block cipher[M]. Beijing:Science Press, 2010.(in Chinese)

[12] Wang Yong, Li Sheng-zhu. Block encryption algorithm based on multiple logistic maps[J]. Computer Engineering, 2007,33(22):162-164.(in Chinese)

[13] Vaudenay S.Security flaws induced by CBC padding—applications to SSL,IPSEC,WTLS[C]∥Proc of the International Conference on the Theory and Applications of Cryptographic Techniques,2002:534-545.

附中文参考文献：

[1] 张舒,褚艳利. GPU高性能运算之CUDA [M].北京:中国水力水电出版社,2009.

[2] 朱兴锋.基于CUDA的高效IDEA加密算法设计与实现[J].计算机与现代化,2011,(12):48-52.

[4] 叶剑,李立新.基于GPU的AES快速实现[J].计算机工程与设计,2010,31(2):256-259.

[5] 张吉力,董西伟,徐少文.浅谈分组密码算法模式—ECB 模式的安全缺陷[J].科技信息,2007(28):341-343.

[6] 殷新春,陈伟鹤,谢立.分组密码的并行工作模式[J].小型微型计算机系统,2005,26(4):601-603.

[7] 殷新春.密码算法并行化研究[D].南京:南京大学,2003.

[8] 冯登国.国内外密码学研究现状及发展趋势[J].通信学报,

2002,23(5):18-25.

[9] 夏春林,周德云,张堃.AES算法的CUDA高效实现方法[J].计算机应用研究,2013,30(6):1907-1910.

[10] 吴文玲,冯登国. 分组密码工作模式的研究现状[J].计算机学报,2006,29(1):21-34.

[11] 李超,孙兵,李瑞林.分组密码的攻击方法与实例分析[M].北京:科学出版社,2010.

[12] 王永,李盛竹.基于多个Logistic映射的分组加密算法[J].计算机工程,2007,33(22):162-164.

WU Wei-min,born in 1956,professor,CCF member(E200030580M),his research interests include data structure and algorithm,visual computing,compiler, virtual machine technology, and intelligent system.

李坚锐(1989-),男,广东汕头人，硕士生，研究方向为数据安全和软件保护。E-mail:372695978@qq.com

LI Jian-rui,born in 1989,MS candidate,his research interests include data security, and software protection.

林志毅(1979-),男,福建连江人，博士，讲师，研究方向为自然计算和模式识别。E-mail:16045411@qq.com

LIN Zhi-yi,born in 1979,PhD,lecturer,his research interests include natural computing, and pattern recognition.

Research on the cipher block random link encryption mode based on GPU

WU Wei-min，LI Jian-rui，LIN Zhi-yi

(School of Computer Science,Guangdong University of Technology,Guangzhou 510006,China)

Most of the traditional block cipher modes cannot be applied effectively on GPU. We study the traditional encryption models and put forward a packet encryption model cipher,called block random link encryption mode (RCBC),which is efficient,safe and meets parallel computing requirements.This model has a high efficiency,and increases the difficulty of decryption at the same time.Experimental results show that the proposed encryption algorithm has efficient processing ability on CPU_GPU.

GPU;data encryption;operation mode

1007-130X(2015)01-0036-06

2013-04-10;

2013-09-23基金项目：高性能计算中心多策略数据安全保护支撑平台研发(20012Y2-00046)

TP309.7

10.3969/j.issn.1007-130X.2015.01.006