首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
V2EX  ›  问与答

有什么常见可靠比 MD5 短的摘要算法?

  •  
  •   nyse · 350 天前 · 2149 次点击
    这是一个创建于 350 天前的主题,其中的信息可能已经有所发展或是发生改变。

    有一个项目,大概就是抓取一些数据,每条数据包含很短的字符串(不超过 200 字)和一些数字。

    现在是通过把这些字符串数字等拼在一起,计算 MD5,存入数据库,以 MD5 作为唯一索引判断是否存在。

    但是感觉 MD5 太长了,占用数据库空间,有没有更短的摘要算法,以减少数据库占用?

    19 回复  |  直到 2018-10-31 14:47:47 +08:00
        1
    qwe61655   350 天前 via iPhone
    要短还要可靠 你不觉得冲突了吗
        2
    creamiced   350 天前   ♥ 2
    抛个砖:使用 MD5 结果的前几位。
    嫌 MD5 占用空间,是否说明数据量极大,能否接受更短的结果带来的更大的碰撞几率?
        3
    kernel   350 天前
    取 md5 一段就行了
        4
    yanaraika   350 天前
    直接随便找个 digest 算法,取输出前若干位
        6
    surfire91   350 天前
    如何定义可靠?
    你要多短的?可以看看 CRC。
        7
    imdong   350 天前
    那你有多少条数据呢?
    10 条数据的话,md5 截取固定两三位也许就够了。
    如果数据量非常大,我认为 md5 已经不够可靠了。
        8
    e9e499d78f   350 天前 via iPhone
    xxhash 64
        9
    wysnylc   350 天前
    建议数据库全清,更省
        10
    batter   350 天前
    再短容易撞吧?
        11
    shoumu   350 天前
    md5 你可以只取 64 位啊,你可以算一下碰撞概率,符合预期还可以取更短的长度
        12
    qq316107934   350 天前
    md5 可以 binary 化映射到 ASCII 全区域啊,32x16/128=4,四个字符长度足矣
        13
    msg7086   350 天前
    @qq316107934 128bit 16 字节的二进制是怎么算出四个字符的。

    @myse 自己计算一下碰撞概率,算出碰撞空间,转换成 bit 就知道该用什么了。
    这些密码学摘要算法的长度就是碰撞可靠性。缩短长度就是缩短碰撞可靠性。
    如前面所说,每减少 1bit,碰撞空间减半,等于碰撞概率加倍。减少一个字节就是碰撞概率变成原来的 256 倍,md5 切一半就是原来的 2^64 倍。
        14
    glues   350 天前
    md5 这种过时的东西,居然还有人在用?
    如 12 楼所说的,摘要指不一定非要用 hex,用 ASCII 的话,应该能省点空间
    另外,硬盘白菜价的年代,还在乎这点空间?
        15
    jjianwen68   350 天前
    md5 前 4 位后 4 位综合判断是不是就够了
        16
    qq316107934   350 天前
    @msg7086 #13 不好意思没仔细思考算错了,一个 ASCII 是 8bit,一个 HEX 是 4bit,应该是长度折半。
        17
    geelaw   350 天前 via iPhone   ♥ 1
    @glues #14 这个场景里并没有 adversarially chosen strings,MD5 属于一种随意的选择。

    回到楼主的问题,如果你把 hash 函数建模为 random oracle,输出长度是 k bits 时,在 2^(k/2) 个 strings 时有常数概率碰撞。一般希望碰撞概率是 negligible,所以可以设置

    k = w(log t) + 2 log N

    其中 N 是数据的个数,t 是安全参数,w 表示严格高阶无穷大。
        18
    zjp   350 天前
    md5 取部分不如 CRC16/CRC32
    实际上差不了多少
        19
    jimages   350 天前 via iPhone
    布隆过滤器?
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3099 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 31ms · UTC 00:56 · PVG 08:56 · LAX 17:56 · JFK 20:56
    ♥ Do have faith in what you're doing.