使用 gKrypt 快速保护您的数据,第 1 部分

使用支持 GPU 的 gKrypt 引擎加快应用程序的加密工作

gKrypt 引擎是世界上首个为数据加密使用通用图形单元 (GPGPU) 的软件包,而数据加密是一个重要的信息安全工具。该引擎使用基于 256 位分组密码的高级加密标准 (AES) 来提供强大的安全性。在本系列文章的第 1 部分(共 2 部分)中,我将介绍 AES、针对 Linux 的 Rijndael 算法的 GPU 端口、®AES 算法的并行化,以及如何使用 gKrypt 引擎为基于 NVIDIA 的 GPU 支持 CUDA。

Jawad Masood, 首席工程师, gKrypt Data Security Solutions

Jawad Masood 是 gKrypt Data Security Solutions 的首席开发人员,这家创业公司主要关注于混合使用多核和众核处理器来提供经济高效的数据安全解决方案,从而实现更快的批量数据加密和压缩性能。



2012 年 6 月 08 日

简介

在当今的世界中,人们以及各种机构会存储几乎各种类型的信息,用电子方式处理这些信息,并且经常通过本地网络或 Internet 传输信息。结果是,对这些信息进行未授权访问的风险显著增加了,并且对信息安全的挑战也在日益增加。对被截取的传输内容进行未经授权的访问可能危及个人和组织敏感个人信息与财务信息的安全,导致严重违反安全性的问题。对于企业而言,这种违反安全性的问题会使其遭受财务方面的损失、昂贵的法律诉讼,以及声誉和业务受损。对于个人而言,这种问题会导致其身份被盗用以及财务历史信息丢失和信用等级下降。并且从这种信息问题造成的影响中恢复过来可能需要数年的时间以及高昂的成本。加密是保护敏感和重要的个人与组织信息不受这些信息安全性问题影响的有效解决方案,因此加密也成为数据安全系统的基本要素。

批量加密技术提供了在数据传输或存储期间对大量数据进行加密的方法。但在最近几年,对于必须同时加密的敏感信息量,其增长速度已经超出了 CPU 计算能力的增长速度。目前,批量加密的处理能力需求必须通过专门的硬件解决方案,以密码加速器的形式(参阅 参考资料)才能得到满足。诸如数据加密标准 (DES) 和高级加密标准 (AES) 等大部分加密算法本身具有较高级别的数据并行性和计算密度,使其很适合 GPU 上的并行实现,并且可有效取代专用的硬件密码解决方案(参阅 参考资料)。


gKrypt 引擎

gKrypt 引擎是一个现成的密码模块,提供了简单的 API 来使用 Rijndael 高级加密标准与 GPU(参阅 参考资料)。它可充分利用显卡和计算处理器形式的底层并行硬件,将计算密集型的加密工作负载从处理器上卸载下来。gKrypt 简单的 C/C++ 接口与 Java™ 和 C# 接口的绑定让希望部署 GPU 解决方案,但又缺乏并行语言(如 CUDA 和 OpenCL)知识的开发人员具有了显著的优势。

该框架支持基于 AMD 和 NVIDIA 的 GPU 以及多核 CPU,因此很容易利用并行处理器的优势。下节解释了 AES 的底层方法以及并行性分析。


高级加密标准 (AES) 算法

高级加密标准 (AES) 是美国国家标准与技术研究院 (NIST) 认可的加密标准,它基于 Rijndael 密码(参阅 参考资料)。Rijndael 是由比利时密码学家 Joan Daemen 和 Vincent Rijmen 为 NIST 发起的 AES 选择过程所提议的对称密钥分组密码(参阅 参考资料)。NIST 于 2001 年 11 月批准 Rijndael 成为高级加密标准 (AES),并且该标准实际取代了已经老化的数据加密标准 (DES)。AES 标准由 3 个分组密码 (block-cipher) 组成,密钥大小为 128、192 和 256 位,但都具有相同的 128 位数据块,因此分别命名为 AES-128、AES-192 和 AES-256。

AES 分组密码是在一个二维字节数组上运行的,该数组又称为状态 (state),用 s 表示。状态数组的大小为 16 字节(128 位),排列为四行四列。这用 Nb = 4 来表示,实际上是一个状态数组中的列数。AES 支持的密钥大小是 128、192 和 256 位,分别用 Nk = 4、6 或 8 表示。AES 应用面向字节的转换(通常称为 AES 转换)来加密或解密状态数组。这些转换适用于具体数量的轮次 Nr,这取决于密钥大小。对于 128、192 和 256 位密钥,Nr 分别为 10、12 和 14。

图 1 显示了 AES 算法的各个阶段。

图 1. AES 算法的各个阶段
AES 算法的各阶段图

开始 AES 转换之前,会使用 Rijndael 密钥编排 (Key-Schedule) 扩展用户提供的密码-密钥。密钥扩展步骤(如 图 1 所示)实现了密钥编排并为后续阶段中的所有轮次提供扩展后的密钥。扩展后的密钥大小计算方法是 Nb(Nr + 1),这是 32 位字(列)的数目。扩展后的密钥的另一部分在每个轮次的 AddRoundKey 步骤中使用。

AES 加密过程的第一步是 AddRoundKey 转换,即使用 图 2 中等式所定义的按位异或 (Exclusive OR, xor) 运算将状态数组的每个字节与轮次密钥 (round-key) 组合起来。

图 2. AES 加密过程的第一步
该公式显示了 AES 加密过程的第一步

下面的 图 3 阐释了该步骤。状态、新状态和轮次密钥都表示为 4x4 的字节数组(128 位),因为 Nb = 4。字节数据是用十六进制字形式表示的。

图 3. AddRoundKey 转换
AddRoundKey 转换图

在 AES 的下一个阶段中,按照 图 3 中所示的顺序,所有四个转换会重复应用 Nr - 1 次,从 Nr = 1 开始,直到 Nr - 1。我会按照转换的应用顺序解释每个转换。

SubBytes 转换是一个非线性字节替代步骤,会根据一个称为 S-Box 的查找表替换状态数组中的每个字节。状态数组中的每个字节都被 S-Box 中的一个条目所替代,该条目与要替代的字节的十六进制值具有相同的索引。图 4 更好地展示了该过程。

图 4. SubBytes 转换
非线性字节替代步骤图

此处状态数组的第一个字节拥有一个十六进制值。根据行索引 1 和列索引 9 的交点来确定替代值。同样,字节 {be} 将被 S-Box 中的行索引 b 和列索引 e 所替代。

ShiftRows 转换中,按照 图 5 中的等式约定,将 状态 数组中的每一行循环位移不同的偏移量。

图 5. 状态数组中的每一行循环位移不同的偏移量
该图显示了状态数组中的每一行循环位移不同的偏移量

移位值 shift(r, Nb) 取决于行号 r,如 图 6 中的公式所示。

图 6. 移位值取决于行号
该等式显示了移位值取决于行号

针对每一行解析上面的等式表明:第一行是不移位的,而第二行、第三行和第四行的每个字节分别向左移位 1、2 和 3 字节。下面的 图 7 解释了如何移位每一行以及最终得到的新状态数组。

图 7. ShiftRows 转换
ShiftRows 转换图

移位模式将各字节移到该行中较低的位置,而将最后一个字节移到该行的开头。

MixColumns 转换在状态数组的各列上执行操作,将每个列视为 GF(28) 上的一个四元素多项式。然后使用 x4 + 1 为模将每个列与 图 8 中的多项式系数等式相乘。

图 8. 多项式系数
多项式系数图

这相当于将状态数组中的每个列替换为该列与系数矩阵的矩阵乘积,如 图 9 所示。

图 9. MixColumns 转换
MixColumns 转换图

针对 CUDA 架构的并行 AES 算法

现在您已经了解了一些 AES 加密算法的知识。可以开始用 CUDA 框架实现点什么了。在下面的几节中,我会简要介绍 CUDA 框架,然后详细讨论设计方法和实现机制。这些都是准备工作,所以您可以运行本系列文章第二部分中的示例。

CUDA 架构

CUDA 于 2006 年引入,是由 NVIDIA 开发的一种并行计算架构,通过充分利用 NVIDIA GPU 的计算能力来提高计算性能(参阅 参考资料)。市面上已安装的一亿多个 GUP 均支持 CUDA,所以在 CUDA 上运行的应用程序已经有了很庞大的潜在用户群。CUDA 发布后,开发人员已经在很多应用程序中实现了显著的性能改进,特别是与图像处理和高清视频播放有关的应用(见 图 10)。

图 10. CUDA 线程模型
CUDA 线程模型图,其中包括两个串行码 CPU 和两个 GPU 并行内核

CUDA 编程模型的概念是生成按单程序流多数据流 (SPMD) 方式并行执行的数千个线程,每个线程都在一小块数据上执行操作。由于 GUP 的核心数要多于 CPU(尽管 GPU 核心的处理能力要远低于 CPU 的核心),因此是并行执行数千个线程的理想之选,此时每个线程都在一小块数据上进行计算。这些线程被组织成多个块和网格 (grid),其中一个线程块是一组线程,而一个线程网格则是一组线程块。CUDA 架构(其所有功能及内存层次结构)都需要详细说明,但这超出了本文的范围。

设计策略

如前所述,AES 是一种分组密码算法,独立地在 128 位的数据块(状态)上进行操作。由于 AES 加密在每个状态块上执行相同的操作,并且每个块之间没有依赖关系(ECB 模式),所以它提供了很高的数据级别并行性。我实现了一种分叉与汇合的策略来利用 AES 分组密码中的这种数据级别的并行性。在该方法中,可同时加密多个状态块,每个线程负责一个状态块,因此可实现更高的吞吐量。由于数据规模越大,并行性级别也越高,所以执行批量加密时 GPU 要更为高效。

图 11 显示了主机-设备工作分区并介绍了 AES 各部分的本质。从中可以看出,AES 中惟一的串行操作是为后续 AES 轮次提供轮次密钥的密钥编排操作。所有 AES 转换都是高度并行性的操作,因为会为每个 128 位状态块单独应用这些转换操作。因此可以将工作分布在 CUP 主机处理器和 GPU 设备上,让这种实现方法获得最高的吞吐量。因此,在 CPU 设备上执行密钥编排操作一次,然后将结果作为内核参数传递到 GPU 设备。然后使用 CUDA 实现核心 AES 算法(即各种 AES 转换),目的就是充分利用 GPU 的并行计算资源。

图 11. 主机-设备工作分区
主机-设备工作分区图

在本系列文章第二部分介绍的实现中,每个 CUDA 线程将一个状态块(16 字节)作为输入内容,通过应用指定数量轮次的面向字节的 AES 转换,将其转换为密码-文本。一个 128 位状态块的加密操作仍是串行的;但是您可使用 GPU 特定的优化技术(如循环展开)来优化代码。在访问输入数据和写回加密后的数据时,每个 CUDA 线程有一个 16 字节(一个状态块)的净偏移量。图 12 显示了线程间的工作分区以及该实现方法使用的线程分配模型。

图 12. CUDA 线程分配
CUDA 线程分配图

CUDA 设备上的线程执行

从理论上讲,您可能认为加密 100 MB 数据所需的时间与加密 128 位数据所需的时间相同,因为所有线程都是同时执行的,但情况并非如此。您已经知道在 CUDA 中会将多个线程绑定成块在 CUDA 设备上执行操作。在目前的 CUDA 架构中,执行资源(核心)被分为多个流式多处理器 (SM),并且每个 SM 一次可执行 112 个块(见 图 13)。如果设备有 14 个 SM(Tesla C2050 就是如此,每个 SM 有 32 个核心),那么一次只能执行 16 个块,前提是没有其他限制因素。如果块的数目多于 16 个,后续的块就必须等待轮到它们执行。这是设备上最简单的线程执行情况。还有很多其他因素需要考虑,如每个 SM 的线程束 (warp) 数目、每个线程的寄存器使用情况、每个块的共享内存等。有关 CUDA 如何为 SM 分配线程块的更多信息,请参阅 CUDA Occupancy Calculator(参阅 参考资料)。

图 13. 将线程块分配给流式多处理器 (SM)
将线程块分配给流式多处理器 (SM) 图

在目前的 CUDA 架构(仍在不断发展)中,一旦将某个线程块分配给流式多处理器,就会将该线程块分为多个线程束,每个线程束中有 32 个线程。这些线程束可能不会并行执行操作,但它们的确以非常高效的方式执行操作。例如,如果一个线程束正在等待内存转换,此时下一个线程束会在此时同一核心上执行其数据操作。如果有多个线程束已准备好执行操作,驱动程序会在这些线程束之间设定一个优先级机制。虽然核心数可能会少于一个内核中所启动的线程数,但 CUDA 架构和驱动程序可确保使用所有硬件资源,从而实现最高的性能。


在 Linux 上配置 CUDA

CUDA 框架需要基于 NVIDIA 的图形处理单元 (GPU) 才能充分利用底层的并行硬件并实现高性能。CUDA 运行时附带了一个 NVIDIA 开发人员视频驱动程序。要想使用具有 CUDA 功能的显卡,第一步是配置基本的视频驱动程序。请打开终端并执行以下命令:$ sudo apt-get --purge remove nvidia*

下一步是将那些与 CUDA 开发人员驱动程序发生冲突的默认 nouveau 驱动程序加入黑名单。在 /etc/modprobe.d 中新建一个文件并在该文件中插入 清单 1 中所列的代码。

清单 1. 将那些与 CUDA 开发人员驱动程序发生冲突的默认 nouveau 驱动程序加入黑名单
# /etc/modprobe.d/blacklist-nouveau.conf 
blacklist nvidiafb 
blacklist nouveau 
blacklist rivafb 
blacklist rivatv 
blacklist vga16fb 
options nouveau modeset=0

要更新内核文件,可运行此命令:$ sudo update-initramfs -u

然后重新启动系统,让修改生效。系统重新启动后,就可以安装 CUDA 开发驱动程序了。

安装 CUDA 驱动程序

您可直接从 NVIDIA 网站下载最新的 CUDA 驱动程序官方发行版(参阅 参考资料)。必须先关闭图形显示管理器,然后才能继续安装工作。要想切换到控制台模式,可按 CTRL+ALT+F2 组合键。现在可从控制台开始驱动程序文件的自动安装过程:$ sudo sh devdriver_4.1_linux_32_285.05.32.run

安装完驱动程序后,重启系统,并通过可显示当前已安装的 GUP 的 Administration 菜单验证 X Server 正在运行。

现在您可以运行本系列第 2 部分文章中所述的各种优化技术了。


结束语

gKrypt 引擎附带了很多平台二进制文件以及代码片断,介绍了与 C/C++ 项目的集成。显然正确地使用系统资源至关重要。我们的理念是利用优化的插件即刻提高性能,同时不会牺牲兼容性或易用性。在第 2 部分文章中,我们会详细介绍各种优化技术,通过示例重点介绍一些集成方法。

参考资料

学习

获得产品和技术

讨论

条评论

developerWorks: 登录

标有星(*)号的字段是必填字段。


需要一个 IBM ID?
忘记 IBM ID?


忘记密码?
更改您的密码

单击提交则表示您同意developerWorks 的条款和条件。 查看条款和条件

 


在您首次登录 developerWorks 时,会为您创建一份个人概要。您的个人概要中的信息(您的姓名、国家/地区,以及公司名称)是公开显示的,而且会随着您发布的任何内容一起显示,除非您选择隐藏您的公司名称。您可以随时更新您的 IBM 帐户。

所有提交的信息确保安全。

选择您的昵称



当您初次登录到 developerWorks 时,将会为您创建一份概要信息,您需要指定一个昵称。您的昵称将和您在 developerWorks 发布的内容显示在一起。

昵称长度在 3 至 31 个字符之间。 您的昵称在 developerWorks 社区中必须是唯一的,并且出于隐私保护的原因,不能是您的电子邮件地址。

标有星(*)号的字段是必填字段。

(昵称长度在 3 至 31 个字符之间)

单击提交则表示您同意developerWorks 的条款和条件。 查看条款和条件.

 


所有提交的信息确保安全。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=10
Zone=Linux, Open source
ArticleID=820300
ArticleTitle=使用 gKrypt 快速保护您的数据,第 1 部分
publish-date=06082012