问题标签 [hash-collision]

这在现实世界中可能从未发生过，也可能永远不会发生，但让我们考虑一下：假设您有一个 git 存储库，进行提交，然后变得非常非常不幸：其中一个 blob 最终具有相同的 SHA-1作为另一个已经在您的存储库中的。问题是，Git 将如何处理这个问题？只是失败？找到一种方法来链接这两个 blob，并根据上下文检查需要哪一个？

与其说是一个实际的问题，不如说是一个脑筋急转弯，但我发现这个问题很有趣。

对于由给定（对称或非对称）加密算法在明文/密钥对上工作生成的给定密文，找到产生相同密文的不同明文/密钥对有多难？

两个明文/密钥对导致相同的密文有多难？

导致这个问题的原因是另一个可能与上述问题无关的问题：

如果你有一个密文和一个密钥，并且想使用一些解密程序来解密它，这个程序通常会告诉你密钥是否正确。但是它是怎么知道的呢？它是否在结果明文中寻找某种模式，表明解密成功？在某些不同的明文中是否存在另一个关键结果，它包含模式并且也被例程报告为“有效”？

受答案和评论启发的后续问题：

如果允许的明文/密钥对在以下（或两种）方式中受到限制：

1）明文以密钥的KCV（Key check value）开头。

2) 明文以某个明文/密钥组合的哈希值开头

这会使碰撞发现不可行吗？是否清楚，这样的明文/密钥存在=

我有一个 md5 函数，我已经确认它对文件和字符串都适用。但是当我在非常大的文件的可变大小块上使用它时，它会生成相同的 md5 值，但块的大小不同。

我想知道两个长度不同但内容相同的块是否有可能导致相似的 md5 指纹。

大多数应用程序，尤其是数据库，可以按小整数或浮点数进行排序和过滤，速度比字符串比较快得多。

因此，我想知道是否有一个散列函数可以用来返回一个 32 位或 64 位的短字符串（大约 5 - 40 个字符），以便我可以通过整数而不是字符串进行比较。

我首先想到了 crc32，但它似乎太小了，可能会导致少于 50,000 个哈希值的冲突（我需要做超过一百万个）。

我最感兴趣的是使用 Python、PHP、V8 Javascript、PostgreSQL 和 MySQL。

我必须找到 2^25 个随机字符串的 SHA256 哈希。然后寻找冲突（对最后一个使用生日悖论，例如，仅 50 位散列）。

我将字符串：哈希对存储在 dict 变量中。然后使用值（不是键）对变量进行排序，然后使用 O(n) 循环查找冲突。

问题是因为有 2^25 个字符串和它们的 2^25 个哈希，所以 dict 变量中有 2^50 个值。这是非常耗费资源的。那么，我该如何在有限的 RAM（比如 1GB 左右）的情况下做到这一点？

我已经尝试过：
1. 使用 6GB 交换空间运行它。该程序运行了一夜，仍然没有完成。这基本上比 O(n_square) 搜索还要慢！哈希值是使用大约 3.2 GB 的 RAM 使用量计算的。但在那之后，当涉及到 sort 命令时，使用的 RAM 又开始猛增！我虽然 python 排序使用 In-Place-Quicksort :(
2。我只存储了哈希值并发现了一个冲突。但由于没有存储它而找不到相应的字符串。

我不应该使用数据库等。最多是一个文本文件，但这无济于事。另外，我对 Python 还是很陌生，但不要让这限制了你的答案水平。

PS：这是一个任务。一些人声称在 300MB RAM 的情况下不到一分钟就发现了冲突。不知道这是不是真的。我已经解决了这个问题，但答案是无法得到的！在工作中，所以现在无法访问代码。将很快添加。

代码：

如果我有一个系统，其中哈希是从 100 万种可能性的总排列中生成的。如果有 10% 的碰撞几率，我应该担心生成算法运行 5 次吗？

• 我有一个类似于 jsfiddle 的系统，用户可以在我的服务器上“保存”一个文件。现在我使用'23456789abcdefghijkmnopqrstuvwxyz'的是 33 个字符，文件长度为 4 个字符，总共有多种33^4 = 1,185,921可能性。
• “文件名”是随机生成的，如果发生冲突，它会重新运行以获取另一个文件名。使用生日悖论计算器我可以看到，在我有 500 个条目后，我有 10% 的机会发生碰撞。
• 我连续发生 5 次以上碰撞的可能性有多大？4个呢？
• 有没有办法解决这个问题？我应该担心吗？5000 个条目后会发生什么？
• 有没有一个程序可以通过任意输入来解决这个问题？

我需要一种方法散列可变长度（10-20 个字符）的字母数字 + 特殊字符（ascii）字符串。输出应为可变长度，但最长为 25 个字符，字母数字且不区分大小写。

另外我不想产生碰撞，所以我需要一些无碰撞或至少没有被证明（还没有？）的东西来产生碰撞。

如果我在使用 git 时发生哈希冲突，实际上会发生什么？

例如，我设法提交了两个具有相同 sha1 校验和的文件，git 会注意到它还是会损坏其中一个文件？

可以改进 git 以适应这种情况，还是我必须更改为新的哈希算法？

（请不要通过讨论不太可能来转移这个问题 - 谢谢）

我正在复习我的数据结构期末考试，我在去年的期末考试中遇到了一个问题。在过去三个小时的工作中，我仍然无法找到解决它的方法，除非通过反复试验。这是问题：

“假设你的哈希表的大小是 31，常数 g 也是 31，并且你使用下面的哈希码

并且您使用单独的链接来解决冲突。列出五个不同的名称，它们将散列到表中的同一位置。”

我认为必须有某种技巧，可能涉及模运算符来解决这个问题，考虑到哈希表的大小为 31，与常数 g 相同。对不起，如果我听起来像这样，但我不是要代码或任何东西，只是对这个问题的一些想法/提示。非常感谢任何评论。谢谢

我正在使用 SHA-256 算法来检测数据库中的相同图像。因为我们使用了很多不同的图像格式，所以我不想直接在文件上计算哈希值。相反，我想提取像素数据并计算其哈希值。

不幸的是，我遇到了很多随机冲突：68 个不具有相同字节的图像使用相同的像素提取（如下）从 6000 个图像中散列到相同的值。我觉得这是一个疯狂的碰撞次数。此外，我将我从像素数据计算的字节转储到文件中，然后尝试：

回声-n [字节转储文件] | sha256sum

这导致转储图像的哈希值不同，这让我相信我在使用 MessageDigest 时做错了什么。

这是我获取像素数据的方法：

然后我使用 MessageDigest 类计算哈希：

其中 encodeHex 只是：