encrypt - PHP-¿Cuál es una buena manera de producir una cadena alfanumérica corta a partir de un hash md5 largo?

md5 generator

Question

Esto tiene el propósito de tener una URL corta y agradable que se refiere a un hash md5 en una base de datos. Me gustaría convertir algo como esto:

a7d2cd9e0e09bebb6a520af48205ced1

en algo como esto:

hW9lM5f27

Ambos contienen aproximadamente la misma cantidad de información. El método no tiene que ser directo y reversible, pero sería bueno (más flexible). Por lo menos me gustaría una cadena generada al azar con el hash hexadecimal como la semilla para que sea reproducible. Estoy seguro de que hay muchas respuestas posibles, tengo curiosidad por ver cómo la gente lo haría de una manera elegante.

Oh, esto no tiene que tener una correspondencia perfecta de 1: 1 con el hash original, pero eso sería una ventaja (supongo que ya lo insinué con los criterios de reversibilidad). Y me gustaría evitar las colisiones si es posible.

EDITAR Me di cuenta de que mis cálculos iniciales estaban totalmente equivocados (gracias a las personas que respondieron aquí, pero me tomó un rato darme cuenta) y realmente no se puede reducir mucho la longitud de la cuerda al agregar letras minúsculas y mayúsculas a la mezcla . Así que supongo que querré algo que no se convierta directamente de hex a base 62.

Answer 1

Aquí hay dos funciones de conversión para la conversión de Base-16 a Base-64 y la inversa de Base-64 a Base-16 para longitudes de entrada arbitrarias:

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

Si necesita codificación Base-64 con la URL y el alfabeto seguro de nombre de archivo , puede usar estas funciones:

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

Si ahora desea que una función comprima sus valores hexadecimales de MD5 utilizando caracteres seguros de URL, puede usar esto:

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

Y la función inversa:

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

Answer 2

Aquí hay una pequeña función a considerar:

/** 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;
}

Básicamente tienes 16 bytes de datos en la cadena de hash MD5. Tiene 32 caracteres de longitud porque cada byte se codifica como 2 dígitos hexadecimales (es decir, 00-FF). Así que los dividimos en bytes y construimos una cadena de 16 bytes. Pero debido a que esto ya no es ASCII válido ni legible por humanos, lo codificamos en base a 64 en caracteres legibles. Pero como la base 64 da como resultado una expansión de ~ 4/3 (solo generamos 6 bits por 8 bits de entrada, por lo que se requieren 32 bits para codificar 24 bits), los 16 bytes se convierten en 22 bytes. Pero debido a que la codificación de base-64 típicamente rellena a longitudes múltiplos de 4, podemos tomar solo los primeros 22 caracteres de la salida de 24 caracteres (los últimos 2 de los cuales son relleno). Luego reemplazamos los caracteres no seguros para URL utilizados por la codificación base-64 con equivalentes seguros para URL.

Esto es completamente reversible, pero se deja como un ejercicio para el lector.

Creo que esto es lo mejor que puede hacer, a menos que no se preocupe por ASCII, en cuyo caso solo puede usar $ md5_bin_str directamente.

Y también puede usar un prefijo u otro subconjunto del resultado de esta función si no necesita conservar todos los bits. ¡Desechar datos es obviamente la forma más sencilla de acortar cosas! (Pero entonces no es reversible)

PS para su entrada de "a7d2cd9e0e09bebb6a520af48205ced1" (32 caracteres), esta función devolverá "VUDNng4JvrtqUgr0QwXO0Q" (22 caracteres).

Answer 3

Depende de qué es a7d2cd9e0e09bebb6a520af48205ced1 . Suponiendo que está hablando de un número hexadecimal ya que proviene de md5 , simplemente podría ejecutar una base64_encode . Si tiene el hex en forma de cadena, desearía ejecutar hexdec . Tenga cuidado de no tener problemas de maxint sin embargo.

Answer 4

Por supuesto, si quiero una función para satisfacer mis necesidades perfectamente, mejor la hago yo mismo. Aquí es lo que se me ocurrió.

//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);
}

Este es un generador de cadenas aleatorias de propósito muy general, sin embargo, no es solo un generador de cadenas aleatorias antiguas, ya que el resultado está determinado por la cadena de entrada y cualquier cambio leve en esa entrada producirá un resultado totalmente diferente. Puedes hacer todo tipo de cosas con esto:

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

¿Alguien ha visto algún problema con él o hay algún margen de mejora?

Answer 5

Usted podría simplemente hacer la conversión de base vieja y sencilla. El hash se expresa en hexadecimal y, a continuación, puede crear un alfabeto del tamaño que desee para expresar el hash. Base64 funciona bien para este propósito, aunque probablemente querrá escribir su propia función para terminar codificando el valor, no la cadena.

Sin embargo, tenga en cuenta que la Base64 estándar contiene caracteres que no querría poner en una URL; +, / y el carácter de relleno =. Puede reemplazar esos caracteres con otra cosa al convertir de un lado a otro para obtener una codificación Base64 segura para URL (o, para comenzar, use un conjunto seguro de caracteres si escribe su propia función).

Answer 6

Yo aconsejaría contra una correspondencia 1-1:

Con la codificación base-64, solo podrá disminuir la entrada a (4/8) / (6/8) -> 4/6 ~ 66% en tamaño (y esto suponiendo que trate con los caracteres "feos" de base64 sin añadir nada nuevo).

Probablemente consideraría un método de búsqueda (secundario) para obtener valores verdaderamente "bonitos". Una vez que haya establecido este método alternativo, elegir cómo generar valores en ese rango, por ejemplo, números aleatorios, puede estar libre del valor de hash de origen (porque de todos modos se pierde la correspondencia) y se puede usar un conjunto de objetivos "bonito" arbitrario , quizás [az] [AZ] [0-9].

Puede convertir a la base (62 arriba) simplemente siguiendo el método de dividir y acarrear y una búsqueda en una matriz. Debe ser divertido poco ejercicio.

Nota: Si elige el número aleatorio de [0, 62 ^ 5), obtendrá un valor que empaquetará completamente la salida codificada (y se ajustará a valores enteros de 32 bits). Luego, puede realizar este proceso varias veces seguidas para obtener un gran valor de resultado de 5, como xxxxxyyyyyzzzzzz (donde x, y, z son grupos diferentes y el valor total está en el rango (62 ^ 5) ^ 3 -> 62 ^ 15 -> "un valor enorme")

Editar, para comentar :

Porque sin la correspondencia 1-1, puede hacer cosas bonitas realmente cortas, tal vez tan "pequeñas" como de 8 caracteres, con base62, 8 caracteres pueden almacenar hasta 218340105584896 valores, lo que probablemente sea más de lo que nunca necesitará. ¡O incluso 6 caracteres que "solo" permiten almacenar 56800235584 valores diferentes! (Y aún no puede almacenar ese número en un entero liso de 32 bits :-) Si baja a 5 caracteres, nuevamente reduce el espacio (a poco menos de mil millones: 916,132,832), pero ahora tiene algo que puede encaja en un entero de 32 bits con signo (aunque es un desperdicio).

El DB debe asegurar que no haya duplicados, aunque un índice en este valor será de "fragmentación rápida" con una fuente aleatoria (pero podría usar contadores o lo que sea). Un PRNG bien distribuido debería tener conflictos mínimos (leer: reintentos) en un rango suficientemente grande (suponiendo que mantenga la semilla rodando y no la reinicie, o la restablezca adecuadamente) - Super 7 incluso puede garantizar NO duplicados durante un ciclo (de solo ~ 32k), pero como puede ver arriba, el espacio objetivo todavía es grande . Vea las matemáticas en la parte superior de lo que mantener una relación 1-1 requiere en términos de tamaño de codificación mínimo .

El método de dividir y acarrear simplemente explica cómo obtener su número de fuente en una base diferente, tal vez base62. Se puede aplicar el mismo método general para pasar de la base "natural" (base10 en PHP) a cualquier base.