c# - 可变位长度非加密散列/校验和

Question

在 https://preshing.com/20110504/hash-collision-probabilities/ 的“小碰撞概率”部分您可以根据哈希值的大小看到权衡取舍。而是 32 位或 160 位哈希取决于您的用例和限制。

在给定整数 n 的情况下，如何构建 n 位的校验和/哈希？

想法是散列函数的调用者可以确定适合他们需要的权衡(只想存储整数而不关心冲突，使用 32 位等)。

碰撞概率应与相同位长的典型哈希函数相当(给定 n = 160，碰撞概率接近 sha-1。给定 n = 32，碰撞概率接近crc-32)

我的尝试:

if n < 160, sha-1(input) truncate first bits to bit-size n.
if n = 160, sha-1(input) 
if n > 160, sha-1(input) & sha-1(input) [Repeat concatenation (n % 160) times and then truncate bits to n)

我意识到对于 n > 160，我的碰撞概率并没有降低，因为它执行相同的散列。也不需要 sha-1，因为我的目的本质上不是加密的，更多的是校验和

Answer 1

对于 n*160 位的散列，您可以选择 n 个前缀(不同但长度相同，以避免冲突)并对附加到前缀的输入数据进行散列，得到 n 个不同的 160 位散列。如果您可以在执行此操作时创建冲突，您应该能够将其追溯到底层哈希函数中的冲突，因为不同的输入数据值永远不会为底层哈希函数产生相同的输入。

论文“通用哈希的计算复杂性”，例如在 https://core.ac.uk/download/pdf/82448366.pdf表明位向量的二进制卷积是一个(非安全的)通用哈希函数。要对 n 位的位向量进行散列并生成 m 位的位向量作为输出，您需要使用 n+m-1 位的位向量和 xor 与 m 位的位向量进行卷积。 (声明 2.2 P 5 标记为 125)