一文讀懂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
的資料。
經過上面兩個步驟的處理，最終得到的處理後的資料如下圖所示:
步驟三: 初始化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:
word B:01 23 45 67
word C:89 ab cd ef
word D:fe dc ba 98
76 54 32 10
不過這裡要注意一點，程式實作的話，需要按照下面的方式來處理一下(上面加黑的部分, 低位元組在前面[low-order byte first]):
let A = 0x67452301;
let B = 0xEFCDAB89;
let C = 0x98BADCFE;
let D = 0x10325476;
步驟四: 對每一個分塊進行處理
這一步是整個MD5算法的核心，也是最繞的一部分，如果我哪裡描述的不是很清晰，那麼大佬們結合原始的
rfc
來看吧。
圖中的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拿答案, 盡量嘗試還原算法。
參考資料
- rfc1321
- MD5 - Wikipedia