Funkcja haszująca Jenkinsa
Funkcje skrótu Jenkinsa to zbiór (niekryptograficznych ) funkcji skrótu dla kluczy wielobajtowych zaprojektowanych przez Boba Jenkinsa . Pierwsza z nich została oficjalnie opublikowana w 1997 roku.
Funkcje skrótu
jeden_czas_czasu
Jenkinsa one_at_a_time jest tutaj zaadaptowany ze strony WWW autorstwa Boba Jenkinsa, która jest rozszerzoną wersją jego artykułu dr Dobba . Pierwotnie został stworzony, aby spełnić pewne wymagania opisane przez Colina Plumba, kryptografa, ale ostatecznie nie został wykorzystany.
0
0
uint32_t jenkins_one_at_a_time_hash ( const uint8_t * klucz , size_t długość ) { size_t i = ; uint32_t hash = ; while ( i != długość ) { hash += klucz [ i ++ ]; hash += hash << 10 ; hash ^= hash >>
6 ; } hash += hash << 3 ; hash ^= hash >> 11 ; hash += hash << 15 ; zwrotny skrót ; }
Przykładowe wartości skrótu dla funkcji skrótu one_at_a_time .
one_at_a_time ( "a" , 1 ) 0xca2e9442 one_at_a_time ( "Szybki brązowy lis przeskakuje nad leniwym psem" , 43 ) 0x519e91f5
Zachowanie lawinowe tego skrótu pokazano po prawej stronie.
Każdy z 24 wierszy odpowiada pojedynczemu bitowi w 3-bajtowym kluczu wejściowym, a każda z 32 kolumn odpowiada bitowi w wyjściowym mieszaniu. Kolory są wybierane na podstawie tego, jak dobrze bit klucza wejściowego wpływa na dany wyjściowy bit skrótu: zielony kwadrat oznacza dobre zachowanie podczas mieszania, żółty kwadrat słabe zachowanie podczas mieszania, a czerwony oznacza brak mieszania. Tylko kilka bitów w ostatnim bajcie klucza wejściowego jest słabo zmieszanych z mniejszością bitów w wyjściowym mieszaniu.
Standardowe implementacje języka programowania Perl przed wersją 5.28 obejmowały hash Jenkinsa jeden po drugim lub jego utwardzony wariant, który był używany domyślnie.
wyszukiwanie2
Funkcja lookup2 była tymczasowym następcą funkcji jeden po drugim. Jest to funkcja określana jako „My Hash” w artykule w czasopiśmie Dr. Dobbs z 1997 r., Chociaż została przestarzała przez późniejsze funkcje wydane przez Jenkinsa. Zastosowania tej funkcji skrótu można znaleźć w:
- kontroler modelu SPIN do probabilistycznego wykrywania błędów. W artykule na temat tego programu badacze Dillinger i Manolios zauważają, że lookup2 jest „popularnym wyborem wśród implementatorów tablic mieszających i filtrów Blooma ”. Badają lookup2 i jego proste rozszerzenie, które generuje 96-bitowe zamiast 32-bitowych wartości skrótu.
- Komponent zapory sieciowej Netfilter systemu Linux , w którym zastąpił wcześniejszą funkcję skrótu, która była zbyt wrażliwa na kolizje. Wykazano jednak, że wynikowy system nadal jest wrażliwy na zalewania hashem , nawet jeśli hash Jenkinsa jest losowany przy użyciu tajnego klucza.
- Program, który rozwiązał grę w kalah , wykorzystywał funkcję haszującą Jenkinsa zamiast techniki haszowania Zobrist , częściej stosowanej w tego typu problemach; powodem tego wyboru była szybkość funkcji Jenkinsa na małych reprezentacjach tablic kalah, a także fakt, że podstawowa zasada kalah może radykalnie zmienić planszę, negując korzyści wynikające z przyrostowego obliczania funkcji mieszających przez Zobrist.
wyszukiwanie3
Funkcja lookup3 zużywa dane wejściowe w 12-bajtowych (96-bitowych) porcjach. Może być odpowiedni, gdy szybkość jest ważniejsza niż prostota. Należy jednak pamiętać, że jakakolwiek poprawa szybkości wynikająca z użycia tego skrótu może być przydatna tylko w przypadku dużych kluczy, a zwiększona złożoność może również mieć konsekwencje dla szybkości, takie jak uniemożliwienie kompilatorowi optymalizacyjnemu wstawiania funkcji skrótu.
SpookyHash
W 2011 roku Jenkins wypuścił nową 128-bitową funkcję skrótu o nazwie SpookyHash. SpookyHash jest znacznie szybszy niż lookup3.
Przykład dla V2 (little-endian x64):
Krótka metoda dla mniej niż 192 bajtów (43 bajty):
Hash128("Szybki brązowy lis przeskakuje nad leniwym psem") 2b12e846aa0693c71d367e742407341b
Standardowa metoda dla więcej niż 191 bajtów (219 bajtów):
Hash128("Szybki brązowy lis przeskakuje leniwego psa Szybki brązowy lis przeskakuje leniwego psa Szybki brązowy lis przeskakuje leniwego psa Szybki brązowy lis przeskakuje leniwego psa Szybki brązowy lis przeskakuje leniwego psa") f1b71c6ac5af39e7b69363a60dd29c49