Страницы

Поиск по вопросам

пятница, 14 декабря 2018 г.

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

Возник вопрос - если существует значение функции 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 коллизии. Существует ли подобная законормерность ?


Ответ

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

Комментариев нет:

Отправить комментарий