快速实现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整数加法。