我被要求寻找一个完美的散列/单向函数来散列 10^11 个数字。但是，由于我们将使用嵌入式设备，它没有存储相关存储桶的内存，所以我想知道如果没有它们，是否有可能拥有一个像样的（最小）完美哈希？
计划是使用设备对数字进行散列，我们使用彩虹表或使用散列作为偏移量的文件。
干杯
编辑：
我会尝试提供更多信息:)
1) 10^11 现在实际上是 10^10，这样更容易。这个数字是可能的组合。所以我们可以得到一个介于 0000000001 和 10000000000 (10^10) 之间的数字。
2) 我们的计划是将其作为单向功能的一部分，以确保号码安全，以便我们可以通过不安全的方式发送它。然后，我们将使用彩虹表查找另一端的原始数字。问题是设备的源通常有 512k-4Meg 的内存可供使用。
3）它必须是完美的——我们100%不能发生碰撞。
编辑2：
4）我们不能使用加密，因为我们被告知它在设备上实际上是不可能的，如果可以的话，密钥管理将是一场噩梦。
编辑3：
由于这是不明智的，现在它纯粹是学术问题（我保证）
好的，既然你已经澄清了你想要做什么，我重写了我的答案。
总结一下：使用真正的加密算法。
首先，让我回顾一下为什么您的散列系统是一个坏主意。
据我了解，您提出的系统是这样的：
您的嵌入式系统（我将其称为 C）正在发送某种值空间为 10^11 的数据。这些数据在传输到某种服务器（我将其称为 S）时需要保密。
您的建议是将值发送hash(salt + data)给 S。然后 S 将使用彩虹表来反转此哈希并恢复数据。salt是 C 和 S 都知道的共享值。
加密算法，当你归结为它是任何给你保密的算法。由于您的目标是机密性，因此任何满足您目标的算法都是加密算法，包括这个。
首先，有不可避免的碰撞机会。此外，冲突值的集合每天都不同。
其次，即使对于合法服务器 S，解密也是极其耗费 CPU 和内存的。更改盐的成本更高。
第三，虽然您声明的目标是避免密钥管理，但您的盐是关键！您根本没有解决密钥管理问题；任何有盐的人都可以像你一样破解信息。
第四，它只能从 C 到 S 使用。你的嵌入式系统 C 将没有足够的计算资源来反转哈希，只能发送数据。
大多数安全散列算法在计算上与合理的分组密码一样昂贵，如果不是更糟的话。例如，SHA-1 要求对每个 512 位块执行以下操作：
每 512 位消息有一个块，最后可能还有一个额外的块。这是每个块 1136 次二进制操作（不包括内存操作），或者每个字节大约 16 次操作。
为了比较，RC4 加密算法每个字节需要四个操作（三个加法，加上消息的异或），加上两次数组读取和两次数组写入。它还只需要 258 字节的工作内存，而 SHA-1 的峰值为 368 字节。
对于任何保密系统，您都必须拥有某种秘密。如果你没有秘密，那么其他任何人都可以实现相同的解码算法，你的数据就会暴露给全世界。
所以，你有两个选择来把秘密放在哪里。一种选择是将加密/解密算法保密。但是，如果算法的代码（或二进制文件）被泄露，你就输了——很难替换这样的算法。
因此，秘密通常很容易替换——这就是我们所说的密钥。
您提议的哈希算法的使用将需要一个盐 - 这是系统中唯一的秘密，因此是一个密钥。不管你喜不喜欢，你都必须小心管理这个密钥。并且如果泄漏比其他密钥更难替换 - 每次更改时您都必须花费大量 CPU 小时生成一个新的彩虹表！
使用真正的加密算法，并花一些时间实际考虑密钥管理。这些问题之前已经解决了。
首先，使用真正的加密算法。AES专为高性能和低 RAM 要求而设计。正如我之前提到的，您还可以使用像 RC4 这样的流密码 - 但是，使用 RC4 需要注意的是，您必须丢弃密码输出的前 4 KB 左右，否则您将很容易受到同样的攻击困扰 WEP 的攻击。
其次，考虑密钥管理。一种选择是简单地将密钥刻录到每个客户端中，如果客户端受到威胁，则物理上出去并更换它。如果您可以轻松地物理访问所有客户端，这是合理的。
否则，如果您不关心中间人攻击，您可以简单地使用Diffie-Hellman 密钥交换来协商 S 和 C 之间的共享密钥。如果您担心中间人攻击，那么您需要开始查看ECDSA或其他东西来验证从 DH 交换获得的密钥 - 但请注意，当您开始走这条路时，很容易出错。我建议在那时实施 TLS。它并没有超出嵌入式系统的能力——事实上，已经有许多 嵌入式 商业（和开源） 库 可用。如果您不实施 TLS，那么在实施之前至少让专业的密码学家检查您的算法。
显然，没有“完美”哈希之类的东西，除非您的哈希桶数至少与输入一样多；如果您不这样做，那么您的两个输入将不可避免地共享同一个哈希桶。
但是，您不太可能存储0 到 10^11 之间的所有数字。那么模式是什么？如果有一个模式，那么您的实际数据集可能会有一个完美的哈希函数。
不过，无论如何，找到一个“完美”的散列函数真的没那么重要。哈希表非常快。碰撞率非常低的函数——在散列整数时，这意味着几乎任何简单的函数，比如模数——都很好，你会得到 O(1) 的平均性能。