1000字范文 > 山东大学软件工程应用与实践——使用CUDA/GPU技术加速密码运算（第四周）

山东大学软件工程应用与实践——使用CUDA/GPU技术加速密码运算（第四周）

时间：2023-05-07 17:34:52

SC@SDUSC

上一章大致分析了AES在高级程序语言中的实现，这里再给出c++实现AES的完整源代码，帮助理解。

#include <iostream>#include <cstdlib>#include <stdio.h>using namespace std;typedef unsigned char byte;struct word{byte wordKey[4];};class AES{public:AES(){initRcon();};// ~AES();void setCipherKey(byte key[]);void setPlainText(byte plain[]);//void keyExpansion(byte key[], word w[]);word rotWord(word w);word subWord(word w);word wordXOR(word w1, word w2);//functions in encryption and decryptionvoid encryption();void processEncryption();void addRoundKey(word in[], int round);void subByte(word in[]);void shiftRows(word in[]);void mixColumn(word in[]);byte GFMultiplyByte(byte L, byte R);void decryption();void processDecryption();void invShiftRows(word in[]);void invSubByte(word in[]);void invMixColumn(word in[]);void initRcon();void showWord(word w[], int len);void showMesage();private:byte cipherKey[16];word plainText[4];word cipherText[4];word deCipherText[4];static const int Nb=4, Nk=4, Nr=10;word Rcon[11];word wordKey[44];static const byte SBox[16][16];static const byte invSBox[16][16];static const byte mixColumnMatrix[4][4];static const byte invmixColumnMatrix[4][4];};void AES::showWord(word w[], int len){int i,j;for(i=0; i<len; i++){for(j=0; j<4; j++){printf("%x ", w[i].wordKey[j]);}}cout<<endl;}void AES::showMesage(){cout<<"plainText:"<<endl;showWord(plainText, 4);cout<<"wordKey:"<<endl;showWord(wordKey, Nb*(Nr+1));cout<<"cipherText:"<<endl;showWord(cipherText, 4);cout<<"deCipherText:"<<endl;showWord(deCipherText, 4);}// initialize the plainText--trans plaintext from vector to state_matrixvoid AES::setPlainText(byte plain[]){int i;for(i=0; i<16; i++){plainText[i/4].wordKey[i%4] = plain[i];}}//initialize the key--from vector to state_matrixvoid AES::setCipherKey(byte key[]){int i;for(i=0; i<16; i++){cipherKey[i] = key[i];}keyExpansion(cipherKey, wordKey);}//initialize the Rconvoid AES::initRcon(){int i,j;for(i=0; i<4; i++)for(j=0; j<4; j++){Rcon[i].wordKey[j] = 0x0;}Rcon[1].wordKey[0] = 0x01;Rcon[2].wordKey[0] = 0x02;Rcon[3].wordKey[0] = 0x04;Rcon[4].wordKey[0] = 0x08;Rcon[5].wordKey[0] = 0x10;Rcon[6].wordKey[0] = 0x20;Rcon[7].wordKey[0] = 0x40;Rcon[8].wordKey[0] = 0x80;Rcon[9].wordKey[0] = 0x1b;Rcon[10].wordKey[0] = 0x36;}//initialize the const of mixColumn and invMixColumnconst byte AES::mixColumnMatrix[4][4] = {{0x02, 0x03, 0x01, 0x01},{0x01, 0x02, 0x03, 0x01},{0x01, 0x01, 0x02, 0x03},{0x03, 0x01, 0x01, 0x02}};const byte AES::invmixColumnMatrix[4][4] = {{0x0e, 0x0b, 0x0d, 0x09},{0x09, 0x0e, 0x0b, 0x0d},{0x0d, 0x09, 0x0e, 0x0b},{0x0b, 0x0d, 0x09, 0x0e}};//initialize SBoxconst byte AES::SBox[16][16] = {{0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76},{0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0},{0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15},{0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75},{0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84},{0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf},{0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8},{0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2},{0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73},{0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb},{0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79},{0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08},{0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a},{0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e},{0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf},{0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16}};const byte AES::invSBox[16][16] = {0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38, 0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb,0x7c, 0xe3, 0x39, 0x82, 0x9b, 0x2f, 0xff, 0x87, 0x34, 0x8e, 0x43, 0x44, 0xc4, 0xde, 0xe9, 0xcb,0x54, 0x7b, 0x94, 0x32, 0xa6, 0xc2, 0x23, 0x3d, 0xee, 0x4c, 0x95, 0x0b, 0x42, 0xfa, 0xc3, 0x4e,0x08, 0x2e, 0xa1, 0x66, 0x28, 0xd9, 0x24, 0xb2, 0x76, 0x5b, 0xa2, 0x49, 0x6d, 0x8b, 0xd1, 0x25,0x72, 0xf8, 0xf6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xd4, 0xa4, 0x5c, 0xcc, 0x5d, 0x65, 0xb6, 0x92,0x6c, 0x70, 0x48, 0x50, 0xfd, 0xed, 0xb9, 0xda, 0x5e, 0x15, 0x46, 0x57, 0xa7, 0x8d, 0x9d, 0x84,0x90, 0xd8, 0xab, 0x00, 0x8c, 0xbc, 0xd3, 0x0a, 0xf7, 0xe4, 0x58, 0x05, 0xb8, 0xb3, 0x45, 0x06,0xd0, 0x2c, 0x1e, 0x8f, 0xca, 0x3f, 0x0f, 0x02, 0xc1, 0xaf, 0xbd, 0x03, 0x01, 0x13, 0x8a, 0x6b,0x3a, 0x91, 0x11, 0x41, 0x4f, 0x67, 0xdc, 0xea, 0x97, 0xf2, 0xcf, 0xce, 0xf0, 0xb4, 0xe6, 0x73,0x96, 0xac, 0x74, 0x22, 0xe7, 0xad, 0x35, 0x85, 0xe2, 0xf9, 0x37, 0xe8, 0x1c, 0x75, 0xdf, 0x6e,0x47, 0xf1, 0x1a, 0x71, 0x1d, 0x29, 0xc5, 0x89, 0x6f, 0xb7, 0x62, 0x0e, 0xaa, 0x18, 0xbe, 0x1b,0xfc, 0x56, 0x3e, 0x4b, 0xc6, 0xd2, 0x79, 0x20, 0x9a, 0xdb, 0xc0, 0xfe, 0x78, 0xcd, 0x5a, 0xf4,0x1f, 0xdd, 0xa8, 0x33, 0x88, 0x07, 0xc7, 0x31, 0xb1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xec, 0x5f,0x60, 0x51, 0x7f, 0xa9, 0x19, 0xb5, 0x4a, 0x0d, 0x2d, 0xe5, 0x7a, 0x9f, 0x93, 0xc9, 0x9c, 0xef,0xa0, 0xe0, 0x3b, 0x4d, 0xae, 0x2a, 0xf5, 0xb0, 0xc8, 0xeb, 0xbb, 0x3c, 0x83, 0x53, 0x99, 0x61,0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26, 0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d};//keyExpansion-get the round keyvoid AES::keyExpansion(byte key[], word w[]){int i=0;int j,k;word temp;while(i < Nk){for(j=0; j<4; j++){w[j].wordKey[i] = key[j+4*i];}i++;}i = Nk;while(i < Nb*(Nr+1)){temp = w[i-1];if((i%Nk) == 0){temp = rotWord(temp);temp = subWord(temp);temp = wordXOR(temp, Rcon[i / Nk]);}else if(Nk > 6 && (i%Nk) == 4){temp = subWord(temp);}w[i] = wordXOR(w[i - Nk], temp);i++;}}// some sector in keyExpansionword AES::rotWord(word w){int i;word temp;for(i=0; i<4; i++){temp.wordKey[(i+3) % 4] = w.wordKey[i];}return temp;}word AES::subWord(word w){int i;byte L, R;for(i=0; i<4; i++){L = w.wordKey[i] >> 4;R = w.wordKey[i] & 0x0f;w.wordKey[i] = SBox[L][R];}return w;}word AES::wordXOR(word w1, word w2){int i;word temp;for(i=0; i<4; i++){temp.wordKey[i] = w1.wordKey[i] ^ w2.wordKey[i];}return temp;}//encryptionvoid AES::encryption(){int i, j ,k;for(i=0; i<4; i++){for(j=0; j<4; j++){cipherText[i].wordKey[j] = plainText[i].wordKey[j];}}// round functionaddRoundKey(cipherText, 0);for(i=1; i<10; i++){subByte(cipherText);shiftRows(cipherText);mixColumn(cipherText);addRoundKey(cipherText, i);}subByte(cipherText);shiftRows(cipherText);addRoundKey(cipherText, 10);}void AES::subByte(word in[]){int i,j;byte L, R;for(i=0; i<4; i++){for(j=0; j<4; j++){L = in[i].wordKey[j] >> 4;R = in[i].wordKey[j] & 0x0f;in[i].wordKey[j] = SBox[L][R];}}}void AES::shiftRows(word in[]){int i,j;word temp[4];for(i=0; i<4; i++){for(j=0; j<4; j++){temp[i].wordKey[j] = in[(i+j)%4].wordKey[j];}}for(i=0; i<4; i++){for(j=0; j<4; j++){in[i].wordKey[j] = temp[i].wordKey[j];}}}void AES::mixColumn(word in[]){word result[4];int i, j, k;for(i=0; i<4; i++){for(j=0; j<4; j++){result[i].wordKey[j] = GFMultiplyByte(mixColumnMatrix[j][0], in[i].wordKey[0]);for(k=1; k<4; k++){result[i].wordKey[j] ^= GFMultiplyByte(mixColumnMatrix[j][k], in[i].wordKey[k]);}}}for(i=0; i<4; i++){for(j=0; j<4; j++){in[i].wordKey[j] = result[i].wordKey[j];}}}//forexample: 0xaf * 0x25 计算多项式模乘的结果（列混淆中的操作）byte AES::GFMultiplyByte(byte L, byte R){byte temp[8];byte result = 0x00;temp[0] = L;int i;// temp[0] = L, temp[1] = L*x(modm(x)), temp[2] = L*x^2(mod(m(x))), temp[3] = L*x^3(mod(m(x)))...//先计算，再存起来，后面根据R的实际情况选用需要的for(i=1; i<8; i++){if(temp[i-1] >= 0x80){temp[i] = (temp[i-1] << 1) ^ 0x1b;}else{temp[i] = temp[i-1] << 1;}}for(i=0; i<8; i++){if(int((R >> i) & 0x01) == 1){result ^= temp[i];}}return result;}void AES::addRoundKey(word in[], int round){int i, j;for(i=0; i<4; i++){for(j=0; j<4; j++){in[i].wordKey[j] ^= wordKey[i+4*round].wordKey[j];}}}//decryptionvoid AES::decryption(){int i, j, k;for(i=0; i<4; i++){for(j=0; j<4; j++){deCipherText[i].wordKey[j] = cipherText[i].wordKey[j];}}addRoundKey(deCipherText, 10);for(i=9; i>0; i--){invShiftRows(deCipherText);invSubByte(deCipherText);addRoundKey(deCipherText, i);invMixColumn(deCipherText);}invShiftRows(deCipherText);invSubByte(deCipherText);addRoundKey(deCipherText, 0);}void AES::invShiftRows(word in[]){int i,j;word temp[4];for(i=0; i<4; i++){for(j=0; j<4; j++){temp[i].wordKey[j] = in[(i-j+4)%4].wordKey[j];}}for(i=0; i<4; i++){for(j=0; j<4; j++){in[i].wordKey[j] = temp[i].wordKey[j];}}}void AES::invSubByte(word in[]){int i,j;byte L, R;for(i=0; i<4; i++){for(j=0; j<4; j++){L = in[i].wordKey[j] >> 4;R = in[i].wordKey[j] & 0x0f;in[i].wordKey[j] = invSBox[L][R];}}}void AES::invMixColumn(word in[]){word result[4];int i, j, k;for(i=0; i<4; i++){for(j=0; j<4; j++){result[i].wordKey[j] = GFMultiplyByte(invmixColumnMatrix[j][0], in[i].wordKey[0]);for(k=1; k<4; k++){result[i].wordKey[j] ^= GFMultiplyByte(invmixColumnMatrix[j][k], in[i].wordKey[k]);}}}for(i=0; i<4; i++){for(j=0; j<4; j++){in[i].wordKey[j] = result[i].wordKey[j];}}}int main(int argc, char const *argv[]){int i;//设置明文和密钥byte plain[16], key[16];for(i=0; i<16; i++){plain[i] = byte(i);key[i] = 0x01;}AES aes;aes.setPlainText(plain);aes.setCipherKey(key);aes.encryption();aes.decryption();aes.showMesage();return 0;}

上面的代码主要是针对128bit的明文和密钥进行AES算法的实现。

由于本周有认识实习这门课加之其他课以及大大小小事情的叠加，本来打算这周对AES算法进行CPU和GPU的实际检测比较分析。但综上只能拖到下周再谈。

本周报告主要是在进一步对CPU和GPU进行更为详细的了解，看看GPU在计算能力方面到底强在哪里？

一、CPU和GPU的对比（CPU）

谈到计算，我们一般会想到CPU。CPU的全称是Central Processing Unit，而GPU的全称是Graphics Processing Unit。在命名上。这两种器件相同点是它们都是Processing Unit——处理单元；不同点是CPU是“核心的”，而GPU是用于“图像”处理的。在我们一般理解里，这些名称的确非常符合大众印象中它们的用途——一个是电脑的“大脑核心”，一个是图像方面的“处理器件”。但是聪明的人类并不会被简单的名称所束缚，他们发现GPU在一些场景下可以提供优于CPU的计算能力。

于是有人会问：难道CPU不是更强大吗？这是个非常好的问题。为了解释这个疑问，我们需要从CPU的组织架构说起。由于Intel常见的较新架构如broadwell、skylake等在CPU中都包含了一颗GPU，所以它们不能作为经典的CPU架构去看待。我们看一款相对单纯的CPU剖面图。

这款CPU拥有8颗处理核心（Core），其他组件有L3缓存和内存控制器等。可以见得该款CPU在物理空间上，“核心”并不是占绝大部分。

CPU是个集各种运算能力的大成者。这就如同一些公司的领导，他们可能在各个技术领域都做到比较精通。但是一个公司仅仅只有这样的什么都可以做的领导是不行的，因为领导的价值并不只是体现在一线执行能力上，还包括调度能力。

纵然有一台国产号称8核心，每颗核心可达2GHz的手机，目前打开两个应用也会卡顿严重。而即使是这台低等配置的两核心，最高睿频2.8GHz的笔记本，也可以轻轻松松运行多个应用。抛开系统和应用的区别以及CPU支持的指令集来思考，到底是什么让Intel的CPU使用起来越来越流畅？

有人可能说是主频，我们看下CPU主频的发展图。

由上图可知CPU的主频在2000年以前还是符合摩尔定律的。但是在左右，各大厂商都没有投放更高主频的CPU（理论上现在主频应该达到10GHz了），有的反而进行了降频。为什么？一是CPU的主频发展在当前环境下已经接近极限，而且功耗也会随着主频增加而增加。但是我们感觉到电脑越来越慢了么？显然是没有的。

有人可能说是核心数。最近10来年，市面上桌面版intel系列CPU还是集中在2、4、8核心数上。以的奔腾D系列双核处理器和现在core i3 双核处理器来对比，奔腾D应该难以顺畅的运行Win10吧（它的执行效率连发布的Core 2 Duo都不如）。

除了上述观点外，还有缓存存取速率、缓存大小等影响因素。但是这些因素，ARM系列CPU也可以做到，但是为什么还是没Intel快呢？接下来只罗列出个人认为比较重要的几个原因。

分支预测（Branch predictor）。以下面的一段代码为例：

int b = 3;int c = 4;bool a = memory_enough();if (a) {b *= c;}else {b += c;}

如果按照一般的想法，CPU执行的流程是：获取a的值后选择一个分支去执行。假如a的逻辑可能比较耗时（比如存在IO等待操作），CPU要一直等待下去么？

现在CPU的做法则相对智能，它会预测a的值，执行预测对应的分支。然后等到a的值返回后再校验是否猜测正确，如果正确，我们将节省一个分支执行的等待时间。如果猜测错误，则回退回去再执行正确的流程。

可能有人会怀疑分支在代码逻辑中的比例那么高么？需要独立设计这么一个功能来优化？实际上这个比例是相当高的，不妨看看自己写的代码。分支作为基础的逻辑结构，可以运用在多种场合。因此CPU预测可以大大加快速度。就算预测错了也是再执行，总比傻傻等在那里什么都不干强。

说了这么多，我只想说明一个观点：CPU是一个拥有多种功能的优秀领导者。它的强项在于“调度”而非纯粹的计算。而GPU则可以被看成一个接受CPU调度的“拥有大量计算能力”的员工。

二、CPU和GPU的对比（GPU）

为什么说GPU拥有大量计算能力。下面我们看一张NV GPU的架构图。

这款GPU拥有4个SM（streaming multiprocessor），每个SM有4*8=32个Core，一共有4*4*8=128个Core（此处的Core并不可以和CPU结构图中的Core对等，它只能相当于CPU微架构中的一个“执行单元”。之后我们称GPU的Core为cuda核）。

再对比一下CPU的微架构和架构图，以FP mul“执行单元为例”，一个CPU的Core中有2个，六核心的CPU有12个。虽然我们不知道GPU cuda核的内部组成，但是可以认为这样的计算单元至少等于cuda核数量——128。由此直接产生对比，相当于128比12。

下面我们看一张最新的NV显卡的数据。

5120已经和12不是一个数量级的了，差距更加大。

如果说cuda核心数不能代表GPU的算力。那我们再回到上图，可以发现这款GPU提供了640个Tensor核心，该核心提供了浮点运算能力。我并不太清楚CPU中有多少类似的核心，但是从NV公布的一幅图可以看出两者之间的差距——也差一个量级。

综上可知GPU的计算能力无论是从“算力单位”的数量还是能力，都远超CPU。

除了计算能力，还有一个比较重要的考量因素就是访存的速率。当我们进行大量计算时，往往只是使用寄存器以及一二三级缓存是不够的。

目前Intel的CPU在设计上有着三级缓存，它们的访问速度关系是：L1>L2>L3，而它们的容积关系则相反：L1<L2<L3。以图中Intel Core i7 5960X为例，其L3缓存的大小只有20M。很明显CPU自带的缓存大小太小，不足以承载所有的系统。于是需要使用内存来补充。该款CPU的最大支持64G内存，其内存最大带宽是68GB/s。

然而GPU对应的显存带宽则比CPU对应内存又高出一个数量级！如下图：