应用SIMD并行技术的SHA-1加密算法的批量实现

陈亦欢，严伟超

(华南理工大学软件学院，广州 510006)

加密技术是对信息进行编码的技术。编码是把原来可读信息(又称明文)译成代码形式(又称为密文)。加密技术的要点是加密算法。随着信息安全技术的不断发展，利用各种加密算法进行口令保护的技术也在不断提高，计算的时间与复杂度也在不断增大，传统意义上各种加密算法的串行版本已经无法满足应用的需求，迫切需要应用更效的指令集来编写加密算法，以形成更为强大的计算能力［1-7］。

SSE2(sreaming SIMD etensions 2)指令集是Intel公司在SSE指令集基础上发展起来的。SSE2使用了144个指令，扩展了MMX技术和SSE技术。这些指令提高了应用程序的运行性能。随MMX技术引进的SIMD整数指令从64位扩展到128位，使SIMD整数类型操作的有效执行率成倍提高，也就是说1条SSE2指令1次可以对4个32位或2个64位的数据类型进行运算处理。SSE2指令由2部分组成:SSE部分和MMX部分。SSE部分主要负责处理浮点数，而MMX部分则专门计算整数［8-9］。本文旨在使用SSE2指令集的MMX部分实现对大量数据的SHA-1散列运算。

1 SHA-1算法

1.1 SHA-1 介绍

1993年美国国家标准局(NIST)公布了安全散列算法SHA(后称之为SHA-0)，该算法已经被美国政府作为标准，即 FIPS 180 Secure Hash Standard(SHS)，实际的标准文件称之为安全散列标准。FIPS规定必须用SHS实施数字签名算法，主要是和数字签名算法(DSA)相配合。很快在SHA算法中发现了弱点，1994年 NIST公布了SHA的改进版 SHA-1，即 FIPS 180-1 Secure Hash Standard(SHS)，取代了SHA。SHA-1的设计思想基于MD4，因此在很多方面与MD5算法有相似之处。SHA-1对任意长度的明文可以生成160 bits的消息摘要［10-12］。

1.2 SHA-1 描述

SHA-1对明文的处理和MD5相同，第1个填充位为“1”，其余填充位均为“0”，然后将原始明文的真实长度表示为64 bits，附加在填充结果后面。填充后明文的长度为512的整数倍。填充完毕后，明文按照512 bits分组(block)。

SHA-1操作的循环次数为明文的分组数，对每一个明文分组的操作有4轮，每轮20个步骤，共80个步骤。每一步操作针对5个32 bits的寄存器(记录单元)进行。这5个工作变量(记录单元、链接变量)的初始值为:

SHA-1中使用了一组逻辑函数ft(t表示操作的步骤数，0≤t≤79)。每个逻辑函数均对3个32 bits的变量B、C、D进行操作，产生一个32 bits的输出。逻辑函数ft(B，C，D)定义为:

SHA-1中同时用到了一组常数Kt(t表示操作的步骤数，0≤t≤79)，每个步骤使用1个。这一组常数的定义为:

将明文按照规则填充，然后按照512 bits分组为 M(0)，M(1)，…，M(n)，对每个512 bits的明文分组M(i)操作的步骤的操作如下:

1)将512 bits的1个明文分组又分成16个32 bits的子分组:M0，M1，…，M15，M0 为最左边的一个子分组。

2)再按照以下法则将16个子分组变换成80个32 bits的分组:W0，W1，…，W79:

3)将5个工作变量中的数据复制到另外5个记录单元中，即令:

4)进行4轮共80个步骤的操作(t表示操作的步骤数，0≤t≤79):

5)第4轮的最后一步完成后，再作运算:

所得到的5个记录单元中的 H0、H1、H2、H3、H4成为下一个分组处理时的初始值。

最后一个明文分组处理完毕时，5个工作变量的数值级联成为最终的散列值。整个实现过程如图1所示。

图1 SHA-1的实现流程

2 SIMD技术

多核处理器技术是当前高性能微处理器系统发展的主流趋势。以Intel为代表的国际主流微处理器厂商已经成功推出了多款双核和四核微处理器系统，应用领域也从高端服务器向一般桌面系统延伸。如何充分发挥多核处理器在性能方面的优势，已经成为对当前软件设计领域的重要挑战。

2.1 SIMD 指令

SIMD(single instruction multi data，单指令流多数据流)指令是现代微处理器指令系统的重要组成部分。在1条SIMD指令中可以实现多个数据的并行操作，即用1个控制器对1组数据(又称“数据向量”)中的每一个分别执行相同的操作来实现空间上的并行性，从而实现数据级并行，可以有效提高程序的执行效率。

当前广泛使用的SIMD指令是x86体系结构中的MMX指令集和SSE指令集。1997年，Intel公司的Pentium II处理器中引入了MMX指令集，其数据宽度为64位，一次可以完成8个1字节或4个2字节或2个4字节的整数加减运算。1999年，Intel公司的Pentium III处理器中引入了SSE指令集，其数据宽度为128位，一次可以完成4个4字节的单精度浮点算术运算或者是2个8字节双精度浮点运算。在SSE指令的基础上，Intel公司又相继推出了SSE2、SSE3和SSE4的指令扩展。表1给出了MMX和各SSE指令系统的功能扩展。

2008年，Intel宣布支持AVX(Advanced Vector eXtended，高级向量扩展)，并且将原有的SSE操作从128位扩展到256位，重新定义了约250条指令的操作，并且增加了128条新指令。随着微电子技术的发展，SIMD的数据宽度还将不断增加。

表1 Intel公司SIMD指令系统功能

2.2 寄存器结构

图2给出了32位Intel处理器的寄存器结构，其中MMX指令系统和SSE指令系统涉及到8个128位的XMM寄存器、8个64位的MMX寄存器、MXCSR寄存器、通用寄存器、EFLAGS寄存器、内存等。SIMD指令操作的数据主要在XMM寄存器和MMX寄存器。除此之外，8个通用寄存器用于SSE指令内存寻址，也可存放一些SSE指令的操作数。MXCSR寄存器存放SIMD指令的状态和控制信息。EFLAGS标志寄存器存放部分SSE比较指令的执行结果［9-10］。

图2 SSE指令的寄存器结构

MMX、SSE和SSE2支持的数据类型如图3所示。SSE3和SSE4中没有引入新的数据类型。

2.3 SSE2的指令功能

SSE2可以支持双精度浮点、字节整数、16位整数、32位整数和64位整数等多种数据类型，提供了双精度浮点计算、64位和128位的整数计算，以及Cache控制和指令顺序化功能［9-10］。

图3 MMX，SSE，SSE2指令的数据类型

双精度浮点计算支持打包或标量形式的数据移动、算术运算、比较、转换、逻辑运算和混洗操作。数据移动指令支持双精度浮点在XMM寄存器之间，或者XMM寄存器和主存之间的数据移动。算术运算支持双精度浮点数的加法、减法、乘法、除法、平方根、最大/最小计算。逻辑运算支持双精度浮点数的与(AND)，与非(AND NOT)，或(OR)以及异或(XOR)操作。比较指令则可以比较打包或标量形式的双精度浮点数，并将结果写入目的操作数或者EFLAGS寄存器。混洗和解包指令实现了2个XMM寄存器中双精度浮点数的混洗或交换，如图4所示。转换指令可以完成双精度浮点与单精度浮点或者双精度浮点与双字整数或者单精度浮点与双字整数之间的格式转换。

图4 SSE2的混洗和解包指令

整数指令则实现了双字数据移动、加法、减法、乘法、混洗、逻辑左移、逻辑右移、解包、MMX寄存器和XMM寄存器之间的数据交换等功能。

Cache控制指令则可以实现Cache特定行的清除、非重复使用变量的直接写入内存、存储器访问顺序化、暂停和分支预测等功能。

2.4 SSE指令的内嵌原语

可以在程序中直接使用汇编语言调用SSE指令，这样虽然效率较高，但是程序的可读性和可维护性比较差。为方便使用SSE指令，编译器将指令封装成intrinsic形式方便程序员以C语言函数的方式来调用这些指令。但是intrinsic和指令并不是一一对应的，对于一些简单的操作，intrinsic对应于1条指令，而对一些复杂操作，intrinsic对应若干条指令，在这种情况下选择合适的intrinsic就显得十分重要。不同编译器的内嵌原语有所不同，在此只对 GCC编译器中的内嵌原语加以介绍。

目前Gcc最高可以支持SSE4.2指令集，其中不同的头文件对应不同的SSE指令集。表2列举了GCC中头文件的定义。

表2 Gcc中头文件的定义

在使用SSE原语时，常常需要将内存中的数据按照一定大小对齐。Gcc中提供了void*memalign(size_t alignment，size_t size)。原语用于程序中对齐声明的内存单元，其中对齐的大小可以是2的整数次幂，例如以下代码:

申请的内存单元ptr将按照16字节对齐，即该数据结构的起始地址为16的整倍数，内存大小为16字节。

Gcc还提供了_m64和_m128(_m128i和_m128d)等数据类型分别对应于64位的MMX寄存器和128位的XMM寄存器。在使用这些数据类型时，由编译器为数据自动分配相应的寄存器，不需要手工控制，可以有效减少程序设计的难度。

内嵌原语的一般结构为_mm_＜intrin_op＞_＜suffix＞。其中intrin_op为原语的操作码，suffix为操作的数据类型。suffix首先由p(packed，打包)，ep(extended packed，扩展打包)，s(scalar，标量)开始，然后跟随具体的数据类型，如表3所示。

表3 内嵌原语suffix中数据类型的含义

3 基于SSE2指令集的SHA-1实现

鉴于SSE2具有丰富的数据读取、存储、算术运算、逻辑运算、置位运算、转换运算、比较操作等指令以及SHA-1基于整数运算这一现实，使用SSE2指令集来实现SHA-1是大有裨益的。使用SSE2指令集实现的SHA-1算法，1次可对4条等长的明文数据进行运算，如 abc、123、ABC、Ab1。根据以上SHA-1算法的描述，对某4组数据填充完整后的关键代码如下:

在此，约定凡是具有128 bit的SSE2类型__m128i，变量名前均以“__*”为前缀。

5个工作变量(记录单元、链接变量)的初始化可定义为:

同理，SHA-1中同时用到了一组常数Kt(t表示操作的步骤数，0≤t≤79)可定义为:

逻辑函数ft(B，C，D)需要进行或、与、与非、异或等逻辑操作，则可定义为:

然后按照填充好的4*512 bits(4意为4组填充好的数据，SSE2可1次对此4组数据进行运算)分成4*16组:

特别指出，如果 M［i］‴，M［i］″，M［i］'，M(i)是连续内存地址的值，则可用

内嵌原语来装载数据，这样可以大大提高性能［5］。因为1条_mm_set_epi32()语句会被编译器翻译成7条SSE2指令:

而_mm_loadu_si128()只能编译成1条pmovdqu指令。这样在同等情况下就大大提高了利用SSE2指令的效率，提高了代码性能。

对每个数据分组__M(i)操作的步骤:

1)按以下法则将16个子分组__M(i)变换成80个4×32bits的分组__W0，__W1，…，__W79:

2)将5个工作变量中的数据复制到另外5个记录单元中，令

3)进行4轮共80个步骤的操作，t表示操作的步骤数，0≤t≤79:

其中__ROL(__A，5)及__ROL(__B，30)表示SSE2类型的变量循环左移若干位，定义为:

4)第4轮最后一步完成后，再作加运算:

所得到的5个记录单元中的 __H0、__H1、__H2、__H3、__H4成为下一个分组处理时的初始值。最后一个明文分组处理完毕时，5个工作变量的数值级联成为最终的散列值。此时，这5个工作变量包含了4条明文所对应的散列值，如图5所示，即1次SHA-1处理可以产生4条散列值，达到了CPU并行计算的效果。

图5 5个工作变量级联成的4条最终散列值

特别注意，由于SSE2是批量处理明文数据，故这些明文数据有一定的宽度限制，即同时处理的4条明文数据必须是等长的。但是，不用额外增加硬件设备，只需要将MMX指令系统寄存器和SSE指令系统的寄存器充分利用起来，就能提高程序的并行计算能力，此优点是无可比拟的。

4 结束语

本文对安全散列算法进行了深入分析，给出了SHA-1算法的计算步骤，提出了一种使用SIMD技术批量实现SHA-1算法的方法。与传统的串行程序相比，该算法进一步地利用了CPU计算的并行能力，提高了应用程序的开发效率，为大量数据的散列运算提供了参考。除SHA-1以外，其他的散列算法，如RIPEMD-160、MD4、MD5及由其引申的算法也适宜使用SIMD技术对其进行批量运算，这为信息安全与高性能计算都有积极的影响。

［1］陈园园，朱孝成，叶甬渝.一种改进的DCT信息隐藏算法［J］.重庆理工大学学报:自然科学版，2011(12):100-105.

［2］刘文荣.计算机安全技术中的数据加密技术分析［J］.信息系统工程，2012(3):66-67.

［3］徐秦.详解加密技术概念及加密方法［J］.科技信息，2010(1):731-732.

［4］纪钢，朱孝成，张菲.基于LSB二次嵌入隐藏算法在材料腐蚀图像中的应用［J］.重庆理工大学学报:自然科学版，2010(7):81-85.

［5］刘君，李黎，郭秋东.网络激光标示二维码的Square加密算法［J］.激光杂志，2010(2):35.

［6］冯俊伟，唐云海，李云飞，等.涉密网络中信息输入输出控制和管理［J］.四川兵工学报，2010(6):132-135.

［7］鲁丁，颜才杰，金伟民.基于分数傅立叶变换和相位恢复算法的彩色图像加密［J］.激光杂志，2010(6):18-19.

［8］Intel处理器定义［EB/OL］.［2012-01-18］.SSE2 http://www. intel. com/support/cn/processors/sb/cs-030123.htm?wapkw=(sse2)

［9］Intel Corporation.IA 32 lntel Architecture Software Developer’s Manual Volume:1 Basic Architecture［EB/OL］.［2011-12-12］.Order Number 253665-038US 2011.

［10］华南理工大学.多核软件设计课程-英特尔?软件网络/SSE 编程［EB/OL］.［2011-09-21］.http://software.intel.com/zh-cn/articles/scut-mcpcourse/?wapkw=(SSE).

［11］William S.密码学与网络安全:原理与实践［M］.4版.北京:电子工业出版社，2006:254.

［12］SSE优化中_mm_set_* 的陷阱http://software.intel.com/zh-cn/blogs/2009/12/06/sse_mm_set/?wapkw=(sse).