PHP - Каков хороший способ получить короткую буквенно-цифровую строку из длинного хеша md5?

Question

Это сделано для того, чтобы иметь хороший короткий URL, который ссылается на хэш md5 в базе данных. Я хотел бы преобразовать что-то вроде этого:

a7d2cd9e0e09bebb6a520af48205ced1

примерно так:

hW9lM5f27

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

О, это не обязательно должно иметь полное соответствие 1: 1 с оригинальным хешем, но это было бы бонусом (я думаю, я уже подразумевал это с критериями обратимости). И я хотел бы избежать столкновений, если это возможно.

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

Answer 1

Вот небольшая функция для рассмотрения:

/** Return 22-char compressed version of 32-char hex string (eg from PHP md5). */
function compress_md5($md5_hash_str) {
    // (we start with 32-char $md5_hash_str eg "a7d2cd9e0e09bebb6a520af48205ced1")
    $md5_bin_str = "";
    foreach (str_split($md5_hash_str, 2) as $byte_str) { // ("a7", "d2", ...)
        $md5_bin_str .= chr(hexdec($byte_str));
    }
    // ($md5_bin_str is now a 16-byte string equivalent to $md5_hash_str)
    $md5_b64_str = base64_encode($md5_bin_str);
    // (now it's a 24-char string version of $md5_hash_str eg "VUDNng4JvrtqUgr0QwXOIg==")
    $md5_b64_str = substr($md5_b64_str, 0, 22);
    // (but we know the last two chars will be ==, so drop them eg "VUDNng4JvrtqUgr0QwXOIg")
    $url_safe_str = str_replace(array("+", "/"), array("-", "_"), $md5_b64_str);
    // (Base64 includes two non-URL safe chars, so we replace them with safe ones)
    return $url_safe_str;
}

В основном у вас есть 16-байтовые данные в хеш-строке MD5.Это 32 символа в длину, потому что каждый байт кодируется как 2 шестнадцатеричные цифры (т.е. 00-FF).Таким образом, мы разбиваем их на байты и собираем из них 16-байтовую строку.Но так как это больше не является читаемым или действительным ASCII, мы base-64 кодируем его обратно в читаемые символы.Но поскольку base-64 приводит к расширению ~ 4/3 (мы выводим только 6 бит на 8 бит ввода, что требует 32 бита для кодирования 24 бита), 16 байтов становятся 22 байтами.Но поскольку кодирование base-64 обычно дополняется до длин, кратных 4, мы можем взять только первые 22 символа из 24 выводимых символов (последние 2 из которых являются заполнителями).Затем мы заменяем не-URL-безопасные символы, используемые кодировкой base-64, на URL-безопасные эквиваленты.

Это полностью обратимо, но это оставлено читателю в качестве упражнения.

Iдумаю, что это лучшее, что вы можете сделать, если вы не заботитесь о человекочитаемом / ASCII, и в этом случае вы можете просто использовать $ md5_bin_str напрямую.

А также вы можете использовать префикс или другое подмножестворезультат этой функции, если вам не нужно сохранять все биты.Выбрасывание данных, очевидно, самый простой способ сократить время!(Но тогда это не обратимо)

PS для вашего ввода "a7d2cd9e0e09bebb6a520af48205ced1" (32 символа), эта функция возвратит "VUDNng4JvrtqUgr0QwXO0Q" (22 символа).

Answer 2

Вот две функции преобразования для преобразования Base-16 в Base-64 и обратное преобразование Base-64 в Base-16 для произвольной длины ввода:

function base16_to_base64($base16) {
    return base64_encode(pack('H*', $base16));
}
function base64_to_base16($base64) {
    return implode('', unpack('H*', base64_decode($base64)));
}

Если вам требуется кодировка Base-64 с URL-адресом и безопасным алфавитом имени файла , вы можете использовать следующие функции:

function base64_to_base64safe($base64) {
    return strtr($base64, '+/', '-_');
}
function base64safe_to_base64($base64safe) {
    return strtr($base64safe, '-_', '+/');
}

Если вы хотите, чтобы функция сжимала шестнадцатеричные значения MD5 с помощью безопасных символов URL, вы можете использовать это:

function compress_hash($hash) {
    return base64_to_base64safe(rtrim(base16_to_base64($hash), '='));
}

И обратная функция:

function uncompress_hash($hash) {
    return base64_to_base16(base64safe_to_base64($hash));
}

Answer 3

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

//takes a string input, int length and optionally a string charset
//returns a hash 'length' digits long made up of characters a-z,A-Z,0-9 or those specified by charset
function custom_hash($input, $length, $charset = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUFWXIZ0123456789'){
    $output = '';
    $input = md5($input); //this gives us a nice random hex string regardless of input 

    do{
        foreach (str_split($input,8) as $chunk){
            srand(hexdec($chunk));
            $output .= substr($charset, rand(0,strlen($charset)), 1);
        }
        $input = md5($input);

    } while(strlen($output) < $length);

    return substr($output,0,$length);
}

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

custom_hash('1d34ecc818c4d50e788f0e7a9fd33662', 16); // 9FezqfFBIjbEWOdR
custom_hash('Bilbo Baggins', 5, '0123456789bcdfghjklmnpqrstvwxyz'); // lv4hb
custom_hash('', 100, '01'); 
// 1101011010110001100011111110100100101011001011010000101010010011000110000001010100111000100010101101

Кто-нибудь видел какие-либо проблемы с этим или какие-либо возможности для улучшения?

Answer 4

Я бы посоветовал против 1-1 переписка:

В кодировке base-64 вы сможете только уменьшить входные данные до (4/8) / (6/8) -> 4/6 ~ 66% (и это при условии, что вы имеете дело с "уродливым" "символы base64 без добавления чего-либо нового).

Я бы, вероятно, рассмотрел (вторичный) метод поиска, чтобы получить действительно "красивые" значения. После того, как вы установили этот альтернативный метод, выберите способ генерации значений в этом диапазоне - например, случайные числа - могут быть свободны от исходного хеш-значения (потому что в любом случае соответствие теряется), и может использоваться произвольный «симпатичный» набор целей, например, [a-z] [A-Z] [0-9].

Вы можете преобразовать в базу (62 выше), просто следуя методу «разделяй и переноси» и просматривая массив. Это должно быть забавное маленькое упражнение.

Примечание. Если вы выберете случайное число из [0, 62 ^ 5), вы получите значение, которое будет полностью упаковывать закодированный вывод (и соответствовать 32-битным целочисленным значениям). Затем вы можете выполнить этот процесс несколько раз подряд, чтобы получить результат, кратный -5, например xxxxxyyyyyzzzzzz (где x, y, z - разные группы, а общее значение находится в диапазоне (62 ^ 5) ^ 3 -> 62 ^ 15 -> «огромное значение»)

Редактировать, для комментария :

Поскольку без соответствия 1-1, вы можете создавать действительно короткие симпатичные вещи - возможно, «маленькие» длиной до 8 символов - с base62, 8 символов могут хранить до 218340105584896 значений, что скорее всего, больше, чем вам когда-либо понадобится. Или даже 6 символов, которые «только» позволяют хранить 56800235584 различных значений! (И вы все еще не можете сохранить это число в виде простого 32-разрядного целого числа :-) Если вы уменьшите число до 5 символов, вы снова уменьшите пространство (до чуть менее одного миллиарда: 916 132 832), но теперь у вас есть кое-что, что может вписывается в 32-разрядное целое число со знаком (хотя это несколько расточительно).

БД должна обеспечивать отсутствие дубликатов, хотя индекс по этому значению будет «быстро фрагментироваться» со случайным источником (но вы можете использовать счетчики или еще много чего). Хорошо распределенный PRNG должен иметь минимальные конфликты (читай: повторы) в достаточно большом диапазоне (при условии, что вы продолжаете посевную работу и не сбрасываете ее, или сбрасываете ее соответствующим образом) - Super 7 может даже гарантировать отсутствие дубликатов во время цикла (всего ~ 32k), но, как вы можете видеть выше, целевое пространство по-прежнему большое . Посмотрите математику в верхней части того, что требуется для поддержания отношения 1-1 в терминах минимальный кодированный размер .

Метод «разделяй и переноси» просто объясняет, как получить номер вашего источника в другую базу - возможно, в base62. Тот же самый общий метод может применяться для перехода от «естественной» базы (base10 в PHP) к любой базе.

Answer 5

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

Обратите внимание, однако, что стандартный Base64 содержит символы, которые вы не хотели бы вставлять в URL; +, / и символ заполнения =. Вы можете заменить эти символы чем-то другим при преобразовании туда и обратно, чтобы получить URL-безопасную кодировку Base64 (или использовать безопасный набор символов для начала, если вы пишете свою собственную функцию).

Answer 6

Это зависит от того, что a7d2cd9e0e09bebb6a520af48205ced1.Предполагая, что вы говорите о шестнадцатеричном числе, поскольку оно исходит от md5, вы можете просто запустить base64_encode.Если у вас есть гекс в строковой форме, вам нужно выполнить hexdec.Будьте осторожны, вы не столкнетесь с проблемами максинта.