可升级的摘要/校验和算法

Question

我想创建一个包含许多文件的校验和的数据库，我担心校验和-拼接(两个不同的文件具有相同的校验和)。

问题1:两个不同文件具有相同MD5和的概率是多少？

作为一种变通方法，我考虑使用递增校验和。从一个小的校验和开始，在发生冲突的情况下，计算一个更大的校验和，它可以派生为较小的校验和，这样我就不必重新计算数据库中已经存在的所有文件的校验和……我仍然希望能够搜索较小大小的校验和。

问题2:哪种校验和/摘要算法可以做到这一点？我需要一个校验和算法，可以计算一定大小的值和“向后”兼容(较小的大小)。即。file1的2字节校验和为0x1234，4字节校验和为0x12345678，2字节校验和可从4字节校验和派生而来。

Answer 1

问题1:取决于你有多少个文件。对于每一对，它大约是2^128中的1。如果你有2^64个文件(我估计你可能没有)，那么它们之间至少发生一次冲突的概率大约是0.5。

这假设生成文件的人没有恶意。存在已知的MD5冲突，以及生成冲突的文件的已知方法。如果有人可以通过让你接触碰撞来赚钱，那么碰撞的概率接近1 :-)

问题2:通常你只需要使用一个更好的散列(可能是SHA-256)，然后你的“小”散列要么是大散列的前几个字节，要么是以某个大数为模的第一个散列，可能是一个质数。但这取决于你想要它做什么。

一个便宜而令人愉悦的选择是，“大”散列是两个或多个“小”散列连接在一起--例如，向前和向后对文件进行散列。当然，一旦小散列被破坏，就不知道这个中断是否会导致two+散列组合的中断。

Answer 2

在谷歌上搜索“生日悖论”，并满足于知道数字是无法管理的巨大。碰撞的概率增加得相当快，但对于像SHA或MD这样的东西，它不会对前两种情况的原始概率产生太大影响。

顺便说一句，如果这是出于加密目的，则不推荐使用MD5。如果你只是在做重复数据删除之类的事情，MD5应该没问题。