Was ist eine gute Hashfunktion?

Gibt es keine solche Sache wie eine "gute hash-Funktion" für universal-hashes (ed. ja, ich weiß, es gibt so etwas wie ein "universelles hashing" aber das ist nicht das, was ich meinte). Je nach Kontext sind verschiedene Kriterien bestimmen die Qualität eines hash. Zwei Menschen, die bereits erwähnten SHA. Dies ist eine kryptographische hash-und das ist überhaupt nicht gut für die hash-Tabellen, die du wahrscheinlich meinst.

Hash-Tabellen haben sehr unterschiedliche Anforderungen. Aber trotzdem, das finden einer guten hash-Funktion universell ist schwer, da unterschiedliche Daten-Typen stellen verschiedene Informationen, können zerlegt werden. Als Faustregel ist es gut, zu überlegen alle Informationen, die ein type enthält gleichermaßen. Dies ist nicht immer einfach oder gar möglich. Aus Gründen der Statistik (und damit auch Konflikt), es ist auch wichtig zu generieren, die eine gute Streuung über das problem Raum, D. H. alle möglichen Objekte. Dies bedeutet, dass beim hashing zahlen, die zwischen 100 und 1050 es ist nicht gut, wenn sich die meisten signifikanten stellen spielen eine große Rolle in der hash-weil für ~ 90% der Objekte, ist diese Ziffer 0. Es ist viel mehr wichtig, dass Sie die letzten drei Ziffern bestimmen die hash.

Ähnlich wie beim hashing von strings ist es wichtig, betrachten Sie alle Charaktere – außer, wenn es im Voraus bekannt, dass die ersten drei Zeichen aller strings identisch sein; über diese wird dann eine Verschwendung.

Dies ist tatsächlich einer der Fälle, wo ich mich beraten zu Lesen, was Knuth zu sagen hat, in Die Kunst der Computer-Programmierung, vol. 3. Ein weiteres gutes Lesen ist Julienne Walker Die Kunst der Vermischung.

InformationsquelleAutor Konrad Rudolph

Dies ist ein Beispiel für eine gute und auch ein Beispiel dafür, warum würden Sie nie schreiben wollen.
Es ist ein Fowler /Noll /Vo (FNV) Hash, der zu gleichen teilen aus informatik-Genie und Reine 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;
}

Edit:

• Landon Curt Noll empfiehlt auf seine Website die FVN-1A-Algorithmus über die original-FVN-1 Algorithmus: Der verbesserte Algorithmus besser streut das Letzte byte der hash. Ich stellte den Algorithmus entsprechend.

InformationsquelleAutor Nick Van Brunt

Eine gute hash-Funktion hat die folgenden Eigenschaften:

1. Einem gegebenen hash einer Nachricht ist es rechnerisch unmöglich für einen Angreifer findet eine weitere Nachricht, so dass Ihre Hashwerte gleich sind.

2. Gegeben ein paar von Nachricht m' und m, ist es rechnerisch unmöglich, zu finden, zwei so, dass h(m) = h(m')

Beiden Fällen nicht das gleiche. Im ersten Fall gibt es bereits ein hash, dass Sie versuchen, eine Kollision zu finden. Im zweiten Fall werden Sie versuchen zu finden alle zwei Nachrichten, die kollidieren. Die zweite Aufgabe ist deutlich einfacher, wegen dem Geburtstag "paradox."

Wo ist die Leistung nicht so groß ein Problem, sollten Sie immer mit einem sicheren hash-Funktion. Es gibt sehr clevere Angriffe, die ausgeführt werden kann, zwingt Kollisionen in hash. Wenn Sie etwas stark von Anfang an, Sie sichern sich gegen diese.

Nicht mit MD5 oder SHA-1 in neuen designs. Die meisten Kryptographen, mich eingeschlossen, würden betrachten Sie gebrochen. Die grundlegende Quelle der Schwäche in beiden designs ist, dass die zweite Eigenschaft, die ich oben skizziert, nicht für diese Konstruktionen. Wenn ein Angreifer erzeugen kann, zwei Nachrichten m und m', die beide hash den gleichen Wert, den Sie verwenden können, diese Nachrichten gegen Sie. SHA-1 und MD5 leiden auch unter message-Erweiterung Angriffen, die tödlich Schwächen Ihrer Anwendung, wenn Sie nicht vorsichtig sind.

Ein moderneres hash wie Whirpool ist eine bessere Wahl. Es leidet darunter nicht, diese Nachricht extension Angriffe und verwendet die gleiche Mathematik wie AES verwendet, um zu beweisen Sicherheit gegen eine Vielzahl von Angriffen.

Hoffe, das hilft!

InformationsquelleAutor Simon Johnson