V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐关注
Meteor
JSLint - a JavaScript code quality tool
jsFiddle
D3.js
WebStorm
推荐书目
JavaScript 权威指南第 5 版
Closure: The Definitive Guide
quxinna
V2EX  ›  JavaScript

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

  •  
  •   quxinna · 2021-04-04 22:40:32 +08:00 via Android · 1761 次点击
    这是一个创建于 1308 天前的主题,其中的信息可能已经有所发展或是发生改变。
    这是 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 位。

    完全不一样啊,是说明写错了吗?
    8 条回复    2021-05-05 20:38:39 +08:00
    Flymachine
        1
    Flymachine  
       2021-04-06 15:45:38 +08:00   ❤️ 1
    你对位运算的知识了解不够啊,我建议你学一下<深入理解计算机系统>的前两章。

    你给的是 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
        2
    quxinna  
    OP
       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 赋值为数组排序长度
    //并不是补开头
    quxinna
        3
    quxinna  
    OP
       2021-04-06 22:21:21 +08:00 via Android
    len 取 1,x[len >> 5] |=0x80 << 8
    len 取 56,(((len + 64) >>> 9) << 4) + 14=(56*8+64)>>>9=1*16+14=30
    Flymachine
        4
    Flymachine  
       2021-04-07 10:06:05 +08:00   ❤️ 1
    @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
        5
    quxinna  
    OP
       2021-04-12 00:35:31 +08:00 via Android
    @Flymachine 这么说 rfc1321 说的 padding 是对的
    quxinna
        6
    quxinna  
    OP
       2021-04-12 02:15:06 +08:00 via Android
    @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
        7
    quxinna  
    OP
       2021-05-04 23:40:20 +08:00 via Android
    @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
        8
    quxinna  
    OP
       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
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   921 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 19ms · UTC 21:29 · PVG 05:29 · LAX 14:29 · JFK 17:29
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.