Преобразование URL в уникальный токен из 32 символов

Question

Я пишу партнерскую систему и хочу сгенерировать уникальный токен шириной 32 символа по URL.

Проблема заключается в том, что URL может иметь длину до 128 символов (IIRC).Могу ли я создать уникальный ключ / токен шириной 32 символа по заданному URL-адресу без каких-либо «коллизий»?

Я не уверен, что это проблема кодирования, шифрования или хешированиясмесь всех трех).

Я буду реализовывать эту «функцию отображения» с использованием PHP, поскольку именно этот язык я использую для построения этой конкретной системы.Любые предложения о том, как это сделать?

Можно ли даже однозначно отобразить строку из 128 символов в строку из 32 символов (т.е. без коллизий?) ...

[Править]

Я только что прочитал и обнаружил, что максимальная длина URL-адреса на самом деле составляет порядка 2К.Тем не менее, я не беспокоюсь о «глупых» крайних случаях, подобных этому.Я почти уверен, что в 99,9% случаев мой установленный лимит в 128 символов должен быть достаточным.

Answer 1

Можно ли даже однозначно отобразить строку из 128 символов в строку из 32 символов (т.е. без коллизий?) ...

Частично.Вы можете использовать хеш-функцию, например md5 или sha1 .Это то, для чего они были созданы.
MD5 генерирует строку из 32 символов, а SHA1 генерирует строку из 40 символов.

Конечно, вы не можете гарантировать , что не будетбыть столкновения.Это невозможно, поскольку пространство сообщений слишком велико для ваших хэшей (есть 2 ¹⁰²⁴ сообщений против 2 ¹²⁸ возможных хэшей, если вы используете MD5), но эти функции предназначены для коллизийустойчивы и трудно повернуть.

Ссылки Википедии:

http://en.wikipedia.org/wiki/Hash_function
http://en.wikipedia.org/wiki/MD5
http://en.wikipedia.org/wiki/SHA-1

Answer 2

Можно ли даже однозначно отобразить строку из 128 символов в строку из 32 символов (т.е. без коллизий?) ...

Это зависит от алфавита, используемого для обоих входных данных.и вывод.Если ваш результирующий 32-хэшный хэш ограничен алфавитом a-z, вы можете закодировать в нем максимум 26^32 = 1.901722×10^45 значений.URL может содержать не менее a-z и довольно много других символов, поэтому может содержать не менее 26^128 = 1.307942×10^181 значений.Таким образом, алфавита из 26 символов недостаточно.

Используя a-zA-Z0-9, вы можете закодировать 62^32 = 2.272658×10^57 уникальные значения, чего по-прежнему недостаточно.Даже алфавит из 100 символов дает вам только 100^32 = 1.0×10^64 возможных значений.

В зависимости от того, что именно вы хотите сделать, вам следует либо увеличить длину хэша, либо переосмыслить общий подход.