Хэш-функция PHP с большой длиной вывода?

Внутри моего кода я генерирую хэши URL-адресов (практически неограниченной длины). В настоящее время я использую sha1(), который, как я знаю, имеет крошечную вероятность столкновения, но у меня есть до 255 байтов для хранения хэша, поэтому я чувствую, что могу также использовать это доступное пространство, чтобы снизить вероятность столкновения даже дальше.

Есть ли:

  1. Другая хэш-функция PHP с более длинной или настраиваемой длиной хэша?
  2. Способ использования хэш-функции фиксированной длины, такой как sha1, с вводом переменной длины для создания более длинного хэша?

Или достаточно ли 20-байтового хэша sha1 для чего-либо, и я должен перестать беспокоиться об этом?


php hash
person Ciaran McNulty    schedule 17.11.2008    source источник

Ответы (7)


arrow_upward
5
arrow_downward

Или 20-байт sha1 достаточно для чего угодно, и я должен перестать беспокоиться об этом?

Точно.

Хэш-таблицы, классификация и дни рождения
http://www.codinghorror.com/blog/archives/001014.html

person Jeff Atwood    schedule 17.11.2008
comment
Парадокс дня рождения - это именно то, о чем я беспокоюсь - я не хочу достичь стадии, когда, когда у меня есть несколько строк по 100 000, вероятность столкновения становится незначительной. Учитывая, что у меня есть достаточно байтов для хранения гораздо более длинного хеша, не должен ли я использовать его, если он доступен? - person Ciaran McNulty; 17.11.2008

arrow_upward
3
arrow_downward

Давайте посмотрим... http://www.cryptography.com/cnews/hash.html

Вопрос. Насколько сложно будет найти коллизии в алгоритме SHA-1?
Ответ. Описанные атаки требуют расчетного коэффициента работы 2^69 (примерно 590 миллиардов миллиардов) хеш-вычислений.

Похоже, риск довольно низок... ^_^

person PhiLho    schedule 17.11.2008

arrow_upward
1
arrow_downward

Если вы действительно беспокоитесь, выберите 256- или 512-битный хэш (32 или 64 символа).

Если вы действительно параноик, добавьте соль.

Если вы более параноик, объедините два хэша для более длинного, например, md5 и sha-256.

person warren    schedule 17.11.2008
comment
Похоже, что эта система используется для предотвращения ввода повторяющихся URL-адресов... наличие соли не принесет пользы, если это так. - person Powerlord; 17.11.2008
comment
правда... хотя я думаю, что если вы на самом деле ожидаете столкновения, то вы собираете слишком много URL-адресов :) - person warren; 18.11.2008

arrow_upward
0
arrow_downward

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

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

Конечно, если вы не пытаетесь скрыть эти хэши от кого-либо, то почему бы просто не использовать последовательный идентификатор?

person Gareth    schedule 17.11.2008

arrow_upward
0
arrow_downward

если вы хотите по-настоящему сойти с ума, вы можете объединить хэши разных частей URL-адреса.

Скажем, URL-адрес имеет длину 40 символов — разбейте его на 5 частей: получите SHA1 из символов 1–8, соедините с SHA1 из символов 9–16, соедините с SHA1 из 17–24... и т. д. Теоретически вы тогда у вас будет 2800 возможностей, и вам нужно будет начать беспокоиться о коллизиях только после 2(69*5) = 2345 = 7,2 * 10 103 строки.

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

person nickf    schedule 17.11.2008

arrow_upward
0
arrow_downward

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

found = false
hv = hash(urlValue)
if table[hash,url] contains pair (hv,urlValue)
   found = true
endif

if (not found)
   insert table (hv,urlValue)
endif

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

person tvanfosson    schedule 17.11.2008

arrow_upward
0
arrow_downward

Ну, это имеет смысл, только если у вас есть короткий хеш-ключ. В противном случае существует риск переполнения данных в таблице.

person Community    schedule 24.07.2009