只使用校验和传输文件？

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。有时精确重建是可能的，但更多的时候它被用作图像和其他视觉或声音数据的有损压缩方案。