一文读懂MD4
一文读懂MD4
❝MD4是麻省理工学院教授Ronald Rivest于1990年设计的一种信息摘要算法。它是一种用来测试信息完整性的密码散列函数的实行。其摘要长度为128位。这个算法影响了后来的算法如MD5、SHA家族和RIPEMD等。【维基百科】
❞
因为我先看完的MD5算法，因此再返回来看这个的时候，感觉有好多相似的，虽然说MD4先于MD5, 感觉我顺序看反了，不过没关系，不影响算法的学习，在这里说一下，实际上MD4已经不再安全，此文仅供学习使用，生产环境请使用「安全的标准化算法」。
算法描述
这个和MD5的结构十分相似，我先看的MD5, 读者忍一下蛤，主要过程如下, 采用RFC当中的描述
数据填充(Append Padding Bits)
MD4是按照分块进行处理的，分块长度为512bit, 大多数情况下，数据的长度不会恰好满足是512的整数倍，因此需要进行「padding」到给定的长度。
「填充规则」: 原始明文消息的b位之后补100..., 直到满足b + paddingLength % 512 = 448, 那如果b % 512在[448, 512(0)]之间呢，则在增加一个分块，按照前面的规则填充即可。
长度填充
之前说了，需要满足b + paddingLength % 512 = 448， 那么对于最后一个分块，就还剩512 - 448 = 64 bit 这剩下的64bit存放的是原始消息的长度，也就是b。这也就是说，「MD4」最多可以处理明文长度小于等于2^64 bit的数据。
经过上面两个步骤的处理，最终得到的处理后的数据如下图所示:
MD4-Padding
初始化MD缓冲区
这个缓冲区和MD5一样，不过多解释了，值都一个样。
let A = 0x67452301; let B = 0xEFCDAB89; let C = 0x98BADCFE; let D = 0x10325476;
对每一个分块进行处理
MD4-分块处理
这依然是整个算法的核心，主要用到了下面三个逻辑函数:
F(X,Y,Z) = XY v not(X) Z G(X,Y,Z) = XY v XZ v YZ H(X,Y,Z) = X xor Y xor Z
MD5改进之后，用到了4个逻辑函数，有兴趣的可以看看我之前写过的MD5的文章，MD4用到的常量表只有两个常量，分别为0x5A827999, 0x6ED9EBA1。具体三轮的计算流程，参考一下RFC当中的描述吧，里面描述的还是比较清晰的。
输出
最后a0, b0, c0, d0按照小端输出，即为最后的结果, 这里也也MD5是一样的。
编码实现
下面给出MD4的代码实现:
pub struct MD4 {} fn f(x: u32, y: u32, z: u32) -> u32 { (x & y) | (!x & z) } fn g(x: u32, y: u32, z: u32) -> u32 { (x & y) | (x & z) | (y & z) } fn h(x: u32, y: u32, z: u32) -> u32 { x ^ y ^ z } fn ff(a: u32, b: u32, c: u32, d: u32, m: u32, s: u32) -> u32 { // a = (a + F(b,c,d) + X[k]) <<< s a.wrapping_add(f(b, c, d)).wrapping_add(m).rotate_left(s) } fn gg(a: u32, b: u32, c: u32, d: u32, m: u32, s: u32) -> u32 { // a = (a + G(b,c,d) + X[k] + 5A827999) <<< s a.wrapping_add(g(b, c, d)).wrapping_add(m).wrapping_add(0x5A827999).rotate_left(s) } fn hh(a: u32, b: u32, c: u32, d: u32, m: u32, s: u32) -> u32 { // (a + H(b,c,d) + X[k] + 6ED9EBA1) <<< s a.wrapping_add(h(b, c, d)).wrapping_add(m).wrapping_add(0x6ED9EBA1).rotate_left(s) } impl MD4 { fn padding(message: &[u8]) -> Vec<u8> { let message_length = message.len() as u64 * 8; 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 for b in 0..8 { result.push((message_length >> (b * 8)) as u8); } return result; } pub fn hash(message: &[u8]) -> String { let padding_message = MD4::padding(message); // init MD Buffer let mut a0 = 0x67452301u32; let mut b0 = 0xefcdab89u32; let mut c0 = 0x98badcfeu32; let mut d0 = 0x10325476u32; for chunk in padding_message.chunks(64) { let m: Vec<u32> = chunk.chunks(4).map(|i| { ((i[3] as u32) << 24) | ((i[2] as u32) << 16) | ((i[1] as u32) << 8) | ((i[0] as u32) << 0) }).collect(); let mut a = a0; let mut b = b0; let mut c = c0; let mut d = d0; // round 1 for &i in &[0, 4, 8, 12] { a = ff(a, b, c, d, m[i], 3); d = ff(d, a, b, c, m[i + 1], 7); c = ff(c, d, a, b, m[i + 2], 11); b = ff(b, c, d, a, m[i + 3], 19); } // round 2 for i in 0..4 { a = gg(a, b, c, d, m[i], 3); d = gg(d, a, b, c, m[i + 4], 5); c = gg(c, d, a, b, m[i + 8], 9); b = gg(b, c, d, a, m[i + 12], 13); } // round3 for &i in &[0, 2, 1, 3] { a = hh(a, b, c, d, m[i], 3); d = hh(d, a, b, c, m[i + 8], 9); c = hh(c, d, a, b, m[i + 4], 11); b = hh(b, c, d, a, m[i + 12], 15); } a0 = a0.wrapping_add(a); b0 = b0.wrapping_add(b); c0 = c0.wrapping_add(c); d0 = d0.wrapping_add(d); } // output let mut result = String::new(); for v in &[a0, b0, c0, d0] { result.push_str(&format!( "{:02x}{:02x}{:02x}{:02x}", (v >> 0) as u8, (v >> 8) as u8, (v >> 16) as u8, (v >> 24) as u8) ) } result } } #[cfg(test)] mod test { use crate::md4::MD4; #[test] fn test() { println!("MD4([empty string]) = {}", MD4::hash("".as_bytes())); println!("MD4([The quick brown fox jumps over the lazy dog]) = {}", MD4::hash("The quick brown fox jumps over the lazy dog".as_bytes())); } }
