Hashes: Unterschied zwischen den Versionen

Aus Xinux Wiki
Zur Navigation springen Zur Suche springen
 
(40 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
 
=Grundlagen=
 
=Grundlagen=
−
Eine Hashfunktion (auch Streuwertfunktion) ist eine Abbildung, die eine große Eingabemenge (die Schlüssel) auf eine kleinere Zielmenge (die Hashwerte) abbildet. Der Name „Hashfunktion“ stammt vom englischen Verb to hash, das sich als „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“. Speziell in der Informatik verwendet man auch den Begriff Hash-Algorithmus, da Hashfunktionen oftmals in Form eines Algorithmus statt einer mathematischen Funktion spezifiziert werden. Eine „gute“ Hashfunktion liefert dabei für die (erwarteten) Eingabedaten Werte so, dass zwei unterschiedliche Eingaben auch zu unterschiedlichen Ausgabewerten führen. 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.
+
==Hashfunktion==
 +
*Eine Hashfunktion (auch Streuwertfunktion) ist eine Abbildung, die eine große Eingabemenge (die Schlüssel) auf eine kleinere Zielmenge (die Hashwerte) abbildet.  
 +
*Eine „gute“ Hashfunktion liefert dabei für die (erwarteten) Eingabedaten Werte so, dass zwei unterschiedliche Eingaben auch zu unterschiedlichen Ausgabewerten führen.
 +
*Ein Hashwert wird deshalb auch als englisch Fingerprint bezeichnet, da er eine nahezu eindeutige Kennzeichnung einer größeren Datenmenge darstellt.
 +
==Kollisionen==
 +
*Eine sog. 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.
 +
*Eine gute Hashfunktion zeichnet sich dadurch aus, dass sie für die Eingaben, für die sie entworfen wurde, möglichst wenige Kollisionen erzeugt.
 +
=Funktion=
 +
;Auf Rechner1 wird aus den Daten ein Hash-Rechner1 gebildet
 +
{{#drawio:hash}}
  
−
Eine sog. 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.
 
  
−
In der Datenspeicherung kann ein Hashwert verwendet werden, um die Speicherstelle der angefragten Daten zu berechnen (z. B. Hashtabelle). Bei Prüfsummen verwendet man Hashwerte, um Übertragungsfehler zu erkennen. In der Kryptologie werden spezielle kryptologische Hashfunktionen verwendet, bei denen zusätzlich gefordert wird, dass es praktisch unmöglich ist, Kollisionen absichtlich zu finden.
+
;Rechner1 schickt Daten und Hash an Rechner2
 +
{{#drawio:r1-r2}}
 +
 
 +
 
 +
;Rechner2 bidet aus den empfangenen Daten den Hash-Rechner2
 +
{{#drawio:hash-r2}}
 +
 
 +
;Ergebnis
 +
 
 +
[[Datei:Hash-ergebnis.png]]
 +
 
 
=Anwendungen=
 
=Anwendungen=
 
Hashfunktionen haben verschiedene Anwendungsfelder. Dabei lassen sich drei große Gebiete unterteilen:
 
Hashfunktionen haben verschiedene Anwendungsfelder. Dabei lassen sich drei große Gebiete unterteilen:
 
*Datenbanken
 
*Datenbanken
 +
**In der Datenspeicherung kann ein Hashwert verwendet werden, um die Speicherstelle der angefragten Daten zu berechnen (z. B. Hashtabelle).
 
*Prüfsummen
 
*Prüfsummen
 +
**Bei Prüfsummen verwendet man Hashwerte, um Übertragungsfehler zu erkennen.
 
*Kryptologie
 
*Kryptologie
 +
**In der Kryptologie werden spezielle kryptologische Hashfunktionen verwendet, bei denen zusätzlich gefordert wird, dass es praktisch unmöglich ist, Kollisionen absichtlich zu finden.
 +
 
=Kryptologische Hashfunktionen=
 
=Kryptologische Hashfunktionen=
−
Eine kryptologische Hashfunktion oder kryptographische Hashfunktion ist eine spezielle Form der Hashfunktion, welche kollisionsresistent sein sollte und nach Definition immer eine Einwegfunktion ist. Kryptologische Hashfunktionen werden in schlüssellose und schlüsselabhängige eingeteilt. Schlüssellose Hashfunktionen werden ferner unterteilt in Einweg-Hashfunktionen (englisch: One-Way Hash Function oder OWHF) und kollisionsresistente Hashfunktionen (englisch: Collision Resistant Hash Functions, CRHFs). Schlüsselabhängige Hashfunktionen werden auch Message Authentication Codes (MAC) genannt. Zu diesen zählen Konstrukte wie HMAC, CBC-MAC oder UMAC.
+
*Eine kryptologische Hashfunktion oder kryptographische Hashfunktion ist eine spezielle Form der Hashfunktion, welche kollisionsresistent sein sollte und nach Definition immer eine Einwegfunktion ist.
 +
*Kryptologische Hashfunktionen werden in schlüssellose und schlüsselabhängige eingeteilt.
 +
=Einfaches Beispiel Quersumme=
 +
*Fritz bekommt als Rechnaufgabe auf <math>x</math> auszurechnen. <math>x = 9^2\times 2+7</math>
 +
*Die Quersumme beträgt 16.
 +
*Fritz rechnet aus 169 aus.
 +
*Fritz zählt <math>1+6+9=16</math>
 +
*Ergebnis stimmt.
 
=Merkle-Damgård-Verfahren=
 
=Merkle-Damgård-Verfahren=
−
In der Merkle-Damgård-Konstruktion wird eine Kompressionsfunktion iteriert.
+
*Bei der Merkle-Damgård-Konstruktion wird die eingegebene Nachricht M zuerst in Blöcke fester Länge geteilt
−
Eine Kompressionsfunktion nimmt als Eingabe zwei Bitfolgen der Längen n und m und gibt eine Bitfolge der Länge n aus. Zusätzlich ist sie eine Einwegfunktion, es sollte also schwer sein, zu einer gegebenen Ausgabe passende Eingabewerte zu finden. Oft wird eine Blockchiffre als Kompressionsfunktion benutzt, die Eingaben werden dann als Nachricht und Schlüssel benutzt.
+
*Der letzte Block wird mit zusätzlichen Bits aufgefüllt, so dass die Eingabelänge ein ganzzahliges Vielfaches der Blocklänge beträgt.
 +
*Die Funktion hat als Input einen Nachrichtenblock und den Wert des letzten Hashberechnung(ausser beim ersten Block).
 +
*Der Output entspricht dem Wert der neuen Hashberechnung.
 +
*Der Hashwert der gesamten Nachricht ist der Hashwert des letzten Blocks:
 +
 
 +
: <math>\begin{align}
 +
H\left(0\right)  & = IV \\
 +
H\left(i \right) & = f\left(M\left(i \right),H\left(i-1\right)\right), \qquad i=1,2,\dotsc,t \\
 +
h\left(M \right) & = H(t)
 +
\end{align}</math>
 +
IV bezeichnet einen festen Startwert (initial value).  
 +
 
  
−
Bei der Merkle-Damgård-Konstruktion wird die eingegebene Nachricht M zuerst in Blöcke fester Länge geteilt und mit zusätzlichen Bits aufgefüllt, so dass die Eingabelänge ein ganzzahliges Vielfaches der Blocklänge beträgt. Die Kompressionsfunktion hat als Input einen Nachrichtenblock und den Output der vorherigen Nachrichtenblöcke. Der Hashwert der gesamten Nachricht ist der Hashwert des letzten Blocks:
 
−
*H(0) = IV
 
−
*H(i) = f(M(i),H(i-1)),          i=1,2,...,t
 
−
*h(M) = H(t)
 
−
*IV bezeichnet einen Startwert (''initial value'').
 
 
[[Datei:Merkle-Damgard-1.png]]
 
[[Datei:Merkle-Damgard-1.png]]
 +
 +
=Links=
 +
*https://de.wikipedia.org/wiki/Hashfunktion
 +
*https://de.wikipedia.org/wiki/Kryptologische_Hashfunktion

Aktuelle Version vom 15. Juni 2021, 16:41 Uhr

Grundlagen

Hashfunktion

  • Eine Hashfunktion (auch Streuwertfunktion) ist eine Abbildung, die eine große Eingabemenge (die Schlüssel) auf eine kleinere Zielmenge (die Hashwerte) abbildet.
  • Eine „gute“ Hashfunktion liefert dabei für die (erwarteten) Eingabedaten Werte so, dass zwei unterschiedliche Eingaben auch zu unterschiedlichen Ausgabewerten führen.
  • Ein Hashwert wird deshalb auch als englisch Fingerprint bezeichnet, da er eine nahezu eindeutige Kennzeichnung einer größeren Datenmenge darstellt.

Kollisionen

  • Eine sog. 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.
  • Eine gute Hashfunktion zeichnet sich dadurch aus, dass sie für die Eingaben, für die sie entworfen wurde, möglichst wenige Kollisionen erzeugt.

Funktion

Auf Rechner1 wird aus den Daten ein Hash-Rechner1 gebildet


Rechner1 schickt Daten und Hash an Rechner2


Rechner2 bidet aus den empfangenen Daten den Hash-Rechner2
Ergebnis

Hash-ergebnis.png

Anwendungen

Hashfunktionen haben verschiedene Anwendungsfelder. Dabei lassen sich drei große Gebiete unterteilen:

  • Datenbanken
    • In der Datenspeicherung kann ein Hashwert verwendet werden, um die Speicherstelle der angefragten Daten zu berechnen (z. B. Hashtabelle).
  • Prüfsummen
    • Bei Prüfsummen verwendet man Hashwerte, um Übertragungsfehler zu erkennen.
  • Kryptologie
    • In der Kryptologie werden spezielle kryptologische Hashfunktionen verwendet, bei denen zusätzlich gefordert wird, dass es praktisch unmöglich ist, Kollisionen absichtlich zu finden.

Kryptologische Hashfunktionen

  • Eine kryptologische Hashfunktion oder kryptographische Hashfunktion ist eine spezielle Form der Hashfunktion, welche kollisionsresistent sein sollte und nach Definition immer eine Einwegfunktion ist.
  • Kryptologische Hashfunktionen werden in schlüssellose und schlüsselabhängige eingeteilt.

Einfaches Beispiel Quersumme

  • Fritz bekommt als Rechnaufgabe auf auszurechnen.
  • Die Quersumme beträgt 16.
  • Fritz rechnet aus 169 aus.
  • Fritz zählt
  • Ergebnis stimmt.

Merkle-Damgård-Verfahren

  • Bei der Merkle-Damgård-Konstruktion wird die eingegebene Nachricht M zuerst in Blöcke fester Länge geteilt
  • Der letzte Block wird mit zusätzlichen Bits aufgefüllt, so dass die Eingabelänge ein ganzzahliges Vielfaches der Blocklänge beträgt.
  • Die Funktion hat als Input einen Nachrichtenblock und den Wert des letzten Hashberechnung(ausser beim ersten Block).
  • Der Output entspricht dem Wert der neuen Hashberechnung.
  • Der Hashwert der gesamten Nachricht ist der Hashwert des letzten Blocks:

IV bezeichnet einen festen Startwert (initial value).


Merkle-Damgard-1.png

Links

Abgerufen von „http://wiki.ixheim.de/index.php?title=Hashes&oldid=24105“