【密码学】一文读懂SHA-1

2022-06-12 1148

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： SHA-1（Secure Hash Algorithm 1）是一种密码散列函数，美国国家安全局设计，并由美国国家标准技术研究所（NIST）发布为联邦资料处理标准（FIPS）。SHA-1可以生成一个被称为消息摘要的160位（20字节）散列值，散列值通常的呈现形式为40个十六进制数。

一文读懂SHA-1

$VKM%_NK{%_GBIRT$VYGJ841.jpg$ 一文读懂SHA-1

SHA-1简介

❝
SHA-1（Secure Hash Algorithm 1）是一种密码散列函数，美国国家安全局设计，并由美国国家标准技术研究所（NIST）发布为联邦资料处理标准（FIPS）。SHA-1可以生成一个被称为消息摘要的160位（20字节）散列值，散列值通常的呈现形式为40个十六进制数。【维基百科】
❞

SHA-1实现步骤

消息填充(Message Padding)

这个消息填充方案和MD5类似(注意这里有些不同, 我最开始实现的时候没太注意, 直接复制了之前写MD5的算法, 导致结果不一样)，按照如下的步骤进行填充。

步骤一: 数据填充(Append Padding Bits)

SHA-1是按照分块进行处理的，分块长度为512bit, 大多数情况下，数据的长度不会恰好满足是512的整数倍，因此需要进行「padding」到给定的长度。

「填充规则」: 原始明文消息的b位之后补100..., 直到满足b + paddingLength % 512 = 448, 那如果b % 512在[448, 512(0)]之间呢，则在增加一个分块，按照前面的规则填充即可。

步骤二: 长度填充

之前说了，需要满足b + paddingLength % 512 = 448，那么对于最后一个分块，就还剩512 - 448 = 64 bit 这剩下的64bit存放的是原始消息的长度，也就是b。「SHA-1」最多可以处理明文长度小于等于2^64 bit的数据。

经过上面两个步骤的处理，最终得到的处理后的数据如下图所示:

4PMZ`W$T1RN%@1KD~~{X)PB.png

SHA-1-Padding

❝
注: 这里我没有完全按照RFC当中的Message Padding来描述，我合并了RFC当中的a, b
❞

计算摘要(Computing the Message Digest)

`UH@}J{@EAYRM)146PWWJ@T.png 计算摘要

首先, 初始化5个常量, 如下所示, 类比于「MD5」可以看做是「MDBuffer」:

H0 = 0x67452301
H1 = 0xEFCDAB89
H2 = 0x98BADCFE
H3 = 0x10325476
H4 = 0xC3D2E1F0

然后对于消息按照如下的方式进行处理:

前16个字节([0, 15])，转换成32位无符号整数。
对于后面的字节([16, 79])按照下面的公式进行处理

W(t) = S^1(W(t-3) XOR W(t-8) XOR W(t-14) XOR W(t-16))

令A = H0, B = H1, C = H2, D = H3, E = H4
做如下80轮的散列操作

TEMP = S^5(A) + f(t;B,C,D) + E + W(t) + K(t);
E = D;
D = C;
C = S^30(B);
B = A;
A = TEMP;

令H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4 + E

解释一下，其中f函数如下:

f(t;B,C,D) = (B AND C) OR ((NOT B) AND D)         ( 0 <= t <= 19)
f(t;B,C,D) = B XOR C XOR D                        (20 <= t <= 39)
f(t;B,C,D) = (B AND C) OR (B AND D) OR (C AND D)  (40 <= t <= 59)
f(t;B,C,D) = B XOR C XOR D                        (60 <= t <= 79)

k函数如下:

K(t) = 0x5A827999         ( 0 <= t <= 19)
K(t) = 0x6ED9EBA1         (20 <= t <= 39)
K(t) = 0x8F1BBCDC         (40 <= t <= 59)
K(t) = 0xCA62C1D6         (60 <= t <= 79)

输出

最后H0~H4即为最终「SHA-1」的输出结果。

代码实现

pub struct SHA1 {}
impl SHA1 {
    fn padding(message: &[u8]) -> Vec<u8> {
        let mut result = message.to_owned();
        // padding 1
        result.push(0x80);
        // padding 0
        while ((result.len() * 8) + 64) % 512 != 0 {
            result.push(0b00000000);
        }
        // padding message length 注意这里和MD5不同，没仔细看踩了一个大坑 这里长度padding到前面
        for byte in &((message.len() * 8) as u64).to_be_bytes() {
            result.push(*byte);
        }
        return result;
    }
    fn k(t: usize) -> u32 {
        match t {
            n if n < 20 => 0x5A827999,
            n if 20 <= n && n < 40 => 0x6ED9EBA1,
            n if 40 <= n && n < 60 => 0x8F1BBCDC,
            n if 60 <= n && n < 80 => 0xCA62C1D6,
            _ => 0,
        }
    }
    fn f(t: usize, b: u32, c: u32, d: u32) -> u32 {
        match t {
            n if n < 20 => (b & c) | ((!b) & d),
            n if 20 <= n && n < 40 => b ^ c ^ d,
            n if 40 <= n && n < 60 => (b & c) | (b & d) | (c & d),
            n if 60 <= n && n < 80 => b ^ c ^ d,
            _ => 0,
        }
    }
    pub fn hash(message: &[u8]) -> String {
        let padding_message = SHA1::padding(message);
        let mut buf: [u32; 5]; // Buffer one, A..E
        let mut h: [u32; 5] = [0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476, 0xC3D2E1F0];
        let mut w = [0u32; 80]; // Sequance of W(0)..W(79)
        let mut temp: u32;
        for chunk in padding_message.chunks(64) {
            // 注意这里用的是big-edition
            let m: Vec<u32> = chunk.chunks(4).map(|i| {
                ((i[0] as u32) << 24) | ((i[1] as u32) << 16) | ((i[2] as u32) << 8) | ((i[3] as u32) << 0)
            }).collect();
            for i in 0..16 {
                w[i] = m[i];
            }
            for t in 16..80 {
                // W(t) = S^1(W(t-3) XOR W(t-8) XOR W(t-14) XOR W(t-16)).
                w[t] = (w[t - 3] ^ w[t - 8] ^ w[t - 14] ^ w[t - 16]).rotate_left(1);
            }
            buf = h;
            for t in 0..80 {
                // TEMP = S^5(A) + f(t;B,C,D) + E + W(t) + K(t);
                temp = buf[0].rotate_left(5).wrapping_add(
                    SHA1::f(t, buf[1], buf[2], buf[3])
                        .wrapping_add(buf[4].wrapping_add(w[t].wrapping_add(SHA1::k(t)))),
                );
                buf[4] = buf[3]; // E = D
                buf[3] = buf[2]; // D = C
                buf[2] = buf[1].rotate_left(30); // C = S^30(B)
                buf[1] = buf[0]; // B = A
                buf[0] = temp; // A = TEMP
            }
            for i in 0..5 {
                h[i] = h[i].wrapping_add(buf[i]);
            }
        }
        // output
        return String::from(format!(
            "{:08x}{:08x}{:08x}{:08x}{:08x}",
            h[0], h[1], h[2], h[3], h[4]
        ));
    }
}
#[cfg(test)]
mod test {
    use crate::sha1::SHA1;
    #[test]
    fn test() {
        println!("sha1([empty string]) = {}", SHA1::hash("".as_bytes()));
        println!("sha1([The quick brown fox jumps over the lazy dog]) = {}", SHA1::hash("The quick brown fox jumps over the lazy dog".as_bytes()));
    }
}