3、MD5的数学基础：位运算、模运算、非线性函数
很多人在学MD5时，一上来就盯着那64步的循环看。结果呢？越看越晕。我当初也一样，觉得这东西太复杂了。
后来我发现，其实MD5的数学基础就三个东西：位运算、模运算、非线性函数。搞懂这三个，你就掌握了MD5的核心心跳。
下面我一个个讲。嗯，咱们从最基础的位运算开始。
3.1 位运算：MD5的原子操作
位运算，说白了就是直接在二进制位上干活。你想想看，计算机最底层就是0和1。位运算速度飞快，这是所有哈希算法的首选。
MD5里用到了哪几种位运算？我列了个表，一目了然：
| 运算 | 符号 | 含义 | 例子 (32位) |
|---|---|---|---|
| 按位与 | & | 全1则1，否则0 | 0x12345678 & 0xFFFF0000 = 0x12340000 |
| 按位或 | | | 有1则1，全0则0 | 0x12340000 | 0x00005678 = 0x12345678 |
| 按位非 | ~ | 0变1，1变0 | ~0x12345678 = 0xEDCBA987 |
| 异或 | ^ | 相异为1，相同为0 | 0x12345678 ^ 0x87654321 = 0x95511559 |
| 左移 | << | 高位丢弃，低位补0 | 0x80000001 << 1 = 0x00000002 |
| 右移 | >> | 逻辑右移：高位补0 | 0x80000001 >> 1 = 0x40000000 |
| 循环左移 | <<< | 左移后移出的位补到低位 | 0x80000001 <<< 1 = 0x00000003 |
这里面最关键的，其实是循环左移。MD5的每一轮都会对某个中间结果做循环左移。为什么要循环左移？因为如果不循环，信息就从高位那头跑出去了。循环一下，信息还在里面打转，增加了混合度。
我个人习惯用Python来验证这些位运算。MD5里到处都是32位无符号整数的操作，而Python的整数是无限精度的，所以得加个掩码才能模拟。你看这个例子：
# 模拟32位循环左移
def left_rotate(value, shift):
value &= 0xFFFFFFFF # 截断到32位
return ((value << shift) | (value >> (32 - shift))) & 0xFFFFFFFF
# 测试一下
x = 0x80000001
print(hex(left_rotate(x, 1))) # 输出: 0x3 (因为0x80000001左移1位变0x2，移出的1补回来)
我的经验：位运算切不可掉以轻心。我在一个项目里就吃过亏——Python里没有无符号右移，用>>时负数的符号位会扩展。这就是个坑。MD5里所有数字都必须当作无符号32位来处理，一定要加& 0xFFFFFFFF。
3.2 模运算：2^32的魔法
搞清楚了位运算，咱们再来看看模运算。MD5里只用到一种模运算：模2^32加。
为什么会是2^32？因为MD5处理的是32位整数。2^32就是4294967296。两个32位数相加，结果可能超过32位。怎么办？取个模，把高出的部分丢掉，只保留低32位。
说白了，这就是个溢出加法。我在刚开始学的时候，觉得这玩意儿太粗暴了。后来才明白，这种溢出恰恰是信息混合的关键——高位被丢弃后，低位仍然保留了两份输入的全部信息。
# 模2^32加
a = 0xFFFFFFFF
b = 0x00000001
result = (a + b) & 0xFFFFFFFF
print(hex(result)) # 输出: 0x0 (因为 0xFFFFFFFF + 1 = 0x100000000, 截断后为0)
你看，0xFFFFFFFF加1，正常结果应该是0x100000000，但模2^32之后变成0了。这就是溢出。
避坑指南：我曾经在一个C项目里忘记把加法的结果强制转为uint32_t，结果编译器做了整型提升，中间结果用了64位，最终哈希值完全不对。排查了两天才找到。记住：每一步加法都要模2^32，不能等最后再取模。
MD5里除了加法，没有乘法、减法、除法。为什么呢？因为哈希算法的设计要求就是快。加法在CPU里一个时钟周期就完事，而乘除法要慢得多。
3.3 非线性函数：混合的催化剂
有了位运算和模运算，MD5还需要一个东西：非线性函数。没有它们，整个运算就太线性了，输入的小变化只能引起输出的线性变化，哈希效果就很差。
MD5用了四个非线性函数，对应四轮运算：
| 轮次 | 函数 | 表达式 | 特点 |
|---|---|---|---|
| 第1轮 | F | (X & Y) | (~X & Z) | 每一位的结果是Y和Z根据X选择的 |
| 第2轮 | G | (X & Z) | (Y & ~Z) | 与F对称，只是角色互换 |
| 第3轮 | H | X ^ Y ^ Z | 异或，完全对称 |
| 第4轮 | I | Y ^ (X | ~Z) | 混合了或和非 |
你看这规律：F和G是对称的，H是最简单的异或，I稍微复杂一点。它们都是非线性的——也就是说，你不能用线性组合来逼近它。这就保证了MD5的雪崩效应：输入哪怕只改一个比特，输出的一半比特都会翻转。
# MD5的四个非线性函数
def F(x, y, z):
return (x & y) | (~x & z)
def G(x, y, z):
return (x & z) | (y & ~z)
def H(x, y, z):
return x ^ y ^ z
def I(x, y, z):
return y ^ (x | ~z)
# 测试一下
x, y, z = 0x12345678, 0x9ABCDEF0, 0xFEDCBA98
print(hex(F(x, y, z))) # 0x1A345678
print(hex(H(x, y, z))) # 0x4B9BCF06
关键点：这四个函数虽然不同，但有一个共同性质——它们都在比特级别上均匀混合了三个输入。无论输入怎么变，输出的每一位都有50%的翻转概率。这是MD5安全性的基础。
现在我画一张图，把这三个基础的关系理清楚。你看了就明白MD5是怎么搭建的了：
看到没？位运算、模运算、非线性函数，三个基础模块汇聚到MD5的压缩函数里。MD5的每一轮步子都是这样：先对三个32位输入做非线性函数，再加一个32位常量和某个消息字，然后循环左移，最后加回原始值。
我的一点建议：如果你想把MD5的自己实现一遍，先别急着写64步。先把left_rotate和四个非线性函数写对，然后用几个简单的输入验证结果。我在一个测试框架里就是这么做的，先测位操作，再测函数，最后集成。这样出了问题，定位很快。
3.4 三个基础如何配合？
前面讲了三个基础分别是什么。现在我来聊聊它们怎么配合的。
你想想看，如果你只用位运算，那就是线性的，很容易找到碰撞。如果你只用模运算，那就是加法，输入和输出的关系太直接。如果你只用非线性函数，没有移位和加法，信息扩散不出去。
MD5的高明之处，就在于把三者组合起来：
- 非线性函数做第一层混合：根据三个输入产生一个输出，打破线性关系。
- 模加做第二层混合：把当前状态和消息字、常数混在一起，产生溢出。
- 循环左移做第三层扩散：让高位的比特跑到低位去，下次运算时就能影响到其他比特。
这三步构成了MD5的一轮运算，迭代16次就是一层，4层就是64次。每一次都在前一次的基础上把信息搅得更均匀。
一句话总结：MD5的数学基础其实就是三个玩意儿——位运算让你能快速操作比特，模运算让你能自然溢出，非线性函数让输出不可预测。三者缺一不可。
好了，这一章就到这儿。你只要把位运算、模加和非线性函数搞清楚了，后面看MD5的64步循环时，就会发现每一步都是在做同样的事情——混合、扩散、再混合、再扩散。