PHP - Qual è un buon modo per produrre una stringa alfanumerica breve da un lungo hash MD5?

Question

Questo è con lo scopo di avere un bel URL breve che si riferisce a un hash MD5 in un database. Vorrei convertire qualcosa di simile:

a7d2cd9e0e09bebb6a520af48205ced1

in qualcosa di simile a questo:

hW9lM5f27

Coloro entrambi contengono circa la stessa quantità di informazioni. Il metodo non deve essere diretto e reversibile, ma sarebbe bello (più flessibile). Per lo meno vorrei una stringa generata a caso con l'hash hex come seme in modo che sia riproducibile. Sono sicuro che ci sono molte possibili risposte, sono curioso di vedere come le persone lo farebbero in modo elegante.

Oh, questo non deve avere una corrispondenza 1: 1 perfetta con l'hash originale ma sarebbe un bonus (credo di averlo già implicito con i criteri di reversibilità). E vorrei evitare le collisioni, se possibile.

EDIT ho realizzato i miei calcoli iniziali erano del tutto sbagliato (grazie alle persone che rispondono qui, ma mi c'è voluto un po 'per indizio in) e non si può davvero ridurre la lunghezza della stringa molto lanciando in tutta la bassa maiuscolo e maiuscolo nel mix. Quindi credo che io voglio qualcosa che non si converte direttamente da hex basare 62.

Answer 1

Ovviamente se voglio che una funzione soddisfi perfettamente le mie esigenze, è meglio che io la realizzi da sola. Ecco cosa mi è venuto in mente.

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

Questo è un generatore molto generale scopo stringa casuale, tuttavia non è solo un vecchio generatore stringa casuale perché il risultato è determinato dalla stringa di input e qualsiasi cambiamento leggero a quell'ingresso produrrà un risultato completamente diverso. Si può fare ogni sorta di cose con questo:

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

Qualcuno ha visto alcun problema con esso o qualsiasi margini di miglioramento?

Answer 2

Dipende da quello che è a7d2cd9e0e09bebb6a520af48205ced1. Supponendo che tu stia parlando di un numero esadecimale poiché proviene da md5, potresti semplicemente eseguire un base64_encode. Se disponi dell'esagono in formato stringa, devi eseguire hexdec. Attenzione però a non incorrere in problemi di maxint.

Answer 3

Si potrebbe semplicemente fare il vecchio base conversion. L'hash è espresso in esadecimale e puoi quindi creare un alfabeto della dimensione che vuoi esprimere l'hash. Base64 funziona bene per questo scopo, anche se probabilmente vorrai scrivere la tua funzione in modo da finire per codificare il valore, non la stringa.

Si noti, tuttavia, che Base64 standard contiene caratteri che non si desidera inserire in un URL; +,/e il carattere di riempimento =. È possibile sostituire questi caratteri con qualcos'altro durante la conversione avanti e indietro per ottenere una codifica Base64 sicura dall'URL (o utilizzare un set di caratteri sicuro per iniziare se si scrive la propria funzione).

Answer 4

Ecco un po 'di funzione a titolo oneroso:

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

Fondamentalmente si hanno 16-byte di dati nella stringa di hash MD5. È lungo 32 caratteri perché ogni byte è codificato come 2 cifre esadecimali (ad esempio 00-FF). Quindi li suddividiamo in byte e ne creiamo una stringa di 16 byte. Ma poiché questo non è più un ASCII leggibile o valido, la base-64 lo codifica in caratteri leggibili. Ma dal momento che base-64 risulta in espansione ~ 4/3 (produciamo solo 6 bit per 8 bit di input, richiedendo quindi 32 bit per codificare 24 bit), i 16 byte diventano 22 byte. Ma poiché la codifica base-64 tipicamente si adatta a multipli di lunghezze di 4, possiamo prendere solo i primi 22 caratteri dell'output di 24 caratteri (gli ultimi 2 dei quali sono padding). Quindi sostituiamo i caratteri non URL-safe usati dalla codifica base-64 con equivalenti sicuri dell'URL.

Questo è completamente reversibile, ma è lasciato come esercizio al lettore.

Penso che questo sia il meglio che puoi fare, a meno che non ti interessi su ASCII leggibile da umani, nel qual caso puoi semplicemente usare $ md5_bin_str direttamente.

E inoltre è possibile utilizzare un prefisso o un altro sottoinsieme del risultato di questa funzione se non è necessario conservare tutti i bit. Lanciare i dati è ovviamente il modo più semplice per accorciare le cose! (Ma poi non è reversibile)

P.S. per l'input di "a7d2cd9e0e09bebb6a520af48205ced1" (32 caratteri), questa funzione restituirà "VUDNng4JvrtqUgr0QwXO0Q" (22 caratteri).

Answer 5

Vorrei consigliare contro un 1-1 corrispondenza:

Con codifica base-64 vi sarà solo in grado di diminuire l'ingresso (4/8)/(6/8) -> 4/6 ~ 66% di dimensioni (e questo presuppone che tu abbia a che fare con i "brutti" personaggi base64 senza aggiungere nulla di nuovo).

Probabilmente considererei un metodo di ricerca (secondario) per ottenere valori veramente "carini". Una volta stabilito questo metodo alternativo, scegli come generare valori in quell'intervallo, ad es. numeri casuali - possono essere privi del valore hash di origine (poiché la corrispondenza viene persa in ogni caso) e può essere utilizzato un target-set "carino" arbitrario, forse [a-z] [A-Z] [0-9].

È possibile convertire alla base (62 sopra) semplicemente seguendo il metodo divide e Trasporta e una ricerca in una matrice. Dovrebbe essere divertente piccolo esercizio.

Nota: se si sceglie il numero casuale da [0, 62^5), si otterrà un valore che comprimerà completamente l'output codificato (e si adatta ai valori interi a 32 bit). È quindi possibile eseguire questo processo più volte di seguito per ottenere un buon valore di risultato multiplo di 5, ad esempio xxxxxyyyyyzzzzzz (dove x, y, z sono gruppi diversi e il valore totale è compreso nell'intervallo (62^5)^3 -> 62^15 -> "un valore enorme")

Modifica, per un commento:

Perché senza la corrispondenza 1-1 si può fare veramente le cose belle brevi - forse come "piccola "con una lunghezza di 8 caratteri - con base62, 8 caratteri possono memorizzare fino a 218340105584896 valori, che è probabilmente più di quanto tu abbia mai bisogno. O anche 6 caratteri che "solo" consentono la memorizzazione di 56800235584 valori diversi! (E non puoi ancora memorizzare quel numero in un semplice numero intero a 32 bit :-) Se passi a 5 caratteri, riduci di nuovo lo spazio (a poco meno di un miliardo: 916,132,832), ma ora hai qualcosa che può inserirsi in un intero con segno a 32 bit (anche se è un po 'dispendioso).

Il DB non dovrebbe garantire duplicati, anche se un indice su questo valore sarà "frammentazione rapida" con una fonte casuale (ma è possibile utilizzare contatori o quant'altro). Un PRNG ben distribuito dovrebbe avere conflitti minimi (leggi: tentativi) in un intervallo abbastanza ampio (supponendo che tu mantenga il seme in rotazione e non lo reimposti, o resettato in modo appropriato) - Super 7 può anche garantire NESSUN duplicato durante un ciclo (di soli ~ 32k), ma come potete vedere sopra, lo spazio di destinazione è ancora grande. Vedere la matematica in cima a ciò che richiede il mantenimento di una relazione 1-1 in termini di dimensione minima codificata .

Il metodo divide-and-carry spiega solo come ottenere il numero sorgente in una base diversa, forse base62. Lo stesso metodo generale può essere applicato per passare dalla base "naturale" (base10 in PHP) a qualsiasi base.

Answer 6

Qui ci sono due funzioni di conversione per Base-16 a base 64 conversione e l'inverso Base-64 a base-16 per lunghezze di ingresso arbitrario:

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

Se avete bisogno di Base-64 encoding with the URL and filename safe alphabet, è possibile utilizzare queste funzioni :

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

Se ora si vuole una funzione per comprimere i valori MD5 esadecimali utilizzando URL caratteri sicuri, è possibile utilizzare questo:

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

E la funzione inversa:

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