SHA散列算法擴(kuò)展指令探究

范建軍

(湖北科技學(xué)院 計算機(jī)科學(xué)與技術(shù)學(xué)院,湖北 咸寧 437100)

SHA散列算法擴(kuò)展指令探究

范建軍

(湖北科技學(xué)院 計算機(jī)科學(xué)與技術(shù)學(xué)院,湖北 咸寧 437100)

網(wǎng)絡(luò)安全領(lǐng)域中的鑒別和數(shù)字簽名是保障數(shù)據(jù)傳輸安全的重要手段之一，在互聯(lián)網(wǎng)的應(yīng)用中已被商家和客戶廣泛接受，但實(shí)現(xiàn)它們的算法計算量較大，耗費(fèi)時間，有時需要專用設(shè)備完成，成本較高。使用SHA指令系統(tǒng)，由CPU來完成這些任務(wù)，這可以很好地降低成本，提高速度。文章研究了SHA指令的特性并給出了具體的應(yīng)用。

SHA-1算法；SHA-256算法；散列指令

一、SHA散列算法概述[1]

SHA散列算法(Secure Hash Algorithm)廣泛地用于數(shù)字簽名和報文識別應(yīng)用程序開發(fā)中。該算法經(jīng)過安全領(lǐng)域?qū)＜叶嗄陙淼难芯亢蛯?shí)驗(yàn)，現(xiàn)已被全世界廣泛采用。該算法的核心是將接收到的一段報文以一種不可逆的方式將它轉(zhuǎn)換成一段長度較短、位數(shù)固定的輸出密文即散列值的過程。

SHA散列算法已由美國國家標(biāo)準(zhǔn)技術(shù)研究所發(fā)布作為美國國家標(biāo)準(zhǔn)，編號為FIPS PUB 180。該標(biāo)準(zhǔn)規(guī)定了SHA-1，SHA-224，SHA-256，SHA-384，和SHA-512這幾種單向散列算法。SHA-1，SHA-224和SHA-256適用于長度不超過264二進(jìn)制位的報文。SHA-384和SHA-512適用于長度不超過2128二進(jìn)制位的報文。其中，SHA-1生成的散列值為160位，SHA-256生成的散列值為256位。

SHA散列算法的處理過程包含5個步驟：

步驟1：附加填充比特。將報文以512位為單位分成若干個數(shù)據(jù)塊，每塊又分成16個32位字，但報文長度與448模512同余，不夠部分需填充比特位，使其達(dá)到要求，填充的最高位為1，其余都為0。

步驟2：附加長度值。將一個64位塊附加到報文后面，這個塊被當(dāng)作一個無符號二進(jìn)制數(shù)，它的值等于初始報文(填充前)的位長度。

步驟3：初始化SHA緩存。對于SHA-1使用一個160比特的緩存來存放該散列算法的中間值及最終值；該緩存分為5個32位的寄存器(A，B，C，D，E)。對于SHA-256使用一個256比特的緩存來存放該散列算法的中間值及最終值；該緩存分為8個32位的寄存器(A，B，C，D，E，F(xiàn)，G，H)。這些寄存器用規(guī)定的常量進(jìn)行初始化。

步驟4：處理512位(16個32位字)報文分塊序列中的每個報文塊。算法的核心由80輪(對于SHA-1)或由64輪(對于SHA-256)構(gòu)成，每輪結(jié)構(gòu)相似，但使用不同的原始邏輯Round函數(shù)。

1)SHA-1報文調(diào)度值Wi的計算：

For i=0 to 79

If (0 ≤ i ≤ 15) Wi = Mi

Else Wi = ROL1(Wi-3 XOR Wi-8 XOR Wi-14 XOR Wi-16)

2)SHA-256報文調(diào)度值Wi的計算，它包括σ函數(shù)，ROR(右旋轉(zhuǎn))和SHR (右移)操作：

For i=0 to 63

If (0 ≤ i ≤ 15) Wi = Mi

Else Wi = σ1(Wi-2) + Wi-7 + σ0(Wi-15) + Wi-16

其中σ0(W)是ROR7(W) XOR ROR18(W) XOR SHR3(W)，σ1(W)是ROR17(W) XOR ROR19(W) XOR SHR10(W)。

3)SHA-1各Round函數(shù)為：

For i=0 to 79

{

T = ROL5(A) + fi(B, C, D) + E + Ki + Wi；

E = D；D = C；C = ROL 30 (B)；B = A；A = T

}

其中，K是4個常量值(針對輪0-19、20-39、40-59、60-79)，f是基于相同的K四個函數(shù)之一。

4)SHA-1本次數(shù)據(jù)塊計算的最后輸出：

前一次數(shù)據(jù)塊計算的最后輸出加上本次數(shù)據(jù)塊計算最后一輪Round函數(shù)的對應(yīng)輸出。

5)SHA-256各Round函數(shù)為：

For i=0 to 63

{

T1 = H + Σ1(E) + Ch(E,F,G) + Ki + Wi

T2 = Σ0(A) + Maj(A,B,C)

H = G；G = F；F = E；E = D + T1；D = C；C = B；B = A；A = T1 + T2

}

K是64個常量值，Σ1()、Σ0()、Ch()、Maj()是邏輯函數(shù)。

6)SHA-256本次數(shù)據(jù)塊計算的最后輸出：

前一次數(shù)據(jù)塊計算的最后輸出加上本次數(shù)據(jù)塊計算最后一輪Round函數(shù)的對應(yīng)輸出。

步驟5：輸出。所有的512位數(shù)據(jù)塊處理完成后，最后階段產(chǎn)生的輸出就是該報文的散列值，SHA-1是160位，SHA-256是256位。

二、SHA指令執(zhí)行環(huán)境[2]

SHA指令是在原來的處理器SIMD指令集的基礎(chǔ)上添加的擴(kuò)展指令集,利用SIMD定義的16個全新的128位寄存器XMM0—XMM15，每個寄存器可以同時存放4個32二進(jìn)制數(shù)的特點(diǎn)，SHA指令使用它們來完成SHA算法的相應(yīng)處理步驟。SIMD的寄存器和這個4個32二進(jìn)制數(shù)在寄存器中排列順序見圖1：

圖1 XXM寄存器

XXM寄存器中的這個128位SIMD的二進(jìn)制數(shù)據(jù)中包含了4個32二進(jìn)制數(shù)DATA0、DATA1、DATA2和DATA3。

三、SHA散列算法指令集的研究[3]

SHA散列算法指令集分2組，一組是針對SHA-1散列算法，另一組是針對SHA-256散列算法。類似于通用的X86指令，SHA指令包括兩種尋址方式：reg-reg和reg-mem。

1.SHA-1新指令集

SHA-1指令共4條指令。兩條指令sha1msg1和sha1msg2提供SHA-1算法的調(diào)度值計算。sha1msg1指令加速調(diào)度值的Wt-14 XOR Wt-16部分的計算。sha1msg2指令加速 Wt-3與之前計算的Wt-8 XOR Wt-14 XOR Wt-16的異或，然后左旋轉(zhuǎn)1位，最終得到4個32位調(diào)度值。sha1rnds4指令執(zhí)行4輪Round函數(shù)功能。sha1nexte指令快速計算出E。

1)SHA1RNDS4 xmm1, xmm2/m128，imm8

說明：使用由第一個操作數(shù)提供的初始化SHA-1狀態(tài)變量 (A,B,C,D)，由第二個操作數(shù)提供的一些預(yù)先計算好的分別用于4輪的報文雙字以及狀態(tài)變量E，執(zhí)行4輪Round函數(shù)計算，更新SHA-1的狀態(tài)(A、B、C、D)，將結(jié)果存儲到目的操作數(shù)中，imm8決定使用哪一個f()。SHA1RNDS4指令的操作：

IF(imm8[1:0]=0)

THEN f()←f0(), K←K0 ;

ELSE IF (imm8[1:0] = 1 )

THEN f()←f1(), K←K1 ;

ELSE IF (imm8[1:0] = 2 )

THEN f()←f2(), K←K2 ;

ELSE IF (imm8[1:0] = 3 )

THEN f()←f3(), K←K3;

FI;

A←SRC1[127:96];

B←SRC1[95:64];

C←SRC1[63:32];

D←SRC1[31:0];

W0E←SRC2[127:96];

W1←SRC2[95:64];

W2←SRC2[63:32];

W3←SRC2[31:0];

Round i = 0 operation:

A_1←f(B,C,D)+(A ROL 5)+W0E+K;

B_1←A;

C_1←B ROL 30;

D_1←C;

E_1←D;

FOR i = 1 to 3

A_(i+1)←f(B_i,C_i,D_i)+(A_i ROL 5)+Wi+E_i+K;

B_(i+1)←A_i;

C_(i+1)←B_i ROL 30;

D_(i+1)←C_i;

E_(i+1)←D_i;

ENDFOR

DEST[127:96]←A_4;

DEST[95:64] ←B_4;

DEST[63:32] ←C_4;

DEST[31:0] ←D_4;

2)SHA1NEXTE xmm1, xmm2/m128

說明：第一個操作數(shù)存放的是根據(jù)4輪計算之后SHA-1的狀態(tài)值，利用其A值計算出E值并與第一個操作數(shù)存放的調(diào)度值相加，再將它們存儲在目的操作數(shù)中。

3)SHA1MSG1 xmm1, xmm2/m128

說明：為下一次SHA-1的4個調(diào)度值做一次中間計算。

4)SHA1MSG2 xmm1, xmm2/m128

說明：做最后一次計算，以得到下一次SHA-1的4個調(diào)度值。

2.SHA-256新指令集

SHA-256指令共有3條指令。兩條指令sha256msg1和sha256msg2提供SHA-256算法的調(diào)度值計算。sha256msg1指令加速調(diào)度值的σ0(Wt-15) + Wt-16部分的計算。sha256msg2指令加速σ1(Wt-2)與之前計算的Wt-7 + Σ0(Wt-15) + Wt-16的加法，最終得到4個32位調(diào)度值。sha256rnds2指令執(zhí)行2輪Round函數(shù)功能。

1)SHA256RNDS2 xmm1, xmm2/m128,

說明：執(zhí)行2輪SHA-256操作。第一個操作數(shù)是初始化的SHA-256狀態(tài)(C,D,G,H)，第二個操作數(shù)是初始化的SHA-256狀態(tài)(A,B,E,F)，XMM0存儲著預(yù)先計算好的分別用于下2輪的報文雙字。請注意，只有xmm0較低的兩個雙字被指令使用。把更新的SHA-256狀態(tài)(A，B，E，F(xiàn))寫入到第一個操作數(shù)，而第二個操作數(shù)可以作為以后輪的更新狀態(tài)(C，D，G，H)。SHA256RNDS2指令的操作：

A_0←SRC2[127:96];

B_0←SRC2[95:64];

C_0←SRC1[127:96];

D_0←SRC1[95:64];

E_0←SRC2[63:32];

F_0←SRC2[31:0];

G_0←SRC1[63:32];

H_0←SRC1[31:0];

WK0←XMM0[31: 0];

WK1←XMM0[63: 32];

FOR i = 0 to 1

A_(i+1)←Ch(E_i,F_i,G_i)+Σ1(E_i)+WKi+H_i+Maj(A_i,B_i,C_i)+Σ0( A_i);

B_(i+1)←A_i;

C_(i+1)←B_i ;

D_(i+1)←C_i;

E_(i+1)←Ch(E_i,F_i,G_i)+Σ1(E_i)+WKi+H_i+D_i;

F_(i+1)←E_i ;

G_(i+1)←F_i;

H_(i+1)←G_i;

ENDFOR

DEST[127:96]←A_2;

DEST[95:64] ←B_2;

DEST[63:32] ←E_2;

DEST[31:0] ←F_2;

2)SHA256MSG1 xmm1, xmm2/m128

說明：為下一次SHA-256的4個調(diào)度值做一次中間計算。

3)SHA256MSG2 xmm1, xmm2/m128

說明：做最后一次計算，以得到下一次SHA-256的4個調(diào)度值。

四、應(yīng)用舉例[4]

下面給出SHA-1指令的應(yīng)用實(shí)例。

SHA-1每次處理一個512位即64個字節(jié)的數(shù)據(jù)塊，在處理過程中需要做80輪Round計算。下面給出運(yùn)用SHA-1指令編寫實(shí)施SHA-1算法的程序代碼。假設(shè)64個字節(jié)大小的數(shù)據(jù)塊存儲在內(nèi)存緩沖區(qū)中，用指針BLOCK_PTR指向該內(nèi)存緩沖區(qū)，代碼中涉及的工作變量如ABCD_SAVE、BLOCK0表示某一個XMM寄存器。

首先將初始值保存到工作變量，先從內(nèi)存緩沖區(qū)取16個字節(jié)，做0-3輪，由sha1rnds4指令完成；再從內(nèi)存緩沖區(qū)取16個字節(jié)，做4-7輪，由sha1nexte、sha1rnds4指令完成，sha1msg1指令為下一輪準(zhǔn)備調(diào)整值；再一次從內(nèi)存緩沖區(qū)取16個字節(jié)，做8-11輪，由sha1nexte、sha1rnds4指令完成，sha1msg1和pxor指令為下一輪準(zhǔn)備調(diào)整值；從內(nèi)存緩沖區(qū)中取出最后16個字節(jié)，做12-15輪，由sha1nexte、sha1msg2、sha1rnds4指令完成，sha1msg1和pxor指令為下一輪準(zhǔn)備調(diào)整值；代碼如下：

movdqa ABCD_SAVE, ABCD

movdqa E_SAVE, E0

movdqu BLOCK0, [BLOCK_PTR + 0*16]

pshufb BLOCK0, SHUF_MASK

paddd E0,BLOCK0

movdqa E1,ABCD

sha1rnds4 ABCD, E0, 0

movdqu BLOCK1, [BLOCK_PTR + 1*16]

pshufb BLOCK1, SHUF_MASK

sha1nexte E1, BLOCK1

movdqa E0, ABCD

sha1rnds4 ABCD, E1, 0

sha1msg1 BLOCK0, BLOCK1

movdqu BLOCK2, [BLOCK_PTR + 2*16]

pshufb BLOCK2, SHUF_MASK

sha1nexte E0, BLOCK2

movdqa E1,ABCD

sha1rnds4 ABCD, E0, 0

sha1msg1 BLOCK1, BLOCK2

pxor BLOCK0, BLOCK2

movdqu BLOCK3, [DATA_PTR + 3*16]

pshufb BLOCK3, SHUF_MASK

sha1nexte E1, BLOCK3

movdqa E0, ABCD

sha1msg2 BLOCK0, BLOCK3

sha1rnds4 ABCD, E1, 0

sha1msg1 BLOCK2, BLOCK3

pxor BLOCK1, BLOCK3

之后繼續(xù)直到第64-67輪，都采取12-15輪模式完成，但不包括讀取數(shù)據(jù)部分，代碼模式如下：

sha1nexte E0,BLOCK0

movdqa E1,ABCD

sha1msg2 BLOCK1, BLOCK0

sha1rnds4 ABCD, E0, 0

sha1msg1 BLOCK3, BLOCK0

pxor BLOCK2, BLOCK0

末尾12輪(68-79)只需要少量的指令就可以完成，代碼如下：

;;68-71輪

sha1nexte E1,BLOCK1

movdqa E0,ABCD

sha1msg2 BLOCK2, BLOCK1

sha1rnds4 ABCD, E1, 3

pxor BLOCK3, BLOCK1

;;72-75輪

sha1nexte E0,BLOCK2

movdqa E1,ABCD

sha1msg2 BLOCK3, BLOCK2

sha1rnds4 ABCD, E0, 3

;;76-79輪

sha1nexte E1,BLOCK3

movdqa E0,ABCD

sha1rnds4 ABCD, E1, 3

最后用sha1nexte指令計算E的最終值，paddd指令計算ABCD的最終值：

sha1nexte E0, E_SAVE

paddd ABCD, ABCD_SAVE

SHA-256指令的應(yīng)用實(shí)例類似上述代碼思路，受篇幅限制不再舉例。

五、結(jié)論

隨著Intel i7處理器的廣泛普及，使用SHA指令必將給程序設(shè)計人員在開發(fā)網(wǎng)絡(luò)安全產(chǎn)品時帶來新選擇。利用文中詳細(xì)介紹的內(nèi)容，程序員可以簡化相關(guān)算法的代碼設(shè)計，創(chuàng)造出更好的信息識別軟件產(chǎn)品。

[1] Federal Information Processing Standards Publication 180-2：Announcing the SECURE HASH STANDARD[M/CD]. 2002 August 1. http://csrc.nist.gov/publications/fips/fips180-2/

[2]Intel Corporation: Intel 64 and IA-32 Architecture Software Developer's Manual Volume 1: Basic Architecture[M/CD]. http://WWW.INTEL.COM Order Number 253665-059US 2016.

[3]Intel Corporation: Intel 64 and IA-32 Architecture Software Developer's Manual Volume 2: Instruction Set Reference [M/CD]. http://WWW.INTEL.COM Order Number 325383-059US 2016.

[4]Se-Joon Chung ，Euiwoong Lee: In-Depth Analysis of Bitcoin Mining Algorithm Across Different Hardware[M/CD]. http://WWW.INTEL.COM.

2095-4654(2016)12-0053-04

2016-06-18

TP313

A