子字符串 md5 碰撞

I need a 4-character hash. At the moment I am taking the first 4 characters of a md5() hash. I am hashing a string which is 80 characters long or less. Will this lead to collision? or, what is the chance of collision, assuming I'll hash less than 65,536 (16⁴) different elements?

嗯，每个角色md5是一个十六进制位。这意味着它可以具有 16 个可能值之一。因此，如果您只使用前 4 个“十六进制位”，则意味着您可以16 * 16 * 16 * 16 or 16^4或 65536 或2^16的可能性。

因此，这意味着结果的总可用“空间”只有 16 位宽。现在，根据生日攻击/问题，有以下发生碰撞的机会：

• 50%机会->300 entries
• 1%机会->36 entries
• 0.0000001%机会->2条目。

所以发生碰撞的可能性相当大。

现在，您说您需要 4 个字符的哈希值。根据具体要求，您可以执行以下操作：

• 4 个十六进制位用于16^4(65,536) 个可能值
• 4 个字母位26^4(456,976) 可能的值
• 4 个字母数字位36^4(1,679,616) 可能值
• 4 个 ascii 可打印位大约93^4(74,805,201) 个可能值（假设 ASCII 33 -> 126）
• 4 个完整字节256^4(4,294,967,296) 个可能值。

现在，您选择哪个将取决于实际用例。哈希值需要传输到浏览器吗？你如何存储它等等。

我将给出每个示例（在 PHP 中，但应该很容易翻译/看看发生了什么）：

4 个十六进制位:

$hash = substr(md5($data), 0, 4);

4 个字母位:

$hash = substr(base_convert(md5($data), 16, 26)0, 4);
$hash = str_replace(range(0, 9), range('S', 'Z'), $hash);

4 个字母数字位:

$hash = substr(base_convert(md5($data), 16, 36), 0, 4);

4 个可打印的 Ascii 位:

$hash = hash('md5', $data, true); // We want the raw bytes
$out = '';
for ($i = 0; $i < 4; $i++) {
    $out .= chr((ord($hash[$i]) % 93) + 33);
}

4 个完整字节:

$hash = substr(hash('md5', $data, true), 0, 4); // We want the raw bytes