www.wikidata.de-de.nina.az

Hashfunktion Eine oder Streuwertfunktion ist eine Abbildung die eine große Eingabemenge die Schlüssel auf eine kleinere

Hashfunktion

Eine Hashfunktion oder Streuwertfunktion ist eine Abbildung, die eine große Eingabemenge, die Schlüssel, auf eine kleinere Zielmenge, die Hashwerte, abbildet. Eine Hashfunktion ist daher im Allgemeinen nicht injektiv. Die Eingabemenge kann Elemente unterschiedlicher Längen enthalten, die Elemente der Zielmenge haben dagegen meist eine feste Länge.

Eine Hashfunktion, die Namen auf Ganzzahlen abbildet. Für die Namen „John Smith“ und „Sandra Dee“ gibt es eine Kollision.

Der Name Hashfunktion stammt vom englischen Verb to hash, das sich mit „zerhacken“ übersetzen lässt. Der deutsche Name lautet Streuwertfunktion. Beide Namen deuten darauf hin, dass diese Funktionen normalerweise darauf angelegt sind, die Daten zu „verstreuen“ und zu „zerhacken“ (siehe auch Zerhacker in der Funktechnik). Speziell in der Informatik verwendet man auch den Begriff Hash-Algorithmus (englisch hash algorithm), da Hashfunktionen oftmals in Form eines Algorithmus spezifiziert werden, der die Berechnung der mathematischen Funktion beschreibt.

Die Hash- oder Streuwerte sind meist skalare Werte aus einer begrenzten Teilmenge der natürlichen Zahlen. Eine gute Hashfunktion liefert dabei für die Eingabedaten Werte derart, dass zwei unterschiedliche Eingaben auch zu unterschiedlichen Ausgabewerten führen.

Eine Kollision tritt dann auf, wenn unterschiedlichen Eingabedaten derselbe Hashwert zugeordnet wird. Da die Menge der möglichen Hashwerte meist kleiner ist als die der möglichen Eingaben, sind solche Kollisionen dann prinzipiell unvermeidlich, weshalb es Verfahren zur Kollisionserkennung geben muss. Eine gute Hashfunktion zeichnet sich dadurch aus, dass sie für die Eingaben, für die sie entworfen wurde, möglichst wenige Kollisionen erzeugt. Für bekannte und beschränkte Eingabemengen können auch perfekte (kollisionsfreie) Hashfunktionen gefunden werden.

In der Datenspeicherung kann ein Hashwert verwendet werden, um die Speicherstelle der angefragten Daten zu berechnen, z. B. in einer Hashtabelle. Bei Prüfsummen verwendet man Hashwerte, um Übertragungsfehler zu erkennen. Ein Hashwert wird deshalb auch als englisch Fingerprint bezeichnet, da er eine nahezu eindeutige Kennzeichnung einer größeren Datenmenge darstellt, so wie ein Fingerabdruck einen Menschen nahezu eindeutig identifiziert. In der Kryptologie werden spezielle kryptographische Hashfunktionen verwendet, bei denen zusätzlich gefordert wird, dass es praktisch unmöglich ist, Kollisionen absichtlich zu finden.

Definition Bearbeiten

Eine Abbildung heißt Hashfunktion, wenn gilt. Insbesondere liefert eine Hashtabelle der Größe . Die Menge repräsentiert die Daten, die gehasht werden sollen, und wird auch die Menge der Schlüssel genannt; die Menge ist die Menge der möglichen Hashwerte. Typischerweise wird die Menge der Hashwerte als Anfangsstück der natürlichen Zahlen gewählt: . Diese Menge heißt dann auch Adressraum.

Typischerweise wird in der Praxis immer nur eine kleine Teilmenge der Schlüssel mit abgebildet. Die Menge sind dann die tatsächlich genutzten Hashwerte.

Das Verhältnis liefert den Belegungsfaktor.

Der Fall wird als Kollision bezeichnet. Eine injektive Hashfunktion heißt perfekt, u. a. weil sie keine Kollisionen erzeugt.

Kriterien Bearbeiten

  • Geringe Wahrscheinlichkeit von Kollisionen der Hashwerte für den Eingabewertebereich, also möglichst eine Gleichverteilung der Hashwerte auf die erwarteten Eingabewerte.
  • Surjektivität – Kein Ergebniswert (Hashwert) soll unmöglich sein, jedes Ergebnis (jeder Hashwert im definierten Wertebereich) soll tatsächlich vorkommen können.
  • Effizienz – Die Funktion muss schnell berechenbar sein, ohne großen Speicherverbrauch auskommen (der Speicherbedarf des Hashwertes soll deutlich kleiner sein als jener des Schlüssels / Eingabewertes) und sollte die Quelldaten (Eingabewerte) möglichst nur einmal lesen müssen.

Folgende Kriterien spielen je nach Anwendung eine unterschiedliche Rolle:

  • falls die Hashfunktion einen sortierten Zugriff in der Hashtabelle einer Datenbank erlauben soll: ordnungserhaltend
  • bei kryptologischen Hashfunktionen: Chaos oder Lawineneffekt – Die Hashfunktion soll eine gute Diffusion besitzen; ähnliche Quellelemente (Eingabewerte) sollen zu völlig verschiedenen Hashwerten führen. Im Idealfall verändert das Umkippen eines Bits in der Eingabe durchschnittlich die Hälfte aller Bits im resultierenden Hashwert.
  • bei kryptologischen Hashfunktionen: Konfusion – Vom Hashwert sollen keine Rückschlüsse auf den Eingabewert gemacht werden können.
  • bei kryptologischen Hashfunktionen: Unumkehrbarkeit – Es soll kein praktisches Verfahren möglich sein, das aus einem Hashwert den Eingabewert bestimmt.

Anwendungen Bearbeiten

Hashfunktionen werden typischerweise angewendet, um

  • einem komplexen Objekt eine Speicheradresse zuzuweisen. Zum Beispiel könnte „Max Mustermann“ im Ordner M abgelegt werden, dem ersten Buchstaben des Nachnamens.
  • eine kurze Prüfsumme zu dem Objekt zu berechnen. Beispiel sind die Prüfsumme einer ISBN und die zyklische Redundanzprüfung zur Erkennung von Übertragungsfehlern von Dateien.
  • einen Inhalt nahezu eindeutig, aber mit wenig Speicherplatz zu identifizieren, ohne etwas über den Inhalt zu verraten, zum Beispiel in der Kryptographie.

Je nach Anwendung hat man unterschiedliche Anforderungen an die Funktion. Gruppiert man beispielsweise eine Adresskartei nach dem ersten Buchstaben des Nachnamens, so spart man sich offensichtlich bei der Suche viel Zeit, denn man braucht nur einen von 26 Teilen zu durchsuchen. Diese Hashfunktion ist für den Menschen sehr praktisch, da sie sehr einfach zu berechnen ist, jedoch würde ein Computerprogramm andere Verfahren verwenden, um ein Adressbuch zu organisieren. Für das Programm ist es nämlich wichtig, möglichst wenige Kollisionen zu haben. Es gibt aber offenbar viele Namen, die mit demselben Anfangsbuchstaben beginnen, und sie kommen ungleichmäßig oft vor. Legt man also beispielsweise Personalakten nach diesem Prinzip ab, so hat man oftmals viele Akten im Ordner mit dem Buchstaben S, während der Ordner Q leer bleibt.

Die einstellige Quersumme ist eine sehr einfache Hashfunktion. Sie ordnet einer beliebigen Zahl eine einstellige Zahl zu, so wird beispielsweise 25 auf 2 + 5 = 7 abgebildet. Als Prüfsumme ist diese Quersumme aber nicht gut geeignet, da die Vertauschung von Ziffern – ein typischer Fall beim Abtippen von langen Zahlen – nicht erkannt wird. So hat auch die Zahl 52 dieselbe Quersumme 5 + 2 = 7. Prüfsummen wie bei der ISBN eines Buches oder die CRC-32-Prüfsumme einer Datei, z. B. beim Prüfen einer aus dem Internet heruntergeladenen Datei auf Übertragungsfehler, eignen sich besser, derartige Fehler zu erkennen.

Bei der Identifikation von Inhalten mit kryptographischen Hashfunktionen ist es nicht nur wichtig, dass sich der gesamte Hashwert mit allen Bits bei jeder kleinen Modifikation scheinbar zufällig ändert und dass es fast unmöglich ist, einen zweiten Inhalt mit demselben Hashwert zu erzeugen, um einen Komplettaustausch des Inhaltes zu vermeiden. Ebenso wichtig ist es, dass der Inhalt nicht aus dem Hashwert rekonstruiert werden kann. Hat man zwei Dokumente ausgetauscht und möchte beispielsweise am Telefon die erfolgreiche Übertragung überprüfen, so reicht es, am Telefon die Korrektheit des Hashwertes zu überprüfen. Wird das Gespräch abgehört, so wird dabei nichts über den Inhalt der Nachricht verraten, selbst falls Teile des Inhalts bereits bekannt sein sollten.

Datenbanken Bearbeiten

Datenbankmanagementsysteme verwenden Hashfunktionen, um Daten in großen Datenbeständen mittels Hashtabellen zu suchen. Darüber wird ein Datenbankindex realisiert.

Mittels Hashfunktionen kann zudem die Fragmentierung von Datensätzen realisiert werden. Dabei wird die Hashfunktion auf den Primärschlüssel des betreffenden Objektes angewandt. Das Ergebnis referenziert dann seinen Speicherort.

Auch für vergleichsweise kleine Datenmengen werden Hashfunktionen benutzt, beispielsweise in Kompressionsalgorithmen wie LZW.

Prüfsummen Bearbeiten

Prüfsummen sind ein einfaches Mittel, um die Plausibilität zur Erkennung von Veränderungen an übertragenen Daten zu erhöhen. Nur die Teilmenge der Datenvarianten, die bei Berechnung der Prüfsumme das gleiche Ergebnis wie das der Original-Daten erzeugen, kann noch als Verfälschung unerkannt bleiben. Mit mehreren verschiedenen passend erzeugten Prüfsummen kann die Wahrscheinlichkeit einer Kollision stark reduziert werden.

Ein Fehler ist immer feststellbar, wenn die berechnete Prüfsumme der empfangenen Daten sich von der übertragenen Prüfsumme, also der der Originaldaten, unterscheidet. Falls ein Fehler festgestellt wird, kann die Verfälschung auch ausschließlich in der Prüfsumme enthalten sein. Die Eignung verschiedener Hashfunktionen zur Prüfsummenberechnung hängt von deren Kollisionswahrscheinlichkeit ab.

Wenn die Prüfsumme vor gezielten Manipulationen der Daten schützen soll, wird eine kryptographische Hashfunktion verwendet, da hier nur mit sehr hohem Rechenaufwand eine Kollision gefunden werden kann.

Beispiele Bearbeiten

Hashwerte haben unter anderem bei P2P-Anwendungen aus verschiedenen Gründen eine wichtige Aufgabe. Die Hashwerte werden hier sowohl zum Suchen und Identifizieren von Dateien als auch zum Erkennen und Prüfen von übertragenen Dateifragmenten verwendet. So lassen sich große Dateien zuverlässig in kleinen Segmenten austauschen.

Zur Anwendung in P2P-Netzen kommen vor allem gestufte Hashfunktionen, bei denen für kleinere Teile einer Datei der Hashwert und dann aus diesen Werten ein Gesamtwert berechnet wird. Bei den Netzwerken Gnutella G2, Shareaza und Direct Connect sind dies zum Beispiel Tiger-Tree-Hash-Funktionen.

Das Auffinden von Dateien anhand des Hashwertes ihres Inhaltes ist zumindest in den USA als Softwarepatent geschützt. Der Inhaber verfolgt Programme und Firmen, die auf Basis dieses Systems die Suche von Dateien ermöglichen. Sogar Firmen, die im Auftrag der Recording Industry Association of America oder der Motion Picture Association Anbieter von unlizenzierten Inhalten ermitteln wollen, sind betroffen.

Bei der Programmierung von Internet-Anwendungen werden Hashfunktionen zum Erzeugen von Session-IDs genutzt, indem unter Verwendung von wechselnden Zustandswerten (wie Zeit, IP-Adresse) ein Hashwert berechnet wird.

Kryptologie Bearbeiten

Kryptographische Hashfunktionen besitzen spezielle Eigenschaften, in der Praxis sind es kollisionsresistente Einwegfunktionen. Sie werden verwendet, um Nachrichten zu signieren bzw. die Integrität von Daten sicherzustellen. Zum Hashen von Passwörtern, mit dem Ziel, sie sicher zu speichern oder daraus Schlüssel zu gewinnen, werden spezielle Hashfunktionen verwendet (z. B. aus der Klasse der "sicheren Hashalgorithmen"). Diese sind im Idealfall besonders aufwändig zu berechnen, um Brute-Force-Angriffe zu erschweren. Weiterhin müssen sie insbesondere den Eigenschaften der Konfusion und Unumkehrbarkeit genügen, damit das Klartextpasswort bzw. eine Menge von Kandidaten nicht ohne weiteres aus dem Schlüsselwert generierbar ist.

Hash-Algorithmen Bearbeiten

In der Praxis können oft heuristische Techniken anwendet werden, um eine gute Hashfunktion zu erstellen. Qualitative Informationen über die Verteilung der Schlüssel können in diesem Entwurfsprozess nützlich sein. Generell sollte eine Hashfunktion von jedem einzelnen Bit des Schlüssels abhängen, so dass sich zwei Schlüssel, die sich nur in einem Bit oder einer Bitfolge unterscheiden, unabhängig davon, ob die Folge am Anfang, am Ende oder in der Mitte des Schlüssels oder vorhanden ist, den gesamten Schlüssel-Hash auf verschiedene Werte abbildet. Daher ist eine Hashfunktion, die einfach einen Teil eines Schlüssels extrahiert, nicht geeignet. Wenn zwei Schlüssel einfach Permutationen voneinander sind, z. B. 256 und 625, sollten sie ebenfalls in unterschiedliche Werte gehasht werden.

Heuristischen Methoden sind Hashing durch Division und Hashing durch Multiplikation.

Hashing durch Division Bearbeiten

Bei dieser Methode wird ein Schlüssel einem Hashwert zugeordnet, indem der Rest des Schlüssels bei Division durch die Größe der Hashtabelle berechnet wird. Das heißt, die Hashfunktion ist definiert als

Weil nur eine einzige Divisionsoperation erforderlich ist, ist das Hashing durch Division ziemlich schnell. Wenn die Divisionsmethode verwendet wird, sollten bestimmte Werte für die Größe der Hashtabelle vermieden werden. Sie sollte keine Potenz einer Zahl sein. Wenn ist, dann ist der Hashwert immer gleich den letzten Bits von . Wenn wir nicht wissen, dass alle -Bit-Muster niedriger Ordnung gleich wahrscheinlich sind, ist es besser, die Hashfunktion so zu gestalten, dass sie von allen Bits des Schlüssels abhängt. Es hat sich gezeigt, dass die besten Ergebnisse mit der Divisionsmethode erzielt werden, wenn die Größe der Hashtabelle eine Primzahl ist. Eine Primzahl, die nicht zu nah bei einer Zweierpotenz liegt, ist oft eine gute Wahl für die Größe der Hashtabelle.

Hashing durch Multiplikation Bearbeiten

Bei dieser Methode wird der Schlüssel mit einer konstanten reellen Zahl im Bereich multipliziert und die Nachkommastellen von genommen. Dann wird dieser Wert mit der Größe der Hashtabelle multipliziert und mithilfe der Abrundungsfunktion der ganzzahlige Teil davon berechnet. Die Hashfunktion kann dargestellt werden als

Ein Vorteil besteht darin, dass die Größe der Hashtabelle nicht kritisch ist. Sie ist typischerweise eine Zweierpotenz, weil die Hashfunktion dann schneller implementiert werden kann. Obwohl diese Methode mit jeder reellen Zahl funktioniert, funktioniert sie mit einigen Werten besser als mit anderen.

Bekannte Hashfunktionen Bearbeiten

Bekannte Hashfunktionen sind zum Beispiel

Gitterbasierte Hashfunktionen Bearbeiten

Prüfsummen Bearbeiten

Kryptographische Hashfunktionen Bearbeiten

Nicht-kryptographische Hashfunktionen Bearbeiten

Hashfunktion Geschwindigkeit Entwickler Jahr
xxHash 5,40 GB/s Yann Collet 2012
MurmurHash 3a 2,70 GB/s Austin Appleby 2008
SBox 1,40 GB/s Bret Mulvey 2007
Lookup3 1,20 GB/s Bob Jenkins 2006
CityHash64 1,05 GB/s Geoff Pike & Jyrki Alakuijala 2011
FNV 0,55 GB/s Fowler, Noll, Vo 1991
SipHash/HighwayHash Jan Wassenberg & Jyrki Alakuijala 2016 / 2012

Passwort-Hashfunktionen Bearbeiten

Literatur Bearbeiten

Weblinks Bearbeiten

Wiktionary: Hashfunktion – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

Einzelnachweise Bearbeiten

  1. ↑ GeeksforGeeks: What are Hash Functions and How to choose a good Hash Function?
  2. C. P. Schnorr, Serge Vaudenay: Parallel FFT-hashing. In: Fast Software Encryption, pp 149–156, 1993
  3. K. Bentahar, D. Page, J. H. Silverman, M.-J. O. Saarinen, N.P. Smart: LASH. 2nd NIST Cryptographic Hash Workshop, 2006
  4. github.com
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Eine Hashfunktion oder Streuwertfunktion ist eine Abbildung die eine grosse Eingabemenge die Schlussel auf eine kleinere Zielmenge die Hashwerte abbildet Eine Hashfunktion ist daher im Allgemeinen nicht injektiv Die Eingabemenge kann Elemente unterschiedlicher Langen enthalten die Elemente der Zielmenge haben dagegen meist eine feste Lange Eine Hashfunktion die Namen auf Ganzzahlen abbildet Fur die Namen John Smith und Sandra Dee gibt es eine Kollision Der Name Hashfunktion stammt vom englischen Verb to hash das sich mit zerhacken ubersetzen lasst Der deutsche Name lautet Streuwertfunktion Beide Namen deuten darauf hin dass diese Funktionen normalerweise darauf angelegt sind die Daten zu verstreuen und zu zerhacken siehe auch Zerhacker in der Funktechnik Speziell in der Informatik verwendet man auch den Begriff Hash Algorithmus englisch hash algorithm da Hashfunktionen oftmals in Form eines Algorithmus spezifiziert werden der die Berechnung der mathematischen Funktion beschreibt Die Hash oder Streuwerte sind meist skalare Werte aus einer begrenzten Teilmenge der naturlichen Zahlen Eine gute Hashfunktion liefert dabei fur die Eingabedaten Werte derart dass zwei unterschiedliche Eingaben auch zu unterschiedlichen Ausgabewerten fuhren Eine Kollision tritt dann auf wenn unterschiedlichen Eingabedaten derselbe Hashwert zugeordnet wird Da die Menge der moglichen Hashwerte meist kleiner ist als die der moglichen Eingaben sind solche Kollisionen dann prinzipiell unvermeidlich weshalb es Verfahren zur Kollisionserkennung geben muss Eine gute Hashfunktion zeichnet sich dadurch aus dass sie fur die Eingaben fur die sie entworfen wurde moglichst wenige Kollisionen erzeugt Fur bekannte und beschrankte Eingabemengen konnen auch perfekte kollisionsfreie Hashfunktionen gefunden werden In der Datenspeicherung kann ein Hashwert verwendet werden um die Speicherstelle der angefragten Daten zu berechnen z B in einer Hashtabelle Bei Prufsummen verwendet man Hashwerte um Ubertragungsfehler zu erkennen Ein Hashwert wird deshalb auch als englisch Fingerprint bezeichnet da er eine nahezu eindeutige Kennzeichnung einer grosseren Datenmenge darstellt so wie ein Fingerabdruck einen Menschen nahezu eindeutig identifiziert In der Kryptologie werden spezielle kryptographische Hashfunktionen verwendet bei denen zusatzlich gefordert wird dass es praktisch unmoglich ist Kollisionen absichtlich zu finden Inhaltsverzeichnis 1 Definition 2 Kriterien 3 Anwendungen 3 1 Datenbanken 3 2 Prufsummen 3 2 1 Beispiele 3 3 Kryptologie 4 Hash Algorithmen 4 1 Hashing durch Division 4 2 Hashing durch Multiplikation 4 3 Bekannte Hashfunktionen 4 3 1 Gitterbasierte Hashfunktionen 4 3 2 Prufsummen 4 3 3 Kryptographische Hashfunktionen 4 3 4 Nicht kryptographische Hashfunktionen 4 3 5 Passwort Hashfunktionen 5 Literatur 6 Weblinks 7 EinzelnachweiseDefinition BearbeitenEine Abbildung h K S displaystyle h colon K rightarrow S nbsp heisst Hashfunktion wenn K S displaystyle K geq S nbsp gilt Insbesondere liefert h displaystyle h nbsp eine Hashtabelle der Grosse S displaystyle S nbsp Die Menge K displaystyle K nbsp reprasentiert die Daten die gehasht werden sollen und wird auch die Menge der Schlussel genannt die Menge S displaystyle S nbsp ist die Menge der moglichen Hashwerte Typischerweise wird die Menge der Hashwerte als Anfangsstuck der naturlichen Zahlen gewahlt S 0 m 1 displaystyle S subseteq left 0 dotsc m 1 right nbsp Diese Menge heisst dann auch Adressraum Typischerweise wird in der Praxis immer nur eine kleine Teilmenge der Schlussel K K displaystyle K subseteq K nbsp mit h displaystyle h nbsp abgebildet Die Menge S h k k K displaystyle S h k k in K nbsp sind dann die tatsachlich genutzten Hashwerte Das Verhaltnis b S S displaystyle beta frac left S right left S right nbsp liefert den Belegungsfaktor Der Fall k k h k h k displaystyle k not k land h k h k nbsp wird als Kollision bezeichnet Eine injektive Hashfunktion heisst perfekt u a weil sie keine Kollisionen erzeugt Kriterien BearbeitenGeringe Wahrscheinlichkeit von Kollisionen der Hashwerte fur den Eingabewertebereich also moglichst eine Gleichverteilung der Hashwerte auf die erwarteten Eingabewerte Surjektivitat Kein Ergebniswert Hashwert soll unmoglich sein jedes Ergebnis jeder Hashwert im definierten Wertebereich soll tatsachlich vorkommen konnen Effizienz Die Funktion muss schnell berechenbar sein ohne grossen Speicherverbrauch auskommen der Speicherbedarf des Hashwertes soll deutlich kleiner sein als jener des Schlussels Eingabewertes und sollte die Quelldaten Eingabewerte moglichst nur einmal lesen mussen Folgende Kriterien spielen je nach Anwendung eine unterschiedliche Rolle falls die Hashfunktion einen sortierten Zugriff in der Hashtabelle einer Datenbank erlauben soll ordnungserhaltend bei kryptologischen Hashfunktionen Chaos oder Lawineneffekt Die Hashfunktion soll eine gute Diffusion besitzen ahnliche Quellelemente Eingabewerte sollen zu vollig verschiedenen Hashwerten fuhren Im Idealfall verandert das Umkippen eines Bits in der Eingabe durchschnittlich die Halfte aller Bits im resultierenden Hashwert bei kryptologischen Hashfunktionen Konfusion Vom Hashwert sollen keine Ruckschlusse auf den Eingabewert gemacht werden konnen bei kryptologischen Hashfunktionen Unumkehrbarkeit Es soll kein praktisches Verfahren moglich sein das aus einem Hashwert den Eingabewert bestimmt Anwendungen BearbeitenHashfunktionen werden typischerweise angewendet um einem komplexen Objekt eine Speicheradresse zuzuweisen Zum Beispiel konnte Max Mustermann im Ordner M abgelegt werden dem ersten Buchstaben des Nachnamens eine kurze Prufsumme zu dem Objekt zu berechnen Beispiel sind die Prufsumme einer ISBN und die zyklische Redundanzprufung zur Erkennung von Ubertragungsfehlern von Dateien einen Inhalt nahezu eindeutig aber mit wenig Speicherplatz zu identifizieren ohne etwas uber den Inhalt zu verraten zum Beispiel in der Kryptographie Je nach Anwendung hat man unterschiedliche Anforderungen an die Funktion Gruppiert man beispielsweise eine Adresskartei nach dem ersten Buchstaben des Nachnamens so spart man sich offensichtlich bei der Suche viel Zeit denn man braucht nur einen von 26 Teilen zu durchsuchen Diese Hashfunktion ist fur den Menschen sehr praktisch da sie sehr einfach zu berechnen ist jedoch wurde ein Computerprogramm andere Verfahren verwenden um ein Adressbuch zu organisieren Fur das Programm ist es namlich wichtig moglichst wenige Kollisionen zu haben Es gibt aber offenbar viele Namen die mit demselben Anfangsbuchstaben beginnen und sie kommen ungleichmassig oft vor Legt man also beispielsweise Personalakten nach diesem Prinzip ab so hat man oftmals viele Akten im Ordner mit dem Buchstaben S wahrend der Ordner Q leer bleibt Die einstellige Quersumme ist eine sehr einfache Hashfunktion Sie ordnet einer beliebigen Zahl eine einstellige Zahl zu so wird beispielsweise 25 auf 2 5 7 abgebildet Als Prufsumme ist diese Quersumme aber nicht gut geeignet da die Vertauschung von Ziffern ein typischer Fall beim Abtippen von langen Zahlen nicht erkannt wird So hat auch die Zahl 52 dieselbe Quersumme 5 2 7 Prufsummen wie bei der ISBN eines Buches oder die CRC 32 Prufsumme einer Datei z B beim Prufen einer aus dem Internet heruntergeladenen Datei auf Ubertragungsfehler eignen sich besser derartige Fehler zu erkennen Bei der Identifikation von Inhalten mit kryptographischen Hashfunktionen ist es nicht nur wichtig dass sich der gesamte Hashwert mit allen Bits bei jeder kleinen Modifikation scheinbar zufallig andert und dass es fast unmoglich ist einen zweiten Inhalt mit demselben Hashwert zu erzeugen um einen Komplettaustausch des Inhaltes zu vermeiden Ebenso wichtig ist es dass der Inhalt nicht aus dem Hashwert rekonstruiert werden kann Hat man zwei Dokumente ausgetauscht und mochte beispielsweise am Telefon die erfolgreiche Ubertragung uberprufen so reicht es am Telefon die Korrektheit des Hashwertes zu uberprufen Wird das Gesprach abgehort so wird dabei nichts uber den Inhalt der Nachricht verraten selbst falls Teile des Inhalts bereits bekannt sein sollten Datenbanken Bearbeiten Datenbankmanagementsysteme verwenden Hashfunktionen um Daten in grossen Datenbestanden mittels Hashtabellen zu suchen Daruber wird ein Datenbankindex realisiert Mittels Hashfunktionen kann zudem die Fragmentierung von Datensatzen realisiert werden Dabei wird die Hashfunktion auf den Primarschlussel des betreffenden Objektes angewandt Das Ergebnis referenziert dann seinen Speicherort Auch fur vergleichsweise kleine Datenmengen werden Hashfunktionen benutzt beispielsweise in Kompressionsalgorithmen wie LZW Prufsummen Bearbeiten Hauptartikel Prufsumme Prufsummen sind ein einfaches Mittel um die Plausibilitat zur Erkennung von Veranderungen an ubertragenen Daten zu erhohen Nur die Teilmenge der Datenvarianten die bei Berechnung der Prufsumme das gleiche Ergebnis wie das der Original Daten erzeugen kann noch als Verfalschung unerkannt bleiben Mit mehreren verschiedenen passend erzeugten Prufsummen kann die Wahrscheinlichkeit einer Kollision stark reduziert werden Ein Fehler ist immer feststellbar wenn die berechnete Prufsumme der empfangenen Daten sich von der ubertragenen Prufsumme also der der Originaldaten unterscheidet Falls ein Fehler festgestellt wird kann die Verfalschung auch ausschliesslich in der Prufsumme enthalten sein Die Eignung verschiedener Hashfunktionen zur Prufsummenberechnung hangt von deren Kollisionswahrscheinlichkeit ab Wenn die Prufsumme vor gezielten Manipulationen der Daten schutzen soll wird eine kryptographische Hashfunktion verwendet da hier nur mit sehr hohem Rechenaufwand eine Kollision gefunden werden kann Beispiele Bearbeiten Hashwerte haben unter anderem bei P2P Anwendungen aus verschiedenen Grunden eine wichtige Aufgabe Die Hashwerte werden hier sowohl zum Suchen und Identifizieren von Dateien als auch zum Erkennen und Prufen von ubertragenen Dateifragmenten verwendet So lassen sich grosse Dateien zuverlassig in kleinen Segmenten austauschen Zur Anwendung in P2P Netzen kommen vor allem gestufte Hashfunktionen bei denen fur kleinere Teile einer Datei der Hashwert und dann aus diesen Werten ein Gesamtwert berechnet wird Bei den Netzwerken Gnutella G2 Shareaza und Direct Connect sind dies zum Beispiel Tiger Tree Hash Funktionen Das Auffinden von Dateien anhand des Hashwertes ihres Inhaltes ist zumindest in den USA als Softwarepatent geschutzt Der Inhaber verfolgt Programme und Firmen die auf Basis dieses Systems die Suche von Dateien ermoglichen Sogar Firmen die im Auftrag der Recording Industry Association of America oder der Motion Picture Association Anbieter von unlizenzierten Inhalten ermitteln wollen sind betroffen Bei der Programmierung von Internet Anwendungen werden Hashfunktionen zum Erzeugen von Session IDs genutzt indem unter Verwendung von wechselnden Zustandswerten wie Zeit IP Adresse ein Hashwert berechnet wird Kryptologie Bearbeiten Hauptartikel Kryptographische Hashfunktion Kryptographische Hashfunktionen besitzen spezielle Eigenschaften in der Praxis sind es kollisionsresistente Einwegfunktionen Sie werden verwendet um Nachrichten zu signieren bzw die Integritat von Daten sicherzustellen Zum Hashen von Passwortern mit dem Ziel sie sicher zu speichern oder daraus Schlussel zu gewinnen werden spezielle Hashfunktionen verwendet z B aus der Klasse der sicheren Hashalgorithmen Diese sind im Idealfall besonders aufwandig zu berechnen um Brute Force Angriffe zu erschweren Weiterhin mussen sie insbesondere den Eigenschaften der Konfusion und Unumkehrbarkeit genugen damit das Klartextpasswort bzw eine Menge von Kandidaten nicht ohne weiteres aus dem Schlusselwert generierbar ist Hash Algorithmen BearbeitenIn der Praxis konnen oft heuristische Techniken anwendet werden um eine gute Hashfunktion zu erstellen Qualitative Informationen uber die Verteilung der Schlussel konnen in diesem Entwurfsprozess nutzlich sein Generell sollte eine Hashfunktion von jedem einzelnen Bit des Schlussels abhangen so dass sich zwei Schlussel die sich nur in einem Bit oder einer Bitfolge unterscheiden unabhangig davon ob die Folge am Anfang am Ende oder in der Mitte des Schlussels oder vorhanden ist den gesamten Schlussel Hash auf verschiedene Werte abbildet Daher ist eine Hashfunktion die einfach einen Teil eines Schlussels extrahiert nicht geeignet Wenn zwei Schlussel einfach Permutationen voneinander sind z B 256 und 625 sollten sie ebenfalls in unterschiedliche Werte gehasht werden Heuristischen Methoden sind Hashing durch Division und Hashing durch Multiplikation 1 Hashing durch Division Bearbeiten Bei dieser Methode wird ein Schlussel einem Hashwert zugeordnet indem der Rest des Schlussels bei Division durch die Grosse der Hashtabelle berechnet wird Das heisst die Hashfunktion h displaystyle h nbsp ist definiert als h k e y k e y m o d t a b l e s i z e displaystyle h mathrm key mathrm key mathrm mod mathrm tablesize nbsp Weil nur eine einzige Divisionsoperation erforderlich ist ist das Hashing durch Division ziemlich schnell Wenn die Divisionsmethode verwendet wird sollten bestimmte Werte fur die Grosse der Hashtabelle vermieden werden Sie sollte keine Potenz einer Zahl sein Wenn t a b l e s i z e r p displaystyle mathrm tablesize r p nbsp ist dann ist der Hashwert h k e y displaystyle h mathrm key nbsp immer gleich den letzten Bits von k e y displaystyle mathrm key nbsp Wenn wir nicht wissen dass alle p displaystyle p nbsp Bit Muster niedriger Ordnung gleich wahrscheinlich sind ist es besser die Hashfunktion so zu gestalten dass sie von allen Bits des Schlussels abhangt Es hat sich gezeigt dass die besten Ergebnisse mit der Divisionsmethode erzielt werden wenn die Grosse der Hashtabelle eine Primzahl ist Eine Primzahl die nicht zu nah bei einer Zweierpotenz liegt ist oft eine gute Wahl fur die Grosse der Hashtabelle 1 Hashing durch Multiplikation Bearbeiten Bei dieser Methode wird der Schlussel k displaystyle k nbsp mit einer konstanten reellen Zahl c displaystyle c nbsp im Bereich 0 lt c lt 1 displaystyle 0 lt c lt 1 nbsp multipliziert und die Nachkommastellen von k c displaystyle k cdot c nbsp genommen Dann wird dieser Wert mit der Grosse der Hashtabelle multipliziert und mithilfe der Abrundungsfunktion der ganzzahlige Teil davon berechnet Die Hashfunktion h displaystyle h nbsp kann dargestellt werden als h k e y f l o o r t a b l e s i z e k e y c m o d 1 displaystyle h mathrm key mathrm floor mathrm tablesize cdot mathrm key cdot c mathrm mod 1 nbsp Ein Vorteil besteht darin dass die Grosse der Hashtabelle nicht kritisch ist Sie ist typischerweise eine Zweierpotenz weil die Hashfunktion dann schneller implementiert werden kann Obwohl diese Methode mit jeder reellen Zahl c displaystyle c nbsp funktioniert funktioniert sie mit einigen Werten besser als mit anderen 1 Bekannte Hashfunktionen Bearbeiten Bekannte Hashfunktionen sind zum Beispiel Brent Hashing Divisions Rest Methode Doppel Hashing Kuckucks Hashing Multiplikative Methode Mittquadratmethode Zerlegungsmethode ZiffernanalyseGitterbasierte Hashfunktionen Bearbeiten Ajtai Micciancio Peikert Rosen Schnelle Fourier Transformation FFT Hashfunktion 2 LASH 3 Prufsummen Bearbeiten Fletcher s Checksum Adler 32 CRC Zyklische Redundanzprufung Paritat QuersummeKryptographische Hashfunktionen Bearbeiten MD2 MD4 MD5 Secure Hash Algorithm SHA RIPEMD 160 Tiger HAVAL WhirlpoolNicht kryptographische Hashfunktionen Bearbeiten Hashfunktion Geschwindigkeit Entwickler JahrxxHash 5 40 GB s Yann Collet 2012MurmurHash 3a 2 70 GB s Austin Appleby 2008SBox 1 40 GB s Bret Mulvey 2007Lookup3 1 20 GB s Bob Jenkins 2006CityHash64 1 05 GB s Geoff Pike amp Jyrki Alakuijala 2011FNV 0 55 GB s Fowler Noll Vo 1991SipHash HighwayHash 4 Jan Wassenberg amp Jyrki Alakuijala 2016 2012Passwort Hashfunktionen Bearbeiten LM Hash PBKDF2 Bcrypt Scrypt Argon2Literatur BearbeitenDonald E Knuth The Art of Computer Programming 2 Auflage Volume 3 Addison Wesley 1998 ISBN 0 201 89685 0 S 513 ff Thomas H Cormen Charles E Leiserson Ronald L Rivest Clifford Stein Algorithmen Eine Einfuhrung 2 Auflage Oldenbourg Munchen Wien 2007 ISBN 978 3 486 58262 8 S 221 ff Lianhua Chi Xingquan Zhu Hashing Techniques A Survey and Taxonomy In ACM Computing Surveys CSUR Band 50 Nr 1 April 2017 11 doi 10 1145 3047307 Weblinks Bearbeiten nbsp Wiktionary Hashfunktion Bedeutungserklarungen Wortherkunft Synonyme Ubersetzungen CRC Press Handbook of Applied Cryptography Kapitel 9 PDF 471 kB Konstruktion von Hashfunktionen PDF 841 kB Online Generator fur Hashberechnungen md sha ripemd whirlpool tiger snefru gost adler cc salsa haval Einzelnachweise Bearbeiten a b c GeeksforGeeks What are Hash Functions and How to choose a good Hash Function C P Schnorr Serge Vaudenay Parallel FFT hashing In Fast Software Encryption pp 149 156 1993 K Bentahar D Page J H Silverman M J O Saarinen N P Smart LASH 2nd NIST Cryptographic Hash Workshop 2006 github com Abgerufen von https de wikipedia org w index php title Hashfunktion amp oldid 239423250