加密算法SHA

需求描述

近期想实现一个用户管理系统，因此希望实现一种将任意长度字符串转为定长字符串的算法，初步搜索发现了 SHA-256 算法。

据说在加密货币中也用到了，这激发了我的兴趣。

SHA-256

介绍

SHA-256（Secure Hash Algorithm 256-bit）能够将任意长度的输入消息转换为**256位（32字节）**的固定长度输出，通常表示为64个十六进制字符。

神秘常数

private static final int[] K = {
        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
};

private int[] H = {
        0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19
};

此处的K是用质数的立方根算的，H是用质数的平方根算的（都是小数部分）。似乎这些数的选取可以随意？

但总之，8个H是用于生成最后加密结果的，64个K用于对消息块做64轮加密运算。

预处理：消息分块

我们考虑一串消息由ASCII表示。例如：消息 abc ，转化为ASCII就是： 01100001 01100010 01100011 ( 0x616263 )。

一个目标分块(chunk)具备如下的性质 (16进制数表示，共16个32位Word，64个字节)：

61626380 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000018

相当于划分成：

W₀      61626380 
W₁      00000000
W₂      00000000
W₃      00000000
W₄      00000000
W₅      00000000
W₆      00000000
...
W₁₅     00000018

接下来具体讲解如何得到chunk。

实际上，可以理解为不断向原字符串(abc)不断push_back新字符的过程。具体步骤如下：

1. push_back(0x80) ： 向二进制串添加 1000 0000

2. 添加0：假设原消息有 $oriLen$ 个字节，需要添加$x$个0字节，则：
   $$
   (oriLen+1+x) % 64 = 56
   $$

3. 最后添加一个8字节数据，是oriLen的16进制表示(注意补0)

private byte[] chunk(byte[] data){
    int oriLen = data.length;
    int x = oriLen + 1;
    long bitLen = ((long) oriLen << 3);
    while(((x) % 64) != 56){
        x++;
    }
    byte[] res = new byte[x + 8]; // 自动补0
    System.arraycopy(data, 0, res, 0, oriLen);
    res[oriLen] = (byte) 0x80;
    for (int i = 0; i < 8; i++) {
        res[x + i] = (byte) (bitLen >>> (56 - 8 * i));
    }
    return res;
}

获取64轮加密用Word

接下来讲解如何由 chunk 得到 16 个 Word (使用int存储)。

实际上就是通过位运算，将 int 与 data 的bit流对齐。以下是代码：

private int[] processOneChunkTo16Words(byte[] data){
    int[] w16 = new int[16];
    for(int i = 0; i < 16; ++i){
        // 1 int = 32 bits
        w16[i] = (data[i*4] << 24) & 0xff | (data[i*4+1] << 16) & 0xff | (data[i*4+2] << 8) & 0xff | data[i*4+3] & 0xff;
    }
    return w16;
}

得到 w16 (16个字) ，接下来就是扩展的过程。我们需要通过各种运算得到 w64 (64个字)

这里还需要用到一些辅助函数：

// 循环右移
private int rotr(int x, int n) {
    return (x >>> n) | (x << (32 - n));
}

// SHA-256 特有的逻辑函数
private int Sigma0(int x) { return rotr(x, 7) ^ rotr(x, 18) ^ (x >>> 3); }
private int Sigma1(int x) { return rotr(x, 17) ^ rotr(x, 19) ^ (x >>> 10); }
private int sum0(int x)   { return rotr(x, 2) ^ rotr(x, 13) ^ rotr(x, 22); }
private int sum1(int x)   { return rotr(x, 6) ^ rotr(x, 11) ^ rotr(x, 25); }
private int Ch(int x, int y, int z)  { return (x & y) ^ ((~x) & z); }
private int Maj(int x, int y, int z) { return (x & y) ^ (x & z) ^ (y & z); }

字扩展的核心逻辑：

private int[] expand16WordsTo64Words(int[] w16) {
    int[] w64 = new int[64];
    System.arraycopy(w16, 0, w64, 0, 16);
    for (int i = 16; i < 64; i++) {
        // 公式: W[i] = σ1(W[i-2]) + W[i-7] + σ0(W[i-15]) + W[i-16]
        w64[i] = Sigma1(w64[i - 2]) + w64[i - 7] + Sigma0(w64[i - 15]) + w64[i - 16];
    }
    return w64;
}

主加密逻辑

准备工作已经完备。接下来就是使用上述部件进行一次 64 轮的加密工作。

public String encode(byte[] originalData) {
    byte[] paddedData = chunk(originalData); // 获取补位后的数据
    // 遍历每一个 512-bit (64-byte) 的块
    for (int i = 0; i < paddedData.length / 64; i++) {
        byte[] chunk = new byte[64];
        System.arraycopy(paddedData, i * 64, chunk, 0, 64);

        int[] w16 = processOneChunkTo16Words(chunk);
        int[] W = expand16WordsTo64Words(w16);

        // 初始化 8 个工作变量
        int a = H[0], b = H[1], c = H[2], d = H[3];
        int e = H[4], f = H[5], g = H[6], h = H[7];

        // 64轮核心压缩循环
        for (int j = 0; j < 64; j++) {
            int t1 = h + sum1(e) + Ch(e, f, g) + K[j] + W[j];
            int t2 = sum0(a) + Maj(a, b, c);
            h = g;
            g = f;
            f = e;
            e = d + t1;
            d = c;
            c = b;
            b = a;
            a = t1 + t2;
        }
        H[0] += a; H[1] += b; H[2] += c; H[3] += d;
        H[4] += e; H[5] += f; H[6] += g; H[7] += h;
    }
    // 将 H[0-7] 转换为 16 进制字符串
    StringBuilder sb = new StringBuilder();
    for (int hVal : H) {
        sb.append(String.format("%08x", hVal));
    }
    return sb.toString();
}