從MD5校驗和中提取數據

想象一下，您有一個MD5和，它是從一個數組N 64字節元素計算得出的。我想用新元素替換源數組中任意索引處的元素。然後，我不想通過重新運行MD5函數來重新計算MD5總和，而是想從結果中「減去」舊的元素，並將新的數據「添加」到它。從MD5校驗和中提取數據

是有點更清晰，這裏的一些僞斯卡拉：

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算法似乎支持這樣做（但我可能會漏掉一些明顯的東西）。

來源

2016-02-17 Travis Gockel

TTBOMK MD5計算嚴格按升序進行字節處理。如果是這樣，那麼可以在每個64字節單元之後記錄MD5計算的中間（狀態）值的順序：然後如果data [i]被更改，則可以從這一點重新開始MD5計算，即重新計算剩餘的n-i + 1）* 64字節。如果變化是隨機的，這將平均節省一半的計算量。 TTBOMK任何改變都會以不可預知的方式改變所有「下游」狀態，所以我懷疑可以採取任何措施來緩解接近開始的變化。 –

我相信，如果不花費更多的時間，然後重新運行md5，這是不可能的。你能告訴你爲什麼你認爲**實際的MD5算法似乎支持這樣做**？ –

問題不在於重新運行算法的計算時間 - 而是我必須執行昂貴的操作（IO）才能確定哪些數據甚至可以提供算法。 –

我想我更好地理解你現在想做什麼。我下面的解決方案並沒有涉及到MD5計算，但涉及IO和存儲大量MD5散列之間的權衡。它不是計算整個數據集的簡單MD5哈希，而是計算不同的MD5哈希，但它應該具有相同的重要屬性：對任何元素的任何更改（大幅度地）都會改變它。

首先，決定塊尺寸b使得
- 你能負擔得起從磁盤讀取的B值（或任何IO你在談論）每個元素的變化，
- 你可以承擔在內存中保留2n/b MD5哈希。
創建MD5散列的二叉樹。此樹中的每個葉子將是大小爲b的塊的MD5哈希。每個內部節點是其兩個孩子的MD5哈希。我們將使用這棵樹根的散列作爲「該」MD5散列。
當元素i發生變化時，讀取塊RoundDown（i/b）中的b元素，爲此計算新的MD5散列，然後向樹上傳播更改（這最多需要log2（n）步）。

來源

2016-02-17 20:54:48

雖然我喜歡你的答案，但這是我試圖擺脫的確切的事情（https://en.wikipedia.org/wiki/Merkle_tree）。 –

雖然我喜歡你的評論，但它真的可以幫助你清楚地表明你已經嘗試過/想到這個想法並且駁回了它（順便說一句：爲什麼？）。 –

公平點。簡單的答案是，從使用的角度來看，不必處理跟蹤樹的所有內部節點（最低級別的塊以兆億爲單位表示，因此即使有很大的分支因子，也沒有辦法將內部節點存儲在內存中）。我寧願在這裏不使用MD5（並且使用允許我想要的操作的總結系統），但是也有一些外部因素迫使我這樣做。我真的希望有一些神奇的數學可以用來解決整個世界:-) –

從MD5校驗和中提取數據

回答

相關問題