Насколько хороша идея использовать только часть sha1 как bigint?

Question

[Сергей Пуговкин]

Данные будут добавляется примерно 10 тыс в час.
Какие шансы получить коллизию, если использовать только первые 16 символов (как unsigned bigint) от sha1 строки в 100-500 символов utf-8?
В идеале если 50 лет коллизия не грозит - отлично.

Comments

[Александр Аксентьев]

int

sha1

sha1 - a0f1490a20d0211c997b44bc357e1972deab8ae3

ничего не смущает в этой схеме?

[Сергей Пуговкин]

Александр Аксентьев, 16 символов hex-строки sha1 == unsigned bigint,
например, a0f1490a20d0211c == 11597130823304749340

[Сергей Пуговкин]

Такое представление в БД занимает меньше места, и индексы быстрее.
Но вот насколько это снижает надёжность в плане коллизий - не понятно.
Понятное дело, что sha1 - хорошо, а sha256 - ещё лучше, но, вполне может быть, что такая надёжность избыточна.

Answer 1

[Сергей Пуговкин]

Вобщем, тесты показали: даже 14 символов sha1 достаточно для уникальности 1 млрд таких вот хэшей (~12 лет при моей нагрузке).

<?php

declare(strict_types=1);
declare(ticks=1);

error_reporting(E_ALL);
ini_set('display_errors', '1');

function gmp_base_convert($number, int $frombase, int $tobase): string
{
    return gmp_strval(gmp_init($number, $frombase), $tobase);
}

$c = 0;

$t = [];

for ($i = 0; $i < 1000000000; $i++) {

    $s = uniqid((string)$i, true) . microtime() . $i;

    $n = rand(0, 500);

    for ($j = 0; $j < $n; $j++) {
        $s .= chr(rand(0, 255));
    }

    $v = (string)sha1($s);
    $k = (int)gmp_base_convert(substr($v, 0, 14), 16, 10);

    if (isset($t[$k])) {
        $c++;
        echo "{$i}: {$c}\n";
    } else {
        $t[$k] = true;
    }

}

echo "{$i}: {$c}\n";

exit(0);

А уж 16 - и подавно хватит за глаза.

Answer 2

[Developer]

Шансы получить коллизию огромны.
Подсчитать элементарно.
Коллизии будут ежедневно. Ни о каких 50 годах и речи быть не может