5

我们有一个非常旧的、不受支持的程序，它可以跨 SMB 共享复制文件。它有一个校验和算法来确定文件内容是否在复制之前发生了变化。该算法似乎很容易被愚弄——我们刚刚发现了一个示例，其中两个文件相同，除了单个“1”变为“2”外，返回相同的校验和。这是算法：

unsigned long GetFileCheckSum(CString PathFilename)
{
        FILE* File;
        unsigned long CheckSum = 0;
        unsigned long Data = 0;
        unsigned long Count = 0;

        if ((File = fopen(PathFilename, "rb")) != NULL)
        {
                while (fread(&Data, 1, sizeof(unsigned long), File) != FALSE)
                {
                        CheckSum ^= Data + ++Count;
                        Data = 0;
                }
                fclose(File);
        }
        return CheckSum;
}

我不是一个程序员（我是系统管理员），但我知道基于 XOR 的校验和会非常粗糙。对于两个大小相同但内容不同的文件，该算法返回相同校验和的可能性有多大？（我不期待一个确切的答案，“远程”或“很可能”很好。）

如果没有巨大的性能影响，如何改进它？

最后，是怎么回事fread()？我快速浏览了文档，但无法弄清楚。是否Data被依次设置到文件的每个字节？编辑：好的，所以它将文件读入unsigned long（假设这里是 32 位操作系统）块。每个块包含什么？如果文件的内容是，那么第一遍abcd的值是多少？Data是（在 Perl 中）：

(ord('a') << 24) & (ord('b') << 16) & (ord('c') << 8) & ord('d')
4

8 回答 8

7

MD5常用于验证传输文件的完整性。源代码在 c++ 中很容易获得。它被广泛认为是一种快速准确的算法。

另请参阅稳健且快速的校验和算法？

于 2009-06-25T17:43:31.677 回答
5

我建议你看一下Fletcher 的校验和，特别是 fletcher-32，它应该相当快，并检测当前 XOR 链无法检测到的各种情况。

于 2009-06-25T17:58:49.830 回答
3

您可以使用如下公式轻松改进算法：

Checksum = (Checksum * a + Data * b) + c;

如果 a、b 和 c 是大素数，这应该会返回好的结果。在此之后，旋转（而不是移动！）校验和的位将进一步改善它。

使用素数，这是一种类似于用于线性同余生成器的算法——它保证了长周期和良好的分布。

于 2009-06-25T17:36:56.160 回答
0

我似乎您的算法没有努力处理大小不是 4 个字节的精确倍数的文件。fread 的返回值不是布尔值，而是实际读取的字节数，在 EOF 或发生错误的情况下与 4 不同。你没有被检查，只是假设如果它没有返回 0，那么你在“数据”中有 4 个有效字节来计算你的哈希值。

如果您真的想使用哈希，我会推荐几件事。首先，使用像 MD5 这样的简单加密哈希，而不是 CRC32。CRC32 在检查数据有效性方面是不错的，但对于跨越文件系统并确保没有冲突，它不是一个很好的工具，因为其他地方的评论中提到了生日悖论。其次，不要自己写函数。查找现有的实现。最后，考虑简单地使用 rsync 来复制文件，而不是滚动您自己的解决方案。

于 2009-06-25T17:39:23.350 回答
0

该fread位一次读取一个文件块。每个块都是 long 的大小（在 c 中这不是一个明确定义的大小，但您可以假设 32 或 64 位）。根据缓冲的方式，这可能还不错。OTOH，将更大的块读入数组并循环它可能会快得多。

于 2009-06-25T17:41:28.573 回答
0

即使是“昂贵的”加密哈希函数通常也需要多次迭代才能花费大量时间。尽管不再推荐用于加密目的，用户会故意尝试创建冲突，但 SHA1 和 MD5 等函数已广泛可用并适用于此目的。

如果需要较小的散列值，CRC 是可以的，但不是很好。n位 CRC将无法检测到长于n位的一小部分更改。例如，假设文件中只有一个美元金额发生了变化，从 12,345 美元变为 34,567 美元。32 位 CRC 可能会错过该更改。

截断较长加密散列的结果将比 CRC 更可靠地检测更改。

于 2009-06-25T17:44:27.433 回答
0 
{
   CheckSum ^= Data + ++Count;
   Data = 0;
}

我不认为“++Count”做很多工作。该代码等效于

{
  CheckSum ^= Data;
}

对字节序列进行异或是不够的。尤其是文本文件。

我建议使用散列函数。

于 2009-06-25T17:50:44.803 回答
0

SHA-1 和（最近的 SHA-2）提供了出色的散列函数，我相信由于更好的散列特性，它们正在慢慢取代 MD5。所有这些（md2、sha 等）都有高效的实现，并返回几个字符长的缓冲区的哈希值（尽管始终是固定长度）。被证明比将散列简化为整数更可靠。如果我有我的 druthers，我会使用 SHA-2。按照此链接获取实现 SHA 校验和的库。

如果您不想在这些库中编译，linux（可能还有 cygwin）具有以下可执行文件：md5sum、sha1sum、sha224sum、sha256sum、sha384sum、sha512sum；您可以向其中提供您的文件，他们会将校验和打印为十六进制字符串。您可以使用 popen 执行这些程序 - 使用如下所示：

const int maxBuf=1024;
char buf[maxBuf];
FILE* f = popen( "sha224sum myfile", "w" );
int bytesRead = f.read( buf, maxBuf );
fclose( f );

显然，这会运行得慢很多，但对于第一次通过来说是有用的。如果速度是一个问题，考虑到像这样的文件散列操作和 I/O 绑定（内存和磁盘访问将成为瓶颈），我希望所有这些算法的运行速度与产生无符号整数的算法一样快。Perl 和 Python 还附带了 MD5 SHA1 和 SHA2 的实现，并且可能会像在 C/C++ 中一样快地运行。

于 2009-06-25T22:00:20.347 回答