SHA算法

    SHA算法，即安全散列算法（Secure Hash Algorithm）是一种与MD5同源的数据加密算法，该算法经过加密专家多年来的发展和改进已日益完善，现在已成为公认的最安全的散列算法之一，并被广泛使用。

    SHA算法能计算出一个数位信息所对应到的，长度固定的字串，又称信息摘要。而且如果输入信息有任何的不同，输出的对应摘要不同的机率非常高。因此SHA算法也是FIPS所认证的五种安全杂凑算法之一。原因有两点：一是由信息摘要反推原输入信息，从计算理论上来说是极为困难的；二是，想要找到两组不同的输入信息发生信息摘要碰撞的几率，从计算理论上来说是非常小的。任何对输入信息的变动，都有很高的几率导致的信息摘要大相径庭。

    SHA实际上是一系列算法的统称，分别包括：SHA-1、SHA-224、SHA-256、SHA-384以及SHA-512。后面4中统称为SHA-2，事实上SHA-224是SHA-256的缩减版，SHA-384是SHA-512的缩减版。各中SHA算法的数据比较如下表，其中的长度单位均为位：

一、SHA-1算法

SHA-1 (Secure Hash Algorithm 1) 是一种常用的加密算法，用于生成具有固定长度的消息摘要或哈希值。其摘要的长度为160位。

下面是SHA-1算法的详细图解：

1. 消息填充：首先需要将输入消息进行填充，使其长度为512位的倍数。填充的过程如下：

1.1 扩展消息：将消息的二进制表示形式扩展为大于等于64位的倍数。

1.2 消息长度：在扩展消息的末尾添加64位的二进制表示的原始消息长度，以保留消息的完整性。

2. 划分消息：将填充后的消息划分为512位的消息块。

3. 初始化状态：使用固定的初始状态，包含5个32位的初始变量(A,B,C,D,E)。

4. 逐块处理：对每个消息块进行处理，得到新的状态。

4.1 扩展消息块：将512位的消息块扩展为80个32位的字(Word)。

4.2 迭代计算：对每个消息块进行80次迭代计算，更新状态。

4.2.1 提取字：从扩展消息块中提取一个字。

4.2.2 循环运算：对当前字进行循环右移、与运算、加运算等操作，生成一个新的字。

4.2.3 更新状态：根据当前的迭代次数，更新状态变量(A,B,C,D,E)。

4.3 更新哈希值：将当前的状态变量(A,B,C,D,E)与前一次的哈希值相加。

5. 重复逐块处理：对每个消息块重复步骤4，直到处理完所有的消息块。

6. 输出哈希值：最后的哈希值由状态变量(A,B,C,D,E)组成，将其连接起来形成160位的二进制表示，即为SHA-1的摘要。

SHA-1算法的图解如上所述，它通过对消息进行填充、划分和逐块处理等步骤来生成160位的消息摘要。这个摘要在安全领域被广泛应用，常用于数据完整性校验、数字签名等场景。

步骤

这里主要基于SHA-1介绍算法步骤，该算法也分为：补位、添加长度、初始化缓存、处理数据、输出这五个步骤，其中补位与添加长度与MD5一致，后面三个稍有不同。

1、补位：补位与添加长度与MD5一致，将最终位数补成对512求模的结果为448，即原文长度补位成只差64位(bit)就是512的整数倍，即使本身长度符合差64位就是512的倍数也要补一次512位，补位规则第一个补1，后面都补0。

2、添加长度：计算补位前的长度，取其二进制的64位，长度数值大于64位的取64位低位，比如长度为8，二进制表示为 1000，前面补60个0就是8的64位二进制表示了。最后消息就是为512的整数倍。

3、初始化缓存：SHA-1需要初始化4个32位的常数K以及5个32位的初始散列值H，这5个H就是初始化的摘要（160位）。K用16进制表示分别为：5A827999(0<=t<=19))、6ED9EBA1(20<=t<=39)、8F1BBCDC (40<=t<=59)、CA62C1D6 (60<=t<=79)，H用16进制表示分别为：67452301、EFCDAB89、98BADCFE、10325476、C3D2E1F0。

4、数据处理：初始化常数后，则将K和H以及分组的原文进行循环运算，每次循环需要经过4个函数处理，具体函数如下：

5、输出：最终的5个H(32位)就是SHA1的输出，共160位二进制，转化为16进制输出就是40个字符。

优点

1、安全：相对于MD5来讲，SHA算法更安全，目前SHA-2还没出现碰撞。

2、对原文敏感：哪怕原文有一个二进制的变化，都会导致密文不同（雪崩效应）。

3、算法不可逆：知道密文除了穷举，基本无法可解密出原文。

缺点

1、加密速度慢：相对于MD5来讲，SHA算法更慢(大数据量下)。

2、碰撞：虽然已经主流使用了SHA-2算法，可以返回256位甚至512位结果，结果返回足够大，目前够用，但依旧是有限的结果，后续还是可能出现碰撞。

缺点解决方案

对于加密速度慢的缺点，小段信息比如普通的表单、密码等的加密时间几乎可以忽略不计，可以忽略这个缺点，若有大文件加密且速度慢建议用MD5。

对于碰撞问题或字典解密问题可以采用加盐解决，即使碰撞了。

使用场景

1、密码加密：对于用户的密码，肯定不希望被别人破解，一般会采用不可逆算法，原文也小，可以使用SHA-2算法加密。

2、信息签名：SHA和MD5一样对原文敏感，对于数据或文件的传输，可在传输前后都生成SHA密文来对比校验，来验证数据或文件是否损坏或修改。

二、SHA256算法

目前一些比特币和CA证书就是使用SHA-256加密的。

SHA256算法原理

安全散列算法，即是将一段接收到的message通过哈希算法将其转换成固定位数的哈希值（也称消息摘要）。SHA256就是将message通过哈希算法计算得到一个256位的哈希值。

根据笔者理解，将SHA256计算分成两个大的步骤：

1.信息预处理（Preprocessing）

分两个小的步骤：

第一步，填充比特位，在填充的时候遵循以下公式：

（消息原始长度 + 1 + k) mod 512 = 448

下面来解释一下这个公式：

1：指在原始数据的后面添加1个比特位“1”

k：指使上述公式成立的最小的整数k，在之前填充的“1”后面填充k个“0”

mod：取模运算

读者一定会有疑问，为什么最后取模结果要是448，这就涉及到第二步，请继续往下看。

第二步，填充附加长度

这里的附加长度是指原始message的长度，用64位的二进制数来进行位填充，这样总的长度加上之前的448正好是512的整数倍，将这每512位为一组的数据块称作一个消息分块，对一个原始message进行这样的填充之后，可能分出n个512位的消息分块来。

需要注意的是，即使原始message的长度已经满足上述公式，还是要进行位填充，这里填充512位，1位二进制“1”，511位二进制“0”。所以可以知道，填充的位数在1~512之间。

原始message的长度用64位二进制表示，所以知道这个原始message的长度最长为（2^64 - 1)位。

示例：

假设有一条ASCII码表示的原始消息为“abc"，将其化为二进制数则一共有3*8=24位，这时就需要在24位二进制数后面补充1位“1”和423位“0”，然后再将数据长度24转换为64位的二进制数填充在末尾，就完成了对原始消息的填充，如下图所示：

2.计算摘要

计算摘要前，先来了解两个概念。

（1）消息分块

上面讲过每512位比特位组成的一个消息分块，我们将其记为M(i)，然后将每个M(i)又分成16个32位比特位组成的小分块，将其记为Mj(i)，j取值为0~15，如下图所示：

之所以这样做是因为在后面计算哈希值的时候，要用这样的数据结构（16个32位的数据）进行迭代以完成哈希值的计算。

（2）扩展消息块

用Wj来表示，Wj遵循以下公式：

哈希值计算过程：

（1）计算公式

上式为一个递推公式，当前哈希值H(i)由上一次计算的H(i-1)得到。

函数C：SHA256压缩函数

+：表示每一个运算单元字（word，SHA256中一个字为32位）取模之后做加法运算

（2）逻辑函数

在迭代计算过程中要用到这6个函数。

（3）计算

Step 1：对哈希值进行初始化

上述8个32位的数据级联起来长度有8*32=256，所以可知，哈希值的最终值是由这8个数据组成的。

至于这8个初始值怎么来的，如果不去探讨其背后的数学含义只拿来用的话，读者可以忽略。

Step 2：哈希值计算的中间过程

根据上述公式计算出a~h的值。

Step 3：进行迭代运算，计算中间散列值

根据Step 2公式中的Kj和Wj，可知迭代计算要进行64轮。

以下为算法中主要部分代码，完整代码请移步文章末尾链接。

static const WORD k[64] = 
{
  0x428a2f98,0x71374491,0xb5c0fbcf,0xe9b5dba5,0x3956c25b,0x59f111f1,0x923f82a4,0xab1c5ed5,
  0xd807aa98,0x12835b01,0x243185be,0x550c7dc3,0x72be5d74,0x80deb1fe,0x9bdc06a7,0xc19bf174,
  0xe49b69c1,0xefbe4786,0x0fc19dc6,0x240ca1cc,0x2de92c6f,0x4a7484aa,0x5cb0a9dc,0x76f988da,
  0x983e5152,0xa831c66d,0xb00327c8,0xbf597fc7,0xc6e00bf3,0xd5a79147,0x06ca6351,0x14292967,
  0x27b70a85,0x2e1b2138,0x4d2c6dfc,0x53380d13,0x650a7354,0x766a0abb,0x81c2c92e,0x92722c85,
  0xa2bfe8a1,0xa81a664b,0xc24b8b70,0xc76c51a3,0xd192e819,0xd6990624,0xf40e3585,0x106aa070,
  0x19a4c116,0x1e376c08,0x2748774c,0x34b0bcb5,0x391c0cb3,0x4ed8aa4a,0x5b9cca4f,0x682e6ff3,
  0x748f82ee,0x78a5636f,0x84c87814,0x8cc70208,0x90befffa,0xa4506ceb,0xbef9a3f7,0xc67178f2
};

void sha256_init(SHA256_CTX *ctx)
{
  ctx->datalen = 0;
  ctx->bitlen = 0;
  ctx->state[0] = 0x6a09e667;
  ctx->state[1] = 0xbb67ae85;
  ctx->state[2] = 0x3c6ef372;
  ctx->state[3] = 0xa54ff53a;
  ctx->state[4] = 0x510e527f;
  ctx->state[5] = 0x9b05688c;
  ctx->state[6] = 0x1f83d9ab;
  ctx->state[7] = 0x5be0cd19;
}

void sha256_transform(SHA256_CTX *ctx, const BYTE data[])
{
  WORD a, b, c, d, e, f, g, h, i, j, t1, t2, m[64];

  for (i = 0, j = 0; i < 16; ++i, j += 4)
    m[i] = (data[j] << 24) | (data[j + 1] << 16) | (data[j + 2] << 8) | (data[j + 3]);
  for ( ; i < 64; ++i)
    m[i] = SIG1(m[i - 2]) + m[i - 7] + SIG0(m[i - 15]) + m[i - 16];
  /* Step 1 ：Hash initialize */
  a = ctx->state[0];
  b = ctx->state[1];
  c = ctx->state[2];
  d = ctx->state[3];
  e = ctx->state[4];
  f = ctx->state[5];
  g = ctx->state[6];
  h = ctx->state[7];

  for (i = 0; i < 64; ++i) {
    t1 = h + EP1(e) + CH(e,f,g) + k[i] + m[i];
    t2 = EP0(a) + MAJ(a,b,c);
    h = g;
    g = f;
    f = e;
    e = d + t1;
    d = c;
    c = b;
    b = a;
    a = t1 + t2;
  }

  ctx->state[0] += a;
  ctx->state[1] += b;
  ctx->state[2] += c;
  ctx->state[3] += d;
  ctx->state[4] += e;
  ctx->state[5] += f;
  ctx->state[6] += g;
  ctx->state[7] += h;
}

密匙相关的HMAC算法也是基于SHA，利用密匙和明文进行两轮哈希运算，笔者有空会继续和大家分享。

参考文献

https://blog.csdn.net/qq_38933606/article/details/130419710

https://zhuanlan.zhihu.com/p/404396915

https://blog.csdn.net/foxclever/article/details/80447870

https://zhuanlan.zhihu.com/p/146353007?utm_id=0

原文始发于微信公众号（豆豆咨询）：SHA算法