基于OpenCL的Salsa20算法实现与优化

０引言当前环境中，随着通信技术的快速发展，网络带来快捷性的同时，也伴随着出现了诸多信息安全隐患，使得人们对隐私和信息保护越来越重视。在传输层采用基于流加密算法的Salsa20可以有效阻止信息泄露，防止通信关系被暴露，成为保障用户信息隐秘传输的有力手段。在物联网的世界，日常设备之间信息相互交换十分频繁，使其非常容易受到安全攻击。而基于Salsa20的流密码算法采用轮函数迭代的设计结构，利用AES中的行移位和列混合思想，具有较少的参数、较小的内存占用空间和较少的执行周期，在资源受限的设备上性能良好，可以设计用于物联网中资源受限的设备，能够实施其当前无法提供的安全服务，以保护用户的数据隐私并保护系统免受攻击。Salsa20算法作为入选eSTREAM计划的序列密码加密算法，对其进行研究具有重大意义。Salsa20旨在提供非常快速的软件加密性能，即使与AES相比也不会影响安全性。OpenCL全称OpenComputingLanguage，是一个面向异构平台并行编程框架标准，被广泛应用于密码分析系统。OpenCL的优势是使程序员能够控制所有功能系统中的各个可用处理单元。OpenCL用于编写跨异构平台执行的程序的框架。其中，该异构平台由中央处理单元、图形处理单元、数字信号处理器、现场可编程门阵列和其他组件组成处理器或硬件加速器。通过将流密码算法Salsa20在OpenCL中实现，可以获得加速，并且可以有效提高算法执行速度。本篇文章结构如下：第1节介绍了Salsa算法和基于OpenCL的高性能计算平台；第2节分析密码算法原理；第3节测试和评估方法；第4节展望未来的工作。１Salsa20算法和OpenCL介绍1.1Salsa20算法简介流密码因为安全性高和加密速度快等优点，非常适合在网络加密数据传输和受限资源场合应用。Salsa20密码长度可灵活变化，且具有运算速度快等优点，被Shadowsocks推荐使用。它基于add-rotate-XOR（ARX）操作-32位加法，按位加法和旋转操作的伪随机函数构建。核心功能将256位密钥、64位随机数和64位计数器映射到密钥流的512位块。密钥分为128bit和256bit两种类型。Salsa20算法首先对密钥进行扩展。如图1所示，扩展所用的quarterround函数用数学公式表示为：图1Salsa20中QuarterRound函数Salsa20算法的初始状态是由16个字节构成的一个４×4矩阵，其中包括8个密钥、4个常数、2个初始IV值、2个时间标号。假设用表示初始状态，则为：（6）将初始状态经过10轮变换后的输出与进行模加，得到密钥流后，对明文分组进行异或操作便可得到密文数据，操作流程如图2所示。图2Salsa20加密原理

1.2OpenCLOpenCL所支持的平台可由多核CPU、GPU或其他类型的处理器组成。OpenCL主要由两部分组成，一是用于编写内核程序（在OpenCL设备上运行的代码）的语言，二是定义并控制平台的API。图3中的设备可以被看成是CPU/GPU，而设备中的计算单元可以被看成是CPU/GPU的核。计算单元的所有处理节点作为SIMD单元或SPMD单元（每个处理节点维护自己的程序计数器）执行单个指令流。抽象的平台模型更与当前的GPU的架构接近。图3OpenCL模型OpenCL程序由主机程序（HostProgram）和内核程序（Kernel）组成。主机程序为Kernel定义了上下文并管理Kernel代码的执行，Kernel则在支持OpenCL的计算设备（ComputeDevice）如GPU上执行具体的计算任务。平台可被认为是不同厂商提供的API的实现。一个平台选定后，一般只能运行该平台所支持的设备。一般而言，A公司的平台选定后不能与B公司的平台进行通信。OpenCL的本地内存是片上内存，使得它非常快。访问共享内存通常需要4～6个周期。但是，共享内存非常小，通常为16kB，因此必须用于存储经常用于计算和更新的数据。共享内存可以由工作组的所有工作项访问，因此可以用于同一工作组的工作项之间的通信。此功能非常适合在需要在工作项之间共享数据情况。另一个有用的内存空间是常量缓存（只读内存），通常为64kB，位于芯片上。当工作组中有多个线程尝试读取相同的常量缓存地址空间时，它只占用一个事务，否则会对不同地址的读取进行序列化。该内存空间用于通过缓存常用数据来加快读取的速度。类似的缓存也可以使用纹理缓存，以加快图像读取速度对象。专用内存（寄存器）是最快的内存，由SM私密地分配到工作组的工作项。每个多处理器的内存总量受到限制，介于8192和16384个32位寄存器（32～64kB）之间，并划分为多个线程。如果工作组需要更多的寄存器，则会出现性能问题，称为“寄存器压力”。寄存器是存储需要频繁使用的少量数据的最佳解决方案。２破解算法2.1基于OpenCL的密码算法实现根据Salsa20加密算法原理，设计基于OpenCL的密码实现，具体密码算法流程如图4所示。图4算法实现流程将Salsa20代码分为两部分：第一部分是创建块密钥流的加密过程；第二部分是密钥流与原始数据的实际混合（通过使用XOR）。加密算法将原始消息切分成相等的块，通过按位操作应用于函数来确定大小并进行计算。在设计Salsa20算法内核时，还需要注意每个工作项注意如下参数。（1）字节偏移量，表示包含到现在共处理了多少字节的信息。（2）块大小，表示根据每个工作项负责多少字节消息而创建适当大小的密钥流。（3）传输到GPU的总字节数，如果块大小未完全划分总工作量，则最后一个工作项将需要产生一个较小的密钥流。（4）块号，当工作项要计算块号时，必须首先计算它在所有工作组的所有工作项中的位置，然后考虑块大小，并通过添加块偏移量来计算块编号。（5）随机数，字节偏移量和块大小在全局内存中传递，并由所有工作项使用。工作组的所有工作项都可以从同一内存地址读取随机数。基于先前对其他加密算法的研究，发现该算法的最佳块大小相对较小，为1024Byte，选择通过寄存器而不是共享内存来处理数据，以获得更好的性能。经过实验，以16Byte（128位）的块的形式写入全局存储器性能最佳。2.2密码算法内存优化OpenCL体系结构中有几个不同的内存空间。不同存储空间的位置描述如图5所示。GPU体系结构的主要最大内存是片外全局内存，高端GPU通常介于128MB到几GB之间。访问全局内存需要400～600个周期，使得在访问全局内存时必须谨慎。所有工作组的所有工作项可以访问全局内存。全局内存区域按顺序保留用作常量的只读存储器，称为常量存储器。图5OpenCL中内存分布Salsa20算法内核参数需要确定最佳的块大小。所谓“块大小”，是指分配给每个工作项的数据量。大的块不会导致私有内存问题，因为密钥流是在固定大小（64Byte）的块中生成，然后写入全局内存，且使用同一私有内存生成下一个密钥流块。但是，由于生成的密钥流的数据量大，块大会导致全局内存问题，所以需要尝试不同的块大小，并找到此方法的最佳选择。最佳块大小还取决于硬件，因此在获取GPU设备有关工作组中最大工作项数的信息后，必须在运行时确定它。因此，对于不同的GPU，该值可能会有所不同，但变化不大。假设GPU设备支持共X个并行线程，并且将块大小确定为Y（这是可以并行执行的数据大小）。为了隐藏延迟，需要在GPU上传递此大小的多个Z。XYZ即它们的乘积必须小于支持的GPU内存总量，否则编译器将出现错误。由于寄存器资源被占用直到内核完成才释放变量，可见导致了资源浪费。因此，本文进行了重复使用寄存器优化操作，以减少浪费。寄存器重用分配了两个完全不同的地方，在不影响正确性的情况下对一个变量表示含义。它损害了程序的可读性，但节省了寄存器使用，并带来了性能的提升。根据程序性能对不同数量的工作组进行自动化评估，是寻找工作组最优数量的有效手段。工作组数量越多，该程序执行速度会越快，因为内核启动耗时同步会随着工作组编号的增加而增加。但同时每个内核的执行时间将变长，且需要中间结果等待更长的时间，所以这个数字不应该太大。３实验结果与分析本文对上述算法进行测试，测试平台和实验结果如表1和表2所示。表1实验环境表2GPU吞吐率对比实验中，将算法加密的字符串大小限制为1MB。结果表明，基于GPU平台的OpenCL算法实现速度达到11.5Gb/s，相较于优化前提高了2倍多。对不同大小的算法加密字符串在GPU平台上进行测试，结果如图6所示。从图6可以看出，字符串越大，算法的吞吐率越高。图6不同大小字符串在GPU平台速度优化前后速度４结