只使用校驗和傳輸文件？

Question

是否可以僅使用校驗和系統傳輸大文件，然後通過計算重建原始文件？

假設您傳輸文件的MD5校驗和和文件的大小。通過製作一個「虛擬文件」並計算它的校驗和，嘗試每一個位組合，你最終應該「到達」原始文件。但在途中，您也會遇到許多「校驗和」匹配的「衝突」。

因此，我們將原始文件的第一個字節更改爲某個指定的值，再次計算校驗和，並將其發送出去。如果我們在虛擬文件中進行相同的替換，我們可以測試每個「碰撞」以查看它是否仍然匹配。這應該縮小一點，我們可以多次這樣做。

當然，這樣做的計算能力將是巨大的。但是在理論上是可能的，你需要多少校驗和來轉移某些東西（比如1mb）？或者可能需要傳輸校驗和的數據量幾乎與文件一樣大，從而使其毫無意義？

Answer 1

您需要傳輸的數據量肯定與文件大小相同。請考慮：如果您可以與n-1字節的數據通信n字節文件，這意味着您已獲得256^(n-1)可能的數據模式，您可能已發送，但正在從256^n大小的空間中進行選擇。這意味着每256個文件中就有一個不能用這種方法表達 - 這通常被稱爲pidegonhole principle。

現在，即使這不是問題，也沒有保證在任何給定數量的校驗和之後不會發生碰撞。校驗和算法旨在避免衝突，但對於大多數校驗和/散列算法而言，沒有強有力的證據表明，在X哈希之後，可以保證在N字節空間內不會發生衝突。

最後，散列算法至少要設計成很難反轉，所以即使有可能，也要花費大量的CPU功率。

也就是說，對於類似的方法，您可能有興趣閱讀有關Forward Error Correction codes - 它們根本不是哈希算法，但我認爲您可能會發現它們很有趣。

Answer 2

你在這裏有什麼是信息問題。校驗和對於一組特定的數據來說並不一定是唯一的，事實上，這樣做有效地需要有許多位信息作爲源。它可以表示的是，收到的數據並不是校驗和生成的確切數據，但在大多數情況下無法證明。

Answer 3

簡答：沒有任何意義的形式。

龍答：

讓我們假設一個任意文件file.bin有1000字節大小。有2^(8*1000)不同的組合可能是它的實際內容。通過發送例如一個1000位校驗和， 你仍然有大約2^(7*1000)衝突的替代品。

通過發送一個額外的位，您可能可以將這些減少一半......並且仍然有2^6999衝突。在您消除拼合時，您將發送至少8000位，即等於或大於文件大小的量。

這是理論上可行的（注意：我沒有說「可行」，更let論「實用」）的唯一方法是如果文件沒有真正包含隨機數據，並且可以使用該知識來修剪替代。在這種情況下，您最好使用壓縮，ayway。內容感知壓縮算法（例如，用於音頻的FLAC）使用關於輸入數據屬性的先驗知識來改善壓縮比。

Answer 4

總之「不」。假設一個假設的例子，考慮一個24像素的6像素照片 - 這6個像素上的每個顏色通道有2 ^（24 * 6）（2^144）個可能的亮度組合，所以您可以如果你要評估每一種可能性，你將得到一個MD5碰撞保證（因爲MD5是一個128位的數字）。

Answer 5

我想你在想什麼實際上是一個有趣的話題，但是你沒有選擇正確的方法。如果我可以嘗試重寫您的問題，您是問有沒有辦法將某個函數應用於某些數據，傳輸該函數的結果，然後從terser函數結果中重建原始數據。對於單個MD5校驗和，答案是否定的，但是如果您有其他功能，只要您願意發送多個功能結果，就可以。一般來說，這個研究領域被稱爲compressed sensing。有時精確重建是可能的，但更多的時候它被用作圖像和其他視覺或聲音數據的有損壓縮方案。