符 鹤，李春江，王 昊，谢永芳

(1.中南大学信息科学与工程学院,湖南 长沙 410083;2.国防科技大学计算机学院,湖南 长沙 410073)

1 引言

密码算法的设计基础是数学问题计算的困难性，通常为了增加密码破解的难度会增加密钥的长度或者增加算法的复杂性，这就意味着计算量的增加。使用密码算法的相关应用在运行时需要处理大量的信息，计算量相当可观，例如密码的暴力穷举攻击，对计算能力以及吞吐率都有非常高的要求。

为解决高吞吐率密码的加速问题，本文首先提出了一个面向众核加速器的并行加速框架，可以加速密码算法相关应用的运行。其次，在框架中实现了高吞吐率的多级任务分批技术。在天河超级计算机结点的众核协处理器MIC平台上的实验结果表明，本文的工作对加速密码算法非常有效。

2 相关工作

基于对密码算法高吞吐量并行优化的需求，早在GPU出现的初期研究人员就已经尝试了基于GPU的密码算法优化方案。1999年Kedem等[1]就使用了定制的GPU架构“PixelFlow”来对DES和RC4密码算法进行暴力破解，充分证明了GPU设备应用在密码领域的可行性。

2007年，Harrison 等[2]使用NVIDIA G80在CUDA平台上实现了AES密码算法，并获得了4倍的速度提升。同年，Manavski[3]使用NVIDIA GeForce 8800 GTX实现了AES密码算法，并在输入为8Mb的情况下，使得AES 128达到了8.28 Gbps；并且其性能相比于Open SSL也有20倍的提升。

2008年，Yeom等[4]在GeForce 8800 GTS上分别使用OpenGL以及CUDA库实现了分组密码算法ARIA，特别是使用CUDA库实现的ARIA，其吞吐量达到了4.8 Gbps。

2009年，Liu等[5]针对分组密码中对数据块进行独立操作的特性，将多种分组密码算法部署在NVIDIA GeForce 9800 GTX上，并取得了显著的性能提升。其中AES算法和RC5算法的吞吐率分别达到了4 200 Mbps和5 300 Mbps；而3DES取得了相比于CPU实现版的30倍的加速比。

2011年，Wu等[6]在GTX 9800上实现了并行化的MD5算法，相比于在AMD II X4 945四核CPU的实现，其获得了16倍的性能加速比。同年，为了减少安全部件中计算资源的使用与增加网页服务器吞吐率，Yeh等[7]使用GPU实现了3DES密码算法，并取得了5倍的加速比。

2016年，Tembhurne等[8]利用CUDA对RSA算法中的64-bit双精度计算操作进行优化，从而提高了整个算法的性能，使其加密与解密的性能分别提升了43.26倍和40.99倍。

在密码破解方面，2003年Lim等[9]使用MPI将John the Ripper并行化，使其可以在众核平台上运行，从而借助MPP的性能优势在更短时间内完成任务问题，其加速比为7.8倍。

2009年，Li Chang-xin等[10]针对PDF文档中的MD5-RC4组合加密流程，设计并实现了基于GTX 9800的并行优化方案，相对于算法的CPU实现其性能提升了5倍，而此加密性能的提升亦可以应用于PDF的暴力破解之中。

2013年，Schmidt等[11]使用CUDA库通过优化BW算法中的迭代过程对其进行了加速，并取得了与CPU集群相比显著的加速比。

上述成果针对某种算法提供加速平台上的加速方案，效果显著。相对于其他领域，密码算法有着独特的处理特点，但此领域算法也有较为统一的计算流程和应用方法，利用统一框架和众核平台的计算能力来设计该领域算法的并行优化方案，有助于快速开发和部署高吞吐率算法应用。因此，本文针对天河二号中MIC众核加速器平台，研究针对密码算法的加速框架和粗粒度算法加速技术，提供具有显著加速结果的应用验证。

3 密码算法及应用介绍

密码算法是用于加密和解密的数学函数，主要包括对称密码(也称传统密码)、公钥密码(也称非对称密码)和散列函数，对称密码算法简单快速、效率高，但安全性依赖于密钥。一旦密钥泄露，就意味着任何人都可以对信息进行加解密。公钥密码运算速度相对较慢，计算复杂、安全性更高。散列函数主要用于对大量数据产生指纹性信息摘要，用于实现电子签名。

常见的密码算法种类众多，在实际应用中广泛使用的有MD5、AES、RC4和SHA256等。这些算法的操作流程都较为相似，都是由迭代型的算法核心构成，在实际应用中也经常组合或级联多种算法来实现有效加密。例如，单向散列函数MD5算法，对于输入的信息产生128位的消息摘要(散列值)，常用于一致性验证、数字签名和安全访问认证等。AES是一个迭代的密码，使用一个循环结构，在循环中进行字节代替、行移位、列混淆、轮密钥加等操作。解密过程是加密过程的逆运算，每一步操作按照相反的顺序进行解密即可恢复成明文。RC4加密算法是在1987年由Ron Rivest设计的，是一种密钥长度可变的流加密算法簇。整个算法原理包含初始化算法KSA和伪随机子密码生成算法PRGA两大部分。安全散列算法SHA主要适用于数字签名标准里面定义的数字签名算法。对于长度可变的消息，SHA会产生一个消息摘要。当接收方收到消息时，可以利用消息摘要验证数据的完整性。

密码算法广泛应用于许多领域，如文件传输、网络通信、数据库系统安全以及身份认证等。在众多应用中都或多或少使用了密码算法或多种密码算法的组合，如PDF文件破解、zip文件破解、网络身份识别、安全登录等等。PDF文件使用AES、RC4算法加密，使用哈希函数的输出值作为加密算法的密钥，将密钥和串或数据流共同加密。对称密码算法中对称密钥的生成，可以达到一次一变不重复来确认用户身份，从而实现安全登录。

总的来说，现在广泛使用的密码应用的核心都是经典的对称密码算法，需要预处理大量加解密需要的数据，并且都有多用户同时加解密的并行需求。

4 面向众核平台的高吞吐率密码加速

4.1 面向众核计算构架的应用加速框架

本文所讨论的密码算法的相关应用属于计算密集型任务，具有很高的吞吐率要求，此类计算量较大的应用无法在CPU上短时间内完成，需要合理分配任务到众核平台如MIC或GPU上运行。因此，本文选择采用异构计算技术，提高密码算法相关应用的性能。CPU+GPU和CPU+MIC是两种主流的异构计算技术，都可以实现高并行计算和高计算吞吐，适用于计算密集型、高并行的应用。但比较来说，GPU需要采用新的编程架构，对自主研发的软件难度大，而MIC兼容传统的CPU编程模式，编程简单且易于维护；另一方面，GPU的核心是轻量级的，内核数量虽多但每个核的性能较弱。但是，MIC虽然只有几十个物理核心，每个核心的性能却比较强，可以兼顾粗粒度并行和细粒度并行。由此看来，本文所讨论的并行度较高、逻辑比较复杂的密码算法相关应用的加速，更适合于采用CPU+MIC的异构系统。

根据众核平台体系结构和算法并行特点，针对密码算法相关应用，本文提出了面向众核MIC平台的并行框架，如图1所示，包括三级并行结构，即多结点、结点内多MIC以及MIC内多线程，利用三级并行架构加速密码算法相关应用。

Figure 1 Accelerating framework of high througput图1 高吞吐率的应用加速框架

该框架中，首先将密码应用所需的数据按照计算量分配到不同结点的不同MIC上，MIC上的计算再按照多线程对任务进一步细分，分配到不同线程内，每个线程独立进行计算。CPU与MIC的数据传输过程采用offload模式，程序从CPU端启动，并选择性地将代码卸载(offload)到MIC端执行，MIC充当加速器的角色。在这种工作模式下，多次调用MIC函数进行计算时没有依赖关系，做到了数据传输层面的异步。MIC卡包含众多的物理核，同时每个核上可以开启多个线程。将数据合理分派到MIC上，充分利用MIC中所有的物理核发挥MIC的最大性能。最终将正确结果传送回CPU上，完成密码应用的运行。

该框架能有效加速密码算法相关应用的前提是：选择合适的任务分派技术将任务合理分配到每个线程，充分利用计算资源使程序执行时间最小化。这需要对程序的流程、数据流十分了解，从而选择在合适的层级上实现并行，以提高性能。根据密码应用的特性，我们采用粗粒度并行技术优化性能。

4.2 任务分派技术

密码应用加速最重要的一点是将数据合理分派到不同线程中，充分利用现有资源提高吞吐率，以达到加速的目的。

如图2所示，本文选择的任务分派技术是：首先将密码应用所需的数据进行预处理，存入一个行数为总线程数的二维动态数组，再用一个数组存放动态数组中每行数据的位数；然后，按用户输入的线程数参数，简单运算后决定将二维数组中合适的数据分派到哪个线程中；最后，每个线程使用相同的操作运行，直至计算完成，输出正确结果。

Figure 2 Task allocation mechanism图2 任务分派

这种任务分派技术线程选择灵活性高，可以根据用户输入的线程数参数决定将要测试的数据分配到哪个线程上运行。每个线程执行的操作相同，数据之间不存在相互依赖，并行度高。因此，用户可以充分利用现有线程，加速密码应用的运行。

当加密应用采用此种任务分派技术时，若使用相同密钥加密不同明文，将不同明文存入二维动态数组，使用线程计算函数决定将数组中明文分派给哪条线程进行加密，各线程使用相同密钥进行相同加密操作，最后输出密文。若使用不同密钥分别加密不同明文，将明文存入一个二维动态数组，再使用一个二维数组存放明文数组中每行数据对应使用的密钥，使用线程计算函数将明文数组和密钥数组中的数据分派到每个线程上，之后各线程进行相同的加密操作，最后输出密文。更复杂的情况是加密应用采用任务分组方式，组内明文使用相同密钥加密，组间明文使用不同密钥加密。这种情况下，将明文存入二维动态数组，密钥存入另一个二维动态数组，再使用一个二维数组存放每个明文的对应组号。首先根据线程计算函数，将明文数组中数据分派到各线程上，然后根据数组中明文的对应组号选择密钥数组中的对应密钥分派到线程上进行加密；各线程处理完成后，最后输出密文。

Figure 4 Extending all cores of MIC图4 扩展MIC所有核心

当暴力破解密码采用此种任务分派技术时，首先获取加密文件并解析文件，之后获取用户输入的规则，根据规则生成待测密码，将生成的密码存入二维动态数组。最后将用户输入的线程数参数经过简单运算，决定将数组中密码分派给哪个线程进行操作，得出正确密码后返回给CPU端。

当使用字典文件和规则破解密码时，在读取加密文件并解析文件后，再逐条读取字典文件，将读取的信息与用户输入的规则做对比，当信息符合规则时存入二维动态数组。再根据线程计算函数计算所得将数组中数据分派给各线程操作，最后返回结果。

4.3 异构粗粒度并行优化技术

密码算法相关应用的加速技术研究适合于CPU+MIC的异构系统，而并行程序是否选择在合适的层级上实现并行，是性能优化中最为关注的重要问题。要提高程序的执行性能，可以通过两个层次的并行来获得：一是粗粒度线程并行，二是细粒度线程并行。根据并行程序尽可能使用粗粒度的并行原则，尽可能在最上层并行化代码。

由于密码算法计算过程中数据依赖性强，每一步的输入都依赖于前一步的计算结果，因此采用粗粒度并行优化将相对完整的并行任务分配到各线程上执行。我们不关心应用中密码算法的内部运算过程，只是基于多线程优化技术，让每一个线程独立地完成密码算法任务。这样不仅使编程简单有效，还可以减少线程调度的次数，也就是减少了线程本身的开销所占的比例，隐藏底层的线程交互，也减少了不必要的同步带来的损耗。

Figure 3 Diagram of heterogeneous computation framework using CPU and MIC图3 CPU+MIC异构计算示意图

一般来说，将操作次数只有一次或者数据为所有线程所公用的任务，部署在CPU端，减少CPU端与MIC端的通信次数，提高运行效率。而计算密集但逻辑简单的任务，部署在MIC端。当程序在CPU端将数据预处理之后，根据给定的线程数目，同时启动MIC端多个指定数目的线程，将数据传输至各线程上。

当使用MIC端多个核心时，设置环境变量KMP_AFFINITY为scatter，线程“分布”到所有核上，如图4所示。首先所有线程在核间扩展，1到N条线程分布到N个核心上，每个核心使用一条线程。然后多于核心数目的其余线程再次从第一个核开始分配，N+1到N*2+1条线程表示N个核心各自使用的第二条线程，同理N*2+2到N*3+2条线程表示N个核心各自使用的第三条线程，N*3+3到N*4+3条线程表示n个核心各自使用的第四条线程。这样可以扩展MIC的所有核心。

多个不同线程执行几乎相同的计算量和相同的操作，产生结果后根据不同密码应用的特点采用不同的处理模式。模式1，所有线程上的数据都处理完毕后，MIC端从CPU端获得下一批数据再进行处理，直至所有数据处理完毕，应用完成。适用于多明文加密等需要将多个明文进行加密得到相应密文的应用。模式2，所有线程同一时间开始处理数据后，当某一线程优先完成任务，应用完成。适用于破解应用，只需要以最快的速度找到正确密码。最后，将结果返回至CPU端。

4.4 性能及分析

为证明面向众核构架的粗粒度并行加速框架的有效性和实际加速效果，我们选择了几个算法及典型算法组合进行具体实现和测试。首先，选择单一算法MD5进行吞吐量测试SA1(Single Algorithm)；其次，选择了两种很多加密应用中使用的典型算法组合：一种为包含AES、RC4和SHA256的算法组合CA1(Comprehensive Algorithm)，另一种为MD5和RC4的算法组合(CA2)。我们在CPU平台和MIC平台分别测试这三种算法，进行性能对比。

4.4.1 基于MIC平台的MD5算法优化

SA1中数据依赖相对较高，每一步操作都依赖前一步的计算结果，因此采用粗粒度并行优化。根据SA1的特征，我们基于MIC平台进行多线程优化，实现每个线程独立完成明文加密流程。

本节用来测试的程序采用分载模式，需要保留一个协处理器核心用于处理运行时的控制和数据交换。因此，虽然3120A拥有57个核心，但用来运行程序的核心数为56，最多可利用56*4=224条线程。

Table 1 Test platform for SA1表1 SA1测试平台

我们使用1 287.2 MB数据测试程序，表2为SA1在CPU和MIC平台上的性能对比。

Table 2 Performance comparisonof SA1 between MIC and CPU表2 SA1在MIC平台与CPU平台的性能对比

由表2可知，当MIC平台使用单核单线程时，与CPU平台单线程相比加速比为0.2，性能仅为CPU平台的1/5；随后单核上线程数虽然增加，与CPU平台相比加速比仍在0.5以下；但当单核双线程时与单核单线程相比，性能增加接近一倍；之后线程数增加，加速比增加较少。

当使用所有可用的56个核心时，每个核心使用单线程时，与CPU平台相比加速比将近10。之后每个核心使用的线程数增加到2、3、4时，加速比相差在0.2左右。而与MIC单核单线程相比，每个核心使用最多可用的4个线程时，加速比最大为102.05。

单核双线程时，性能增加最大的原因有两个：一是CPU主频为2 GHz，MIC主频为1.1 GHz，二者相差近一倍；二是MIC的指令调度机制决定了在每个时钟周期总是会调用一个新的线程执行。例如，当单个核上只使用一个线程时，调度机制决定在一个周期内高效切换到一个空闲线程上，从而与单核单线程相比性能提高近一倍，此后增加线程数性能提升也不再显著。

但是，在多核运行时，若使用112条线程即每个核心使用2条核心，每个核心上2线程之间产生竞争或等待公用内存缓冲区，造成了性能损耗，从而没有明显的性能提升。

4.4.2 基于众核构架的密码应用加速

CA1中三种对称密码算法计算密钥过程都使用了较为复杂的数学函数，步骤之间数据依赖性强，因此我们采用异构粗粒度并行优化技术，在高性能众核平台上实现应用加速。测试平台如表3所示。

Table 3 Test platform for CA1表3 CA1测试平台

使用数据量为196 KB的数据在CPU和MIC平台进行测试，并分别以CPU单核单线程和MIC单核单线程为基准计算加速比，对比应用CA1在CPU和 MIC平台上的性能。

由表4可以看出，当MIC单核运行时，只使用一条线程时，性能仅为CPU的0.6。这是因为MIC在单线程模式下执行程序时，会跳过调度新线程的任何其他时钟周期，直接使性能下降一半左右。MIC的指令调度机制默认使用至少2条线程解决计算量大的问题，因此当线程数逐渐增加到4时，性能逐渐上升，但加速比仍在2以下。

Table 4 Performance comparisonof CA1 between CPU and MIC表4 CA1在CPU平台和MIC平台上的性能对比

当MIC多核运行时，即使每个核心只使用一个线程，与单核单线程运行时相比加速比增加到25.4。但是，当每个核心使用线程数增加时，虽然执行时间依然比单核运行时缩短了许多，但比不上多核单线程时运行得快。这就说明，不是线程数越多，性能越高。有时线程间的竞争和等待会造成很大损耗，从而导致性能下降。

CA2运行过程中每条数据之间没有关联，各线程可以独立进行操作，因此采用粗粒度并行优化将数据分别分配到一个线程上。

Table 5 Test platform of CA2表5 CA2测试平台

经过粗粒度并行优化，我们对程序在MIC单核、多核上使用不同线程数进行了测试，并以原始程序在CPU上单线程的测试时间和MIC上单核单线程为基准得到优化的加速比，数据规模为74.94 MB。表6展示了CA2在CPU平台和MIC平台上的性能对比。

Table 6 Performance comparisonof CA2 between CPU and MIC表6 CA2在CPU平台和MIC平台上的性能对比

由表6可知，当MIC单核运行且只使用一个线程时，性能仅为CPU平台的0.24。之后增加线程数量，与CPU平台相比加速比增加0.1左右，最高不过CPU平台性能的一半左右。单核上增加线程数量，加速比增加0.4左右，当单核双线程时增加最快。

当MIC多核运行时，当所有可用核心各自只使用一个线程共同工作时，与CPU平台相比性能提升最快，加速比为13.2。同样与单核单线程相比加速比为55，此后在每个核心上增加使用线程数，加速比增加幅度变小。当充分利用56个核心共224个线程时，加速比达到最大117.9。

从上面的实验可以得出，当MIC单核运行时达不到CPU平台上的性能，主要是因为CPU与MIC之间的数据传输开销影响了MIC的计算性能。而当MIC多核运行时，将数据相对平均地分配到每个线程上，充分利用资源，最终获得了百倍的性能加速比。

5 结束语

CPU+MIC是现今最为流行的异构计算技术之一，在处理计算密集型任务时有着巨大优势。为解决密码算法相关应用的加速问题，本文提出了一种面向众核构架的粗粒度并行加速框架。介绍了加速框架需要的任务分派技术和异构粗粒度并行优化技术，通过几个算法及典型算法组合进行具体实现和测试，证明了加速框架的有效性和加速效果。该技术通过超级计算平台上的任务级并行可以很容易拓展到结节点环境运行，获得更高吞吐率。

参考文献:

[1] Kedem G, Ishihara Y. Brute force attack on UNIX passwords with SIMD computer[C]∥Proc of Conference on Usenix Security Symposium, 1999:8.

[2] Harrison O, Waldron J. AES encryption implementation and analysis on commodity graphics processing units[C]∥Proc of International Workshop on Cryptographic Hardware and Embedded Systems, 2007:209-226.

[3] Manavski S A. CUDA compatible GPU as an efficient hardware accelerator for AES cryptography[C]∥Proc of IEEE International Conference on Signal Processing and Communications, 2008:65-68.

[4] Yeom Y, Cho Y, Yung M. High-speed implementations of block cipher ARIA using graphics processing units[C]∥Proc of International Conference on Multimedia and Ubiquitous Engineering, 2008:271-275.

[5] Liu G, An H, Han W, et al. A program behavior study of block cryptography algorithms on GPGPU[C]∥Proc of International Conference on Frontier of Computer Science and Technology, 2010:33-39.

[6] Wu H, Liu X, Tang W. A fast GPU-based implementation for MD5 hash reverse[C]∥Proc of IEEE International Conference on Anti-Counterfeiting, Security and Identification, 2011:13-16.

[7] Yeh H P, Chang Y S, Lin C F, et al. Accelerating 3-DES performance using GPU[C]∥Proc of International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, 2011:250-256.

[8] Tembhurne J V, Sathe S R. RSA public key acceleration on CUDA GPU[C]∥Proc of the Artificial Intelligence and Evolutionary Computations in Engineering Systems, 2016: 365-375.

[9] Lim R. Parallelization of John the Ripper (JtR) using MPI[EB/OL][2017-12-01].https://www.researchgate.net/publication/266576776_Parallelization_of_John_the_Ripper_JtR_using_MPI.

[10] Li Chang-xin, Wu Hong-wei, Chen Shi-feng, et al. Efficient implementation for MD5-RC4 encryption using GPU with CUDA[C]∥Proc of International Conference on Anti-Counterfeiting, Security, and Identification in Communication, 2009:167-170.

[11] Schmidt B, Aribowo H, Dang H. Iterative sparse matrix-vector multiplication for accelerating the block Wiedemann algorithm over GF(2) on multi graphics processing unit systems[J]. Concurrency & Computation Practice & Experience, 2013, 25(4):586-603.