# SHA256 哈希算法原理和 Rust 实现

## 介绍

SHA256 的输入是任意长度的字节串，输出是一个 256 bit 的字节串。例如，

• 输入：字符串 abc（相当于字节数组 [0x6c, 0x65, 0x73, 0x73, 0x2d, 0x62, 0x75, 0x67, 0x2e, 0x63, 0x6f, 0x6d]

• 输出：

1[0x20, 0x1a, 0xb7, 0x03, 0x64, 0x78, 0xee, 0x8a, 0xba, 0x2e, 0xb3, 0xc7, 0xc0, 0xc6, 0x5b, 0x8b, 0x17, 0x49, 0x58, 0x52, 0xf4, 0xeb, 0xe1, 0x5b, 0x79, 0xe5, 0x34, 0x39, 0x6f, 0x29, 0x0c, 0x5b]

## 示例

1static H: [u32; 8] = [
2    0x6a09e667,
3    0xbb67ae85,
4    0x3c6ef372,
5    0xa54ff53a,
6    0x510e527f,
7    0x9b05688c,
8    0x1f83d9ab,
9    0x5be0cd19,
10];

1>>> hex(int(2**32 *(2**0.5 - int(2**0.5))))
2'0x6a09e667'

1primes = [2, 3, 5, 7, 11, 13, 17, 19]
2for p in primes:
3    print(hex(int(2**32 *(p**0.5 - int(p**0.5)))))

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

1primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311]
2for p in primes:
3    print(hex(int(2**32 *(p**0.3333333333333333 - int(p**0.3333333333333333)))))

1[0x6c, 0x65, 0x73, 0x73, 0x2d, 0x62, 0x75, 0x67, 0x2e, 0x63, 0x6f, 0x6d]

101101100, 01100101, 01110011, 01110011
200101101, 01100010, 01110101, 01100111
300101110, 01100011, 01101111, 01101101

，输入数据大小为 16 个字节.

1. 如果数据长度小于 448 位（56 字节），则在数据后面添加一个 1，然后添加足够的 0，使得数据长度对 512 取模后，等于 448（即 512-64，减去的 64 位留作他用）。

2. 如果数据长度大于等于 448 位（56 字节），则在数据后面添加一个 1，然后添加足够的 0，使得数据长度对 512 取模后，等于 0。然后再添加一个新的分组，这个分组的数据全部为 0，只有最后 64 位为数据长度。

1let padding_len = if input_len % 64 < 56 {
2    56 - input_len % 64
3} else {
4    120 - input_len % 64
5};

101101100, 01100101, 01110011, 01110011
200101101, 01100010, 01110101, 01100111
300101110, 01100011, 01101111, 01101101
410000000, 00000000, ...,      00000000

10x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x60

1byte = ((input_bit_len >> (7 * 8 - i * 8)) & 0xff)

1. 前 16 字节，就是输入数据在对应 block 的字节数据

1let mut w = [0; 64];
2for j in 0..16 {
3    let offset = i * 64 + j * 4;
4    w[j] = ((input_bytes[offset + 0] as u32) << 24)
5        | ((input_bytes[offset + 1] as u32) << 16)
6        | ((input_bytes[offset + 2] as u32) << 8)
7        | ((input_bytes[offset + 3] as u32) << 0);
8}

2. 后 48 字节，需要通过如下公式计算：

1w[i] = w[i-16] + sigma0(w[i-15]) + w[i-7] + sigma1(w[i-2])

其中的 sigma0 和 sigma1 是：

1sigma0(i) = (w[i - 15] rotr 7) xor (w[i - 15] rotr 18) xor (w[i - 15] shr 3)
2sigma1(i) = (w[i - 2] rotr 17) xor (w[i - 2] rotr 19) xor (w[i - 2] shr 10)

其中 rotr 表示循环右移，shr 表示右移。

例如：0b1001 rotr 2 表示让 0b1001 循环右移 2 位，即 0b1100。右侧移除的位在左侧补出。 0b1001 shr 2 表示让 0b1001 右移 2 位，高位补零，即 0b0010

具体代码如下：

1for j in 16..64 {
2let s0 = w[j - 15].rotate_right(7) ^ w[j - 15].rotate_right(18) ^ (w[j - 15] >> 3);
3let s1 = w[j - 2].rotate_right(17) ^ w[j - 2].rotate_right(19) ^ (w[j - 2] >> 10);
4w[j] = w[j - 16]
8}

1s1 = (e rotr 6) xor (e rotr 11) xor (e rotr 25)
2choose = (e and f) xor ((not e) and g)
3temp1 = h + s1 + choose + k[i] + w[i]
4s0 = (a rotr 2) xor (a rotr 13) xor (a rotr 22)
5major = (a and b) xor (a and c) xor (b and c)
6temp2 = s0 + major
7
8working[7] = working[6]
9working[6] = working[5]
10working[5] = working[4]
11working[4] = working[3] + temp1
12working[3] = working[2]
13working[2] = working[1]
14working[1] = working[0]
15working[0] = temp1 + temp2

1fn compress(input_bytes: &Vec<u8>) -> [u32; 8] {
2    static H: [u32; 8] = [
3        0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab,
4        0x5be0cd19,
5    ];
6    static K: [u32; 64] = [
7        0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4,
8        0xab1c5ed5, 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe,
9        0x9bdc06a7, 0xc19bf174, 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f,
10        0x4a7484aa, 0x5cb0a9dc, 0x76f988da, 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
11        0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967, 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc,
12        0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85, 0xa2bfe8a1, 0xa81a664b,
13        0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070, 0x19a4c116,
14        0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
15        0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7,
16        0xc67178f2,
17    ];
18
19    let mut hash = H;
20    let nblocks = input_bytes.len() / 64;
21    for i in 0..nblocks {
22        let mut w = [0; 64];
23        for j in 0..16 {
24            let offset = i * 64 + j * 4;
25            w[j] = ((input_bytes[offset + 0] as u32) << 24)
26                | ((input_bytes[offset + 1] as u32) << 16)
27                | ((input_bytes[offset + 2] as u32) << 8)
28                | ((input_bytes[offset + 3] as u32) << 0);
29        }
30        for j in 16..64 {
31            let s0 = w[j - 15].rotate_right(7) ^ w[j - 15].rotate_right(18) ^ (w[j - 15] >> 3);
32            let s1 = w[j - 2].rotate_right(17) ^ w[j - 2].rotate_right(19) ^ (w[j - 2] >> 10);
33            w[j] = w[j - 16]
37        }
38        let mut working: [u32; 8] = hash; // working variables
39        for j in 0..64 {
40            let s1 = working[4].rotate_right(6)
41                ^ working[4].rotate_right(11)
42                ^ working[4].rotate_right(25);
43            let choose = (working[4] & working[5]) ^ ((!working[4]) & working[6]);
44            let temp1 = working[7]
49            let s0 = working[0].rotate_right(2)
50                ^ working[0].rotate_right(13)
51                ^ working[0].rotate_right(22);
52            let major =
53                (working[0] & working[1]) ^ (working[0] & working[2]) ^ (working[1] & working[2]);
55            working[7] = working[6];
56            working[6] = working[5];
57            working[5] = working[4];
59            working[3] = working[2];
60            working[2] = working[1];
61            working[1] = working[0];
63        }
64
65        for j in 0..8 {
67        }
68    }
69    return hash;
70}
71
72pub fn sha256(input: &[u8]) -> [u8; 32] {
74    let mut input_bytes = input.to_vec();
75    let input_len = input_bytes.len();
76    let padding_len = if input_len % 64 < 56 {
77        56 - input_len % 64
78    } else {
79        120 - input_len % 64
80    };
81
82    input_bytes.push(0x80); // 1000 0000
83    for _ in 0..padding_len - 1 {
84        input_bytes.push(0x00);
85    }
86    assert!(input_bytes.len() % 64 == 56);
87    let input_bit_len = input_len * 8;
88    for i in 0..8 {
89        let byte = ((input_bit_len >> (56 - i * 8)) & 0xff) as u8;
90
91        input_bytes.push(byte);
92    }
93
94    assert!(input_bytes.len() % 64 == 0);
95
96    let hash = compress(&input_bytes);
97
98    let mut ret = [0 as u8; 32];
99    for i in 0..8 {
100        ret[i * 4 + 0] = ((hash[i] >> 24) & 0xff) as u8;
101        ret[i * 4 + 1] = ((hash[i] >> 16) & 0xff) as u8;
102        ret[i * 4 + 2] = ((hash[i] >> 8) & 0xff) as u8;
103        ret[i * 4 + 3] = ((hash[i] >> 0) & 0xff) as u8;
104    }
105
106    ret
107}
108
109#[cfg(test)]
110mod tests {
111    use super::*;
112    fn u8array_to_string(arr: &[u8]) -> String {
113        let mut ret = String::new();
114        for i in arr {
115            ret.push_str(&format!("{:02x}", i));
116        }
117        ret
118    }
119    #[test]
120    fn short_string_test() {
121        let tests = [
122            (
123                "",
124                "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855",
125            ),
126            (
127                "less-bug.com",
128                "201ab7036478ee8aba2eb3c7c0c65b8b17495852f4ebe15b79e534396f290c5b",
129            ),
130            (
131                "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq",
132                "248d6a61d20638b8e5c026930c3e6039a33ce45964ff2167f6ecedd419db06c1",
133            ),
134        ];
135        for (input, expected) in tests.iter() {
136            let input_bytes = input.as_bytes();
137            let output = sha256(input_bytes);
138
139            let output_string = u8array_to_string(&output);
140            assert_eq!(output_string, *expected);
141        }
142    }
143
144    #[test]
145    fn long_string_test() {
146        let input = {
147            let mut ret = String::new();
148            for _ in 0..(512 * 16 + 500) {
149                ret.push_str("a");
150            }
151            ret
152        };
153        let expected =
154            "31ef976b92b5879f6068892a737803b40dac69e6a9c5563e05dd6197b2b39a27".to_string();
155        let input_bytes = input.as_bytes();
156        let output = sha256(input_bytes);
157        let output_string = u8array_to_string(&output);
158        assert_eq!(output_string, expected);
159    }
160}