[Rust] SHA-1 の実装

NIST による SHA-1 のドキュメント (FIPS 180-4) を読みながら Rust で実装したのでメモ. なお SHA-1 は既に破られており, セキュリティの観点からは使うべきではありません.

• FIPS 180-4, Secure Hash Standard (SHS)

コードの読みやすさや実行速度という点からはたぶんもっと最適化できると思いますが, 素直にドキュメントに書かれていることを Rust で書き起こしただけなので, そのあたりはあまり配慮していません.

wrapping_add が大量に出てくるのがちょっと厄介なんですが, std::num::Wrapping で包めば改善できそうです. あるいは wrapping_arithmetic というクレートも便利そうです.

またあちこちでエンディアンに注意する必要があります. SHA-1 の規定によると, すべての u32 はバイト列として扱う際にはビッグエンディアンである必要があります. このあたりで不整合を起こさないよう, sha1 関数の戻り値は [u8; 20] としてあります.

fn rotl<const N: u32>(x: u32) -> u32 {
    (x << N) | (x >> (u32::BITS - N))
}

fn f(t: usize, x: u32, y: u32, z: u32) -> u32 {
    if t < 20 {
        (x & y)^((!x) & z)
    } else if t < 40 {
        x ^ y ^ z
    } else if t < 60 {
        (x & y)^(x & z)^(y & z)
    } else if t < 80 {
        x ^ y ^ z
    } else {
        unreachable!()
    }
}

const K: [u32; 4] = [ 0x5a827999, 0x6ed9eba1, 0x8f1bbcdc, 0xca62c1d6 ];



fn padding(message: &[u8]) -> Vec<u8> {
    let l_in_byte = message.len();
    let k = (119 - (l_in_byte & 63)) & 63;
    
    let mut message: Vec<u8> = message.to_owned();
    message.push(128);
    for _ in 0..k { message.push(0); }
    message.extend(
        (l_in_byte << 3).to_be_bytes()
    );
    
    message
}

fn set_message_schedule(msg: &[u8], w: &mut [u32]) {
    for t in 0..16 {
        w[t] = u32::from_be_bytes(msg[4*t..4*(t+1)].try_into().unwrap());
    }
    for t in 16..80 {
        w[t] = rotl::<1>(w[t-3] ^ w[t-8] ^ w[t-14] ^ w[t-16]);
    }
}



pub fn sha1(message: &[u8]) -> [u8; 20] {
    let message = padding(message);

    let mut hash: [u32; 5] = [
        0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476, 0xc3d2e1f0,
    ];
    let mut w: Vec<u32> = vec![ 0; 80 ];

    for msg in message.chunks(64) {
        set_message_schedule(msg, &mut w);
        let [mut a, mut b, mut c, mut d, mut e] = hash;

        for t in 0..80 {
            let tmp = [ rotl::<5>(a), f(t, b, c, d), e, K[t/20], w[t] ]
                .iter()
                .fold(0, |acc, x| u32::wrapping_add(acc, *x));
            e = d;
            d = c;
            c = rotl::<30>(b);
            b = a;
            a = tmp;
        }

        hash = [ 
            hash[0].wrapping_add(a), 
            hash[1].wrapping_add(b), 
            hash[2].wrapping_add(c), 
            hash[3].wrapping_add(d), 
            hash[4].wrapping_add(e), 
        ];
    }
    
    // `[u32; 5]` を `[u8; 20]` へ変換
    hash.iter()
        .fold(vec![], |mut v, h| {
            v.extend(h.to_be_bytes()); v
        })
        .try_into().unwrap()
}