切断SHA-256熵？

Question

我有一个NoSQL键值数据库.我想在里面插入几百万条记录。

对于密钥生成，我使用前缀(类似于data-one-)，然后将存储的值的SHA-256散列连接起来。所以结束键看起来就像

data-one-0000fdb60e164cf0bf07cef647354d26ed17c9492ca4bbf4114878325871fa1d

问题是，这个键有点大，它会影响DB性能。我想切掉一些哈希，得到一个64位字符串(所以，8个字符)。所以我会把上面的钥匙砍成

data-one-0000fdb6

但是它会给剩下的密钥留下足够的熵吗？数据库会变大，我不想碰撞，很明显。另一个哈希是否更适合这种使用，还是修整SHA-256很好？

Answer 1

假设散列函数是好的，并且人们普遍认为SHA-256是这样的，那么k样本中没有碰撞到一个大小范围的n (例如，通过选择一个字符子集获得)的概率是由exp(-k^2/2n).所限制的。

对你来说，比如说k=2^{21}=2,097,152 (几百万)和n=2^{64}，意味着你没有碰撞的可能性大概是

exp(-2^{42}/2^{65})=exp(-2^{-21})\approx 1-1.2\times 10^{-7}.

如果你有8倍多的投入(超过1600万)，这将变成

exp(-2^{48}/2^{65})=exp(-2^{-17})\approx 1-7.6\times 10^{-6}

所以碰撞的概率将超过百万分之一。