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 结构体主要提供三个方法 defaultupdatefinish,首先使用 Sha256::default() 创建 Sha256 结构体。

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

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

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

标签: Rust, 算法

已有 18 条评论

  1. 可怕

    1. Rust 多棒啊,一点都不可怕!

  2. sbw sbw

    可怕

  3. 可怕

  4. Sequencer Sequencer

    可怕

    1. 币圈大佬可怕!

  5. 可怕

    1. 复读机……

  6. 可怕

  7. 可怕

  8. 可怕

  9. laurencechan laurencechan

    root@SZX1000476955:/home/sha256# cargo run --release --example sha256sum
    Compiling sha256 v0.1.0 (/home/sha256)

    Finished release [optimized] target(s) in 1.38s Running `target/release/examples/sha256sum`

    这个example一直阻塞在这里,是为什么呀

    1. laurencechan laurencechan

      是要输入什么命令去验证吗? 你可以在文章里面写清楚。

    2. 这和 coreutils sha256sum 的行为是一致的。

添加新评论