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 循环中的那些常数值,有什么规律吗?为什么要选这些值,而不选用其他值?

  •  
  •   quxinna · 2021-04-01 10:31:32 +08:00 · 2314 次点击
    这是一个创建于 1083 天前的主题,其中的信息可能已经有所发展或是发生改变。
    a = md5ff(a, b, c, d, x[i], 7, -680876936)
    d = md5ff(d, a, b, c, x[i + 1], 12, -389564586)
    如上面的-680876936,-389564586 等等。
    这些值是根据什么确定的?
    18 条回复    2021-07-12 19:31:49 +08:00
    Bromine0x23
        1
    Bromine0x23  
       2021-04-01 14:47:24 +08:00
    来自 2^32 * sin(i) 取整
    Bromine0x23
        2
    Bromine0x23  
       2021-04-01 14:50:15 +08:00
    漏了个绝对值,是 floor(2^32 * abs(sin(i)))
    quxinna
        3
    quxinna  
    OP
       2021-04-01 15:50:13 +08:00 via Android
    @Bromine0x23

    a = md5ff(a, b, c, d, x[i], 7, -680876936)
    b = md5gg(b, c, d, a, x[i], 20, -373897302)
    d = md5hh(d, a, b, c, x[i], 11, -358537222)
    a = md5ii(a, b, c, d, x[i], 6, -198630844)
    引自 blueimp javascript md5
    i 一样结果不一样啊
    Bromine0x23
        4
    Bromine0x23  
       2021-04-01 16:04:04 +08:00   ❤️ 1
    @quxinna
    一样的,公式算出来是 UInt32,转成 Int32 就对上了
    floor(2^32 * abs(sin(1))) = 3614090360 = 0xD76AA478 => -680876936
    floor(2^32 * abs(sin(20))) = 3921069994 = 0xE9B6C7AA => -373897302
    quxinna
        5
    quxinna  
    OP
       2021-04-01 16:54:04 +08:00 via Android
    @Bromine0x23 i 的取值范围是多少,为什么 md5 是发散的?
    Bromine0x23
        6
    Bromine0x23  
       2021-04-01 21:17:14 +08:00
    @quxinna
    i 取 1~64
    你说的发散不太懂是什么意思
    quxinna
        7
    quxinna  
    OP
       2021-04-01 21:43:18 +08:00
    @Bromine0x23 就是离散的意思,任意长度的 string 如何一一对应到 128 位的 md5 输出的,譬如 blueimp javascript md5 https://github.com/blueimp/JavaScript-MD5/ ,简单的移位和或操作是无法做到的吧,是不是 floor(2^32 * abs(sin(i)))中有什么操作。
    quxinna
        8
    quxinna  
    OP
       2021-04-01 21:50:30 +08:00
    @Bromine0x23 为什么最大取 64,如果文件很大比如 1TB,64 不是不够用吗?
    hsfzxjy
        9
    hsfzxjy  
       2021-04-01 22:16:46 +08:00 via Android
    md5 不是一一对应的,只是摘要算法
    quxinna
        10
    quxinna  
    OP
       2021-04-01 22:25:13 +08:00 via Android
    @hsfzxjy https://blueimp.github.io/JavaScript-MD5/ 譬如这个网址,任意字符都对应不同输出,找到碰撞极难,怎么不是一一对应的呢?
    Bromine0x23
        11
    Bromine0x23  
       2021-04-02 00:05:33 +08:00
    @quxinna
    ……先理解下什么是摘要算法吧
    这些常数是用于每一轮次迭代的计算,在算法设计上可以是随机选取的字节,之所以基于正弦函数是为了表明没有精心构造的后门
    pluvet
        12
    pluvet  
       2021-04-02 10:02:14 +08:00
    @quxinna 惊人言论
    GuuJiang
        13
    GuuJiang  
       2021-04-02 11:22:09 +08:00 via iPhone   ❤️ 2
    @quxinna 看到你连发了几个帖子都是关于 md5 的,感觉有点钻牛角尖了,有几点个人建议仅供参考
    1. 不清楚你为什么要在每个问题里都带上 blueimp,md5 是一个公开的算法,任何一种语言的具体实现都遵循同样的算法
    2. 在深入具体实现细节之前,你应该系统性地学习一下摘要算法的基本概念,摘要算法还有很多,而你存在认知错误的几个性质是所有摘要算法都具备的基本性质,与是不是 md5 无关,事实上对于大多数工程应用来说,首先要当作黑盒,充分了解算法的背景及适用场景,有兴趣再去深究具体实现
    3. 关于你说的一一对应问题,用简单的鸽巢原理就可以得出结论,md5 的值域是有限的,而定义域是远大于值域的,必然不可能是一一对应,找到碰撞极难是因为这个值域虽然有限,但是对于人类来说还是太大了,想单纯靠碰运气的方式找到碰撞可以认为几乎不可能,这也从侧面体现了分散性的良好
    4. 理论上任何一个把任意长度信息映射到固定长度信息的算法都可以称为摘要算法,只是性质有好坏之分,主流的 md5 、sha 等算法之所以能被实际应用在安全领域,是因为它们具备下面这些良好的性质:原文中任意一个位置的改变都会导致结果的改变,原文中任意一个小的改变都会导致结果的大幅度改变,实现细节中的各种操作及常数的选取都是为了实现这两个目标,至于为什么能做到你可以去找别人总结好的背后的数学原理相关的文献看,但是恕我直言按照你现在的理解看这些还为时尚早,毕竟老祖宗也说过,思而不学则殆
    quxinna
        14
    quxinna  
    OP
       2021-04-03 17:21:37 +08:00
    @Bromine0x23 我也知道基于正弦函数的迭代运算是摘要算法的基础,可是 blueimp javascript md5 https://github.com/blueimp/JavaScript-MD5/ ,看到脚本里面都是移位操作,没有正弦函数的迭代运算,是不是里面有什么 javascript 语法我看错了?
    Bromine0x23
        15
    Bromine0x23  
       2021-04-05 15:13:51 +08:00
    @quxinna
    1. 正弦函数是被 MD5 算法的设计者用来选取算法常数,和 MD5 计算散列值的方法本身没有关系
    2. 建议看 RFC 1321,不要揪着具体的某个实现
    quxinna
        16
    quxinna  
    OP
       2021-04-07 02:25:06 +08:00 via Android
    @Bromine0x23 d5 可能是通过异或正弦函数将数值扩散
    quxinna
        17
    quxinna  
    OP
       2021-04-07 02:25:53 +08:00 via Android
    @Bromine0x23 md5 可能是通过异或正弦函数将数值扩散
    quxinna
        18
    quxinna  
    OP
       2021-07-12 19:31:49 +08:00
    常数值类似于 poly 是唯一的
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5488 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 08:02 · PVG 16:02 · LAX 01:02 · JFK 04:02
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.