7-Zip加密算法的OpenCL设计与实现
摘要
随着多媒体计算机技术、计算机网络技术以及现代多媒体通信技术的高速发展，数据在传输过程中的安全问题也凸显出来，所以人们对数据加密的关注度也越来越高。数据加密也称为密码学，主要是指明文通过加密算法和加密密钥转换成密文。现在GPU的发展速度已经远远超过CPU的发展速度，几乎每年都有新一代的GPU产生，而且GPU已经不仅仅局限于3D图形、图像处理等方面，在并行计算，尤其浮点运算等方面已经取得了较大的成功。而作为图形渲染专用的处理器，GPU具有很高度的并行特征，因此GPU的通用计算研究已经成为国内外研究的重点。
2000年10月2日美国政府正式宣布，比利时密码学家Joan Daemen和VincentRijmen提出的一种加密算法RIJNDAEL作为AES加密算法。AES算法主要是指明文经过字节替代，行位移，列混合，轮密钥加四个部分变换之后形成密文。字节替代就是指指利用一个非线性的字节完成替代变换任务，它还能够独立的把状态中的字节利用替代表（s盒）进行替换操作；行位移是指行中的字节向较低位置移动，将最低位的字节交换到最高位；列混合是指将每一列看成是一个4次多项式，然后对每一列进行计算；轮密钥加是指使用一个比特和一个轮密钥进行异或操作，然后在使其作用在与之相关的状态上。在AES算法中有ECB、CBC、CFB、OFB和CTR五种加密模式，而本文研究的AES算法是CTR模式（计数模式），CTR模式加密是指对一系列的输入数据块(称为counter)进行加密，从而产生一系列的输出块，利用这个得到的输出块与明文进行异或操作得到密文。在2008年6月的WWDC大会上，美国苹果公司提出了OpenCL的设计规范。随后，Khronos Group宣布成立GPU通用计算开放行业标准工作组，以苹果的提案为基础创立OpenCL行业规范。OpenCL全称为Open Computing Languange，即为开放计算机语言。其发挥了GPU强大的计算能力，提供了一个互相开发的，兼容的，高效的，易用的开发平台。OpenCL完成了对CPU和GPU的连接，从而使GPU和CPU的结合更加紧密。
本文主要是利用OpenCL实现对7-zip的加密算法进行优化，从加密算法的本身入手，利用OpenCL的实现过程进行实现主要有一下几个步骤：OpenCL平台初始化、OpenCL运行模块、OpenCL内存管理模块等，实现对AES加密算法的改进，从而达到加速的效果。首先比较了GPU与CPU的架构，得出了GPU在运算方面的优势。另外还对AES加密算法进行了详细的研究，分析了AES加密算法的执行过程，以及还学习了执行过程中的应用到的一些数学知识。针对7-zip的加密算法提出了并行优化方案，所以我们提出了基于OpenCL的实现的AES加密算法的方案，利用GPU并行处理的特性提高7-zip的整体运行效率。经过试验得出，经过OpenCL实现后，比单纯的CPU计算提速了20%-30%。
With the high speed development of multimedia computer technology, computer networktechnology, and modern multimedia communications technology, people pay more attentionto the date encryption. data encryption, also known as cryptography, It's about turningbeplaintext to ciphertext by the encryption algorithm and encryption key. The developmentspeed of GPU is faster than the development speed of CPU, almost there will have a newgeneration of GPU every year,the GPU is not only limited to3D graphics, image processing,floating point computing, it has been made more successful in parallel computing. AsDedicated processor for graphics rendering, GPU has a higher degree of parallel, Hence,many researchers pay more attention on the computing of GPU.
In October2,2000, the U.S. government officially announced that the algorithm RIJNDAELproved to be the AES encryption algorithm, which is presented by Belgian cryptographersJoan Daemen and Vincent Rijmen. SubBytes is about the transformations task that turn thenonlinear byte to complete the alternative, it also can replace independently the bytes in thestate mention Representative (s box); ShiftRow refers to the bytes in the linemove to a lowerposition, the lowest byte swapping to the highest level; MixColumns each column as afour-degree polynomial, then calculated for each column; AddRoundKey is the operationabout using a bit and a round key to execute XOR operation, and then ralate to the state r.There are five encryption modes in the AES algorithm,it is ECB, CBC, CFB, OFB and CTR.The mode is CTR that we study in AES algorithm, and the CTR mode encryption is a seriesof input data block (counter)encryption, resulting in a series of output block, the ciphertext isby the operation output block XOR with the plaintext.In June2008, the United States Applehas proposed OpenCL specification of the design on WWDC conference. The Khronos Groupannounced the establishment of the GPU general computing on open industry standards group,based on Apple's proposal for the creation of OpenCL industry standards. The whole name ofOpenCL is Open Computing Languange, is a open computer language, and played a powerfulcomputing of GPU, it provided a mutually developed, more compatible, more efficientplatform. OpenCL could connect GPU with CPU, so that connection more closely. The paper is about the optimization of encryption algorithm in7-zip by OpenCL, there areseveral steps when optimization of encryption algorithm: the OpenCL platform initialization,the OpenCL running module, OpenCL memory managementmodule to achieve improvementsin the AES encryption algorithm, so achieve accelerated results. Firstly, we compared thearchitecture of the GPU with CPU, found the advantage of the GPU. we also a detailed studyof the AES encryption algorithm, we can do some parallel optimization for the encryptionalgorithm of7-zip, we implemented the AES encryption algorithm based on OpenCL,improved the7-zip the overall operating efficiency. After OpenCL implemented, total time isreduced than pure CPU calculation speed about20%-30%.
2000年10月2日美国政府正式宣布，比利时密码学家Joan Daemen和VincentRijmen提出的一种加密算法RIJNDAEL作为AES加密算法。AES算法主要是指明文经过字节替代，行位移，列混合，轮密钥加四个部分变换之后形成密文。字节替代就是指指利用一个非线性的字节完成替代变换任务，它还能够独立的把状态中的字节利用替代表（s盒）进行替换操作；行位移是指行中的字节向较低位置移动，将最低位的字节交换到最高位；列混合是指将每一列看成是一个4次多项式，然后对每一列进行计算；轮密钥加是指使用一个比特和一个轮密钥进行异或操作，然后在使其作用在与之相关的状态上。在AES算法中有ECB、CBC、CFB、OFB和CTR五种加密模式，而本文研究的AES算法是CTR模式（计数模式），CTR模式加密是指对一系列的输入数据块(称为counter)进行加密，从而产生一系列的输出块，利用这个得到的输出块与明文进行异或操作得到密文。在2008年6月的WWDC大会上，美国苹果公司提出了OpenCL的设计规范。随后，Khronos Group宣布成立GPU通用计算开放行业标准工作组，以苹果的提案为基础创立OpenCL行业规范。OpenCL全称为Open Computing Languange，即为开放计算机语言。其发挥了GPU强大的计算能力，提供了一个互相开发的，兼容的，高效的，易用的开发平台。OpenCL完成了对CPU和GPU的连接，从而使GPU和CPU的结合更加紧密。
本文主要是利用OpenCL实现对7-zip的加密算法进行优化，从加密算法的本身入手，利用OpenCL的实现过程进行实现主要有一下几个步骤：OpenCL平台初始化、OpenCL运行模块、OpenCL内存管理模块等，实现对AES加密算法的改进，从而达到加速的效果。首先比较了GPU与CPU的架构，得出了GPU在运算方面的优势。另外还对AES加密算法进行了详细的研究，分析了AES加密算法的执行过程，以及还学习了执行过程中的应用到的一些数学知识。针对7-zip的加密算法提出了并行优化方案，所以我们提出了基于OpenCL的实现的AES加密算法的方案，利用GPU并行处理的特性提高7-zip的整体运行效率。经过试验得出，经过OpenCL实现后，比单纯的CPU计算提速了20%-30%。
With the high speed development of multimedia computer technology, computer networktechnology, and modern multimedia communications technology, people pay more attentionto the date encryption. data encryption, also known as cryptography, It's about turningbeplaintext to ciphertext by the encryption algorithm and encryption key. The developmentspeed of GPU is faster than the development speed of CPU, almost there will have a newgeneration of GPU every year,the GPU is not only limited to3D graphics, image processing,floating point computing, it has been made more successful in parallel computing. AsDedicated processor for graphics rendering, GPU has a higher degree of parallel, Hence,many researchers pay more attention on the computing of GPU.
In October2,2000, the U.S. government officially announced that the algorithm RIJNDAELproved to be the AES encryption algorithm, which is presented by Belgian cryptographersJoan Daemen and Vincent Rijmen. SubBytes is about the transformations task that turn thenonlinear byte to complete the alternative, it also can replace independently the bytes in thestate mention Representative (s box); ShiftRow refers to the bytes in the linemove to a lowerposition, the lowest byte swapping to the highest level; MixColumns each column as afour-degree polynomial, then calculated for each column; AddRoundKey is the operationabout using a bit and a round key to execute XOR operation, and then ralate to the state r.There are five encryption modes in the AES algorithm,it is ECB, CBC, CFB, OFB and CTR.The mode is CTR that we study in AES algorithm, and the CTR mode encryption is a seriesof input data block (counter)encryption, resulting in a series of output block, the ciphertext isby the operation output block XOR with the plaintext.In June2008, the United States Applehas proposed OpenCL specification of the design on WWDC conference. The Khronos Groupannounced the establishment of the GPU general computing on open industry standards group,based on Apple's proposal for the creation of OpenCL industry standards. The whole name ofOpenCL is Open Computing Languange, is a open computer language, and played a powerfulcomputing of GPU, it provided a mutually developed, more compatible, more efficientplatform. OpenCL could connect GPU with CPU, so that connection more closely. The paper is about the optimization of encryption algorithm in7-zip by OpenCL, there areseveral steps when optimization of encryption algorithm: the OpenCL platform initialization,the OpenCL running module, OpenCL memory managementmodule to achieve improvementsin the AES encryption algorithm, so achieve accelerated results. Firstly, we compared thearchitecture of the GPU with CPU, found the advantage of the GPU. we also a detailed studyof the AES encryption algorithm, we can do some parallel optimization for the encryptionalgorithm of7-zip, we implemented the AES encryption algorithm based on OpenCL,improved the7-zip the overall operating efficiency. After OpenCL implemented, total time isreduced than pure CPU calculation speed about20%-30%.
引文
[1] Wen-mei W. Hwu. GPU Computing Gems Emerald Edition, Morgan KaufmannPublishers Inc[M]. San Francisco, CA, USA,2011.
[2] Zhe Fan, Feng Qiu, Arie Kaufman, Suzanne Yoakum-Stover. GPU Cluster for HighPerformance Computing[C]. IEEE Computer Society Washington, DC, USA,2004.
[3] Thomas B. Jablin, Prakash Prabhu, James A. Jablin, Nick P. Johnson, Stephen R.Beard, David I. August. Automatic CPU-GPU communication management andoptimization[C], ACM New York, NY, USA,2011.
[4]邵飞,张淄楠,张翼.基于AES加密算法的GPU高性能计算[C]. ICCSN,2010.
[5] Nhat-Phuong Tran, Myungho，Sugwon Hong, Seung-Jae Lee. Parallel Execution ofAES-CTR Algorithm Using Extended Block Size[C]. IEEE Computer SocietyWashington, DC,2011
[6] Keisuke Iwai, Takakazu Kurokawa, Naoki Nisikawa. AES EncryptionImplementation on CUDA GPU and Its Analysis[C]. IEEE Computer SocietyWashington, DC,2010.
[7] Roger Ferrer, Judit Planas, Pieter Bellens, Alejandro Duran, Marc Gonzalez, XavierMartorell, Rosa M. Badia, Eduard Ayguade, Jesus Labarta. Optimizing theexploitation of multicore processors and GPUs with OpenMP and OpenCL[C]. the23rd international conference on Languages and compilers for parallel computing,2011.
[8] Georg Sch nberger, Jürgen Fu. GPU-assisted AES encryption using GCM[C]. the12th IFIP TC6/TC11international conference on Communications and multimediasecurity,2011.
[9] Khronos. Launches Heterogeneous Computing Initiative[M]. Khronos Group.16June2008. Retrieved18June2008.
[10] Radu Tomoiaga, Mircea Stratulat. AES Performance Analysis on SeveralProgramming Environments. Operating Systems or Computational Platforms[C].IEEE Computer Society Washington, DC,2010.
[11] Owen Harrison, John Waldron. Practical symmetric key cryptography on moderngraphics hardware[C]. USENIX Association Berkeley,2008.
[12] Aaftab Munshi, The OlmnCL Specification[M]. Kh. ronol$OpenCL Working Group2009.
[13] Hennessy J L, Patterson D A.Computer Architecture z A Quantitative Approach[C].IEEE COMPUTING10.JUL-SEP2011,Vol.10,No.3.
[14] Schaminee, H; Aerts, H. IMPACT Short and Winding Road: Software in CarNavigation Systems[C]. IEEE SOFTWARE, Vol.28, No.4,2011.
[15] Moeckel M., Wiedemann C. Flegel S Using parallel computing for the displaysimulation of the space debris environment[C]. ADVANCES IN SPACERESEARCH JUL12011.
[16] OpenCL gets touted in Texas[M]. MacWorld.20November2008. Retrieved12June2009.
[17] The Khronos Group Releases OpenCL1.0Specification[M]. Khronos Group.8December2008. Retrieved12June2009.
[18] David.Kirk,Wen-mei W.Hwu.大规模并行处理器编程实战[M].清华大学出版社,2010.
[19] AMD上海研发中心.跨平台的多核与众核编译讲义——OpenCl的方式[M].AMD,2010.3.
[20] NVIDIA.NVIDIA CUDA.统一计算设备架构编程指南[M]. NVIDIA,2007.
[21]吴世忠,祝世雄,张文政.应用密码学:协议、算法与C源程序[M].机械工业出版社,2000.
[22]范九伦,刘宏月.密码学基础[M].西安电子科技大学出版社.2008.
[23](Behrouz A.Forouzan)福罗赞/马振晗,贾军保.密码学与网络安全[M].清华大学出版社,2009.
[24] DouglasR Stinson.密码学原理与实践[M].电子工业出版社,2009.
[25]何大可,唐小虎.现代密码学[M].人民邮电出版社,2009.
[26]徐茂智,冯荣权.密码学进展-中国密码学会2010年会论文集[C]. Science PressUSA Inc2010.
[27]中国密码学会.中国密码学发展报告2009[C].电子工业出版社,2010.
[28]桑德斯. GPU高性能编程CUDA实战[M].机械工业出版社,2011.
[29]仇德元. GPGPU编程技术——从GLSL,CUDA到OpenCL[M].机械工业出版社,2011.
[30] Stanley B. Lippman Barbara E. Moo Josée LaJoie. C++Primer中文版(第4版）[M].人民邮电出版社,2006.
[31]陈国良.并行计算──结构算法编程(修订版)[M].高等教育出版社,2003.
[32]休斯. C++多核高级编程[M].清华大学出版社,2010.03.
[2] Zhe Fan, Feng Qiu, Arie Kaufman, Suzanne Yoakum-Stover. GPU Cluster for HighPerformance Computing[C]. IEEE Computer Society Washington, DC, USA,2004.
[3] Thomas B. Jablin, Prakash Prabhu, James A. Jablin, Nick P. Johnson, Stephen R.Beard, David I. August. Automatic CPU-GPU communication management andoptimization[C], ACM New York, NY, USA,2011.
[4]邵飞,张淄楠,张翼.基于AES加密算法的GPU高性能计算[C]. ICCSN,2010.
[5] Nhat-Phuong Tran, Myungho，Sugwon Hong, Seung-Jae Lee. Parallel Execution ofAES-CTR Algorithm Using Extended Block Size[C]. IEEE Computer SocietyWashington, DC,2011
[6] Keisuke Iwai, Takakazu Kurokawa, Naoki Nisikawa. AES EncryptionImplementation on CUDA GPU and Its Analysis[C]. IEEE Computer SocietyWashington, DC,2010.
[7] Roger Ferrer, Judit Planas, Pieter Bellens, Alejandro Duran, Marc Gonzalez, XavierMartorell, Rosa M. Badia, Eduard Ayguade, Jesus Labarta. Optimizing theexploitation of multicore processors and GPUs with OpenMP and OpenCL[C]. the23rd international conference on Languages and compilers for parallel computing,2011.
[8] Georg Sch nberger, Jürgen Fu. GPU-assisted AES encryption using GCM[C]. the12th IFIP TC6/TC11international conference on Communications and multimediasecurity,2011.
[9] Khronos. Launches Heterogeneous Computing Initiative[M]. Khronos Group.16June2008. Retrieved18June2008.
[10] Radu Tomoiaga, Mircea Stratulat. AES Performance Analysis on SeveralProgramming Environments. Operating Systems or Computational Platforms[C].IEEE Computer Society Washington, DC,2010.
[11] Owen Harrison, John Waldron. Practical symmetric key cryptography on moderngraphics hardware[C]. USENIX Association Berkeley,2008.
[12] Aaftab Munshi, The OlmnCL Specification[M]. Kh. ronol$OpenCL Working Group2009.
[13] Hennessy J L, Patterson D A.Computer Architecture z A Quantitative Approach[C].IEEE COMPUTING10.JUL-SEP2011,Vol.10,No.3.
[14] Schaminee, H; Aerts, H. IMPACT Short and Winding Road: Software in CarNavigation Systems[C]. IEEE SOFTWARE, Vol.28, No.4,2011.
[15] Moeckel M., Wiedemann C. Flegel S Using parallel computing for the displaysimulation of the space debris environment[C]. ADVANCES IN SPACERESEARCH JUL12011.
[16] OpenCL gets touted in Texas[M]. MacWorld.20November2008. Retrieved12June2009.
[17] The Khronos Group Releases OpenCL1.0Specification[M]. Khronos Group.8December2008. Retrieved12June2009.
[18] David.Kirk,Wen-mei W.Hwu.大规模并行处理器编程实战[M].清华大学出版社,2010.
[19] AMD上海研发中心.跨平台的多核与众核编译讲义——OpenCl的方式[M].AMD,2010.3.
[20] NVIDIA.NVIDIA CUDA.统一计算设备架构编程指南[M]. NVIDIA,2007.
[21]吴世忠,祝世雄,张文政.应用密码学:协议、算法与C源程序[M].机械工业出版社,2000.
[22]范九伦,刘宏月.密码学基础[M].西安电子科技大学出版社.2008.
[23](Behrouz A.Forouzan)福罗赞/马振晗,贾军保.密码学与网络安全[M].清华大学出版社,2009.
[24] DouglasR Stinson.密码学原理与实践[M].电子工业出版社,2009.
[25]何大可,唐小虎.现代密码学[M].人民邮电出版社,2009.
[26]徐茂智,冯荣权.密码学进展-中国密码学会2010年会论文集[C]. Science PressUSA Inc2010.
[27]中国密码学会.中国密码学发展报告2009[C].电子工业出版社,2010.
[28]桑德斯. GPU高性能编程CUDA实战[M].机械工业出版社,2011.
[29]仇德元. GPGPU编程技术——从GLSL,CUDA到OpenCL[M].机械工业出版社,2011.
[30] Stanley B. Lippman Barbara E. Moo Josée LaJoie. C++Primer中文版(第4版）[M].人民邮电出版社,2006.
[31]陈国良.并行计算──结构算法编程(修订版)[M].高等教育出版社,2003.
[32]休斯. C++多核高级编程[M].清华大学出版社,2010.03.