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

Question

我想创建一个包含大量文件的校验和的数据库，并且我担心校验和 - collissions（具有相同校验和的两个不同文件）。

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

作为一种解决方法，我想过使用日益增加的校验和。从一个小的校验和开始，如果发生冲突，计算一个更大的校验和，这个校验和可以派生到较小的校验和，所以我不必重新计算数据库中已有的所有文件的校验和......我仍然想要能够搜索更小尺寸的校验和。

问题2：哪种校验/摘要算法可以做到这一点？我需要一个校验和算法，它可以计算一定大小的值和“向后”兼容（较小的大小）。 IE浏览器。 file1有一个2字节的校验和0x1234和一个4字节的校验和0x12345678，2字节的校验和可以从4字节校验和派生。

Answer 1

问题1：取决于你有多少文件。对于每一对，大约是1^2^128。如果你有2^64个文件（我认为你可能不这样做），它们之间至少有一次碰撞的概率大约是0.5。

这个假设不会产生恶意。已知的MD5冲突以及生成冲突文件的已知方式。如果某人可以通过将您暴露在碰撞中而以您的费用来赚钱，那么碰撞的概率接近于1 :-)

问题2：通常您只需使用更好的哈希值（可能是SHA- 256），然后你的“小”散列或者是大数的前几个字节，或者是第一个以大数字为模数的字节，也许是一个总数。但这取决于你想要什么。

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

Answer 2

谷歌的“生日悖论”，并知道这些数字是难以控制的巨大的内容。碰撞概率增加得相当快，但对于像SHA或MD这样的东西，前两者的原始概率并没有太大的差距。

顺便说一句，如果这是出于加密目的，MD5已被弃用。如果你只是去除重复或其他东西，MD5应该没问题。