快速实现SHA-1算法的硬件结构
算法分析
从算法描述可以看出，SHA-1最核心的计算是一个计算5个中间变量的迭代：
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.
在硬件实现中，5个变量在一个周期内同时由组合逻辑电路根据上次迭代的计算值产生，因此每次迭代所需要的时间是由最慢的计算过程决定。这样一条最慢的计算路径也就是所谓的关键路径。如果完全按照SHA-1的原始算法进行硬件设计，那么很明显的关键路径是变量A的计算。在每次迭代过程中，计算变量A需要进行4次32bit的整数加法和若干组合逻辑。这些计算一共需要的时间也就是算法硬件实现的最短周期。正是因为变量A的计算比较复杂，造成SHA-1算法硬件实现的工作频率难以提高。
因此，加快SHA-1硬件实现的计算速度关键就是改变迭代结构，从而缩短每次迭代过程的关键路径。
硬件快速实现的新结构
观察算法可发现，除了变量A以外，其他4个变量的计算都相当简单。因此，如果将变量A的计算过程通过一定方式分解成若干并行的计算，那么就可以在不增加迭代次数的前提下，缩短整个计算的关键路径。
出于这种目的，1997年A.Bosselaers等人对SHA-1算法的结构进行了分析，发现SHA-1算法的数据流图可以分解成并行的7路数据处理，每路数据上一个周期只需一个基本操作：加法、“异或”或者循环移位。
在此关于SHA-1结构结论的基础上，本文通过引入中间变量的方法，将计算的关键路径分解成若干个较短的路径，从而达到加速硬件计算的效果。考虑到硬件实现中32bit整数加法的延时远远大于循环移位和普通逻辑运算，所以分析关键路径时只考虑加法的代价，而忽略其他逻辑运算的延时。
首先引入中间变量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。也就是说，将第n次迭代的部分计算提前到第n-1次迭代中进行计算。变形后，第n次迭代中A的计算只需要进行一次32bit整数加法。
但是这种方式下，变量P的计算仍然需要依赖于同一次迭代中的其他变量，也就是说在一次迭代中需要在计算完其他变量后才能计算出P，这样的话计算的关键路径还是没有缩短。所以还要充分利用A到E5个变量之间的相互关系
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值可以完全依赖于前一轮也就是第n-2轮的变量值计算而得。迭代计算的关键路径就分裂成变量A和P两路并行的计算。
类似的再引入其他中间变量，不断的分解关键路径，最终的迭代可变形为
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).
可以发现通过引入中间变量，使得计算变量A的关键路径分解成A、P、Q、R的4路并行计算，所需要的4次加法平均在4个周期内完成。这样每次迭代过程中任何一个变量的计算最多只需要一次32bit整数加法和少量组合逻辑。在此基础上，SHA-1算法可以通过如下方法来计算
1)将输入的512bit消息分成16个字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)。
虽然引入中间变量的计算后，每块数据需要额外增加一个预计算的步骤4)，但是因为关键路径得以缩短，整体硬件实现的速度仍然会大大提高。
评论