问题标签 [hash-collision]

情景

我正在构建一个 Web 应用程序，可以在其中动态生成报告（基于从 SQL 数据库检索到的信息）。这些报告将包含图表，这些图表也可以即时生成。因为这些图表包含敏感信息，所以使用 3rd 方图表 API（即：Google Charts）是不可能的。

问题

我正在使用 PHP 的 GD 扩展来生成这些图表。这很慢。缓存是要走的路，但问题是有大量可能的图表；尽管我相信大多数要求的图表都是以前生成的。

部分解决方案

图表是使用数据和其他信息（大小、图表类型等）生成的。因为这些可以唯一标识一个图表，所以我根据这些信息给每个图表一个唯一的哈希并保存它。现在我可以计算一个新请求的图表的哈希值，看看我是否已经渲染了它。

问题在于发生碰撞。为了解决这个问题，我正在考虑将哈希和数据的序列化形式保存在 SQL 表中。然后，如果我有缓存命中，我仍然会比较数据本身。

我过度设计了这个？（这是一个 160 位哈希 - SHA1）
有没有更好的方法来处理这个？

假设根据字符串“temp”的散列函数的数组索引是 155，并且位置 155 被预先占用，然后尝试位置 156。假设位置 156 可用，因此该条目保存在位置 156 而不是 155。稍后我找到另一个字符串“another_temp”，它映射到位置 156。再次将其保存在下一个可用位置 157 中。

问题是：稍后如果我想找出“another_temp”的位置，我怎么知道它是 157 而不是 156，即使哈希函数返回 156？

谢谢。

我有一个 Unicode/ UTF-16 编码路径。路径分隔符是 U+005C '\'。路径是以 null 结尾的根相对 Windows 文件系统路径，例如“\windows\system32\drivers\myDriver32.sys”

我想将此路径散列为64 位无符号整数。它不需要是“加密健全的”。哈希应该不区分大小写，但能够处理非 ascii 字母。显然，散列也应该很好地分散。

我有一些想法：

A) 使用 Windows 文件标识符作为“哈希”。在我的情况下，如果文件被移动，我确实希望哈希值发生变化，所以这不是一个选项。

B) 只需对整个字符串使用常规的 sting 散列：散列 += 素数 * 散列 + 代码点。

我确实觉得可以利用路径由“段”（文件夹名和最终文件名）组成的事实。

总结一下需求：

1) 64 位哈希
2) 文件系统路径的良好分布/很少冲突。
3) 高效
4) 不需要安全
5) 不区分大小写

当负载因子接近 1 以确保最小的内存浪费时，哪种 hashmap 冲突处理方案更好？

我个人认为答案是使用线性探测进行开放寻址，因为在发生冲突时它不需要任何额外的存储空间。它是否正确？

我试图了解哈希表中的键排序/插入检查是如何工作的。我了解到，当我将对象添加到哈希表时，它会在运行时检查那里没有输入相同的键。

在我的测试中，我有 2 个哈希表，其中填充了键： 1- 整数 2- 我重写了 GetHashCode 方法以始终返回 1 的对象。

我的问题是：虽然添加相同的 int 键时第一个测试会中断，但第二个测试不会！怎么来的？应该在插入时检查的哈希码都返回 1。

先感谢您！

我的代码：

}

我想要一个 DateWrapper - 代表一个日期（为 Hibernate 持久性而构建，但这是另一个故事） - 最多在同一日期同时存在。

我对冲突和散列的好键有点困惑。我正在为一个DateWrapper对象编写一个工厂，并且我想使用解析日期的毫秒数作为键，就像我看到其他人所做的那样。但是，如果发生碰撞会发生什么？. 毫秒总是彼此不同，但内部表可能小于可能存在的 Long。并且一旦哈希映射发生冲突，它就会使用等号，但是它如何区分两个不同的对象和我的 Long 呢？也许，这是删除（覆盖）一些我想插入的值的 put 方法......那么，这段代码是安全的，还是有问题？

我不明白如何仅通过进行 MD5 冲突来创建粗略的证书。即使您能够找到另一个哈希与原始字符串匹配的字符串，您将如何对其进行签名？您无权访问证书颁发机构的私钥？

我需要一个 4 个字符的哈希。目前我正在使用md5()哈希的前 4 个字符。我正在散列一个长度为 80 个字符或更少的字符串。这会导致碰撞吗？或者，假设我将散列少于 65,536 (16 ⁴ ) 个不同的元素，碰撞的可能性是多少？

我一直在消息摘要领域进行一些初步研究。特别是加密散列函数（例如 MD5 和 SHA-1）的冲突攻击，例如Postscript 示例和X.509 证书副本。

据我所知，在 postscript 攻击的情况下，生成了特定数据并将其嵌入到 postscript 文件的标题中（在渲染过程中被忽略），这导致 md5 的内部状态处于修改后的措辞文档的最终 MD 值与原始 postscript 文件相同。X.509 采用了类似的方法，将数据注入证书的注释/空白部分。

好的，这是我的问题，我似乎找不到任何人问这个问题：

1. 为什么不将仅消耗的数据的长度作为最终块添加到 MD 计算中？

2. 在 X.509 的情况下 - 为什么将空格和注释作为 MD 的一部分考虑在内？

诸如以下之一的简单过程是否不足以解决建议的碰撞攻击：

1. MD(M + |M|) = xyz
2. MD(M + |M| + |M| * magicseed_0 +...+ |M| * magicseed_n) = xyz

在哪里 ：

1. M : 是消息
2. |M| : 消息的大小
3. MD ：是消息摘要函数（例如：md5、sha、whirlpool 等）
4. xyz : 是消息 M 和 |M| 的实际消息摘要值的配对。<M,|M|>
5. magicseed_{i}：是一组随机值，​​由种子根据添加大小之前的内部状态生成。

该技术应该有效，因为迄今为止所有此类碰撞攻击都依赖于向原始消息添加更多数据。

简而言之，生成碰撞消息所涉及的难度级别如下：

1. 它不仅生成相同的MD
2. 但也是可理解的/可解析的/兼容的
3. 并且与原始消息的大小相同，

如果不是几乎不可能的话，也是非常困难的。有没有讨论过这种方法？任何指向论文等的链接都会很好。

进一步的问题：对于从 U 中随机选择的散列函数 H，公共长度的消息冲突的下限是多少，其中 U 是通用散列函数的集合？

是 1/N（其中 N 是 2^(|M|)）还是更大？如果它更大，则意味着有超过 1 条长度为 N 的消息将映射到给定 H 的相同 MD 值。

如果是这样的话，找到这些其他消息有多实用？蛮力将是O（2 ^ N），有没有一种时间复杂度低于蛮力的方法？

我正在建立一个用户可以上传内容的网站。与往常一样，我的目标是统治世界，所以我想避免两次存储同一个文件。例如，如果用户尝试两次上传同一个文件（通过重命名或只是忘记她过去所做的事情）。

我目前的方法是让跟踪每个上传文件的数据库存储有关每个文件的以下信息：

• 文件大小（以字节为单位）
• 文件内容的MD5总和
• SHA1 文件内容总和

然后是这三列的唯一索引。使用两个散列来最小化误报的风险。

所以，我的问题是：两个大小相同的不同（“真实世界”）文件具有相同 MD5和SHA1 哈希值的概率是多少？

或者：是否有类似（非）复杂性的更智能方法？

（我知道概率可能取决于文件大小）。

谢谢！