15

我有一个 128 位 ID，我想对其执行单向哈希，但我不想为输入消息获得相同的摘要。有谁知道 sha-1 或替代方案是否保证不会为小于其输出摘要大小的消息集产生冲突？这至少在理论上是可能的......

我还考虑过使用 RSA，并丢弃私钥给我一个单向加密，但我需要将结果存储在 32 char DB 字段中，并且我可用的加密方案不会产生任何足够小的东西。

欢迎任何关于产生原始值的确定性、不可逆和无碰撞变换的另一种方法的建议。

4

9 回答 9

7

对于给定的输入，密码散列给出了随机数的非常好的近似值。那么，在获得相同的 160 位之前，您在一个房间中需要多少随机散列？关于平方根（免责声明：我不是统计学家）。因此，您应该会看到大约 80 位的冲突。

我想实用性意味着你应该知道宇宙射线何时会成为比碰撞更大的问题。

于 2010-07-01T13:47:13.513 回答
6

如果要计算从 128 位到 128 位的秘密排列，一个简单的解决方案是使用 128 位分组密码（如 AES）和固定但秘密的密钥。当然，您必须能够永远保守密钥的秘密，否则您将一无所有。

于 2010-07-01T23:36:10.827 回答
4

您的 ID 是唯一的 128 位。

您的评论说明您不能按原样使用 ID。

你需要它是独一无二的，而不仅仅是可能是独一无二的。因此，您不能使用哈希。

你不能拥有两个世界——你不能拥有不可逆的 1:1 映射。这是不可能的。

加密 - 双射运算，因此不会发生冲突- 带有密钥的 ID 将使反转 ID 以确定其原始值非常困难。

AES 有一个很好的 128 位块长度，它将从您的 128 位输入生成 128 位输出，比旧算法（！）更快，并且可广泛用于大多数平台和语言。我建议您将 AES 用于您的目的。

于 2010-07-01T13:50:44.873 回答
2

对于足够大的位大小，我认为离散取幂是 1:1 函数，但反转在计算上是不可行的。我不确定需要多大的“大”。一个无法使用的缓慢（但在概念上可以理解）实现的代码：

unsigned long spin_once(unsigned long dat)
{
  如果 (dat & 1)
    返回（数据 >> 1）；
  返回 (dat >> 1) ^ SomeMagicNumber;
}

无符号长哈希（无符号长数据）
{
  无符号长 i,ret;

  如果 (dat == 0xFFFFFFFF)
    返回0；
  ret = 1;
  对于 (i=0; i < dat; i++)
    ret = spin_once(ret);
}

该程序将花费数十亿步来计算许多 dat 值的哈希值，但使用更复杂的代码可以在合理的时间内完成这项工作。当然，32 位散列在密码学上毫无价值，但该方法可以很容易地扩展到任何大小。

于 2010-07-01T15:28:17.570 回答
2

我不知道哪些哈希函数可以避免冲突，但是，如果您在这里找不到答案，一个好的起点可能是Wikipedia 上的Perfect Hash Function。从该页面：

集合 S 的完美散列函数是将 S 中的不同元素映射到不同整数的散列函数，没有冲突。

该页面上有许多指向您可能会发现有用的更多信息的链接。

话虽如此，你能说为什么你需要一个完美的 has 函数吗？可能还有其他方法可以在不需要该属性的情况下完成您想要的操作，这里的某人可能会提出建议。

于 2010-07-01T13:57:35.000 回答
2

有谁知道 sha-1 或替代方案是否保证不会产生碰撞

哈希函数被设计为不会产生冲突，但没有什么是“保证的”。相反，可以保证会有冲突，因为消息空间实际上是不确定的，而可能的哈希值是有限的。

然而，SHA-1 已被证明是抗碰撞的，这是您所希望的最好的。

于 2010-07-01T13:49:10.150 回答
1

散列“不太可能”产生任何重复，但不能保证。另一方面，任何对称加密方案都会为 128 位输入产生 128 位输出，并保证没有重复。

另一方面，如果您依赖于唯一的哈希，我的直觉是您做错了什么。例如，如果您使用散列来混淆密码，则必须小心不要使散列密码成为事实上的密码。

于 2010-07-02T00:38:31.303 回答
0

您不能（通常）从散列值中恢复原始数据的单向散列点不是吗？那么为什么有人会设计一个哈希函数来防止小输入的冲突呢？

相反，您似乎想要隐藏数据，这对于某些目的来说很好。如果使用公钥加密不实用，还不如编写自己的函数。

于 2010-07-01T14:15:17.390 回答
0

根据这篇文章http://www.debian-administration.org/users/dkg/weblog/48，

美国政府的联邦机构已被指示在 2010 年底前停止对 SHA-1 的所有依赖

但是，据我所知，还没有发现任何碰撞，也就是说，即使是非常努力的人也没有发现任何碰撞。因此，假设没有发生冲突似乎是合理的（如果您不处理高安全性数据）

于 2010-07-01T14:18:28.910 回答