主页 / 问题 / 881045
Accepted
Сергей
Asked:2020-09-14 01:09:46 +0000 UTC2020-09-14 01:09:46 +0000 UTC

计算 CRC32 的冲突

  • 772

问题出现了——例如，如果有一个函数值CRC32——a50985e0它是从一个字节数组中获得的—— （即从一个只有字符的字符串。）那么当函数出现时Hello，完全相同的值（）的概率是多少a50985e0处理从12345即获得的字节数组 从数？

更新。

根据受人尊敬的@Alex 和@Harry 的回答，我得出结论，原则上无法避免冲突。并且随着数值数组的范围越来越大（从 0 到 1,000,000,000），总会有一个与从字符串获得的哈希匹配的哈希。在这方面，我将重新提出问题 - 这些碰撞的数量是否存在模式（是否有可能检测到它）？例如，在总的哈希数组 (0 - 2,000,000,000) 中检查X了一个数字Y（例如 12345）的哈希，发现了 10 个冲突，对于任何数字，结果数组中至少有 10 个冲突。虽然来自字符串的哈希Hello只会产生 1 次冲突，并且就像任何其他字符串一样，不会产生超过 1 次冲突。这样的模式存在吗？

алгоритм

4 个回答

  1. Best Answer

    首先，我想指出，如果您问这个问题，那么您很可能将校验和函数用于其预期目的之外的用途。这意味着你做错了什么。

    据我了解，您想知道如果输入是一串字母或一串数字，发生碰撞的机会是否相同。我想指出，如果您从某个地方（例如）获得 5 个字符长的随机字符串，那么您将拥有相同数字字符串的机会比字母字符串出现时高出许多数量级。

    为了证明发生碰撞的机会是相同的，我为长度为 20 的字符串生成了 1 亿个校验和（我取了 20，以便不会创建相同的数字字符串），并计算数字字符串内部的碰撞，字母串内部，数字串和字母串相互碰撞。这是我的 C# 代码：

    private static uint crc32(byte[] data)
{
    uint crc = 0xffffffff;
    uint poly = 0xedb88320;
    for (int i = 0; i < data.Length; i++)
    {
        uint c = (crc ^ data[i]) & 0xff;
        for (int k = 0; k < 8; k++)
            c = (c & 1) != 0 ? poly ^ (c >> 1) : c >> 1;
        crc = c ^ (crc >> 8);
    }
    return crc ^ 0xffffffff;
}

static void Main(string[] args)
{
    byte[][] digits = new byte[0x10000][];
    for (int i = 0; i < 0x10000; i++)
        digits[i] = new byte[0x10000];

    byte[][] chars = new byte[0x10000][];
    for (int i = 0; i < 0x10000; i++)
        chars[i] = new byte[0x10000];

    var rnd = new Random(123);
    int iterations = 100000000;

    byte[] buffer = Encoding.ASCII.GetBytes("12345678901234567890");
    for (int i = 0; i < iterations; i++)
    {
        int index = rnd.Next(20);
        buffer[index]++;
        if (buffer[index] > '9')
            buffer[index] = (byte)'0';

        uint crc = crc32(buffer);
        digits[crc >> 16][crc & 0xFFFF]++;
    }

    buffer = Encoding.ASCII.GetBytes("abcdefwxyzabcdefwxyz");
    for (int i = 0; i < iterations; i++)
    {
        int index = rnd.Next(20);
        buffer[index]++;
        if (buffer[index] > 'z')
            buffer[index] = (byte)'a';

        uint crc = crc32(buffer);
        chars[crc >> 16][crc & 0xFFFF]++;
    }

    int digitsCollisions = 0;
    for (int i = 0; i < 0x10000; i++)
        for (int j = 0; j < 0x10000; j++)
            if (digits[i][j] > 1)
                digitsCollisions += digits[i][j];

    int charsCollisions = 0;
    for (int i = 0; i < 0x10000; i++)
        for (int j = 0; j < 0x10000; j++)
            if (chars[i][j] > 1)
                charsCollisions += chars[i][j];

    int digitsCharsCollisions = 0;
    for (int i = 0; i < 0x10000; i++)
        for (int j = 0; j < 0x10000; j++)
            if (chars[i][j] > 0 && digits[i][j] > 0)
                digitsCharsCollisions += chars[i][j] * digits[i][j];

    Console.WriteLine(digitsCollisions);
    Console.WriteLine(charsCollisions);
    Console.WriteLine(digitsCharsCollisions);
}

    结果：

    2298490
2304243
2330855

    如您所见，发生碰撞的概率是相同的。

    在另一个测试中，我将输入数据长度设为 10 个字节，而不是随机数，我只是简单地采用数字的字符串表示形式i。结果不一样：

    4431872
2301156
2324554

    如您所见，尽管校验和是根据唯一的输入数据计算的，但数字上的碰撞次数增加了 2 倍。这是因为 10 字节字母的随机字符串比数字字符串具有更多的熵。CRC-32 不是一个完整的加密散列函数，没有雪崩效应。使用一个好的散列函数，我们会得到相同的结果。

    • 8

  2. 如果散列函数是“好”的，那么就不可能从它产生的内容（数字或字母）中理解它。但！CRC32 给出的重复概率超过 50%（惊喜！）已经在 80,000 个输入行上。

    • 2

  3. 实现。在你的问题陈述中，概率是 1。
    总会有一个非数字序列会给你相同的 crc32 值。

    如果问题陈述是在 crc32 中与给定值之一匹配的非数字字符串的概率是多少。

    • 2

  4. 我认为您的问题的答案在此声明中

    对于任何 CRC32 散列，总是存在一个由四个字节组成的序列，其散列将给出给定的

    （此说法源于多项式的所有 256 个值都有不同的高字节）

    根据此声明，在最大长度的消息中，您将有多达四个字节的冲突

    • 0

相关问题