algorithm - 从 MD5 校验和中备份数据

Question

假设您有一个 MD5 和，它是根据 N 个 64 字节元素的数组计算得出的。我想用新元素替换源数组中任意索引处的元素。然后，我不想通过 MD5 函数重新运行它来重新计算 MD5 和，而是想从结果中“减去”旧元素并将新数据“添加”到它。

为了更清楚一点，这里有一些伪 Scala:

class Block {
  var summary: MD5Result

  // The key reason behind this question is that the elements might not be
  // loaded. With a large array, it can get expensive to load everything just to
  // update a single thing.
  var data: Array[Option[Element]]

  def replaceElement(block: Block, index: Integer, newElement: Element) = {
    // we can know the element that we're replacing
    val oldElement = block.data(index) match {
        case Some(x) => x
        case None    => loadData(index) // <- this is expensive
      }

    // update the MD5 using this magic function
    summary = replaceMD5(summary, index, oldElement, newElement)
  }
}

replaceMD5 是否可以实现？虽然所有迹象都表明“这正在破坏(弱)加密哈希”，但实际的 MD5 算法似乎支持这样做(但我可能遗漏了一些明显的东西)。

Answer 1

我想我现在更清楚你想做什么。我下面的解决方案没有假设任何关于 MD5 计算的内容，但涉及 IO 和存储大量 MD5 哈希值之间的权衡。它不是计算整个数据集的简单 MD5 哈希值，而是计算一个不同的 MD5 哈希值，但该哈希值应该具有相同的重要属性:对任何元素的任何更改(彻底)都会改变它。

1. 一开始，决定 block 大小 b 使得
   • 您可以负担得起从磁盘读取 b 值(或您正在谈论的任何 IO)每次更改元素，并且
   • 您有能力在内存中保留 2n/b 个 MD5 哈希值。
2. 创建一个 MD5 哈希的二叉树。这棵树中的每个叶子都是一个大小为 b 的 block 的 MD5 散列。每个内部节点都是其两个子节点的 MD5 散列。我们将使用这棵树的根的哈希值作为“the”MD5 哈希值。
3. 当元素 i 改变时，读入 block RoundDown(i/b) 中的 b 元素，为此计算新的 MD5 散列，然后将变化传播到树上(这最多需要 log2(n) 步) .