md5 - 哈希（md5，sha1）的任何子字符串是否比另一个更“随机”？

Question

这是 3 个示例 md5 哈希

$ md5 -s "1" && md5 -s "2" && md5 -s "3"
MD5 ("1") = c4ca4238a0b923820dcc509a6f75849b
MD5 ("2") = c81e728d9d4c2f636f067f89cc14862c
MD5 ("3") = eccbc87e4b5ce2fe28308fd9f2a7baf3

假设我想从任何哈希中提取 8 个字符。哈希的开头部分是否比结尾更“随机”？中间？还是所有子字符串都同样“随机”？

Answer 1

我自己很好奇，所以我继续编写了一个程序来测试它。您需要Crypto++来编译代码。

免责声明：当谈到密码学，甚至是一般的数学时，我知道的足以让我自首。因此，请对以下结果持保留态度，并记住我对我正在使用的工具只有粗略的了解。

我只采样了三个子字符串：前 8 个字节、中间 8 个字节和最后 8 个字节。长话短说，它们同样随机。

但是，当使用较小的样本空间时，最后 8 位似乎更加随机。采样空间越大，三个子串越接近完全随机性。

---

1000 次迭代：

First:  0.995914
Middle: 0.996546
Last:   0.998104

5000 次迭代：

First:  0.998387
Middle: 0.998624
Last:   0.999501

10000 次迭代：

First:  0.999614
Middle: 0.999457
Last:   1

30000 次迭代：

First:  1
Middle: 1
Last:   1

---

“随机性”由 Crypto++ 的MaurerRandomnessTest类测量。作为参考，从上述代码编译的可执行文件的随机性值为 ，0.632411从 Project Gutenburg 下载的莎士比亚的麦克白副本的随机性值为0.566991.

Answer 2

Nitpick：在这里使用“随机”这个词是错误的，因为散列函数是确定性的。

至于回答你的意思:)，哈希函数的一个理想属性是实现雪崩效应：基本上，让每一位输入都会导致输出发生巨大变化。因此，对于设计良好的散列，每个子字符串都应该受到同样频繁的影响（“尽可能随机”）。

Answer 3

一个好的散列的所有子串（尽管 md5 在密码学上是不安全的，但它相当好）都是同样随机的，所以是的，从字符串中取任何你喜欢的位，它们应该是均匀分布的。

Answer 4

可以使用对伪随机数生成器进行的统计测试来测量散列函数输出的随机性。根据应用密码学手册§5.4.4（免费提供示例章节），有五个基本测试：

1. 频率测试（单比特测试）
2. 串行测试（两位测试）
3. 扑克测试
4. 运行测试
5. 自相关检验

然后，当然，还有 kurige 已经提到的 Maurer 的通用统计检验。