Вопрос подстроки Sha1

Question

Я делаю сайт типа пастбина и пытаюсь сделать id случайной строкой, например paste.com/4RT65L

Я получаю sha1 идентификатора, прежде чем добавить его в базу данных, но я получаю подстроку первых 8 символов sha1. есть ли у них возможность быть двойной копией одного и того же ша1? Я не хочу, чтобы они случайно стали второй пастой с идентификатором, который уже использовался?

Answer 1

Вероятность столкновения в 8 символов значительно выше, чем вероятность столкновения с двумя ключами Sha1, но это не значит, что это произойдет.

Я бы порекомендовал вам провести тестирование на нем. Создайте случайный ввод и посмотрите, сколько времени потребуется, чтобы столкнуться. Если вам нравятся результаты, то иди с этим. В противном случае вам понадобится более длинная строка.

РЕДАКТИРОВАТЬ: Вы также можете рассчитать вероятность столкновения, посмотрев на парадокс дня рождения.

По сути, если вы берете первые 8 шестнадцатеричных цифр из SHA-1, то у вас есть 16**8 (4 294 967 296) различных доступных комбинаций.

Используя онлайн калькулятор Birthay Paradox, после примерно 9200 хешей у вас будет 1% шанс столкновения. Потребуется около 30000 хешей, прежде чем у вас будет шанс 10%, и 77 000, прежде чем у вас будет шанс 50%.

Важно отметить, что до тех пор, пока ваша хеш-функция выполняет приличную работу, будучи псевдослучайной, не имеет значения, какую вы используете (будь то SHA1, MD5 или любая другая форма контрольной суммы)- эти числа предполагают абсолютно случайные входы, и, таким образом, вы можете только приблизиться к этим значениям, используя все более совершенные хэш-функции

Таким образом, в конце концов, это зависит от того, сколько трафика вы ожидаете. Если это маленький сайт, вы можете сойти с рук. Если это большое количество трафика, то ваши шансы на столкновение очень высоки.

Answer 2

Перед назначением идентификатора вы всегда можете проверить, что он не занят... или, что еще лучше, поставить уникальный идентификатор в поле базы данных... проблема решена.:)

Подождите, вы говорите SHA1 идентификатора. Вы не имеете в виду идентификатор autoinc? Мои первые предположения были бы:

356a192b
da4b9237
77de68de

Если вы используете случайный идентификатор, зачем запускать на нем sha1?

Answer 3

Я понял это, мой код:

strtoupper(substr(sha1($token_start . $id . $token_end), 0, 8))

где $id - это идентификатор, который получается при определении общего количества идентификаторов в базе данных + 1, являясь следующим идентификатором, так как это автоматическое увеличение.

затем, когда он вставляет запись, он вставляет зашифрованный.

$ token_start и $token_end - это случайные строки, которые можно выбрать, чтобы сделать новый идентификатор уникальным.

Я сделал цикл, который вставлял их 32 000 раз в базу данных, только идентификатор, автоинкремент вместе с новым идентификатором, и я сделал поиск с отчетливым и не получил повторов. этого более чем достаточно для меня. Любые комментарии будут полезны. Я не знаю, сколько времени это займет, пока я не столкнусь. если кто-нибудь знает, когда будет первый, это было бы здорово.