4

我正在创建一个与文件相关的应用程序。我一直在寻找计算文件校验和的方法。我想知道基于此标准计算文件 md5 或 SHA-1 或其他东西的校验和的最佳散列方法是什么

  • 校验和应该是唯一的。我知道它的理论，但我仍然希望碰撞的概率非常小。
  • 如果校验和相等，可以比较两个文件是否相等。
  • 速度（不是很重要，但仍然）

请随时尽可能详尽。

4

4 回答 4

6

这取决于您的用例。

如果只担心意外碰撞，MD5 和 SHA-1 都可以，MD5 一般更快。事实上，MD4 对于大多数用例来说也足够了，而且通常更快……但它并没有被广泛实施。（特别是，它不在hashlib.algorithms_guaranteed……尽管它应该在hashlib_algorithms_available大多数库存的 Mac、Windows 和 Linux 版本中。）

另一方面，如果您担心故意攻击（即有人故意制作与您的哈希匹配的虚假文件），您必须考虑所保护内容的价值。MD4 几乎肯定是不够的，MD5 可能还不够，但 SHA-1 是临界的。目前，Keccak（很快将由 SHA-3 发布）被认为是最好的选择，但你会想要保持领先，因为情况每年都在变化。

Cryptographic hash function上的 Wikipedia 页面有一个通常会经常更新的表。要理解表格：

产生与 MD4 的碰撞只需要 3 轮，而 MD5 需要大约 200 万轮，而 SHA-1 需要 15 万亿轮。这足以产生碰撞需要几百万美元（以今天的价格计算）。这对你来说可能不够好，也可能不够好，但对 NIST 来说还不够好。

另外，请记住，“通常更快”并不像“在我的数据和平台上测试得更快”那么重要。考虑到这一点，在我的 Mac 上的 64 位 Python 3.3.0 中，我创建了一个 1MB 的随机bytes对象，然后这样做：

In [173]: md4 = hashlib.new('md4')
In [174]: md5 = hashlib.new('md5')
In [175]: sha1 = hashlib.new('sha1')
In [180]: %timeit md4.update(data)
1000 loops, best of 3: 1.54 ms per loop
In [181]: %timeit md5.update(data)
100 loops, best of 3: 2.52 ms per loop
In [182]: %timeit sha1.update(data)
100 loops, best of 3: 2.94 ms per loop

正如你所看到的，md4它比其他的要快得多。

使用hashlib.md5()而不是hashlib.new('md5')和使用bytes较少熵的测试（string.ascii_letters以空格分隔的 1-8 运行）没有显示任何显着差异。

而且，对于我的安装附带的哈希算法，如下所示，没有什么比 md4 更好的了。

for x in hashlib.algorithms_available:
    h = hashlib.new(x)
    print(x, timeit.timeit(lambda: h.update(data), number=100))

如果速度真的很重要，那么您可以使用一个很好的技巧来改进它：使用一个糟糕但非常快的哈希函数，例如zlib.adler32，并且只将它应用于每个文件的前 256KB。（对于某些文件类型，最后 256KB 或最靠近中间的 256KB 不超过等可能比第一个更好。）然后，如果发现冲突，生成 MD4/SHA-1/Keccak/whatever hashes on每个文件的整个文件。

最后，由于有人在评论中询问如何在不将整个内容读入内存的情况下对文件进行哈希处理：

def hash_file(path, algorithm='md5', bufsize=8192):
    h = hashlib.new(algorithm)
    with open(path, 'rb') as f:
        block = f.read(bufsize)
        if not block:
            break
        h.update(block)
    return h.digest()

如果挤压出每一点性能很重要，您将需要bufsize在您的平台上尝试不同的值（从 4KB 到 8MB 的 2 的幂）。您可能还想尝试使用原始文件句柄 (os.open和os.read)，这有时在某些平台上可能更快。

于 2013-05-28T19:08:25.280 回答
2

理论上，具有足够位的哈希大小的冲突可能性非常小：

假设具有均匀分布的随机散列值、n 个不同数据块的集合和一个生成 b 位的散列函数，发生一次或多次碰撞的概率 p 的边界是块对的数量乘以发生碰撞的概率给定的一对将发生碰撞，即

在此处输入图像描述

而且，到目前为止，还没有观察到 160 位的 SHA-1 冲突。假设 1 艾字节 (10^18) 的数据，在 8KB 块中，理论上发生冲突的机会是 10^-20 - 一个非常非常小的机会。

一个有用的快捷方式是通过短路消除已知彼此不同的文件。

例如，在大纲中：

  1. 读取所有感兴趣文件的前 X 块；
  2. 将前 X 个块具有相同哈希值的数据排序为可能相同的文件数据；
  3. 对于具有唯一的前 X 个块的每个文件，您可以假设整个文件与所有其他测试文件相比是唯一的——您不需要读取该文件的其余部分；
  4. 使用剩余的文件，阅读更多块，直到您证明签名相同或不同。

使用足够大小的 X 块，95% 以上的文件将在第一遍中被正确区分为唯一文件。这比盲目地读取整个文件并计算每个文件的完整哈希要快得多。

于 2013-05-28T19:18:47.467 回答
1

md5 往往适用于校验和......与 SHA-1 相同......虽然我认为 SHA-1 的碰撞概率略小，因为它使用更多位，但两者的冲突概率都非常小

如果你真的很担心，你可以使用两个校验和（一个 md5 和一个 sha1）匹配和文件不同的机会非常小（仍然不是 100% 不可能，但非常非常不可能）......（这似乎像糟糕的形式和迄今为止最慢的解决方案）

通常（阅读：在我遇到的每一个例子中）一个 MD5 或一个 SHA1 匹配足以假设唯一性

没有办法 100% 保证唯一性，没有逐字节比较

于 2013-05-28T19:06:11.980 回答
0

几天前我创建了一个小的重复文件删除脚本，它读取文件的内容并为其创建一个哈希，然后与下一个文件进行比较，即使名称不同，校验和也将是相同的。 .

import hashlib
import os

hash_table = {}
dups = []
path = "C:\\images"
for img in os.path.listdir(path):
    img_path = os.path.join(path, img)
    _file = open(img_path, "rb")
    content = _file.read()
    _file.close()
    md5 = hashlib.md5(content)
    _hash = md5.hexdigest()

    if _hash in hash_table.keys():
        dups.append(img)
    else:
        hash_table[_hash] = img
于 2013-05-28T18:59:06.070 回答