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

Question

Esto es con el propósito de tener una buena URL corta 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

Aquellos ambos contienen aproximadamente la misma cantidad de información. El método no tiene que ser directo y reversible, pero sería agradable (más flexible). Como mínimo, me gustaría tener una cadena generada aleatoriamente con el hash hexadecimal como semilla para que sea reproducible. Estoy seguro de que hay muchas respuestas posibles, tengo curiosidad por ver cómo las personas lo harían de una manera elegante.

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

EDITAR me di cuenta de mis cálculos iniciales eran totalmente equivocado (gracias a las personas que responden aquí pero me tomó un tiempo para pista en) y realmente no se puede reducir la longitud de la cadena mucho lanzando en toda la parte baja mayúsculas y minúsculas en la mezcla. Así que supongo que querré algo que no se convierta directamente de hexadecimal a base 62.

Answer 1

Por supuesto, si quiero que una función satisfaga mis necesidades perfectamente, es mejor que la haga yo mismo. Esto 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 = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUFWXIZ'){ 
    $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 muy general finalidad cadena aleatoria, sin embargo, no se trata de cualquier generador de cadena aleatoria de edad, porque el resultado está determinado por la cadena de entrada y cualquier ligero cambio a esa entrada producirá un resultado totalmente diferente. Puede hacer todo tipo de cosas con esto:

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

¿Alguien tiene problemas o alguna mejora?

Answer 2

Depende de qué a7d2cd9e0e09bebb6a520af48205ced1 es. Suponiendo que está hablando de un número hexadecimal dado que proviene de md5, puede ejecutar un base64_encode. Si tiene el hexágono en forma de cadena, querrá ejecutar hexdec. Sin embargo, tenga cuidado de que no se encuentre con problemas de maxint.

Answer 3

Podrías hacer simplemente viejo base conversion. El hash se expresa en hexadecimal, y luego puede crear un alfabeto del tamaño que desea para expresar el hash. Base64 funciona bien para este fin, aunque es probable que desee escribir su propia función para que termine codificando el valor, no la cadena.

Tenga en cuenta, sin embargo, que Base64 estándar contiene caracteres que no le gustaría poner en una URL; +,/y el carácter relleno =. Puede reemplazar esos caracteres con otra cosa al convertir de ida y vuelta para obtener una codificación Base64 segura para URL (o, para empezar, utilizar un conjunto seguro de caracteres si escribe su propia función).

Answer 4

He aquí una pequeña función para su consideración:

/** 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, usted tiene 16 bytes de datos en la cadena de hash MD5. Tiene 32 caracteres de largo porque cada byte se codifica como 2 dígitos hexadecimales (es decir, 00-FF). Entonces los dividimos en bytes y construimos una cadena de 16 bytes. Pero como esto ya no es un ASCII válido o legible para los humanos, lo codificamos en base 64 para que sea legible. Pero dado que la base 64 da como resultado una expansión de ~ 4/3 (solo sacamos 6 bits por cada 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 la base 64 normalmente rellena con longitudes múltiplos de 4, solo podemos tomar los primeros 22 caracteres de la salida de 24 caracteres (los últimos 2 de los cuales son acolchados). Luego reemplazamos los caracteres que no son URL-safe usados ​​por la codificación base-64 con equivalentes seguros para URL.

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

Creo que esto es lo mejor que puede hacer, a menos que no le interese la lectura humana/ASCII, en cuyo caso 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. ¡Lanzar datos es obviamente la forma más simple de acortar cosas! (Pero luego no es reversible)

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

Answer 5

Yo aconsejaría contra una correspondencia 1-1:

Con base 64 codificación que sólo va a ser capaz de disminuir la entrada (4/8)/(6/8) -> 4/6 ~ 66% en tamaño (y esto es asumiendo que lidie con los personajes base "feos" de 64 sin agregar 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, elija cómo generar valores en ese rango, p. Números aleatorios: pueden estar libres del valor hash de origen (porque la correspondencia se pierde de todos modos) y se puede usar un conjunto de objetivos arbitrario "bonito", quizás [a-z] [A-Z] [0-9].

Puede convertir a la base (62 arriba) simplemente siguiendo el método de división y transporte y una búsqueda en una matriz. Debería ser un pequeño ejercicio divertido.

Nota: Si elige el número aleatorio de [0, 62^5), obtendrá un valor que empacará por completo la salida codificada (y se ajustará dentro de los valores enteros de 32 bits). A continuación, puede realizar este proceso varias veces seguidas para obtener un buen valor de resultado múltiple 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 enorme valor")

Editar, para hacer comentarios:

Debido sin la correspondencia 1-1 usted puede hacer cosas bonitas verdaderamente cortos - tal vez como "pequeña "como 8 caracteres de largo - con base62, 8 caracteres pueden almacenar hasta 218340105584896 valores, que es probable más de lo que alguna vez necesitará. ¡O incluso 6 caracteres que "solo" permiten el almacenamiento de 56800235584 valores diferentes! (Y aún no puedes almacenar ese número en un entero simple de 32 bits :-) Si bajas a 5 caracteres, una vez más reduces el espacio (a poco menos de mil millones: 916,132,832), pero ahora tienes algo que puede encajar en un entero de 32 bits con signo (aunque es algo derrochador).

La base de datos debe garantizar que no haya duplicados, aunque un índice en este valor se "fragmentará rápidamente" con una fuente aleatoria (pero puede usar contadores o lo que sea). Un PRNG bien distribuido debe tener conflictos mínimos (léase: reintentos) en un rango lo suficientemente grande (suponiendo que mantenga la semilla en funcionamiento y no la restablezca, o reiníciela adecuadamente) - Super 7 incluso puede garantizar NO duplicados durante un ciclo (de solo ~ 32k), pero como puede ver arriba, el espacio de destino sigue siendo grande. Consulte los cálculos en la parte superior de lo que requiere mantener una relación 1-1 en términos de tamaño mínimo codificado.

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

Answer 6

Aquí hay dos funciones de conversión para Base-16 a Base-64 de conversión y la inversa Base-64 a Base-16 para las 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 Base-64 encoding with the URL and filename safe alphabet, puede utilizar estas funciones :

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

Si ahora desea una función de comprimir los valores de MD5 hexadecimales utilizando caracteres de seguridad de URL, puede utilizar 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)); 
}