安全Hash算法SHA-512

SHA-512总体结构

SHA-512算法总体结构如图所示，后面我们会发现Hash码的每一位都是全部输入位的函数

其中输入消息最大长度为$2^{128}$位，输出为512位消息摘要，消息以1024位分组为单位处理

算法首先对输入进行填充使其长度模1024与896同余，注意即使输入已满足该条件也要填充，因此填充位数为1~1024，填充值以1开头，后续全为0

填充消息后，在消息后附加一个128位的无符号整数表示消息填充前的长度

此时消息的长度已经为1024的整数倍，将消息按1024位分组为$M_1,M_2,…,M_n$

如图所示SHA加密的结构是安全Hash函数结构，可表示为

$\begin{aligned} &H_0=IV\\ &H_i=SUM(F(M_i, H_{i-1}), H_{i-1}) \end{aligned}$

其中函数$F$产生512位输出，$SUM$函数（图中+号）将两个512位输入分别分成8个64位整数，再对应进行模$2^{64}$相加，最后消息摘要为$H_n$

SHA512_structure

如图所示为SHA-512中模块$F$与$SUM$的具体结构

其中上一轮的结果$H_{i-1}$被分为8个64位整数分别按高位在前保存于寄存器abcdefgh中
对于$H_0$则有如图的初值，它们的获取方式为：前8个素数计算平方根后取小数部分前64位

SHA512_H0

该结构中包含了80轮相同的轮函数迭代，其中第$t$轮的输入为由消息扩展算法导出的64位值$W_t$，寄存器abcdefgh和64位轮常数$K_t$，输出值直接更新到寄存器abcdefgh中

轮常数K的获取方法为：对前80个素数开立方根，分别取小数部分前64位
这些常数用于初步消除输入数据里的统计规律

完成80次轮函数迭代后，最后将第一轮输入的abcdefgh和第80轮输出的abcdefgh对应进行模$2^{64}$相加

SHA512_cycle

如图所示为上节所提到的轮函数，其中

$CH(e,f,g)=(e\ AND\ f)\oplus(NOT\ e\ AND\ g)$

$Maj(a,b,c)=(a\ AND\ b)\oplus(a\ AND\ c)\oplus(b\ AND\ c)$

$\sum a=ROTR(a, 28)\oplus ROTR(a, 34)\oplus ROTR(a, 39)$

$\sum e=ROTR(e, 14)\oplus ROTR(e, 1)\oplus ROTR(e, 41)$

$ROTR(x,n)$表示将64位整数$x$循环右移$n$位，+为模$2^{64}$加

SHA512_cycle_f

消息扩展算法公式如下

$W_t=\sigma_1^{512}(W_{t-2})+W_{t-7}+\sigma_0^{512}(W_{t-15})+W_{t-16}$

其中

$\sigma_0^{512}(x)=ROTR(x, 1)+ROTR(x, 8)+SHR(x, 7)\\ \sigma_1^{512}(x)=ROTR(x, 19)+ROTR(x, 61)+SHR(x, 6)$

$SHR(x,n)$表示将64位整数$x$右移$n$位，左边填充0，+为模$2^{64}$加

对于$W0$到$W{15}$，直接将消息$M_i$按64位分组获得

最早的SHA版本SHA-0由FIPS 180于1993年发布，之后SHA-0被发现存在缺陷

SHA-0的修订版SHA-1于1995年发布，虽然目前SHA-1暂未被发现缺陷，但SHA-1在设计上与MD5和SHA-0具有相似结构，而后两者已经被攻破，此外有研究表明，对SHA-1的碰撞攻击数量级可以低至$2^{69}$，因此SHA-1也被认为是不安全的

2002年FISP 180-2给出了三种新的SHA版本，分别为SHA-256、SHA-384和SHA-512，统称为SHA-2，之后又于2015年给出了SHA-512/224和SHA-512/256，它们的参数可见于下图

虽然目前SHA-2并没有发现缺陷，但为了长远考虑，NIST于2007年开始征集新标准，称为SHA-3，2012年Keccak算法被选中，之后将逐渐取代SHA-2

SHA_arg