快速實(shí)現SHA-1算法的硬件結構

算法分析

從算法描述可以看出，SHA-1最核心的計算是一個(gè)計算5個(gè)中間變量的迭代：

An=S5(A n-1)+f n(B n-1，C n-1，D n-1)+

E+Wn+Kn，

Bn=A n-1，

Cn=S30(B n-1)，

Dn=C n-1，

En=D n-1.

在硬件實(shí)現中，5個(gè)變量在一個(gè)周期內同時(shí)由組合邏輯電路根據上次迭代的計算值產(chǎn)生，因此每次迭代所需要的時(shí)間是由最慢的計算過(guò)程決定。這樣一條最慢的計算路徑也就是所謂的關(guān)鍵路徑。如果完全按照SHA-1的原始算法進(jìn)行硬件設計，那么很明顯的關(guān)鍵路徑是變量A的計算。在每次迭代過(guò)程中，計算變量A需要進(jìn)行4次32bit的整數加法和若干組合邏輯。這些計算一共需要的時(shí)間也就是算法硬件實(shí)現的最短周期。正是因為變量A的計算比較復雜，造成SHA-1算法硬件實(shí)現的工作頻率難以提高。

因此，加快SHA-1硬件實(shí)現的計算速度關(guān)鍵就是改變迭代結構，從而縮短每次迭代過(guò)程的關(guān)鍵路徑。

硬件快速實(shí)現的新結構

觀(guān)察算法可發(fā)現，除了變量A以外，其他4個(gè)變量的計算都相當簡(jiǎn)單。因此，如果將變量A的計算過(guò)程通過(guò)一定方式分解成若干并行的計算，那么就可以在不增加迭代次數的前提下，縮短整個(gè)計算的關(guān)鍵路徑。

出于這種目的，1997年A.Bosselaers等人對SHA-1算法的結構進(jìn)行了分析，發(fā)現SHA-1算法的數據流圖可以分解成并行的7路數據處理，每路數據上一個(gè)周期只需一個(gè)基本操作：加法、“異或”或者循環(huán)移位。

在此關(guān)于SHA-1結構結論的基礎上，本文通過(guò)引入中間變量的方法，將計算的關(guān)鍵路徑分解成若干個(gè)較短的路徑，從而達到加速硬件計算的效果?？紤]到硬件實(shí)現中32bit整數加法的延時(shí)遠遠大于循環(huán)移位和普通邏輯運算，所以分析關(guān)鍵路徑時(shí)只考慮加法的代價(jià)，而忽略其他邏輯運算的延時(shí)。

首先引入中間變量P n-1=fn(B n-1，C n-1，D n-1)+E n-1+Wn+Kn，那么可以得到An=S5(A n-1)+P n-1。也就是說(shuō)，將第n次迭代的部分計算提前到第n-1次迭代中進(jìn)行計算。變形后，第n次迭代中A的計算只需要進(jìn)行一次32bit整數加法。

但是這種方式下，變量P的計算仍然需要依賴(lài)于同一次迭代中的其他變量，也就是說(shuō)在一次迭代中需要在計算完其他變量后才能計算出P，這樣的話(huà)計算的關(guān)鍵路徑還是沒(méi)有縮短。所以還要充分利用A到E5個(gè)變量之間的相互關(guān)系

B n-1=A n-2，

C n-1=S30(B n-2)，

D n-1=C n-2，

E n-1=D n-2.

將P的計算變化為P n-1=f n(A n-2，S30(B n-2)，C n-2)+D n-2+Wn+Kn。如此之后，第n-1輪的P值可以完全依賴(lài)于前一輪也就是第n-2輪的變量值計算而得。迭代計算的關(guān)鍵路徑就分裂成變量A和P兩路并行的計算。

類(lèi)似的再引入其他中間變量，不斷的分解關(guān)鍵路徑，最終的迭代可變形為

An=S5(A n-1)+P n-1，

Pn=f n+1(A n-1，S30(B n-1)，C n-1)+Q n-1，

Qn= C n-1+R n-1，

Rn=W n+3+K n+3，

Bn=A n-1，

Cn=S30(B n-1).

可以發(fā)現通過(guò)引入中間變量，使得計算變量A的關(guān)鍵路徑分解成A、P、Q、R的4路并行計算，所需要的4次加法平均在4個(gè)周期內完成。這樣每次迭代過(guò)程中任何一個(gè)變量的計算最多只需要一次32bit整數加法和少量組合邏輯。在此基礎上，SHA-1算法可以通過(guò)如下方法來(lái)計算

1)將輸入的512bit消息分成16個(gè)字W0，W1， …，W15;

2)For t=16 to 79 let Wt=S1(W t-3

W t-8

W t-14

W t-16);

3)LetA=H0，B=H1，C=H2，D=H3;

4)LetP=f 0 (B，C，D)+E+W0+K0，Q=D+W1+K1，R=W2+K2;

5)Fort=0 to 79 do

a)TEMP=S5(A)+P;

b)P=f t+1(A，S30(B)，C)+Q;

c)Q=C+R;

d)R=W t+3+K t+3;

e)B=A;C=S30(B);A=TEMP;

6)LetH0=H0+A，H1=H1+B，H2=H2+ C，H3=H3+S30(A76)，H4=H4+S30(A75)。

雖然引入中間變量的計算后，每塊數據需要額外增加一個(gè)預計算的步驟4)，但是因為關(guān)鍵路徑得以縮短，整體硬件實(shí)現的速度仍然會(huì )大大提高。