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