基于GPU实现的AES加密（一）

　　摘 要：加密标准（Advanced Encryption Standard,AES），在密码学中又称Rijndael 加密法，是美国联邦政府采用的一种区块加密标准。该算法已经被多方分析论证并广为全世界所使用。传统的AES 加密运算是在CPU 上实现的，现在为了提高加密速度以处理大规模的加密运算，文中提出了一种在图像处理器（Graphics Processing Unit）上实现AES 加密算法的方法。该方法的实现有两种，一种是基于传统OpenGL 的AES 实现，另一种是基于技术CUDA 的AES 实现。文中阐述的是前者。经过测试，该方法比传统CPU 的实现提高了15 到40 倍左右的速度。

　　引 言

　　图形处理器（Graphics Processing Unit,GPU），亦称图形处理单元。是一种专用图像渲染设备，分担了中央处理器（CPU）的二维或三维图形处理任务。2001年到2006 年，各种硬件加速的出现使显卡性能突飞猛进。正是这个时候，款可编程图形流水线（programmablegraphics pipeline）的GPU 产品诞生，即Ge-Force3 .从此，可编程的着色功能加入了硬件。

　　GPU 拥有了更大的可扩展性和适应性。GPU 高度并行化的架构和可编程的着色器使人们渐渐开始用它计算通用任务，实现了对通用数据的处理。GPGPU技术也是在这个时期开始发展起来的。GPGPU 代表General Purpose Computing on Graphics Processing Unit,就是“图形处理器通用计算技术”.这种新兴的加速技术试图把个人计算机上的显卡当作CPU 这样的通用处理器来用，使显卡的强劲动力不仅发挥在图形处理上。用着色语言实现的GPGPU 技术是代的GPGPU 技术，也称为经典GPGPU、传统GPGPU .

　　但是传统的GPU 几乎专门用来进行浮点操作，因为整数操作只能使用浮点数尾数来完成，所以就不能完成那些要求按位逻辑操作的处理。然而随着GeForce 8系列GPU 的出现，多种新的扩展和功能被引入。新的整数处理功能不仅包括算术操作，还包括按位的逻辑操作，以及移位操作。然后，数组变量代替纹理提供了一种灵活的方式存储常量表 .目前，如何方便、快速地实现加密算法是密码学领域遇到的一个新的挑战。

　　而GPU 其特有的并行计算特性如果应用到AES 加密算法，将显着提高该算法的加密速度。文中正是基于上述原因，提出了一种基于传统OpenGL 可编程模型的一种AES 加密算法。

　　文中首先将介绍传统GPU 编程模型及相关概念，然后概述AES 加密算法，接着介绍AES 加密算法在GPU 上的实现，将与在传统CPU 上实现的AES加密算法进行性能上的比较。

　　1 图形化处理单元

　　1. 1 图形流水线

　　图形流水线是GPU 工作的通用模型。它以某种形式表示的三维场景为输入，输出二维的光栅图像到显示器，也就是位图。GPU 中的图形流水线的总体框架如图1 所示 .上半部分为OpenGL 传统图形流水线，下半部分为OpenGL 可编程图形流水线。

　　

　　传统图形流水线，首先经过顶点级的光照计算和坐标变换求出每个顶点的光照颜色值，同时还将顶点坐标从物体坐标系转换到裁剪空间。然后，对每个三角形进行光栅化处理并对三角形顶点的颜色进行双线性插值得到了三角形中每一个像素的颜色值。接着进行纹理映射，即根据每一个像素的纹理坐值将纹理图颜色分配到每个像素上。进行颜色混合计算和雾化效果计算得到的结果将会放进帧缓存并显示到屏幕上。

　　可编程着色管线意味着可以用小型程序控制顶点和片段的处理，即顶点着色器和片段着色器。这种小型程序是由OpenGL 着色语言（GLSL）编写。着色器（shader），又叫着色单元，实际上就是GPU 的处理器。

　　一般情况下，一个GPU 会有多个处理器（几百上千个），它们同时工作，体现了GPU 大规模并行处理的能力。进行几何计算的处理器叫顶点着色器，它负责对顶点进行坐标变化、投影变换等；进行片段的颜色处理的叫做片段着色器。应用程序输入GPU 的是三维的点云数据。从流水线输入端直到顶点着色器，流水线计算的对象都是三维几何模型；从光栅化开始，所有的操作都是针对二维的像素了。

　　1. 2 经典GPGPU 技术

　　在了解GPGPU 技术之前，有必要了解一下GPU的并行计算模型SIMD,与数据并行模型实际上是完全相同的。GPU 的并行概念实际就是数据并行（dataparallelism）。它是指多个不同的数据同时被相同的指令、指令集或者算法处理。回顾图形流水线，每个顶点都经过了相同的流水线，实际上流水线只是个抽象的概念，它指的就是一段算法。因此，GPU 计算任务的本质与程序中的循环语句是相同的，但是需要串行处理的数据量减少到了Nparallel,如公式（1）所示。

　　

　　式中， Ndata 是数据的总个数， Nthreads 是线程的个数。当每个线程处理一个数据所需的时间相等时，数据并行处理的速度是单线程循环语句的速度的Nthreads 倍 .

　　经典GPGPU 借助的是GPU 图形流水线的大规模并行计算能力。成千上万的顶点都流经同样的流水线，成为屏幕上的像素。由于每个顶点和每个像素都经过了相同算法的处理，因此SIMD 模型就是GPU 计算的基本模型。

　　目前为止，还有一些很重要的问题亟待解决。比如，流水线的终点是帧缓存或者显示器，而科学计算一般需要写入存储器，这是如何做到图形流水线处理的是坐标信息和像素信息，如何才能处理通用数据？

　　在OpenGL 提供有限数量的图形处理函数的情况下，如何制定科学计算所需要的算法？ 对于个问题其实就是纹理缓存。第二个问题，其实用户只要选择合适的数据类型来声明数组，再将数组作为数据的容器，把这样的数组看作一幅纹理并传输至纹理缓存就可以啦。第三个问题其实就是通过着色语言和着色器来实现的 .

　　2 AES 算法概述

　　AES 加密算法是由Daemen 和Rijmen 早期所设计的Square 改良而来。使用的是置换-组合架构，在软件及硬件上都能快速地加解密，相对来说较易于实际操作，且只需要很少的内存 .作为一个新的加密标准，目前正被部署应用到更广大的范围。

　　该算法具有如下几个特点：

　　（1）对称密钥密码；

　　（2）块密码；

　　（3）支持128 位块大小，当前该算法的联邦信息处理标准规范只支持固定大小的128 位块；

　　（4）支持128 位、192 位、256 位密钥长度 .不同的密钥长度加密的轮数不一样，文中使用128 位的密钥长度。

　　AES 加密过程是在一个4×4 的字节矩阵上运作，这个矩阵又称为“体（state）”,其初值就是一个明文区块（矩阵中一个元素大小就是明文区块中的一个Byte） .

　　加密时，各轮AES 加密循环（除一轮外）均包含如下4 个步骤（加密过程中使用的密钥是由Rijndael密钥生成方案产生）：

　　（1）AddRoundKey:矩阵中的每个字节都与该次回合金钥做XOR（异或）运算。

　　（2）SubBytes:矩阵中的各字节透过一个8 位元的S-box 进行转换。这个步骤提供了加密法非线性的变换能力。S-box 是一个具有256 个元素的已知数组。

　　（3）ShiftRows:针对矩阵的每一个横列操作的步骤。在此步骤中，每一行都向左循环位移某个偏移量。

　　在AES 中（区块大小128 位元），行维持不变，第二行里的每个字节都向左循环移动一格。同理，第三行及第四行向左循环位移的偏移量就分别是2 和3.

　　经过ShiftRows 之后，矩阵中每一竖列，都是由输入矩阵中的每个不同列中的元素组成 .

　　（4）MixColumns:每一直行的四个字节透过线性变换互相结合。每一直行的四个元素分别当作1, x2 ,x3 ,x4 的系数，合并即为GF（28 ）中的一个多项式，接着将此多项式和一个固定的多项式C（x） = 3×3 + x2 + x + 2在modulo x 4 +1 下相乘。此步骤亦可视为Rijndael 有限域之下的矩阵乘法。MixColumns 函数接受4 个字节的输入，输出4 个字节，每一个输入的字节都会对输出的4 个字节造成影响。因此ShiftRows ows 和MixColumns两步骤为这个密码系统提供了扩散性。其流程图如图2 所示。