應用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).