Расчет коллизий при CRC32

#алгоритм #хеширование #hashcode #crc

Возник вопрос - если существует значение функции CRC32, например - a50985e0 которое
было получено из массива байт - Hello (т.е. из строки ТОЛЬКО символов.) то какова вероятность
что точно такое же значение (a50985e0) появится при обработке функцией массива байт
полученных из 12345 т.е. из числа ?

Upd.

Исходя из ответов уважаемых @Alex и @Harry делаю вывод что коллизий не избежать в
принципе. И при постаточно большем диапазоне числового массива (от 0 до 1 000 000 000)
всегда найдется хеш, который совпадет с хешем полученным из строки символов. В связи
с этим переформулирую вопрос - существует ли закономерность (возможно ли ее вообще
обнаружить) в колличестве этих самых коллизий ? Например хеш X из числа Y (например
12345) проверен в обшем массиве хешей (0 - 2 000 000 000) и найдено 10 коллизий, и
так же для любого числа - врезультируещем массиве существует хотябы 10 коллизий. В
то время как хеш из символьной строки Hello даст всего 1 коллизию и так же любая другая
строка из символов даст не более 1 коллизии. Существует ли подобная законормерность ?
    

Ответы

Ответ 1

Вначале хочу заметить, если вы задаетесь таким вопросом, то скорее всего вы используйте
функцию чек-суммы не по прямому назначению. А значит, вы делаете что-то неправильно.

Насколько я понял, вам интересно, одинаков ли шанс получить коллизию, если на входе
строка из букв, или строка из цифр. Хочу заметить, что если у вас откуда-то приходят
случайные строки длиной 5 символов (для примера), то шанс что у вас появятся одинаковые
строки из цифр на много-много порядков выше, чем когда приходят строки из букв.

Что бы показать, что шансы получить коллизию одинаковы, я сгенерировал 100 млн чек-сумм
для строк длиной 20 (я взял 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 не является полноценной криптографической
хеш-фукнцией, и в ней нет лавинного эффекта. С хорошей хеш-функцией мы бы получили
одинаковый результат.


Ответ 2

Если хэш-функция "хорошая", то понять от чего она возникла (цифры, или буквы) нельзя.
Но! CRC32 дает повтор с вероятностью более 50% (сюрприз!) уже на 80 тысячах входных строк.


Ответ 3

Сообразил. В вашей постановке задачи - вероятность 1.
Всегда найдется такая последовательность не из цифр, которая даст вам то же значение
crc32.

Если постановка задачи - с какой вероятностью существует строка не из цифр, совпадающая
по crc32 с одним из данных значений.


Ответ 4

Мне кажется ответ на ваш вопрос в этом утверждении


  Для любого CRC32 хеша всегда существует единственная последовательность из четырех
байт, хеш которых даст заданный


(данное утверждение следует из того, что все 256 значений полинома имеют различный
старший байт)

Исходя из этого утверждения, коллизий у вас будет столько, сколько четверок байт
в сообщении максимальной длины