Read sha-1

SHA – 1 introduction

Secure Hash Algorithm 1 (SHA-1) is a cryptographic Hash function designed by the US National Security Agency and published by the US National Institute of Standards and Technology (NIST) as a Federal Data Processing standard (FIPS). Sha-1 can generate a 160-bit (20-byte) hash value called a message digest, which is typically rendered as 40 hexadecimal numbers. 【 Wikipedia 】

Sha-1 implementation steps

Message Padding

This message padding scheme is similar to MD5 (note that there are some differences here, I did not pay attention to the initial implementation, directly copy the algorithm used to write MD5, resulting in a different result), follow the following steps to fill the message.

Step 1: Data Padding (Append Padding)

Sha-1 is processed in blocks of 512 bits. In most cases, the data length will not be an integer multiple of 512, so padding to the given length is required.

Padding rule: the b bit of the original plaintext message is followed by 100… PaddingLength % 512 = 448 if b % 512 is between [448, 512(0)], add a partition.

Step 2: Length filling

If b + paddingLength % 512 = 448, then we have 512-448 = 64 bits for the last partition, which contains the length of the original message, b. Sha-1 can process data with a plaintext length of up to 2^64 bits.

After the processing of the above two steps, the final processed data is shown as the figure below:

Note: I didn’t exactly describe the Message Padding in RFC. I merged a and B in RFC

Computing the Message Digest

First, initialize 5 constants, as shown below, which can be regarded as MDBuffer by analogy with MD5:

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

The message is then processed as follows:

  • The first 16 bytes ([0, 15]) to a 32-bit unsigned integer.
  • For the following bytes ([16, 79]) according to the following formula
W(t) = S^1(W(t-3) XOR W(t-8) XOR W(t-14) XOR W(t-16))
Copy the code

  • Let A = H0, B = H1, C = H2, D = H3, E = H4

  • Do the following 80 rounds of hashing

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;Copy the code
  • makeH0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4 + E

To explain, f function is as follows:

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)Copy the code

K function is as follows:

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

The output

H0 to H4 are the final sha-1 output results.

Code implementation

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 note that this is different from MD5
        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), nif 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) {
            // Note that big-edition is used here
            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())); }}Copy the code

One day

Calculate the value of sign(LittleQ), still no reverse debugging, welcome to try to restore the algorithm.

Link: pan.baidu.com/s/1Gtdszf76… Extraction code: 9vMB

The resources

  • rfc3174
  • SHA-1 – Wikipedia