2017-02-06 27 views
13

Potrzebuję bardzo szybkiej funkcji haszowania ciągów pasujących do aplikacji napisanej w PHP.Bardzo szybka funkcja mieszająca dla 8-bajtowych łańcuchów hashujących

Problem, który próbuję przezwyciężyć, to przypisywanie identyfikatorów do uprawnień w systemie kontroli dostępu. Zastanawiam się nad użyciem zaszyfrowanych ciągów do reprezentowania identyfikatorów uprawnień. W ten sposób będę mógł sprawdzać uprawnienia w następujący sposób:

if ($Auth->isAllowed($user, "blog.comment")) { 
    // Do some operation 
} 
... 

if ($Auth->isAllowed($user, "profile.avatar.change")) { 
    // Do some other operation 
} 

Tabela DB będzie mapować skróty uprawnień do ról użytkownika. Aby sprawdzić, czy użytkownik może wykonać "profile.avatar.change", odpowiedni ciąg zostanie zaszyfrowany i sprawdzony względem tabeli DB.

Jest to bardzo przydatne i nie będzie trzeba się martwić o zachowanie unikalnych identyfikatorów uprawnień między różnymi modułami. Ale funkcja mieszania powinna być bardzo wydajna.

+1

Hashing jest ulicą jednokierunkową, więc nic nie można sprawdzić w haszyszu, poza jej istnieniem, dla czegoś takiego. –

+0

Najczęstszym sposobem jest podążanie za linuxem. (używając 0-7 do reprezentowania uprawnień). Przypisuj identyfikatory do uprawnień i wykonaj 2^(numer identyfikacyjny), aby utworzyć liczbę całkowitą, a następnie rozwinąć ją w ten sam sposób, aby dowiedzieć się, które uprawnienia masz ... Lub po prostu przekazać obiekty/tokeny z grupą zmiennych i sprawdzić $ user- > can_change_stuff lub $ user-> has_apples – Dimi

+0

@apokryfos, to nie jest duplikat. Te wszystkie pytania są moje. To pytanie jest bardziej szczegółowe na temat mieszania ciągów. – ezpresso

Odpowiedz

10

Pierwszy z nich brzmiał: , dlaczego nie używał prostej funkcji md5?.

próbuje pisać hash przez siebie

Jednym z most frequently referred function to prosta funkcja hash Bernsteina również reffered jako Times 33 with Addition. Jest on używany w php przez Zend to make hashes for keys of associative array. W php mogło być realizowane w następujący sposób:

function djb2($s){ 
    $word = str_split($s); 
    $length = count($word); 

    $hashAddress = 5381; 
    for ($counter = 0; $counter < $length; $counter++){ 
     $hashAddress = (($hashAddress << 5) + $hashAddress) + $word[$counter]; 
    } 
    return $hashAddress; 
} 
echo djb2("stackoverflow"); 

Problemem jest to, że gdy jest realizowany w ten sposób, że jest dość powolna. Testy pokazują, że jest to ~ 3 razy wolniej, niż md5. Musimy więc znaleźć najszybszy internal implementation of a hash function.

Znalezienie najlepszego wewnętrznego mieszania

Wystarczy wziąć wszystkie algos i mierzyć czas do mieszania milion strun.

function testing($algo, $str) { 
    $start = microtime(true); 
    for($ax = 0; $ax < 1000000; $ax++){ 
     hash($algo, $str); 
    } 

    $end = microtime(true); 
    return ($end - $start); 
} 


$algos = hash_algos(); 
$times = []; 

foreach($algos as $algo){ 
    $times[$algo] = testing($algo, "stackoverflow"); 
} 

// sort by time ASC 
asort($times); 

foreach($times as $algo => $time){ 
    echo "$algo -> " . round($time, 2)."sec\n"; 
} 

Moje wyniki to:

fnv1a32 -> 0.29sec 
fnv132 -> 0.3sec 
crc32b -> 0.3sec 
adler32 -> 0.3sec 
crc32 -> 0.31sec 
joaat -> 0.31sec 
fnv1a64 -> 0.31sec 
fnv164 -> 0.31sec 
md4 -> 0.46sec 
md5 -> 0.54sec 
... 
md2 -> 6.32sec 

Wynik nieznacznie zmienia się od wykonania egzekucji - pierwsze 8 algos tasowanie są ze względu na ich bliskich prędkości i jej zależność od obciążenia serwera.

Co należy wybrać?

Możesz użyć dowolnej z 8 funkcji powyżej: $hash = hash('crc32', $string);. W rzeczywistości szeroko stosowana funkcja md5 jest zaledwie 1,7 razy wolniejsza od linii wiodącej.

Bonus

There are another functions like SuperFastHash, które nie zostały zaimplementowane w kodzie php, ale są one 4x szybciej niż crc32.

2

Czas przetwarzania funkcji skrótu można w większości przypadków uznać za nieistotny. Jeśli potrzebujesz trochę skrótu (8 znaków), możesz po prostu użyć funkcji crc32.

<?php 
$hash = hash('crc32', 'WhatDoYouWant'); 
?> 

Możesz również połączyć hash z uniqid, aby utworzyć losowy hash.

<?php 
$hash = hash('crc32', uniqid()); 
?> 
3

Użyj xxHash. Jest używany również przez PrestoDB. Implementacja PHP pod numerem GitHub

Powiązane problemy