快速實現SHA-1算法的硬件結構

摘要：安全散列算法是數字簽名等密碼學應用中重要的工具。目前最常用的安全散列算法是SHA-1算法，它被廣泛地應用于電子商務等信息安全領域。為了滿足應用對安全散列算法計算速度的需要，該文提出了一種快速計算SHA-1算法的硬件結構。該方法通過改變硬件結構、引入中間變量，達到縮短關鍵路徑的目的，進而提高計算速度。這種硬件結構在0.18Lm工藝下的ASIC實現可以達到3.9Gb/s的數據吞吐量，是改進前的兩倍以上;它在FPGA上實現的性能也接近目前SHA-1算法商用IP核的兩倍。

關鍵詞：集成電路設計;安全散列算法(SHA-1);關鍵路徑;硬件結構

單向散列函數是密碼學中一種重要的工具，它可以將一個較長的位串映射成一個較短的位串，同時它的逆函數很難求解。許多安全技術中都會用到單向散列函數的這種特殊性質，比如數字簽名、密碼保護、消息鑒別等。鑒于單向散列函數在密碼系統中的重要地位，密碼學家們設計了各種各樣的安全散列函數。目前最常用的散列函數是NIST于1995年頒布的安全散列算法SHA-1。

SHA-1算法和之前的MD4、MD5等安全散列算法原理很接近，但是安全性更好。它可以通過一系列的迭代計算把任意長度的比特串壓縮成長度為160bit的位串。而且一般認為它的這個計算過程在密碼學意義上是單向的，也就是說很難找到兩個不同的位串可以壓縮成相同的160bit。到目前為止，還沒有對SHA-1有效的攻擊方法。

由于SHA-1算法的良好特性，它被廣泛使用在諸如電子商務這樣的現代安全領域，尤其是被大量應用于公鑰密碼系統的數字簽名中。目前幾乎所有相關密碼協議、標準或者系統中，都包括了SHA-1算法，其中比較著名的有SSL、IPSec和PKCS。在這些場合下，能否快速計算出消息的散列值直接影響到整個系統的處理能力。但是，由于SHA-1算法本身是一個很復雜的算法，計算量也較大，加上每次迭代都需要依賴上次的計算結果，因此不論是硬件還是軟件實現，計算速度都很有限，這大大限制了算法的適用場合。

本文提出一種新的硬件實現方法，通過改變迭代結構，達到縮短關鍵路徑的目的，進而提高SHA-1的計算速度。

SHA-1算法

算法描述

SHA-1算法能夠將任意長的輸入壓縮成160bit的輸出。但是，SHA-1算法中的基本迭代只能處理512bit的數據塊，因此為了處理任意長度的數據，首先需要將輸入的消息每512bit分成一塊，并且將最后一塊不足512bit的消息按一定規則補齊。(限于篇幅，SHA-1算法的詳細描述見文[1]，下面是算法進一步的簡單描述。)

分塊之后就可以對每塊消息按下述方法依次進行處理。

1)在5個中間變量H0、H1、H2、H3和H4中置入特定初值。

2)對每塊消息依次執行步驟a)到e)

a)將512bit的消息塊分成16個32bit的字W0，W1，…，W15;

b)For t=16 to 79l etWt=S1(W t-3W t-8

W t-14

W t-16);

c)LetA=H0，B=H1，C=H2，D=H3，E=H4;

d)For t=0 to 79 do

i)teMP=S 5 (A)+f t(B，C，D)+E+Wt+Kt;

ii)E=D;D=C;C=S30(B);B=A;A=TEMP;

e)LetH0=H0+A，H1=H1+B，H2=H2+C，H3=H3+D，H4=H4+E。

所有消息塊處理完后得到的5個32bit變量H0到H4構成了160bit的數據，這就是SHA-1算法輸出的散列值。

算法中使用了一些簡單的邏輯函數和常數，其中函數ft()和常數Kt分別為

算法中S1(*)、S5(*)和S30(*)分別表示按位循環左移1bit、5bit和30bit。算子“∧”、“∨”、“”和“+”分別表示按位“與”、按位“或”、按位“異或”以及32bit整數加法。