c# - 可变位长非加密哈希/校验和

问题描述

在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，因为我的目的本质上不是加密的，更多的是校验和

标签： c#algorithmhashchecksum

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

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

c# - 可变位长非加密哈希/校验和

问题描述

解决方案

推荐阅读