SHA-256 的纯 Rust 实现

出于了解 SHA-256 算法及学习 Rust 的目的，用纯 Rust 实现了一个 SHA-256 库。

SHA-256 算法简介

首先简单介绍一下 SHA-256 算法，SHA-256 是 SHA-2 系列算法中的一种，关于 SHA-2 的相关介绍可以查看其维基百科，其中也详细介绍了 SHA-256 的算法。

简单的说， SHA-256 算法分为以下几步：

1. 对消息进行填充预处理，先附加 bit 1，然后填充可变数量（0-511）的 bit 0，最后附加 u64（big-endian, 64 bits）类型的原始消息长度的 bit 数，使填充后的消息长度为 512 bits 即 64 bytes）的整数倍
2. 对预处理后的消息进行分片，每 512 bits 为一个分片
3. 对每个分片进行迭代处理，每次迭代以该分片及 8 个 u32 为输入，并输出 8 个 u32 作为下一个迭代的输入
4. 最后一个分片处理完成输出的 8 个 u32 既是最后的结果

要用到的两组常量

其中第 3 步对各个分片的迭代处理又要用到两组常量：

一是对第一个分片进行处理时作为输入的 8 个初始的 u32：

const H: [u32; 8] = [
    0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19,
];

它们是自然数中前 8 个质数 2、3、5、7、11、13、17、19 平方根的小数部分取前 32 bits。

二是在对每个分片进行处理时都要用到的 64 个密钥：

const K: [u32; 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,
];

它们是自然数中前 64 个质数的立方根的小数部分取前 32 bits。

这里有一段 Rust 代码可以生成上面的两组常量：sha2_constants.rs (Rust Playground)。

处理分片

每个分片都经过如下处理（以下处理全部要求 big-endian）：

1.将 512 bits 视为 [u32; 16] 并扩展为 [u32; 64]

fn extend(data: [u32; 16]) -> [u32; 64] {
    let mut w = [0u8; 64];

    for i in 0..16 {
        w[i] = data[i].to_be();
    }

    let (mut s0, mut s1);
    for i in 16..64 {
        s0 = w[i - 15].rotate_right(7) ^ w[i - 15].rotate_right(18) ^ (w[i - 15] >> 3);
        s1 = w[i - 2].rotate_right(17) ^ w[i - 2].rotate_right(19) ^ (w[i - 2] >> 10);
        w[i] = w[i - 16]
            .wrapping_add(s0)
            .wrapping_add(w[i - 7])
            .wrapping_add(s1);
    }

    w
}

2.对上一步产生的 [u32; 64] 进行 64 次迭代处理，对于第一个分片传入初始的 8 个 u32 作为 state

fn sha256map(state: &mut [u32; 8], w: [u32; 64]) {
    let mut h = *state;

    let (mut ch, mut ma, mut s0, mut s1, mut t0, mut t1);
    for i in 0..64 {
        ch = (h[4] & h[5]) ^ (!h[4] & h[6]);
        ma = (h[0] & h[1]) ^ (h[0] & h[2]) ^ (h[1] & h[2]);
        s0 = h[0].rotate_right(2) ^ h[0].rotate_right(13) ^ h[0].rotate_right(22);
        s1 = h[4].rotate_right(6) ^ h[4].rotate_right(11) ^ h[4].rotate_right(25);
        t0 = h[7]
            .wrapping_add(s1)
            .wrapping_add(ch)
            .wrapping_add(K[i])
            .wrapping_add(w[i]);
        t1 = s0.wrapping_add(ma);

        h[7] = h[6];
        h[6] = h[5];
        h[5] = h[4];
        h[4] = h[3].wrapping_add(t0);
        h[3] = h[2];
        h[2] = h[1];
        h[1] = h[0];
        h[0] = t0.wrapping_add(t1);
    }

    for i in 0..8 {
        state[i] = state[i].wrapping_add(h[i]);
    }
}

3.最后一个分片处理完成后得到的 state 即为结果

完整实现

我实现好的库放在了 https://github.com/nanpuyue/sha256，跟上面介绍的有些不同：

实现了一个 Sha256 结构体，这里参考了 ring 的实现

pub struct Sha256 {
    state: [u32; 8],
    completed_data_blocks: u64,
    pending: [u8; 64],
    num_pending: usize,
}

Sha256 结构体主要提供三个方法 default、update、finish，首先使用 Sha256::default() 创建 Sha256 结构体。

然后用 upadte() 传入要处理的消息（&[u8]），这里会立即处理 64 bytes 整数倍的数据，剩余的数据保存在 pending 中留待下次处理，也就是说 update() 可以多次调用。

最后调用 finish() 会处理 pending 中剩余的数据（如果有）并做消息填充，同时结构体被消费，返回 [u8; 32] 的结果。

examples/sha256sum.rs 提供了一个命令行的示例，模拟了 coreutils sha256sum 的行为，只是没有做错误处理，可以使用 cargo run --release --example sha256sum 直接运行。