为什么采用散列的 mod 的加盐散列会导致非常不均匀的分布？

Question

我有一百万个随机生成的唯一 ID。

如果我这样做：

result = int(hash(id + 'some_salt')) % 1000

然后这似乎导致 ID 均匀分布到 0 到 999 之间的某个整数，每个整数都有大约 1000 个 ID 映射到它。

如果我现在对此添加一些盐并再次进行散列：

x = int(hash(id)) % 1000
result = int(hash(str(x) + 'some_salt') % 1000)

那么最终的分布是完全不均匀的。对于每个 ID，结果当然在 [0,999] 范围内，但此范围内的一些整数映射到它们的 ID 为零，而另一些则有数千个。

为什么这会导致值的分布非常不均匀？

对于我的百万个 ID 和任何给定的 salt，我如何调整它以使整数均匀分布在 [0,999] 范围内？我想保留将可能非常大的输入 space 减少到更小的 space （例如大小 1000）的中间步骤。

我正在使用 SHA-256 哈希。

下面是一些 Python 代码，它演示了非常不均匀的结果：

import numpy as np
import hashlib

OUTPUT_RANGE_SIZE = 1000

unique_ids = xrange(1000000) # sequential here, but could be any kind of unique ids
frequencies = np.zeros(OUTPUT_RANGE_SIZE, dtype='int')

for idx in xrange(len(unique_ids)):
    id = unique_ids[idx]
    hash_mod = int(hashlib.sha256(str(id)).hexdigest(), 16) % 1000
    result = int(hashlib.sha256(str(hash_mod) + 'some_salt').hexdigest(), 16) % OUTPUT_RANGE_SIZE
    frequencies[result] = frequencies[result] + 1

print frequencies

Answer 1

通过在您的第一个哈希运算中应用模运算符，您已确保该阶段只有 1000 个唯一输出，无论您有多少个唯一数字作为输入。当您再次对它进行散列和取模时，其中一些散列可能会映射到相同的存储桶；因此，存储桶中的值数量将大约是散列到该存储桶 ID 的值数量的 1000 倍。您可以通过将频率数组中的值除以 1000 来看到这一点：

[1, 0, 2, 1, 0, 0, 0, ...]

如果您从第一步中删除模运算符，您在第二步中的输出值将按预期均匀分布。

强制附言：不要发明自己的密码系统。如果这是安全关键，请了解最佳实践并加以实施。

为什么采用散列的 mod 的加盐散列会导致非常不均匀的分布？

Why does taking the salted hash of the mod of a hash result in a very non-uniform distribution?

security

math

hash

cryptography

non-uniform-distribution