md5 padding 说明和 JavaScript MD5 implementation 完全不一样啊？是说明写错了吗？

这是 blueimp javascript md5 https://github.com/blueimp/JavaScript-MD5 的 md5 padding

x[len >> 5] |= 0x80 << len % 32
x[(((len + 64) >>> 9) << 4) + 14] = len

四个字节一组
数组排序长度*8 右移 5 位，或十六进制 80 十进制 128 左移数组排序长度*8 模 32 数组
数组排序长度*8 加 64 右移 9 位，左移 4 位，加 14，赋值长度

这是网上的 md5 padding 介绍

MD5 可以认为是基于 block 的算法：它要求每次处理的数据长度为 512bits 。但是实际中要处理的明文长度并不一定是 512 的整数倍，怎么办呢？参考 AES 的做法，做数据补齐 /填充（ Padding ）。假设原始明文消息的长度为 K，MD5 的 Padding 可以细分为 2 个子步骤：

附加填充位（ Append Padding Bits ）：从原始明文消息的 K 位之后补 100...一直到 512-64=448 位，填充位的规则是：只有第一个 bit 是 1，之后都是 0 。这里有个问题：如果 K%512 正巧等于 448 怎么办呢？再者，如果 K%512 在[448,512(模运算得到的是 0)]之间怎么办呢？答案：Append Padding Bits 要求至少填充 1 位，如果长度正好是 448，那么就索性再增加一个 block，填充 512bits ；如果模超过 448，也再增加一个 block，填充 512-（ K%512-448 ）；同理，如果模不到 448，就填充 448-K%512 即可。
附加长度（ Append Length ）：这个时候，最后一个 block 只剩下 64bits 需要填充了，其内容是原始明文的长度。试想，64bits 可以表示最长的数据将近 2^30GB 的数据了！如果原始明文大于这个数值，那就只能对 2^64 取模，作者在原文中是这么写的：
In the unlikely event that b is greater than 2^64, then only the low-order 64 bits of b are used.
如果 b 大于 2^64，则仅使用 b 的低阶 64 位。

完全不一样啊，是说明写错了吗？

Flymachine

2021-04-06 15:45:38 +08:00

你对位运算的知识了解不够啊，我建议你学一下<深入理解计算机系统>的前两章。

你给的是 binlMD5 函数实现的头两行，而它是这样被调用的：
binl2rstr(binlMD5(rstr2binl(s), s.length * 8))

binlMD5 的参数是 rstr2binl 函数的结果，而 rstr2binl 是这样实现的：
function rstr2binl(input) {
var i
var output = []
output[(input.length >> 2) - 1] = undefined // 设置数组最大长度（包含原始数据、填充和数据长度）
for (i = 0; i < output.length; i += 1) {
output[i] = 0 // 初始化 0x00, 注意此时实际上也把 00 填充都加上了
}
var length8 = input.length * 8
for (i = 0; i < length8; i += 8) {
output[i >> 5] |= (input.charCodeAt(i / 8) & 0xff) << i % 32 // 写入原始数据
}
return output // 返回此数组
}
已经开始设置填充了。
也就是说 binlMD5 的头两行只是对其的补充：
x[len >> 5] |= 0x80 << len % 32 // 补上填充字段开头一位的 1
x[(((len + 64) >>> 9) << 4) + 14] = len // 补上原始数据的长度

quxinna

2021-04-06 22:13:13 +08:00

@Flymachine

output[(input.length >> 2) - 1] = undefined // 设置数组最大长度（包含原始数据、填充和数据长度）
for (i = 0; i < output.length; i += 1) {
output[i] = 0 // 初始化 0x00, 注意此时实际上也把 00 填充都加上了
}

//这段代码删除也不影响运行,应该不是初始化

x[len >> 5] |= 0x80 << len % 32 // 补上填充字段开头一位的 1
x[(((len + 64) >>> 9) << 4) + 14] = len // 补上原始数据的长度

//len 取 1，0x80 << 8 结果赋值
//len 取 56，数组排序长度(56*8+64)>>>9 即 1*16+14=30 赋值为数组排序长度
//并不是补开头

Flymachine

2021-04-07 10:06:05 +08:00

@quxinna
1. “//这段代码删除也不影响运行,应该不是初始化”，不能这么看，这是 Undefined Behavior （未定义行为），有些编译 /解释器是会把数组元素自动初始化为 0 的，特别是像 JS 这种解释型语言。但这并不一定是语言标准中规定的行为，所以可能存在不会把元素自动初始化的浏览器环境，所以为了防止 UB 导致的未知 BUG，广泛使用的开源库一般都尽量不使用 UB 。因此，你理解代码不能依赖运行结果，而应该理解程序员写这些代码的意图。

建议你看几本喜欢用伪代码解释程序的编程书，你就知道靠运行结果来理解程序有多奇怪了。

2. “//len 取 1，0x80 << 8 结果赋值”，我建议你好好理解

binl2rstr(binlMD5(rstr2binl(s), s.length * 8)) 为什么字符串长度要*8——len 是字符串数组的位长度，所以不要把参数 len 和 s.length 搞混了。

3. “//并不是补开头”，我建议你好好理解

output[i >> 5] |= (input.charCodeAt(i / 8) & 0xff) << i % 32 // 写入原始数据

这段代码，想象 i = len，然后你就明白我为什么说“x[len >> 5] |= 0x80 << len % 32”是在补上填充字段开头一位的 1 了。

这个 MD5 为了执行效率，output 并不是一个字节数组，加上耦合性极高的内部代码，所以理解上确实很困难。

如果你真想理解 MD5 的实现，建议你先去学一下<深入理解计算机系统>的前两章，或者学一下 C 语言，看一下 C 语言下的 MD5 实现。

quxinna

2021-04-12 02:15:06 +08:00

@Flymachine 不对啊
输入 1 个 1 输入得到 len>>5=0，x[len >> 5]=128 << 8+0x31= 32768+49=32817
输入 2 个 1 输入得到 len>>5=0，x[len >> 5]=128 << 16+0x3131=8388608+12593=8401201
输入 3 个 1 输入得到 len>>5=0，x[len >> 5]=128 << 24+0x313131 =-2147483648+3223857=-2144259791
输入 4 个 1 输入得到 len>>5=1，x[len >> 5]=128 << 0+0x313131=0x31313131=825307441

输入 1 个 1 得到(0+64) >>> 9 = 0 << 4+14 = 14
输入 56 个 1 得到(56*32 = 448+64 = 512) >>> 9 = 1 << 4+14 = 30

quxinna

2021-05-04 23:40:20 +08:00

@Flymachine
补为 448 确实如此，开头补 1 有待考证
x[len >> 5] |= 0x80 << len % 32
//len 单位为 8*byte x 单位为 byte/4
//不足 32 位的数据前面加上 128，正好 32 位的数据在后面一组加上 128
//2^5 = 32 0x80=2^7=128
输入 0 个 1 输入得到 len>>5=0，x[len >> 5]=128 << 0=128
输入 1 个 1 输入得到 len>>5=0，x[len >> 5]=128 << 8+0x31=0x8000+0x31=32768+49=32817
输入 2 个 1 输入得到 len>>5=0，x[len >> 5]=128 << 16+0x3131=0x800000+0x3131=8388608+12593=8401201
输入 3 个 1 输入得到 len>>5=0，x[len >> 5]=128 << 24+0x313131=0x80000000+0x313131=-2147483648+3223857=-2144259791
输入 4 个 1 输入得到 len>>5=1，x[len >> 5]=128 << 0=128

x[(((len + 64) >>> 9) << 4) + 14] = len
//输入 1 个 1 得到(8+64) >>> 9 = 0 << 4+14 = 14
//document.write(x[13] + ',')
//undefined,
//document.write(x[14] + ',')
//8,
//document.write(x[15] + ',')
//undefined,
//输入 56 个 1 得到(56*8+64 = 448+64 = 512) >>> 9 = 1 << 4+14 = 30
//除以 512，剩余的数值不足 448 的补充为 448，正好 448 的直接补充 512，超过 448 不足 512 的补充为 512，再补充 448
//2^4*32=512 14*32=448 2^9=512
//document.write(x[29] + ',')
//undefined,
//document.write(x[30] + ',')
//448,
//document.write(x[31] + ',')
//undefined,

quxinna

2021-05-05 20:38:39 +08:00

@quxinna 这个从比特流的角度看确实是数据末尾。字符 1 的 ASCII 码是 49，对应的二进制是 00110001，在它的末尾追加 1 比特和 23 个 0 比特，构成了 00110001 10000000 00000000 00000000 。又因为 x86 平台存储一个整数是用小端序存的，倒过来就是 00000000 00000000 10000000 00110001，所以是 32768+49=32817