V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
lococo
V2EX  ›  程序员

CRC-32 算不算一种哈希算法?

  •  
  •   lococo · 2014-04-24 16:04:32 +08:00 · 10592 次点击
    这是一个创建于 3851 天前的主题,其中的信息可能已经有所发展或是发生改变。
    是不是任意大小的数据都可以通过CRC-32计算出一个32位的数据?

    如果是这样的话那不就是弱版的MD5
    为什么刚刚听老师说CRC-32不算一种哈希算法?
    27 条回复    1970-01-01 08:00:00 +08:00
    timonwong
        1
    timonwong  
       2014-04-24 16:24:12 +08:00   ❤️ 1
    timothyqiu
        2
    timothyqiu  
       2014-04-24 16:26:14 +08:00   ❤️ 2
    哈希是把 任意长度数据 往 固定长度数据 上的一种映射。

    所以 CRC-32 算哈希算法。

    不过,理论上 return 0 也是一种哈希算法,只不过永远碰撞而已。
    lococo
        3
    lococo  
    OP
       2014-04-24 16:30:21 +08:00
    刚刚论文导师说我的论文太水,没看懂我的算法,把我骂一顿
    第一句话就是说:
    P14 crc-32 不是哈希函数!!

    我还以为真是我错了 ``
    nicai000
        4
    nicai000  
       2014-04-24 16:33:03 +08:00
    算, 你老师略弱. "弱版的MD5"这句话说得也略弱.
    Keyes
        5
    Keyes  
       2014-04-24 16:33:54 +08:00
    CRC32是一个妥妥的标准哈希算法,整个CRC系列都是为这目的而诞生的,你导师如此卖萌……
    Keyes
        6
    Keyes  
       2014-04-24 16:35:06 +08:00   ❤️ 1
    你可以去维基摘一些CRC的公式给他……
    lococo
        7
    lococo  
    OP
       2014-04-24 16:50:22 +08:00
    我刚刚把这个帖子的链接贴给导师了 ``
    导师说我如果在论文里写CRC-32是一种哈希算法的话这点就通不过检查的
    raptium
        8
    raptium  
       2014-04-24 16:51:14 +08:00
    http://en.wikipedia.org/wiki/Cryptographic_hash_function
    http://en.wikipedia.org/wiki/Hash_function

    你导师把这两个搞混了
    CRC32 是 Hash Function,不过对碰撞就没啥抵抗了
    lococo
        9
    lococo  
    OP
       2014-04-24 16:51:20 +08:00
    好伤心
    那我还是把我论文里的所有这样写的语句改成
    恩`` 循环冗余校验算法!!
    raptium
        10
    raptium  
       2014-04-24 16:52:23 +08:00
    事实上简单的 Hash Function 可以是 f(x) = x mod n
    在写 hash map 的时候这样就够用了
    xdeng
        11
    xdeng  
       2014-04-24 16:57:04 +08:00
    碰撞率 比 MD5高吧?
    lococo
        12
    lococo  
    OP
       2014-04-24 17:00:04 +08:00
    @xdeng
    对呀 。。
    所以我一直觉得CRC32就好像弱版的MD5
    xdeng
        13
    xdeng  
       2014-04-24 17:30:29 +08:00
    @lococo CRC32 好像是追求的是速度
    Keyes
        14
    Keyes  
       2014-04-24 17:32:01 +08:00
    @xdeng 这也是TCP用它做校验的原因
    lococo
        15
    lococo  
    OP
       2014-04-24 17:34:24 +08:00
    @xdeng
    我的论文是研究大数据完整性验证的,需求就是想要提高验证的效率
    最开始我想用bloom filter + MD5 实现,最后比较了一番
    我才用的 hash set + crc-32 去实现
    min
        16
    min  
       2014-04-24 17:43:21 +08:00
    @lococo
    你把这link发给你导师了?
    还是不要费力搞什么论文了,研究一下换导师实在点儿 :)
    Keyes
        17
    Keyes  
       2014-04-24 17:43:26 +08:00
    其实用于少量数据的完整性校验,并不需要MD5等算法上场

    另外“碰撞”也只是f(data1) == f(data2)而已;

    但如果是我有数据篡改的目的,那我的目的一定是:
    要根据a1的数据进行篡改得到a2,且hash(a1)==hash(a2),且a2要具有实际意义,要保持原有数据结构的长度限制;

    反正我是做不到……要得出长度一样、哈希结果一样,但内容不一样的两组数据,我相信即使CRC32也没有那么容易就做出来的

    半吊子一个……不知道各位能看懂不……求做算法的大神出面详解
    min
        18
    min  
       2014-04-24 17:44:09 +08:00
    验证效率方面,好像有些hash算法是针对性能优化的,可以找来参考参考
    Keyes
        19
    Keyes  
       2014-04-24 17:46:39 +08:00
    @min 默默+1
    nicai000
        20
    nicai000  
       2014-04-24 17:46:47 +08:00
    你竟然把这帖子发给导师, 也真够直的...
    lococo
        21
    lococo  
    OP
       2014-04-24 17:50:21 +08:00
    导师现在已经懒得理我了··
    twor2
        22
    twor2  
       2014-04-24 18:11:50 +08:00
    @lococo “导师现在已经懒得理我了·· ”

    戳中笑点 233333
    zinking
        23
    zinking  
       2014-04-24 18:18:20 +08:00
    我觉得要看你讨论的上下文, 如果上下文里哈希算法指的是用在Map之类数据结构上的话, 我不觉得CRC是哈希算法。 CRC就是通常意义的校验算法而已。 没必要把什么东西都往抽象高层发散。 就像前面同学说的return 0还是哈希算法呢
    quake0day
        24
    quake0day  
       2014-04-24 22:50:20 +08:00   ❤️ 1
    如果检查的人有机会听你辩驳的话你就这么写。如果你没机会申辩的话,那最好还是改成他们容易懂的表述。
    lococo
        25
    lococo  
    OP
       2014-04-24 23:35:50 +08:00
    @quake0day
    嗯 。。我觉得导师还是为我好 。。
    今天有点激动了 。。
    undeadking
        26
    undeadking  
       2014-04-25 13:41:01 +08:00
    hash算法和可用于加密学的安全hash算法是两回事,一般信息安全的课本都会有详细的定义说明啊
    lococo
        27
    lococo  
    OP
       2014-04-25 15:05:05 +08:00 via iPhone
    @undeadking
    最开始导师给我问题背景假设的时候就在说用hash去确保原始数据完整性…
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1251 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 17:58 · PVG 01:58 · LAX 09:58 · JFK 12:58
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.