一文读懂MD5
MD5
❝曾经沧海难为水，除却巫山不是云。-- 元稹
❞
MD5简介
❝MD5消息摘要算法（MD5 Message-Digest Algorithm），一种被广泛使用的密码散列函数，可以产生出一个128位的散列值（hash value），用于确保信息传输完整一致，MD5由美国密码学家罗纳德·李维斯特（Ronald Linn Rivest）设计。
❞
MD5实现步骤
这里根据rfc1321中的描述进行说明, 下文的描述中假设有一个b-bit的消息作为输入，即:
m = m_0 m_1 ... m _{b-1}
步骤一: 数据填充(Append Padding Bits)
MD5是按照分块进行处理的，分块长度为512bit, 大多数情况下，数据的长度不会恰好满足是512的整数倍，因此需要进行「padding」到给定的长度。
「填充规则」: 原始明文消息的b位之后补100..., 直到满足b + paddingLength % 512 = 448, 那如果b % 512在[448, 512(0)]之间呢，则在增加一个分块，按照前面的规则填充即可（因为rfc里面说了，最少填充1bit）。
步骤二: 长度填充
之前说了，需要满足b + paddingLength % 512 = 448， 那么对于最后一个分块，就还剩512 - 448 = 64 bit 这剩下的64bit存放的是原始消息的长度，也就是b。这也就是说，「MD5」最多可以处理明文长度小于等于2^64 bit的数据。
经过上面两个步骤的处理，最终得到的处理后的数据如下图所示:
MD5-Padding
步骤三: 初始化MD缓冲区
MD Buffer是4个32bit的向量，贴一下rfc的原文:
❝A four-word buffer (A,B,C,D) is used to compute the message digest. Here each of A, B, C, D is a 32-bit register. These registers are initialized to the following values in hexadecimal, 「low-order bytes first」): word A:
❞01 23 45 67word B:89 ab cd efword C:fe dc ba 98word D:76 54 32 10
不过这里要注意一点，程序实现的话，需要按照下面的方式来处理一下(上面加黑的部分, 「低字节在前面[low-order byte first]」):
let A = 0x67452301; let B = 0xEFCDAB89; let C = 0x98BADCFE; let D = 0x10325476;
步骤四: 对每一个分块进行处理
这一步是整个MD5算法的核心，也是最绕的一部分，如果我哪里描述的不是很清晰，那么大佬们结合原始的rfc来看吧。
One MD5 Operaton(图片来自维基百科)
图中的F函数，实际上是下面的4个函数:
F(X,Y,Z) = XY v not(X) Z G(X,Y,Z) = XZ v Y not(Z) H(X,Y,Z) = X xor Y xor Z I(X,Y,Z) = Y xor (X v not(Z))
这一部分用到了一个正弦函数表, 根据RFC当中的描述:
❝This step uses a 64-element table T[1 ... 64] constructed from the sine function. Let T[i] denote the i-th element of the table, which is equal to the integer part of 4294967296 times abs(sin(i)), where i is in radians. The elements of the table are given in the appendix.
❞
简单来说，就是下标(注意: 这里下标从1开始的哦)正弦的绝对值乘以一个常量(4294967296)用python输出一下这个表吧。
T = [int(abs(math.sin(i)) * 4294967296) for i in range(1, 65)] # output # [3614090360, 3905402710, 606105819, 3250441966, 4118548399, 1200080426, 2821735955, 4249261313, 1770035416, 2336552879, 4294925233, 2304563134, 1804603682, 4254626195, 2792965006, 1236535329, 4129170786, 3225465664, 643717713, 3921069994, 3593408605, 38016083, 3634488961, 3889429448, 568446438, 3275163606, 4107603335, 1163531501, 2850285829, 4243563512, 1735328473, 2368359562, 4294588738, 2272392833, 1839030562, 4259657740, 2763975236, 1272893353, 4139469664, 3200236656, 681279174, 3936430074, 3572445317, 76029189, 3654602809, 3873151461, 530742520, 3299628645, 4096336452, 1126891415, 2878612391, 4237533241, 1700485571, 2399980690, 4293915773, 2240044497, 1873313359, 4264355552, 2734768916, 1309151649, 4149444226, 3174756917, 718787259, 3951481745]
有了这个表，实际上是MD5的一个重要的特征，可以直接在内存中搜索这个表。
然后是对每一个块进行16轮的运算，具体运算内容我就不贴出来了，直接看下文参考资料当中的rfc的描述就好了。
步骤五: 输出
最后A, B, C, D的最终状态就是输出，这一步非常简单，就不做过多解释了。
代码实现
下面给出MD5的rust实现。
pub static T: [u32; 64] = [ 3614090360, 3905402710, 606105819, 3250441966, 4118548399, 1200080426, 2821735955, 4249261313, 1770035416, 2336552879, 4294925233, 2304563134, 1804603682, 4254626195, 2792965006, 1236535329, 4129170786, 3225465664, 643717713, 3921069994, 3593408605, 38016083, 3634488961, 3889429448, 568446438, 3275163606, 4107603335, 1163531501, 2850285829, 4243563512, 1735328473, 2368359562, 4294588738, 2272392833, 1839030562, 4259657740, 2763975236, 1272893353, 4139469664, 3200236656, 681279174, 3936430074, 3572445317, 76029189, 3654602809, 3873151461, 530742520, 3299628645, 4096336452, 1126891415, 2878612391, 4237533241, 1700485571, 2399980690, 4293915773, 2240044497, 1873313359, 4264355552, 2734768916, 1309151649, 4149444226, 3174756917, 718787259, 3951481745 ]; fn f(x: u32, y: u32, z: u32) -> u32 { (x & y) | (!x & z) } fn g(x: u32, y: u32, z: u32) -> u32 { (x & z) | (y & !z) } fn h(x: u32, y: u32, z: u32) -> u32 { x ^ y ^ z } fn i(x: u32, y: u32, z: u32) -> u32 { y ^ (x | !z) } fn ff(a: u32, b: u32, c: u32, d: u32, m: u32, s: u32) -> u32 { // b + ((a + F(b,c,d) + X[k] + T[i]) <<< s) a.wrapping_add(f(b, c, d)).wrapping_add(m).rotate_left(s).wrapping_add(b) } fn gg(a: u32, b: u32, c: u32, d: u32, m: u32, s: u32) -> u32 { // b + ((a + G(b,c,d) + X[k] + T[i]) <<< s) a.wrapping_add(g(b, c, d)).wrapping_add(m).rotate_left(s).wrapping_add(b) } fn hh(a: u32, b: u32, c: u32, d: u32, m: u32, s: u32) -> u32 { // b + ((a + H(b,c,d) + X[k] + T[i]) <<< s) a.wrapping_add(h(b, c, d)).wrapping_add(m).rotate_left(s).wrapping_add(b) } fn ii(a: u32, b: u32, c: u32, d: u32, m: u32, s: u32) -> u32 { // b + ((a + I(b,c,d) + X[k] + T[i]) <<< s) a.wrapping_add(i(b, c, d)).wrapping_add(m).rotate_left(s).wrapping_add(b) } pub struct MD5 {} impl MD5 { 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 = MD5::padding(message); // init MD Buffer let mut a0 = 0x67452301u32; let mut b0 = 0xefcdab89u32; let mut c0 = 0x98badcfeu32; let mut d0 = 0x10325476u32; // Process Message in 16-Word Blocks 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..16).step_by(4) { a = ff(a, b, c, d, m[i].wrapping_add(T[i]), 7); d = ff(d, a, b, c, m[i + 1].wrapping_add(T[i + 1]), 12); c = ff(c, d, a, b, m[i + 2].wrapping_add(T[i + 2]), 17); b = ff(b, c, d, a, m[i + 3].wrapping_add(T[i + 3]), 22); } // round 2 let mut t = 1; for i in (0..16).step_by(4) { a = gg(a, b, c, d, m[t & 0x0f].wrapping_add(T[16 + i]), 5); d = gg(d, a, b, c, m[(t + 5) & 0x0f].wrapping_add(T[16 + i + 1]), 9); c = gg(c, d, a, b, m[(t + 10) & 0x0f].wrapping_add(T[16 + i + 2]), 14); b = gg(b, c, d, a, m[(t + 15) & 0x0f].wrapping_add(T[16 + i + 3]), 20); t += 20; } // round 3 t = 5; for i in (0..16).step_by(4) { a = hh(a, b, c, d, m[t & 0x0f].wrapping_add(T[32 + i]), 4); d = hh(d, a, b, c, m[(t + 3) & 0x0f].wrapping_add(T[32 + i + 1]), 11); c = hh(c, d, a, b, m[(t + 6) & 0x0f].wrapping_add(T[32 + i + 2]), 16); b = hh(b, c, d, a, m[(t + 9) & 0x0f].wrapping_add(T[32 + i + 3]), 23); t += 12; } // round 4 t = 0; for i in (0..16).step_by(4) { a = ii(a, b, c, d, m[t & 0x0f].wrapping_add(T[48 + i]), 6); d = ii(d, a, b, c, m[(t + 7) & 0x0f].wrapping_add(T[48 + i + 1]), 10); c = ii(c, d, a, b, m[(t + 14) & 0x0f].wrapping_add(T[48 + i + 2]), 15); b = ii(b, c, d, a, m[(t + 21) & 0x0f].wrapping_add(T[48 + i + 3]), 21); t += 28; } 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::md5::MD5; #[test] fn test() { println!("md5([empty string]) = {}", MD5::hash("".as_bytes())); println!("md5([The quick brown fox jumps over the lazy dog]) = {}", MD5::hash("The quick brown fox jumps over the lazy dog".as_bytes())); } }
番外
这里有一个我魔改之后的md5算法(我没验证过抗碰撞性)，能还原算法计算1629547200的md5吗？
链接: https://pan.baidu.com/s/1Y-M-TOel8tyaaMooGndVSw 提取码: 9po4
提示: 这APP没有反调试，不要用hook拿答案, 尽量尝试还原算法。
