algorithm - Jaka jest dobra funkcja skrótu?

Translate

Co to jest dobra funkcja skrótu? Widziałem wiele funkcji skrótu i aplikacji na moich kursach dotyczących struktur danych na studiach, ale głównie dostałem, że dość trudno jest zrobić dobrą funkcję mieszającą. Z zasady, aby uniknąć kolizji, mój profesor powiedział, że:

function Hash(key)
  return key mod PrimeNumber
end

(mod jest operatorem% w C i podobnych językach)

gdzie liczba pierwsza jest rozmiarem tablicy skrótów. Rozumiem, że jest to dość dobra funkcja unikania kolizji i szybka, ale jak mogę zrobić lepszą? Czy są lepsze funkcje skrótu dla kluczy łańcuchowych i klawiszy numerycznych?

This question and all comments follow the "Attribution Required."

Wszystkie odpowiedzi

Translate

Do "normalnego" przeszukiwania tabeli skrótów dla praktycznie każdego rodzaju danych - ta autorstwa Paula Hsieha jest najlepsza, jakiej kiedykolwiek używałem.

http://www.azillionmonkeys.com/qed/hash.html

Jeśli zależy Ci na bezpieczeństwie kryptograficznym lub czymś bardziej zaawansowanym, to YMMV. Jeśli potrzebujesz tylko funkcji skrótu ogólnego przeznaczenia do wyszukiwania tabeli skrótów, to jest to, czego szukasz.

Źródło
Translate

Nie ma czegoś takiego jak „dobra funkcja skrótu” dla uniwersalnych skrótów (red. Tak, wiem, że istnieje coś takiego jak „uniwersalne mieszanie”, ale nie o to mi chodziło). W zależności od kontekstu różne kryteria określają jakość skrótu. Dwie osoby wspomniały już o SHA. To jest kryptograficzny hash i wcale nie jest dobry dla tabel haszujących, co prawdopodobnie masz na myśli.

Tabele skrótów mają bardzo różne wymagania. Jednak znalezienie uniwersalnej dobrej funkcji skrótu jest trudne, ponieważ różne typy danych ujawniają różne informacje, które można zaszyfrować. Z reguły warto to rozważyćwszystkoinformacje, które typ zawiera jednakowo. Nie zawsze jest to łatwe, a nawet możliwe. Ze względów statystycznych (a co za tym idzie kolizji) ważne jest również wygenerowanie dobrego rozrzutu w przestrzeni problemowej, czyli wszystkich możliwych obiektów. Oznacza to, że podczas haszowania liczb od 100 do 1050 nie jest dobrze, aby najbardziej znacząca cyfra odgrywała dużą rolę w haszowaniu, ponieważ dla ~ 90% obiektów ta cyfra będzie równa 0. O wiele ważniejsze jest, aby ostatnie trzy były ważne. cyfry określają skrót.

Podobnie, podczas mieszania ciągów ważne jest, aby wziąć pod uwagę wszystkie znaki - z wyjątkiem sytuacji, gdy z góry wiadomo, że pierwsze trzy znaki wszystkich łańcuchów będą takie same; rozważenie ich wtedy jest marnotrawstwem.

To właściwie jeden z przypadków, w których radzę przeczytać, co ma do powiedzenia KnuthSztuka programowania, vol. 3. Kolejną dobrą lekturą jest Julienne WalkerSztuka haszowania.

Źródło
Translate

Istnieją dwa główne cele funkcji mieszania:

  • aby równomiernie rozproszyć punkty danych na n bitów.
  • bezpiecznie zidentyfikować dane wejściowe.

Nie można polecić skrótu, nie wiedząc, do czego go używasz.

Jeśli tylko tworzysz tabelę skrótów w programie, nie musisz się martwić o to, jak odwracalny lub hakowalny jest algorytm ... SHA-1 lub AES są do tego całkowicie niepotrzebne, lepiej byłoby użyć zaodmiana FNV. FNV osiąga lepszą dyspersję (a tym samym mniej kolizji) niż prosty mod główny, o którym wspomniałeś, i jest bardziej dostosowany do różnych rozmiarów wejściowych.

Jeśli używasz skrótów do ukrywania i uwierzytelniania informacji publicznych (takich jak haszowanie hasła lub dokumentu), powinieneś użyć jednego z głównych algorytmów haszujących zweryfikowanych przez kontrolę publiczną.Salon funkcji skrótuto dobre miejsce na rozpoczęcie.

Źródło
Translate

To jest dobry przykład, a także przykład, dlaczego nigdy nie chciałbyś go napisać. Jest to skrót Fowler / Noll / Vo (FNV), który jest równy geniuszowi informatyki i czystemu voodoo:

unsigned fnv_hash_1a_32 ( void *key, int len ) {
    unsigned char *p = key;
    unsigned h = 0x811c9dc5;
    int i;

    for ( i = 0; i < len; i++ )
      h = ( h ^ p[i] ) * 0x01000193;

   return h;
}

unsigned long long fnv_hash_1a_64 ( void *key, int len ) {
    unsigned char *p = key;
    unsigned long long h = 0xcbf29ce484222325ULL;
    int i;

    for ( i = 0; i < len; i++ )
      h = ( h ^ p[i] ) * 0x100000001b3ULL;

   return h;
}

Edytować:

  • Landon Curt Noll poleca dalejjego stronaalgorytm FVN-1A w porównaniu z oryginalnym algorytmem FVN-1: Ulepszony algorytm lepiej rozprasza ostatni bajt w skrócie. Odpowiednio dostosowałem algorytm.
Źródło
Translate

Powiedziałbym, że podstawową zasadą jest nie rzucać własnym. Spróbuj użyć czegoś, co zostało dokładnie przetestowane, np. SHA-1 lub coś podobnego.

Źródło
Translate

Dobra funkcja skrótu ma następujące właściwości:

  1. Biorąc pod uwagę skrót wiadomości, atakujący nie może znaleźć innej wiadomości, której skróty są identyczne.

  2. Biorąc pod uwagę parę wiadomości, m 'im', jest obliczeniowo niewykonalne znalezienie dwóch takich, że h (m) = h (m ')

Są to dwa przypadkinieto samo. W pierwszym przypadku istnieje wcześniej istniejący skrót, dla którego próbujesz znaleźć kolizję. W drugim przypadku próbujesz znaleźćkażdydwie wiadomości, które się zderzają. Drugie zadanie jest znacznie łatwiejsze ze względu na urodzinowy „paradoks”.

Tam, gdzie wydajność nie jest tak wielkim problemem, należy zawsze używać bezpiecznej funkcji skrótu. Istnieją bardzo sprytne ataki, które można wykonać, wymuszając kolizje w hashu. Jeśli od samego początku użyjesz czegoś mocnego, zabezpieczasz się przed tym.

Nie używaj MD5 ani SHA-1 w nowych projektach. Większość kryptologów, łącznie ze mną, uznałaby je za zepsute. Głównym źródłem słabości obu tych projektów jest to, że druga właściwość, którą nakreśliłem powyżej, nie dotyczy tych konstrukcji. Jeśli osoba atakująca może wygenerować dwie wiadomości, m i m ', obie mają tę samą wartość, może użyć tych wiadomości przeciwko tobie. SHA-1 i MD5 również cierpią z powodu ataków rozszerzających wiadomości, które mogą fatalnie osłabić twoją aplikację, jeśli nie będziesz ostrożny.

Bardziej nowoczesny haszysz, taki jak Whirpool, to lepszy wybór. Nie cierpi z powodu tych ataków rozszerzających wiadomości i używa tej samej matematyki, której używa AES, aby udowodnić bezpieczeństwo przed różnymi atakami.

Mam nadzieję, że to pomoże!

Źródło
Translate

Mówisz tutaj, że chcesz mieć taki, który używa odporności na kolizje. Spróbuj użyć SHA-2. Lub spróbuj użyć (dobrego) szyfru blokowego w funkcji jednokierunkowej kompresji (nigdy wcześniej tego nie próbowałem), jak AES w trybie Miyaguchi-Preenel. Problem polega na tym, że musisz:

1) mieć IV. Spróbuj użyć pierwszych 256 bitów części ułamkowej stałej Khinchina lub coś w tym rodzaju. 2) mają schemat wypełnienia. Łatwy. Wyciągnij to z haszyszu, takiego jak MD5 lub SHA-3 (Keccak [wymawiane „ket-chak”]). Jeśli nie dbasz o bezpieczeństwo (kilka innych to powiedziało), spójrz na FNV lub lookup2 autorstwa Boba Jenkinsa (właściwie to ja jestem pierwszym, który poleca lookup2) Spróbuj też MurmurHash, jest szybki (sprawdź to: .16 cpb ).

Źródło