Diskussion:Hashfunktion/Archiv/1

aus Wikipedia, der freien Enzyklopädie
< Diskussion:Hashfunktion
Letzter Kommentar: vor 4 Jahren von H3xc0d3r in Abschnitt nicht injektiv = surjektiv?
Zur Navigation springen Zur Suche springen

Problematik

Letzter Kommentar: vor 14 Jahren4 Kommentare3 Personen sind an der Diskussion beteiligt

Nehmen wir an, wir haben zwei total unterschiedliche Dateien, die aber denselben hash-wert liefern. das ist doch möglich oder? wie kann das vermieden werden? wie groß ist diese wahrscheinlchkeit, dass zwei dateien den selben hashwert besitzen, bei anerkannten hashwert-programmen (z.b. md5?)

es wäre schön, wenn auf diese problematik eingegangen werden könnte.

Danke, --Abdull 15:33, 22. Dez 2004 (CET)

Theoretisch möglich

Dies ist theoretisch möglich aber praktisch kaum denkbar. Vollständig ausschließen kann man solche Kollisionen nur, wenn der Wertebereich der Hashfunktion mindestens so groß ist wie der Definitionsbereich (mögliche Daten). Dies widerspricht jedoch der Zielsetzung einen möglichst kleinen Prüfwert zu bilden. Bei 128-Bitwerten (md5) ist jedoch eine zufällige Übereinstimmung praktisch auszuschließen. Wegen bekannter Schwächen in der md5-Funktion ist es jedoch möglich Kollisionen zu berechnen. Für SHA-1 wurden solche Kollisionen bis heute noch nicht berechnet (soweit dies bekannt ist). Es ist jedoch nach neuesten Erkenntnissen mit beträchtlichem Rechenaufwand möglich solche Kollisionen schneller als mit Brute Force zu finden. Benutzer:Fsswsb 29.05.06

Der Wertebereich des Hashwertes bestimmt die Kollisionswahrscheinlichkeit. Beispiel: Eine Datenmenge wird auf eine natürliche Zahl zwischen 0 und 9 abgebildet. Dann gibt es 10 Hashwerte. Wahrscheinlichkeit der Kollision: 10%. Anton 22:04, 22. Dez 2004 (CET)
Die Rechnung stimmt so nicht ganz. Dies hängt auch von den Daten und dem verwendeten Algorithmus ab. Ich versuche es einfach zu erklären: Wenn ich eine Reihe von 26 Buchstaben habe, in dem jeder Buchstabe einmal vorkommt, beträgt die Wahrscheinlichkeit einen bestimten Buchstaben zu treffen 1:26. Nimmt man einen deutschen Text und tippt auf einen beliebigen Buchstaben, dann ist die Wahrscheinlichkeit ein e zu treffen erheblich höher als ein y zu erwischen. Deine Rechnung stimmt dann, wenn der Algorithmus zu einer gleichmäsigen Verteilung der Hashwerte führt und somit den Wertebereich voll ausnutzt. Dies ist dann der Fall, wenn bei einer kleinen Änderung sich der Hashwert vollständig ändert - im Inealfall führt eine Änderung eines Bits im Original zu einer Veränderung von 50% der Hashbits.
Benutze mehrere verschiedene Hashfunktionen, dann sinkt die Wahrscheinlichkeit von praktisch kaum denkbar wieder auf praktisch unmöglich. --Stepwiz 23:25, 15. Dez. 2006 (CET)
Naja, zwei Hashfunktionen ist ja wohl dasselbe wie eien Hashfunltion mit entsprechend mehr bits.--Hagman 23:44, 4. Jul. 2007 (CEST)
Nehmen wir an, jeder von ca. 10 Milliarden Erdbewohnern hat eine Festplatte mit einer Kapazität von ein Terabyte und lagert dor Unmengen von Word-Dokumenten, die ja selbst "leer" schon ca. 40KB groß sind. Dann sind das ca. oder Dateien. Nehmen wir diese alle als verschieden an, wie wahrscheinlich ist dann (bei einer perfekten 128-bit Hashfunktion) das Auftreten einer Hash-Dublette? Da gilt, ist selbst in diesem Szenario eine Kollision ziemlich unwahrscheinlich (vgl Geburtstagsanriff).--Hagman 23:44, 4. Jul. 2007 (CEST)
Du denkst zu sehr in einer bestimmten Anwendung. Ich kann die Identitätsfunktion als Hashfunktion verwenden. Habe ich nur 10 mögliche Eingabewerte, und Platz für 10 Buckets, so ist das kein Problem. Natürlich _will_ man in der Regel die Hashtabelle wesentlich kleiner wählen als der mögliche Eingabebereich. Dann muss man auch Kollisionen in Kauf nehmen, will diese aber minimieren und eine effiziente Strategie zur Handhabung von Kollisionen haben. "perfekte" Hashfunktionen (sprich, kollissionsfrei) werden normalerweise nur für _statische_, _komplexe_ Schlüssel berechnet, d.h. wenn nur Such-Anfragen kommen. Nehme ich einen Webserver, der eine endliche, statische Menge an URLs ausliefert. Statisch im Sinne als dass ich es mir leisten kann, bei einer Änderung die komplette Hashtabelle inklusive Hashfunktion neu zu optimieren. Verwende ich eine klassische Hashfunktion und Hashtabelle, so muss ich mit Kollisionen rechnen, oder die Tabelle erheblich größer machen als die Eingabeschlüssel. Alternativ kann ich aber eine optimierte Hashfunktion suchen, die eben garantiert keine Kollisionen liefert für diese Wertemenge und Tabelle. Dann brauche ich keine Kollisionsbehandlung, was den Webserver schneller machen kann. Das ganze geh aber wie gesagt nur, wenn ich "selten neue schlüssel habe". Und man muss aufpassen, dass die Berechnung des Hashfunktion nicht teurer wird als die Kollisionsbehandlung. Bei Objekten mit einem einfachen Schlüssel (beispielsweise eines Integers oder eben eines Strings) gibt es ja ziemlich "billige" Hashfunktionen, die wenig genug Kollisionen auf realen Werten aufweisen. Eine derartige Optimierung kann übrigens bereits einfach das probieren verschiedener "Salts" sein, bis man eben keine oder kaum Kollisionen bekommt. Die so gefundene optimierte Hashfunktion hat dann keine Mehrkosten gegenüber dem Startwert "0". --Chire 15:27, 24. Mai 2010 (CEST)

Definition unvollständig

Letzter Kommentar: vor 19 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

Es geht mitnichten nur darum irgendwelche Texte zu verkleinern um sie besser vergleichen zu können. Es geht darum eine Datenstruktur aufzubauen in der die Schlüsselsuche eine Komplexität von O(1) hat - das findet sich leider nirgends in dem Artikel Erwähnung.

Du meinst einen Hashtable, hier reden wir aber ueber eine Funktion, die einen Hash berechnet. Du hast aber recht, dass es da einen Zusammenhang gibt. Ausserdem findet sie Anwendung in der Verschluesselung von Passwoertern.

Gruss -- Sparti 22:08, 23. Mai 2005 (CEST)

Kommentar zu meinen Überarbeitungen vom 10.8.05 (85.233.18.16 = --Gerhard Buntrock 21:58, 10. Aug 2005 (CEST) )

Speziell habe ich mich bemüht ein anschaulicheres Beispiel vorzustellen. Das mit der Endziffer find ich zu flach, um etwas intuitiv klar zu machen. Für eine Kürzung hätte ich eher das Endzifferbeispiel gestrichen.

Schön finde ich, dass Squizzz meine neue Definition dringelassen hat. Sie ist meiner Ansicht jetzt korrekt und hält auch den meisten Ansprüchen stand.

Gruss --Gerhard Buntrock 21:58, 10. Aug 2005 (CEST)

Hash-Funktion injektiv?

Letzter Kommentar: vor 13 Jahren7 Kommentare4 Personen sind an der Diskussion beteiligt

Das bezweifele ich. Die Hash-Funktion ist surjektiv, und zusätzlich nicht injektiv. Das wäre ja auch ein Unding. Ich würde es trotzdem lieber erst hier diskutieren, bevor ich das im Artikel ändere. --84.130.76.132 19:09, 29. Sep 2005 (CEST)

Antwort: Alles persönliche Meinung: Injektiv bringt nun wirklich nichts. Surjektiv sollte die Hashfunktion im Idealfall sein. Aber es ist keine Voraussetzung. --Squizzz 19:27, 29. Sep 2005 (CEST)
Surjektivität ist Voraussetzung um eine "gute" Hash-Funktion zu haben. Ansonsten würde ich ja nur Kollisionen haben bzw. es gäbe einen Isomorphismus zwischen Quell- und Zielmenge. Das macht dann eine Hash-Funktion in der Anwendung nutzlos. --84.130.76.132 23:34, 29. Sep 2005 (CEST)
Wieso sollet man (viele) Kollisionen haben, wenn die Funktion nicht Surjektiv ist?? -- sparti 07:52, 30. Sep 2005 (CEST)
Stimmt. Ich sollte erst überlegen und dann schreiben. Gerade durch Surjektivität erreiche ich die Gefahr von Kollisionen. Aber gerade die Surjektivität ist der Sinn einer Hash-Funktion. --84.130.81.51 16:58, 30. Sep 2005 (CEST)
Das ist zwar schon richtiger, aber immer noch nicht ganz korrekt. Bei Indexverfahren moechte ich natuerlich keine Kollisionen, sie lassen sich nur in der Praxis nicht vermeiden, da irgendwann die Anzahl der Elemente groesser ist, als der Wertebereich. In der Kryptographie hingegen moecht ich auf keinen Fall Injektivitaet. -- Gruss sparti 21:55, 30. Sep 2005 (CEST)
"Eine Abbildung heißt Hashfunktion, wenn gilt." Das schließt für mich Injektivität aus, das für Injektivität gelten muss aber ich lasse mich gerne korrigieren! (nicht signierter Beitrag von 87.176.217.128 (Diskussion) 14:58, 23. Mai 2010 (CEST))
Falsch. Beispiel für eine injektive Funktion die deine Bedingung nicht erfüllt: die Identität. --Chire 15:06, 24. Mai 2010 (CEST)
Eine nicht-surjektive Hashfunktion lässt Buckets leer. Dadurch steigt zwangsläufig die Gefahr von Kollisionen, wenn der Füllgrad der Tabelle steigt. Insbesondere ist ein Füllgrad von 100% ohne Kollisionen dann unmöglich. Ist deine Funktion injektiv sind Kollisionen ausgeschlossen - daraus folgt in diesem Falle, dass deine Tabelle nie zu 100% gefüllt sein kann; das reduziert natürlich die Effizient ein wenig. Optimal wäre eine injektive und gleichzeitig surjektive Hashfunktion, wenn du vollständige Daten hast. --Chire 15:06, 24. Mai 2010 (CEST)

Schön wenn eine Hashfunktion injektiv wäre, dann gäbe es keine Kollisionen und alle Hashverfahren währen perfekt !!! Bezüglich Kollisionen sollte man das Geburtstag-Paradoxon beachten, was besagt, das man auf jeden Fall schon Kollisionen hat bevor die Hashtabelle voll ist, wenn man Gleichverteilung der Schlüssel auf den Adressbereich der Hashtabelle voraussetzt. z.B. hat man bei einer Tabelle mit 365 Adressen schon nach 27 zufälligen Einträgen eine Kollision. Oder anders ausgedrückt, wenn man 27 zufällig gewählte Personen nach ihrem Geburtstag fragt, dann haben zwei am gleichen Tag Geburtstag (Kollision!!!).

Das Geburtstagsparadoxon passt hier nicht. Wenn du die Personen nach Geburtstag in der Tabelle ablegst, verwendet du bereits eine nicht-injektive Funktion (nämlich die Abbildung auf den Geburtstag!). Egal mit welcher perfekten Hashfunktion du das danach kombinierst, die Verkettung ist nicht injektiv! - sprich: wenn der Schlüssel bereits nicht eindeutig ist, brauche ich nicht nach einer perfekten Hashfunktion suchen. --Chire 15:06, 24. Mai 2010 (CEST)

In der Kryptographie mancht man den möglichen Adressbereich so groß, dass man eine Kollisionen unwahrscheinlich ist, da man die Werte nicht in eine Hashtabelle eintragen muß. Bei 2^64 und mehr wird das auch schwierig, d.h. z.B. es ist unwahrscheinlich, das zwei acht stellige Passwörter auf den gleichen Hashwert abgebildet werden, auch wenn sie sich nur in einem Zeichen unterscheiden.

Hilfestellung zur Injektivität, Surjektivität und Bijektivität, sowie Isomorphismus: Eine Abbildung ist injektiv, wenn das Urbild eines Elementes der Zielmenge eindeutig ist. Sie ist surjektiv, wenn es kein gibt, für das gilt. Mit anderen Worten: Das Bild von ist gleich der Zielmenge. Formal: Zuletzt: ist bijektiv genau dann, wenn sie sowohl injektiv als auch surjektiv ist. Existiert eine bijektive Abbildung zwischen Strukturen und , dann sind diese zueinander isomorph.--84.58.151.165 02:14, 16. Jan 2006 (CET)
P.S. in realen Implementierungen wird man oft mehr als eine Hashfunktion verwenden. Typischerweise bildet die erste Hashfunktion die Eingabedaten auf einen Integer-Wert ab. Anschließend wird dieser Integer-Wert "gekürzt" so dass er für die gewählte Tabellengröße passt (die meisten werden keine Hashtabelle mit 2^32 Buckets anlegen wollen!). Dies geschieht meist durch Modulo (gerne mit einer Primzahl) bzw. durch ein logisches "und" (bei Zweierpotenzen). Dieser letzte Schritt ist offensichtlich nicht injektiv. Die Suche nach einer perfekten Hashfunktion in so einer Implementierung ist dann natürlich nicht umbedingt sinnvoll. (Mal davon abgesehen, dass es auch für den ersten Schritt oft gar keine injektive Funktion geben kann) --Chire 15:06, 24. Mai 2010 (CEST)

Eine surjektive aber nicht bijektive Hashfunktion ist doch für Kollisionen geradezu prädestiniert, das sollte beim Abschnitt "Kriterien für eine gute Hashfunktion" geändert werden. --Nirvana134 18:13, 14. Jun. 2011 (CEST)

In der Kryptographie ist das nicht unerwünscht. sie sollen nur nicht vorhersagbar sein! Du darfst nicht nur an Hashtabellen denken! --87.174.53.81 00:05, 15. Jun. 2011 (CEST)

Bekannte Hashfunktionen

Wäre es nicht genauer, von bekannten Typen von Hashfunktionen zu sprechen? Auch könnte die Auflistung dann durch weitere wichtige Typen ergänzt werden: universelles Hashing, perfektes Hashing und offene Adressierung. Die dazugehörigen Artikel existieren meines Wissens auch noch nicht.--Paschelino 02:23, 16. Jan 2006 (CET)

universelle Hashfunktionen gehen auf die Paper "Universal Classes of Hash Funktions" von J. Lawrence Carter und Mark N. Wegman Journal of Computer and System Sciences 18, 143-154 (1979) Sie geben die drei universellen Hashfunktionen H_1, H_2 und H_3 an.

Es gibt dann noch die Begriffe n-universelle und $\epsilon$-universelle Hashfunktionen. Siehe "New Hash Functions and Their Use in Authentication and Set Equality" von Mark N. Wegman und J. Lawrence Carter in Journal of Computer and System Sciences 22, 265-279 (1981)

Sie geben eine n-universelle und $\epsilon$-universelle Hashfunktion an.

siehe auch "Algorithmen-Eine Einführung" von Th. H. Cormen, C.E. Leiserson, R. Rivest und C. Stien ab S.232 ff.

internes / externes Hashing

Es wäre schön, wenn noch auf internes und externes Hashin eingegangen werden könnte! --Master-2000 00:44, 20. Feb 2006 (CET)

Zufälligkeit

Letzter Kommentar: vor 17 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

Ist die Zufälligkeit wirklich ein Kriterium einer guten Hashfunktion? Für mich steht der Begriff im Gegensatz zur Reproduzierbarkeit der Ergebnisse. Außerdem scheint der Begriff im Gegensatz zur dazugehörigen Erläuterung zu stehen.

Zitat aus Zufall: "Zufall ist dann vorhanden, wenn nur aufgrund der Anfangsbedingungen keine Aussage darüber zu machen ist, was geschieht, bzw. wenn bei exakt gleichen Ausgangsbedingungen nicht immer das gleiche passiert." --84.190.84.32 08:53, 7. Mär 2006 (CET)

Zufälligkeit und Reproduzierbarkeit schließen einander nicht aus: Pseudozufallszahl --Stepwiz 23:25, 15. Dez. 2006 (CET)

Strukturprobleme?

Hallo, was ist mit dem Artikel los? Der gesamte Bereich Definition einer Hash-Funktion ist - oder scheint zumindest - sehr schräg und undurchsichtig, ja fast fehlerhaft formatiert, vor allem die vorformatierten Bereiche. Wer auch immer durch die Formatierung hindurchsteigt, sollte sie entweder klarer gestalten, oder auf jeden Fall klar machen, was sie zu bedeuten hat. --Zaap 18:15, 19. Apr 2006 (CEST)

Wie es aussieht geht das auf Probleme mit der math-Funktion zurück. Kennt sich jemand damit aus? --Zaap 19:09, 19. Apr 2006 (CEST)
Mir ist nicht ganz klar, was Du meinst. Manche Formeln müssen (derzeit) als Bilder dargestellt werden und haben deshalb eine feste Größe, die je nach verwendetem Browser nicht zum Fließtext passt (meistens sind sie zu groß). Vielleicht gibt es demnächst eine Darstellung mittels MathML, aber viele Browser unterstützen das noch nicht ausreichend, der Default wird also wohl erst einmal wie bisher sein.--Gunther 19:15, 19. Apr 2006 (CEST)
Was ich meine habe ich einfach mal in Form eines - verkleinerten - Bildes auf meinen Webspace hochgeladen (jpg, 112 KB). Das sehe ich sowohl in Opera als auch im IE. --Zaap 20:13, 19. Apr 2006 (CEST)
Es gab im Verlauf des heutigen Tages ernsthafte Probleme mit den Servern. Dass solche Probleme nicht wieder verschwinden, liegt meistens am Browser-Cache, versuch' mal F5, Umschalt+F5, oder den Cache zu leeren. Hilft das?--Gunther 23:20, 19. Apr 2006 (CEST)
Jop, heute ist alles wieder im Grünen. Danke! --Zaap 14:09, 20. Apr 2006 (CEST)

Hashfunktion vs. Hash-Funktion

Letzter Kommentar: vor 16 Jahren8 Kommentare3 Personen sind an der Diskussion beteiligt

Hallo, ich würde gerne die Schreibweise der Hash*-Artikel vereinheitlichen. Sowohl innerhalb dieses Artikels wie auch in anderen Artikeln ist die Verwendung uneinheitlich. Dabei bin ich mir der Tatsache bewusst, dass prinzipiell wohl beide Schreibweisen regelkonform sind, aber ebenso klar sollte sein, dass eine einheitliche Schreibweise angestrebt werden sollte. Weitere Begriffe sind in diesem Kontext:

Ich würde hier die Begriffe Hashfunktion, Hashtabelle, Hashwert und Hashverfahren jeweils als ein Wort ohne Bindestrich schreiben. So sollten dann auch die Hauptartikel heißen, die jeweils anderen Schreibweisen werden dann zum Redirect (auf Erhalt der Historie werde ich achten). Hash-Algorithmus erscheint hier in der Bindestrich-Schreibweise angebrachter, da Hashalgorithmus doch ein wenig vielsilbig wird. Ansonsten bin ich auch mit jeder völlig einheitlichen Schreibweise einverstanden (alles ohne/alles mit Bindestrich). Was meint ihr? Mkleine 17:43, 28. Mai 2006 (CEST)

Der Duden sieht die Sache offiziell (iirc) so: es ist nach neuer Rechtschreibung gleichwertig, sollte aber innerhalb eines Textes einheitlich sein. Nach alter Schreibweise muss ein Bindestrich stehen. Sehe keinen Bedarf, verschiedene Texte zu vereinheitlichen (Wikipedia hat keine Hausschreibweise, Konsistenz ist in Wikipedia:Rechtschreibung nur innerhalb eines Artikels gefordert). Es spricht natürlich auch nichts dagegen. Dann musst du aber jeweils auch die Artikel aufs passende Lemma verschieben. igel+- 12:16, 29. Mai 2006 (CEST)
Ich sehe das soweit ähnlich, mal sehen, ob sich hier noch jemand zu Wort meldet. Idealerweise nimmt man bei getroffener Entscheidung die Schreibweise irgendwann in einen Bot auf, der das dann regelmäßig prüfen kann. Grüße Mkleine 13:22, 29. Mai 2006 (CEST)
Sowas wird hier nicht basisdemokratisch entschieden, zumal wir ja nicht parallel auf allen Seiten diskutieren können, die mit Hash beginnen. Du solltest es, wenn du glaubst, es wird der Menschheit nützen, mutig angehen und hoffen, dass du keinen rv fängst. Am besten tust du als Beschreibung der Änderung einen Verweis auf diese Diskussionsseite. igel+- 17:35, 29. Mai 2006 (CEST)
Ja Igel. Mal so am Rande: Hast du eigentlich mal bemerkt, seit wann ich hier mitarbeite? Auch wenn es vielleicht gut gemeint ist - den Hinweis auf Links wie den oben genannten brauche ich wirklich nicht. In manchen Regionen sagt man auch Don't teach your grandma how to suck eggs. Ansonsten noch viel Spaß. Mkleine 22:50, 29. Mai 2006 (CEST)
Welche Regionen sind das denn? igel+- 00:30, 30. Mai 2006 (CEST)
Englischsprachige ... Mkleine 00:32, 30. Mai 2006 (CEST)
Ich habe mal in den einschlägigen deutschen Kryptotexten unter Hashfunktion nachgeschaut (Buchmann, Beutelspacher, dt. Übersetzung vom Schneier). Alle schreiben ein Wort ohne Bindestrich. Insofern halte ich es dringend für erforderlich, die Schreibweise hier entsprechend anzupassen und keine Sonderweg zu gehen (der meinem Sprachgefühl auch widerspricht). Grüße vom Zahlendreher 08:07, 15. Jun 2006 (CEST)

Hab den Artikel mal umbenannt, einige Änderungen habe ich manuell vorgenommen, da ich keine Lust habe, mich mit Bots auseinanderzusetzen. --Supaari mail 22:27, 18. Sep. 2008 (CEST)

Redundanz zu Hash-Wert

Letzter Kommentar: vor 17 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

Habe die Redundanz beendet und Hash-Wert weitgehend überführt. Hier die alten Beiträge:

-- ReqEngineer Au weia!!! 11:15, 24. Dez. 2006 (CET)

Authentizität durch Hashfunktion?

Letzter Kommentar: vor 16 Jahren3 Kommentare2 Personen sind an der Diskussion beteiligt

Die folgende Aussage ist m. E. falsch: "Mit einem Hashcode werden z.B. Binärdokumente gekennzeichnet, um deren Authentizität beim Empfänger prüfbar zu machen, ohne den Inhalt des Dokuments selbst offen zu legen, etwa bei der verbreiteten MD5 Funktion." Zumindest in der Informatik versteht man unter Authentizität nicht nur, dass ein Objekt unverfälscht ist, sondern zudem auch den Nachweis der Quelle (siehe auch Authentizität). Eine Hashfunktion soll dagegen zunächst einmal die Integrität gewährleisten. Das gilt auch für MD5. Erst in Verbindung mit Verschlüsselung (beispielsweise als Digitale Signatur) wird auch die Quelle überprüfbar und damit Authentizität erreicht.
Außerdem verstehe ich nicht, wieso der Einschub "ohne den Inhalt des Dokuments selbst offen zu legen" dort enthalten ist. Gibt es für diese Einschränkung einen Grund? Mir fällt nicht einmal ein Anwendungsfall ein, in dem die Integrität gewährleistet werden soll, obwohl auf die Inhalte nicht zugegriffen werden kann. --Freischlad 16:56, 20. Feb. 2008 (CET)

Was man auf diese Weise machen kann und gemeint sein könnte, ist folgendes: Bevor Adam sich mit Bill über ein geheimes Thema unterhält, möchten beide sicherstellen, dass beiden tatsächlich die geheime Datei X vorliegt – und so verhindern, dass etwa geheime Informationen an uneingeweihte Außenseiter gelangen. Hierzu schickt Adam and Bill eine Challenge, etwa "Adam 2008-02-20 20:03:10", ebenso Bill an Adam etwa "Bill 2008-02-20 20:03:12". Beiden ist es möglich, Y = md5sum(X + "Adam 2008-02-20 20:03:10" + "Bill 2008-02-20 20:03:12") zu berechnen. Bill kann seinen Wert gefahrlos mitteilen und Adam kann anhand dessen sicherstellen, dass Bill tatsächlich X besitzt. Es wurde jedoch "keine" Information über X übermittelt.--Hagman 20:09, 20. Feb. 2008 (CET)
Meines Erachtens beschreibt dies einen Message Authentication Code (MAC), der mit einer Hashfunktion gebildet wird. Notwendig dafür ist ein geheimer Schlüssel (die Datei X). Im RFC 2104 ist eine solche Verwendung als HMAC beschrieben (HMAC: Keyed-Hashing for Message Authentication). Ich würde also vorschlagen, den betroffenen Absatz entsprechend zu überarbeiten. --Freischlad 16:31, 6. Mär. 2008 (CET)

Kriterien für kryptographisch sichere Hashfunktionen

Letzter Kommentar: vor 15 Jahren2 Kommentare2 Personen sind an der Diskussion beteiligt

Ich denke der Absatz aus dem Artikel beinhaltet einen Fehler:

"Außerdem gilt schwache Kollisionsresistenz (2nd-preimage resistance): es ist praktisch unmöglich für einen gegebenen Wert x ein davon verschiedenes x′ zu finden, das denselben Hash-Wert h(x) = h(x′) = y ergibt."

Für die Kryptographie ist denke ich starke Kollisionsresistenz gewünscht. Es sollen ja möglichst keine Kollisionen auftreten. Ich ändere das im Artikel. Bitte korrigiert mich, falls ich hier irgendeinen Kryptographiejargon falsch verstanden habe. Edit: Mir ist aufgefallen, dass sich die folgenden Absätze nicht deutlich voneinander unterschieden haben, daher habe ich sie entfernt. Die vorher verwendeten Begriffe "schwache Kollisionsresistenz (2nd-preimage resistance)" und "Beinahe-Kollisionsresistenz (near-collision resistance)" konnte ich in meinem Ersatz nicht unterbringen, da ich sie nicht kenne, und mir der Unterschied nicht klar ist. --Supaari mail 05:15, 1. Mai 2008 (CEST)

Ich habe den Abschnitt neu geschrieben. Ich bitte um Verzeihung für die radikale Maßnahme, aber exakte Formulierungen sind hier von entscheidender Bedeutung. Ich hoffe, es sind keine Unklarheiten mehr vorhanden. Die Begriffe schwache und starke Kollisionsresistenz habe ich vermieden, da sie mir in der Literatur nicht begegnet sind. Wenn ich Supaari richtig verstehe, sind damit wohl Resistenz gegen den Zweites-Urbild- bzw. den Geburtstagsangriff gemeint, vielleicht kann das jemand, der die Begriffe kennt, hinzufügen. --Carsten Milkau 14:51, 22. Jul. 2009 (CEST)

Erklärung für Kollision

Letzter Kommentar: vor 16 Jahren3 Kommentare2 Personen sind an der Diskussion beteiligt

Ich habe gerade die Definition von Kollision im Zusammenhang mit MD5 gesucht. Unter Kollision trifft man aber nur auf eine BKL-Seite, die u.a. auf Kollisionsfreiheit verweist, was auf Hash-Funktion weitergeleitet wird. Dort habe ich etwas mühevoll nach einer Erklärung für Kollision gesucht. Um diesen Weg zu vereinfachen (und den Link auf die BKL-Seite auflösen zu können), habe ich das Wort Kollision in Hash-Funktion durch Fettdruck herausgehoben - was umgehend revertiert wurde.

Wie kann man einen (Halb-)Laien wie mich zielsicher auf eine Definition für Kollision führen? Ein eigenes Lemma Kollision (Hash-Funktion) erscheint mir übertrieben, weil man die ganze Hash-Funktion erläutern muss, um Kollision zu erklären. Am besten ist vielleicht ein eigener Absatz mit der Überschrift "Kollision", auf den man verlinken kann. Ist nur meine Idee, ich will nicht weiter unberufen in Eurem Artikel herumpfuschen. --Ungebeten 20:27, 5. Jun. 2008 (CEST)

Hallo Ungebeten,
das stimmt schon, dass das momentan etwas verwirrend ist. Unter Hashtabelle#Kollisionen gibt es einen Absatz zum Thema. Der Absatz erklaert Kollisionen allerdings nur aus Sicht einer Hashtabelle, auch wenn das mit einander verwandt ist.
Der Fettdruck erklaert natuerlich garnichts, sondern bringt nur das Lesebild durcheinander.
Richtig waere es, unter Hash-Funktion einen Absatz Kollisionen einzufuegen und die BKL direkt dort hin zu verweisen.
Ich werd heute leider nicht die Zeit haben da etwas zu schreiben. Also vielleicht erstmal mit dem Absatz in Hashtabelle vorlieb nehmen. -- sparti 20:43, 5. Jun. 2008 (CEST)
Hallo sparti,
danke für Dein Engagement, viel Spaß beim Schreiben. --Ungebeten 20:57, 5. Jun. 2008 (CEST)

Einheitliches Vokabular "Hashcode" / "Hashwert"

Letzter Kommentar: vor 14 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

Die beiden Bezeichnungen sollten entweder einheitlich verwendet werden, also nur eine davon, oder wenigstens sollte klar sein, dass sie Synonyme sind. (nicht signierter Beitrag von 78.51.233.57 (Diskussion | Beiträge) 12:01, 29. Apr. 2010 (CEST))

Softwarepatent - Quelle?

Letzter Kommentar: vor 14 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

Zitat: "Das Auffinden von Dateien aufgrund des Hashwertes ihres Inhaltes ist zumindest in den USA als Softwarepatent geschützt." Gibt es dazu eine Quelle? -- 91.9.64.176 22:18, 19. Mai 2010 (CEST)

Definition

Letzter Kommentar: vor 13 Jahren4 Kommentare3 Personen sind an der Diskussion beteiligt

Irre ich mich, oder enthält der Artikel tatsächlich keine Definition (im mathematischen Sinne)? Wenn man den ersten Absatz betrachtet:

Eine Hashfunktion oder Streuwertfunktion ist eine Funktion oder Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode (oder Hashwert), erzeugt, meist aus einer kleineren Zielmenge.

kann man nur lernen, es sei eine Funktion, die zu einer "Eingabe" aus einer Menge eine "Ausgabe" aus einer Menge erzeugt. Dies ist bereits (wenn ich mich richtig an die Mathevorlesungen erinnere) so in etwa die Defintion der Funktion. Dass die Mengen "überlicherweise" groß bzw. "meist" klein sind, gibt ja in Sachen Definition nichts her. "Üblicherweise", "meist" klingt für mich jedenfalls so, als wenn es im Einzelfall auch mal anders sein könnte. Damit ist mir nicht mehr klar, was den Begriff "Hashfunktion" jetzt wirklich vom Begriff "Funktion" abgrenzt. Mal ganz abgesehen davon, dass mir nicht klar ist, was mit "großen" oder "kleinen" Mengen genau gemeint ist (hier wäre das Stichwort wahrscheinlich "Mächtigkeit", oder)?

Vorschlag (von dem ich nicht weiß, ob er zutrifft, der aber veranschaulichen soll, wie ich mir eine Definition vorstelle):

Eine Hashfunktion ist eine Funktion f: U→B auf zwei Mengen U und B, wenn die Mächtigkeit von B kleiner (oder gleich?) der von U ist.

Da die Wikipedia ja kein "Mathebuch" sein soll, kann dann noch veranschaulicht werden, was damit gemeint ist (so wie es im Artikel ja bereits der Fall ist).

Aber vielleicht ist eine Hashfunktion ja gar nicht durch ihre mathematischen Eigenschaften definiert, sondern es kann jede Funktion auf den geeigneten Mengen als Hashfunktion angesehen werden, sofern sie für einen bestimmten Zweck verwendet wird.

Wenn das so ist, sollte dies im Artikel auch so gesagt werden. --80.150.2.134 13:16, 18. Nov. 2010 (CET)

Warum muss es eine mathematische Definition geben, wenn sich diese eben nicht von einer "Funktion" unterscheidet? Es gibt auch eine Welt außerhalb der Mathematik ...
In der Tat kommt es auf den Anwendungszweck an. Man verwendet u.A. mitunter die Identität als Hashfunktion. Ob jetzt der Wertebereich kleiner ist ist i.d.R. zweitrangig. Die in Hashtabellen verwendeten Hashfunktionen haben i.d.R. 32-bit auf einem 32-bit-System. Aber ich verwende eben danach gar nicht alle 32 bit. Diesen trivialen Reduktionsschritt will ich aber nicht als die eigentliche Hashfunktion bezeichnen, bloß weil es der Schritt ist, der mir den Wertebereich auf das gewünschte Maß reduziert. So bleibt letztlich nur das Fazit: eine Hashfunktion ist eine Funktion, die man als Hashfunktion verwendet - willst du das so hinschreiben? --Chire 22:21, 18. Nov. 2010 (CET)
ich meine, letztlich steht die mathematische Definition ja da: "Eine Hashfunktion ist eine Funktion." - der Rest ist Erläuterung, was man da eben typischerweise verwendet. --Chire 22:23, 18. Nov. 2010 (CET)
Was (konkret) fehlt dir denn an mathematischer Definition im Absatz Definition einer Hashfunktion? Man kann den Absatz bestimmt noch ausbauen, aber dass eine Definition fehlt würde ich so nicht sagen. Ansonsten wird das Wesentliche auch in der Einleitung gesagt, meines Erachtens sogar mathematischer als es für WP:OMA sinnvoll wäre. Ciao, —octo 22:48, 18. Nov. 2010 (CET)

Perfekte Hashfunktion

Letzter Kommentar: vor 13 Jahren2 Kommentare2 Personen sind an der Diskussion beteiligt

Es ist immer möglich eine perfekte Hashfunktion zu finden, die direkt und ohne Kollisionen abbildet. Nicht nur in Sonderfällen! Hab das im Artikel geändert.-- 134.61.64.231 09:30, 31. Mai 2011 (CEST)

Du hast vergessen es im Artikel zu ändern. Es stimmt aber eh nicht: es geht definitiv z.B. nicht, wenn: 1. die Zielmenge kleiner ist als die reale Schlüsselmenge oder 2. wenn Datenduplikate erlaubt sind! 3. Die Komplexität der Hashfunktion beschränkt ist.
Zeige mir deine perfekte Hashfunktion von { "Müller", "Müller", "Huber", "Meier" } (wobei es zwei verschiedene Müller sind, der Unterschied aber mir nicht bekannt ist) auf { 0, 1 }!
Erst wenn man diese Begrenzungen nicht hat - beispielsweise die Zielmenge frei wählen kann - kann man eine perfekte Hashfunktion konstruieren. Ich würde das einen Sonderfall nennen ... (Was jetzt natürlich nicht bedeutet, dass dieser Sonderfall nicht manchmal erstrebenswert ist!) --Chire 15:38, 31. Mai 2011 (CEST)

Einleitungssatz

Letzter Kommentar: vor 13 Jahren3 Kommentare2 Personen sind an der Diskussion beteiligt

zur begruendung meines reverts: der edit macht den satz sinnlos. die laenge des ausgabe ist immer definiert, nicht nur oft. die ausgabe kommt aus der zielmenge, nicht von ihr. "eingaben grosser definitionsmengen" ist mehrdeutig, die definitionsmenge ist nicht die eingabe. es heisst "etwas unterscheiden nach", aber "sich unterscheiden in/durch". --Mario d 16:10, 3. Jul. 2011 (CEST)

Ich prgrammiere nicht immer mit Hashs, war auch der festen Meinung, dass "oft" weg muss, habe es aber wegen dem ">>typischerweise<< kleineren Zielmenge", was haarsträubend klingt wenn doch die Länge der Zeichenkette und damit auch Größe je nach Funktion fest definiert ist, dazugeschrieben. Der Einleitungssatz "Eine Hashfunktion oder Streuwertfunktion ist eine nahezu beliebige Abbildung, die zu jeder Eingabe aus einer oft sehr großen Quellmenge eine Ausgabe aus einer typischerweise kleineren Zielmenge erzeugt, den sogenannten Hashcode (oder Hashwert)." ist viel zu kurz um einen Überblick über das Thema zu geben. Es heisst es gibt zu wenig Fachleute, erleichtern wir den zukünftigen den Zugang. Der Rest passt so, also "in". mfg--Niesen 17:11, 3. Jul. 2011 (CEST)
du hast recht, ich habe das "typischerweise" entfernt. dass die zielmenge kleiner ist, ist die definition einer hashfkt., der einleitungssatz entspricht damit der definition, die man auch in fachbuechern finden wuerde. ich finde den einleitungsabschnitt recht gelungen, was wuerdest du noch verbessern? --Mario d 17:19, 3. Jul. 2011 (CEST)

Vergleich mit Fingerabdruck des Menschen

Letzter Kommentar: vor 12 Jahren29 Kommentare7 Personen sind an der Diskussion beteiligt

Würden bitte die IPs ihre Rumschubserei dieser Tage um den Vergleich mit dem menschlichen Fingerabdruck einstellen?

Der Passus wäre wohl etwas unmissverständlicher formulierbar, aber die Revertiererei zwischen zwei Versionen bringt es nicht.

  • Der menschliche Fingerabdruck ist hier nur ein anschauliches Beispiel; eine prinzipielle Aussage über die Kollisionshäufigkeit ist ohne konkrete Benennung von Codelängen nicht möglich.
  • 2009 brachen eineiige Zwillinge in das Kaufhaus des Westens ein; mindestens einer von ihnen war am Tatort, aber welcher? Keine Verurteilung möglich.
  • Statistische Aussagen über die Kollisionswahrscheinlichkeit bei einer bestimmten Anzahl von Menschen vs. Hashcode konkreter Methode sind sehr wohl möglich, aber für das Artikelthema völlig wurscht.

Die vorherige Variante „nahezu eindeutige“ hat korrekt und verständlich begründet, warum die Vokabel “Fingerprint” entstanden ist.

VG --PerfektesChaos 19:43, 25. Feb. 2012 (CET)

Vor allem ist bei den Änderungen auf die Grammatik zu achten...
"da er eine Kennzeichnung einer Datenmenge darstellt, ähnlich wie ein Fingerabdruck bei einen Menschen"
Ich glaube der Punkt ist eher, dass ein Fingerabdruck eben nur ein Abdruck ist, und keine vollständige Repräsentation des Menschen. Der bestehende Text ist dahingehend meiner Meinung nach besser.
Danke. --93.134.225.94 20:46, 25. Feb. 2012 (CET)
"nahezu eindeutig" gilt mMn nur fuer kryptographische hashfunktionen, von der ISBN-pruefsumme wuerde ich das nicht behaupten. das sollte in dem abschnitt ueber den login auch ergaenzt werden. --Mario d 09:41, 26. Feb. 2012 (CET)
Ja, genau das hatte ich im Hinterkopf, als ich oben schrieb: „ohne konkrete Benennung von Codelängen nicht möglich“.
  • Im Artikeltext geht es um die Frage, wie man auf die Vokabel “Fingerprint” kam.
  • Es ist völlig klar, dass das bei den 10 Möglichkeiten einer ISBN13-Prüfziffer nicht angebracht ist; sehr wohl trägt die Analogie bei 16 Octets recht gut. Beides ist mit hoher Wahrscheinlichkeit eindeutig, aber gelegentlich durch Schäuble-Zwilling auch mal manipulierbar.
  • Im Artikeltext müsste also zur Klarstellung etwas wie „Ein längerer Hashwert wird deshalb auch …“ formuliert werden, wobei exakte Angaben (wie viele Bytes auf wie viele Millionen Menschen ./. Zwillinge kämen) die Analogie überfordern würden. Es ist nur ein allgemeinverständliches Bild.
Schönen Sonntag --PerfektesChaos 10:43, 26. Feb. 2012 (CET)
Man darf auch nicht zu viel auf der "Eindeutigkeit" herumreiten. Das führt zu weiteren Missverständnissen. Evtl. wäre es gut, hier z.B. den Vergleich Visitenkarte - Fingerabdruck zu ziehen. Eine Visitenkarte "identifiziert" mir eine Person viel besser, denn ich kann sie damit auch wiederfinden. Bei einem Fingerabdruck kann ich nur prüfen, ob eine Person (die ich kenne) wahrscheinlich da war. Umgekehrt ist aber eben eine Visitenkarte leicht zu fälschen.
Im ISBN-Beispiel muss man bedenken, dass sich niemand nur für die Prüfziffer interessiert. Die vollständige ISBN ist da irgendwo der Hashwert für das Buch, abgesichert eben nur gegen Tipp- und Lesefehler. Aber klar, auch bei CRC32 für Netzwerk-Pakete gibt es real mehr Pakete als Hashwerte.
"längerer" finde ich gut. Evtl. kann man noch einen Nebensatz anhängen: "[einen Menschen nahezu eindeutig identifiziert], ohne ihn vollständig zu repräsentieren." Ich finde das einen wichtigen Aspekt, dass der Fingerprint nicht vollständig ist. --Chire 12:29, 26. Feb. 2012 (CET)
mir ging es nicht um die laenge, sondern um die tatsache, dass ein hashwert ein datum eben nicht eindeutig identifiziert, weil leicht andere daten mit dem selben hashwert gefunden werden koennen. der vergleich mit dem fingerabdruck gilt nur fuer kryptographische hashfunktionen, die kollisionsresistent sind. hat eigentlich jemand eine quelle fuer die bezeichnung von hashwerten als fingerprints? oder fuer die von pruefsummen als hashfunktion? der englische artikel sagt dazu: "Hash functions are related to (and often confused with) checksums, check digits, fingerprints, randomization functions, error correcting codes, and cryptographic hash functions." --Mario d 13:17, 26. Feb. 2012 (CET)
Es ist mehr eine Geschmacksfrage, ob und wie du diese Begriffe differenzierst. Die englische Wikipedia würde ich da nicht als Maßgeblich sehen. Der Begriff "hash function" für Krypologische Hashfunktionen ist ein Fakt, den selbst die englische Wikipedia nicht leugnen sollte - en:Cryptographic hash function hat nun mal "hash function" im Namen. Ob man jetzt eine Prüfsumme als Hashfunktion auffasst ist das umgekehrte Problem: mathematisch gesehen handelt es sich um eine Hashfunktion - der Wertebereich wird verkleinert, und "ähnliche" Werte auf unähnliche Werte abgebildet, der "Streuwert" trifft also auch zu. Aber rein technisch wird eben oftmals sogar eine Modulo-Funktion mit großem Erfolg in Hashtabellen als Hashfunktion verwendet. Bzgl. Quellen möchte ich wetten, dass sich ein Lehrbuch finden lässt, das Prüfsummen als Beispiel für Hashfunktionen bringt (und den Vergleich zum Fingerabdruck, sowie den Begriff "Fingerprint". Da reicht auch Google Scholar, tausende Treffer!). Sorry, wir werden nicht darum kommen, in dem Artikel mindestens die drei Fälle "Hashfunktionen als Prüfsummen", "Hashfunktionen zur Datenspeicherung / Hashtabellen", "Hashfunktionen zur identifikation von Inhalten" (z.B. Audio; robust gegen Audiokompression) und "kryptologische Hashfunktionen" (hoffentlich robust gegen gezielte Manipulation) aufzuzeigen, Gemeinsamkeiten und Unterschiede zu diskutieren und auf die jeweiligen Hauptartikel zu verweisen. Kollissionsresistenz ist übrigens kein gute Kriterium. Denn viele "krypotologische Hashfunktionen" haben sich dann doch als nicht so kollissionsresistent wie erhofft erwiesen. Ich glaube für keine wurde eine Kolissionsresistenz bewiesen (da das vermutlich nicht möglich ist), sondern es ist eben nur ein "Experten glauben, das Hash ist sicher". Jedenfalls ist Kollissionsresistenz ein zu weiches Kriterium. Prüfsummen sind auch kolissionsresistent - nicht gegen gezielte Manipulation, aber gegen typische Übertragungsfehler. --Chire 22:09, 26. Feb. 2012 (CET)
den abschnitt habe ich jetzt erst bemerkt, weil er mittendrin versteckt ist. wir sind uns sicher einig, dass der artikel momentan in einem schlechten zustand ist. wenn du ihn ueberarbeiten moechtest, kann ich gerne den part mit den kryptographischen hashfunktionen uebernehmen. wenn du eine literaturquelle hast, waere es sicher gut, die zu zitieren, der ausdruck "eindeutig identifizieren" ist mMn zu unscharf um ihn so wie jetzt im artikel zu lassen. --Mario d 13:37, 27. Feb. 2012 (CET)
  • @IP (im Zweifelsfall alle beide):
    • Hrrrrhhrrrmmm (vernehmliches Räuspern). Ich hatte mich eigentlich eingangs dieses Abschnitts zum Thema Rumschubsen geäußert.
    • Gern noch mal zur Erläuterung, wie das hier funktioniert: Es wird erst auf dieser Disku eine inhaltliche Lösung gefunden, und hinterher das Endergebnis in den Artikel übertragen.
    • Es gäbe auch die freundliche Halbsperrung; ohne Sichtung bekommt eure Edits sowieso keiner mit.
  • @MarioS et al.:
    • Das sprachliche Durcheinander entsteht, wenn die unterschiedlichen Längen für Codes zusammengeworfen werden:
      1. Bei der ISBN ist es eine checksum/Prüfziffer/check digit, weil nur 10 bzw. 11 unterschiedliche Werte möglich sind. Hier würde man auch nicht von einem "hash" sprechen.
      2. Ein CRC32 und besser entspricht dem Fingerabdruck; mit minimalem Restrisiko einer manipulativen oder zufälligen Kollision, analog zu Schäubles CCC-Zwilling. Auch das ist ein Hashcode.
      3. Dazwischen lägen Streuwerte mittlerer Größe, etwa typische "Hashcodes" mit 1024 Möglichkeiten zur möglichst gleichverteilten Gruppierung wie zum Lagern und Speichern.
      4. Ein "Fingerabdruck Plus" wäre ein kryptografisch unknackbarer Sicherheitscode. Den gibt es letztlich auch nicht.
    • Die Vokabel "Fingerprint" ist mir seit 20 Jahren geläufig; es ist wohl kein exakt definierter Fachbegriff, wird aber im Kontext auf Anhieb richtig verstanden.

Schönen Abend --PerfektesChaos 21:13, 26. Feb. 2012 (CET)

ad 2: das ist ja genau nicht der fall. a) der CRC ist eine pruefsumme und dient dazu, fehler zu erkennen. mit kollisionen hat das nichts zu tun. b) beim CRC ist es eine leichte uebung, kollisionen zu finden, er bietet keinen schutz gegen "manipulative kollision". das sprachliche durcheinander entsteht, wenn begriffe durcheinandergeworfen werden und ist unabhaengig von laengen, und dass der begriff "fingerprint" zu verwirrung fuehrt sehen wir ja gerade. --Mario d 21:52, 26. Feb. 2012 (CET)
CRC ist halt keine kryptologische Hashfunktion, aber trotzdem eine Hashfunktion. Du wirfst gerade diese beiden Begriffe durcheinander. Nicht jede Hashfunktion muss gegen absichtliche Kollissionen resistent sein, das ist nur etwas, was man sich von krypotogischen Hashfunktionen erhofft. Und der Fingerprint passt auch bei Prüfsummen. Dort muss der Fingerabdruck zum Rest der Daten passen, sonst "hat man den falschen". Auch die Kollissionswahrscheinlichkeit ist nur eine Zahl, was ist denn der Mindestwert, ab dem etwas eine Hashfunktion sein soll? Wenn ich von einer SHA-Summe den Modulo-10 Wert übertrage, ist das dann eine Prüfsumme, ein Hash oder ein kryptologischer Fingerprint? Ist doch SHA, also ist es nicht leicht, gezielt eine Kollission herzustellen (andererseits braucht man brute force halt ca. 10 Versuche ...) => der Unterschied ist eigentlich vor allem, wozu man sie verwendet, und was man sich davon erhofft (Absicherung gegen Übertragungsfehler vs. Absicherung gegen gezielte Manipuation vs. maximale Streuung vs. Resistenz gegenüber Audioverzerrungen)! --Chire 22:09, 26. Feb. 2012 (CET)
"Fingerprinting" ist definitiv (siehe Google Scholar; das findet das selbst in diversen Patenten) ein geläufiger Ausdruck hierfür; insbesondere im Bereich von Audio/Video/Multimedia. Für die Berechnung von "identifizierenden" Hashwerten halte ich es sogar für geläufiger als Hashfunktion, da das eben auch Prüfsummen und Streuwertverfahren abdeckt. Wobei man eben bei Audio-Fingerprints noch darüber streiten kann, ob es wirklich eine Hashfunktion ist. m.E. ja. --Chire 22:09, 26. Feb. 2012 (CET)
Da sich die IPs weiter bekriegen, statt hier mitzudiskutieren, habe ich jetzt eine Halbsperre beantragt. Es sind ja genug registrierte Nutzer hier, um sinnvolle Änderungvorschläge einzuarbeiten. --Chire 08:06, 27. Feb. 2012 (CET)
ich werfe die begriffe nicht durcheinander, ich versuche sie in der diskussion zu trennen. du hast behauptet: "Ein CRC32 und besser entspricht dem Fingerabdruck; mit minimalem Restrisiko einer manipulativen oder zufälligen Kollision [...]" (kursiv von mir). darauf habe ich geantwortet, weil ein CRC eben nicht gegen "manipulative Kollision" schuetzt. ansonsten helfen nur einzelnachweise, von denen der artikel bisher effektiv nur einen einzigen hat. --Mario d 13:27, 27. Feb. 2012 (CET)
Also technisch gesehen nicht "ich". Und er hatte geschrieben "CRC32 und besser". Ich kenne jetzt die Geschichte zu wenig, ob man CRC32 ursprünglich auch mal für krypto verwendet hat, und es nur halt schon lange "geknackt" ist, oder ob es (das wäre meine Vermutung) stets nur eine Prüfsumme war. Auch als Prüfsumme wurde es aber sicher gegen Manipulationen eingesetzt. Bspw. bei Datensätzen mit einer festen Länge und Struktur reicht es für viele Anwendungen, sagen wir mal Computerspiel-Highscore-Listen, um sie gegen triviale Texteditor-Angriffe zu schützen. Es muss ja nicht immer gleich "Geheimdienst-Sicherheit" sein. Mich würde es auch nicht wundern, wenn du alte Software findest, die Passwörter als crc32 speichert. Eine kurze Google-Suche hat ergeben, dass Microsoft Outlook wohl PST-Dateien zum Teil nur mit CRC32-Hashes schützt? Damit wäre dann CRC32 eigentlich nicht soo verschieden von MD4/MD5/SHA/... --Chire 23:42, 27. Feb. 2012 (CET)
oh, da hatte ich nicht aufgepasst, ich hoffe du nimmst mir das nicht uebel. CRC war nie fuer krypto gedacht und wurde auch nie als kollisionsresistent angenommen, er musste also auch nicht geknackt werden. pruefsummen schuetzen nicht vor (absichtlichen) manipulationen, nur vor (zufaelligen) uebertragungsfehlern. das bedeutet natuerlich nicht, dass sie nicht zum schutz gegen manipulationen eingesetzt wurden, weil ein programmierer nicht verstanden hat, welches verfahren er eigentlich benutzt und welche garantien es dafuer gibt. was es outlook gebracht hat, zeigen die google-treffer ja ebenfalls. CRC zum schutz von passwoertern einzusetzen zeugt einfach von grobem unverstaendnis. CRC schuetzt auch nicht vor trivialen manipulationen, denn ich kann (in deinem beispiel) einen beliebigen highscore eintragen, davon den CRC berechnen und mit diesem neuen wert den alten ueberschreiben. das koennte ich auch, wenn eine kryptographische hashfunktion verwendet wird. um das ganze sicher zu machen, muesste der hashwert noch digital signiert werden - und wer einen CRC-wert signiert, dem ist nicht mehr zu helfen (hier ist eine anleitung zum erzeugen von kollisionen). kurz: CRC ist etwas voellig anderes als MD5 usw. dass leute das nicht wissen und ihn genauso benutzen, aendert nichts an den fakten. --Mario d 11:48, 28. Feb. 2012 (CET)

“Fingerprint” ist kein wissenschaftlicher Fachausdruck; insofern gibt es keine präzise Definition, wofür man dieses Wort benutzen darf und wofür nicht.

Es gibt aber eine weit verbreitete Verwendung, die die WP auch reflektieren sollte.

Ich versuche mal die vier Fälle auseinanderzuklamüsern:

  1. Eine einzelne Prüfziffer oder eine zwei- bis dreistellige „Prüfsumme“ (die nicht Resultat einer Addition sein muss) würde man nicht „Fingerabdruck“ nennen.
  2. Einen Hash-Wert für gleichverteilte Speicherstrukturen nennt man Hash-Wert oder Hashcode, aber nicht „Fingerabdruck“.
  3. Beim Daten-Fingerabdruck (CRC32 usw.) ist diese Vokabel sehr gebräuchlich. Er ist als Schutz gegen technische Fehler bei der Übertragung oder Speicherung einer größeren Datenmenge gedacht. Zum Manipulationsschutz ist er ursprünglich nicht vorgesehen, würde aber triviale Angriffe nebenbei verhindern.
  4. Der kryptografische Fingerabdruck ist bewusst darauf ausgelegt, gegen Manipulation zu sichern, und erfordert auch größere Länge und Berechnungsaufwand.

Zum „Daten-Fingerabdruck“ einige Anmerkungen:

  • 32 Bit wären 232 und das sind vier Milliarden Möglichkeiten. In der Weltbevölkerung von sieben Milliarden finden sich sicher mehr als zwei Zwillingspaare. Von der Wahrscheinlichkeit her wäre CRC32 also „sicherer“ als Daktyloskopie.
  • Für technische Zwecke ist CRC32 hinreichend sicher, weil nur zufällige Ursachen unterstellt werden. Alle diese Dinger sind (wie schon bei der ISBN) so konstruiert, dass ein einzelnes falsches oder fehlendes Zeichen immer Inkonsistenz hervorruft. Es müssen also mindestens zwei zufällige Fehler in den Daten oder ein zusätzlicher in der Prüfinformation vorliegen, die sich gerade neutralisieren, damit ein Fehler bei Speichermedium oder Übertragung unbemerkt bliebe.
  • Einige Prüfverfahren sind in Hardware hineingelötet oder werden direkt durch Hardware-Algorithmen unterstützt, was auf kryptografische Hashcodes eher nicht zutrifft.
  • Weil es Standardbibliotheken sind, hatten Programmierer zur Generierung von Lizenzschlüsseln zu einem Benutzernamen oder zur Sicherung von Highscores diese gern mal benutzt. Durch De-Assemblierung bei fehlendem Obfuscating oder simples Ausprobieren war das aber auch öfters geknackt worden und dann durch präzise Methodenbeschreibung oder als kleines Quellprogramm die Generierung der Codes jedermann verfügbar gemacht worden.
  • Der Daten-Fingerabdruck soll mit möglichst einfachem und schnellem Algorithmus die technische Integrität der Daten sicherstellen. Er ist nicht dafür vorgesehen, dass man jemand statt eines Beatles-Songs die Stones unterschiebt.
  • Ich hatte noch nicht die Ehre eines Vaterschaftsnachweises, aber bei der Bekanntgabe von DNA-Analysen heißt es immer, dass dies mit einer Wahrscheinlichkeit von eins zu x Millionen …
  • DNA-Analyse („genetischer Fingerabdruck“) und Daktyloskopie haben gemeinsam, dass nur eine relativ winzige Auswahl von Merkmalen herausgegriffen wird und bereits deren Kombination eine „nahezu eindeutige“ Zuordnung zum Individuum erlaubt. Aus dieser Merkmalskombination lässt sich nicht auf den Gesamt-Menschen zurückrechnen, wie im Artikel schon richtig beschrieben. Genausowenig lässt sich nur aus dem Hashcode die gesamte Datei rekonstruieren; dies bedürfte schon der (kürzesten) verlustfreien Kompression.

LG --PerfektesChaos 10:57, 28. Feb. 2012 (CET)

es sollte zumindest zu klaeren sein, fuer was der begriff tatsaechlich benutzt wird. hier helfen nur einzelnachweise, quellen und belege. ad 2) wenn es sehr gebrauchlich ist, ist es sicher kein problem, eine quelle zu finden und einzubauen. ad 4) der begriff "kryptografischer Fingerabdruck" erscheint mir in diesem zusammenhang merkwuerdig, der begriff bezeichnet in der kryptographie recht speziell einen fingerprint eines schluessels. wir sollten uns auf die bestehende terminologie beschraenken und keine neuen begriffe erfinden. "hashcode" klingt ebenfalls merkwuerdig, eine hashfunktion ist ja gerade kein code, weil nicht injektiv. der artikel braucht einfach viel mehr belege. --Mario d 11:48, 28. Feb. 2012 (CET)

Besucher: Zur Diskussion über den vergleich von Fingerprint -> Fingerabdruck zu Hashwerten. Als eingefleischter Administrator, halte ich den Vergleich mit einem menschlichen Fingerabdruck als zu anmaßend. 1. Der Hashwert besitzt kein erkennbares Alleinstellungsmerkmal, ein einziger Hashwert kann gleichzeit verschiedenen großeb Datenmengen oder sogar Datentypen angehören, z.B. kann eine Bilddatei den gleichen Hashwert wie ein Textdokument haben, der Hashwert alleine läßt darauf keine Rückschlüsse zu. Ein menschlicher Fingerabdruck, wird aber immer als menschlicher Fingerabdruck zu identifizieren sein, auch wenn die Identität der Person selbst nicht ermittelt werden kann!!! 2. Hashwerte haben nur eine geringe Wahrscheinlichkeit der Eindeutigkeit und sind nur im Bruchteil so aussagekräftig wie menschliche Finger- oder DNA-Abdrücke. Es liegt in der Natur der Hashfunktionen, dass diese mit einer geringstmöglichen Datenmenge eine möglichst große Datenmenge vor geringstmöglicher Abweichung sichern sollen. Daher liefern Hashfunktionen bei der geringstmöglichen Abweichung (1-Bit)einen völlig abweichenden Hashwert, weil sie genau hierfür erschaffen wurden um in zwei bekannten Datenmengen nach Differenzen zu suchen, denn es wird hier immer nur von einer bereits bekannten Datenmenge ausgegangen und „angenommen“ das die zweite Datenmenge identisch mit der ersten sein soll. Hier liegt in Hashfunktionen der erste „Knackpunkt“, denn dieser Abgleich funktioniert immer nur bei der geringstmöglichen Abweichung, ist die Abweichung größer als geringstmögliche Abweichung zwischen den Datenmengen, kann es zu einer Kollision kommen wenn die Datenmenge größer als der eigentliche Hashwert ist. Beispiel: Wir haben einen maximalen Hashwert von 4-Bits die bei den Zuständen „0“ oder „1“ 16 verschiedene Kombinationen Bilden können von 0000 bis 1111 daher sind also nur 16 „Hashschlüssel“ möglich. Nun stellen wir uns eine 4-Bit Datenmenge vor, die ja gleichfalls 16 verschiedene Datenmengen bilden kann von 0000 bis 1111, hier kann also noch jeder der 16 möglichen Datenmengen einen eigenen Hashschlüssel besitzen, womit eine „nahezu eindeutige“ Identifizierung der Datenmenge möglich ist. Wenn wir jetzt aber die Datenmenge um nur 1-Bit erhöhen, so können jetzt 32 verschiedene Datenmengen gebildet werden nämlich von 00000 bis 11111, da ich aber nur 16 mögliche Hashschlüssel zur Verfügung habe, muß mindestens 1 Hashschlüssel jetzt mehreren Datenmengen zugeordnet sein, oder aber mehere Hashschlüssel sind mehreren Datenmengen zugeordnet, womit die „nahezu eindeutige“ Identifizierung nicht mehr haltbar ist! Kurz gesagt, ich habe 32 verschiedene Türschlosser die sich alle mit irgendeinem meiner 16 Schlüssel am Schlüsselbund aufschließen lassen. Meiner Meinung nach dürfte ein Hashschlüssel der die Bedingung „nahezu eindeutig“ erfüllt, nur einer sein der z.B. durch eine „Lostless Compression“ Funktion gebiltet wurde, da hier das Alleinstellungsmerkmal erhalten bleibt, auch wenn der Hashschlüssel weniger Daten, als die Bezugsdatenmenge besitzt. Was das tolle Zwillingsbeispiel oben von [Chire] angeht, ja logisch haben Zwillinge Eineige Zwillinge den selben Fingerabdruck, genau wie jede kopierte Datei auch, da ja auch die Datenmenge identisch sind (DNA-Code).

>>>Ein Hashwert wird deshalb auch als Fingerprint bezeichnet, da er eine nahezu eindeutige Kennzeichnung einer größeren Datenmenge darstellt, so wie ein Fingerabdruck einen Menschen nahezu eindeutig identifiziert.<<< könnte man ein: >>>Ein Hashwert wird deshalb auch als Fingerprint bezeichnet, da er eine Kennzeichnung einer größeren Datenmenge darstellt, ähnlich wie der Fingerabdruck eines Menschen.<<< drauß machen? (nicht signierter Beitrag von 217.84.247.96 (Diskussion) 01:28, 29. Feb. 2012 (CET))

  • Ouaaahh – jetzt geht das schon wieder los.
    • Wie ich eingangs schon angemerkt hatte, ist der anschauliche Fingerabdruck-Vergleich nur möglich, wenn auch eine entsprechende Code-Länge dazugeliefert wird.
    • Im Artikeltext müsste mal wieder so etwas stehen wie "längerer Code"; dann kommt es hin.
    • Bei einer ISBN würde man auch nicht von ihrem Fingerabdruck sprechen, die Datenmenge ist zu mickrig und es reicht auch nur zu einer Prüfziffer. Formal ist das natürlich alles das Gleiche.
    • Dass der Vergleich bei einem CRC32 gut passt, habe ich weiter oben vorgerechnet. Das heißt nichts anderes, als dass für praktische Zwecke der CRC32 das Datenpaket mit an Sicherheit grenzender Wahrscheinlichkeit identifiziert. CRC16 würde ich mir auch noch als "Fingerabdruck" gefallen lassen, darunter wird es albern.
  • Zur Frage der Gebräuchlichkeit:
    • Über 1,1 Millionen Treffer bei Google mit CRC32+Fingerprint; den ersten besten habe ich mal herausgegriffen.
  • Abseits vom aktuellen Problem wäre es mal historisch interessant, ob zuerst in der Kryptografie oder in der Speichertechnik die Vokabel "Fingerprint" zuerst auftauchte. Bei Speichermedien dürfte der Vergleich in den 1970ern aufgekommen sein, die nicht-elektrifizierte Kryptografie könnte schon im Zweiten Weltkrieg damit hantiert haben?
Schönen Tag --PerfektesChaos 09:25, 29. Feb. 2012 (CET)
Besucher: Es geht doch nicht um "Fingerprint"<>"Fingerabdruck" sondern mehr um die Verbindung von "nahezu eindeutige Kennung" gegenüber "nahezu eindeutig identifiziert" es wird hier nahezu eindeutig der Eindruck erweckt, dass ein Hashwert grundsätzlich die gleiche unumstößliche Aussagekraft besitzt. (nicht signierter Beitrag von 79.243.51.26 (Diskussion) 11:03, 29. Feb. 2012 (CET))
ich bin auch der meinung, dass die aussage "dass für praktische Zwecke der CRC32 das Datenpaket mit an Sicherheit grenzender Wahrscheinlichkeit identifiziert" so nicht haltbar ist; das gilt nur unter der voraussetzung, dass die fehler zufaellig auftreten. --Mario d 11:23, 29. Feb. 2012 (CET)
Ich lese den Satz in der Einleitung aus: "[ein sicherer Hashwert] wird auch als Fingerprint bezeichnet, weil" (= Erklärung, woher der Begriff kommt) und nicht als ein "Jeder Hashwert heißt auch Fingerprint, weil er eine Datenmenge genau so eindeutig identifiziert wie ein Fingerabdruck einen Menschen" (auch nicht immer eindeutig identifiziert?). Meiner Meinung nach sollten wir alle kryptologischen und quantitativen Feinheiten hier noch aussparen, und und auf den Begriff konzentrieren, warum dieser gebräuchlich ist (ohne jetzt darauf herum zu reiten, ob der Vergleich manchmal hinkt, humpelt oder ein Bein amputiert hat). --Chire 14:00, 29. Feb. 2012 (CET)
im der einleitung steht aber nichts von "sicher", weil "sicher" fuer hashfunktionen gar nicht definiert ist. das problem, das ich hier sehe, ist, dass wir mindestens drei verschiedene begriffe durcheinanderwerfen - fuer welche arten von hashfunktionen ist der begriff "fingerprint" denn gebraeuchlich? nur fuer pruefsummen? wenn es keine praezise definition gibt, sollten wir das auch vermerken, bspw. mit dem hinweis "umgangssprachlich". die loesung im englischen artikel gefaellt mir wesentlich besser. pruefsummen und kryptologische hashfunktionen haben ja bereits einen eigenen artikel, die sollten wir mMn nur am rande behandeln und uns auf die streuwertfunktionen und hashtabellen konzentrieren, die im moment viel zu kurz kommen. dann koennten wir die viel zu lange einleitung auch auf ein vernuenftiges mass kuerzen. dass wir in einen abschnitt zuerst sagen, dass ein hashwert "eine nahezu eindeutige Kennzeichnung einer größeren Datenmenge darstellt" und dann im uebernachsten satz "[d]a der Hashwert in der Praxis meist kürzer als die originale Datenstruktur ist, sind solche Kollisionen dann prinzipiell unvermeidlich" ist keine feinheit. deshalb: begriffe klar trennen und bequellen. --Mario d 14:50, 29. Feb. 2012 (CET)
Naja, aber es gibt ja eben Hashtabelle für die Hashfunktionen die "nur" streuen können. Hier gibt es auch vieles zu sagen, was nicht einfach so in das Thema Hashfunktion passt - Bspw. für erweiterbares lineares Hashing, partielle Erweiterungen etc. - sondern sehr speziell auf die Anforderungen von speziellen Hashtabellen zugeschnitten ist. Kuckucks-Hashing mit zwei möglichs unabhängigen Hashfunnktionen, zweistufige Hashfunktionen und so weiter. Fakt ist ja auch, dass man als Hashfunktionen (gerade als erste Stufe) zum Teil trivialitäten wie die Identitätsfunktion (auf pointern) verwendet ... Warum nicht diese Arten von Hashfunktionen stärker bei Hashtabelle diskutieren, und hier eben den allgemeineren Fall inkl. Prüfsumme und Kryptologischen Hashfunktionen mit Fokus auf den Gemeinsamkeiten diskutieren? Kollissionen gehören da aber dazu: sie sind ja gewollt (und man will sie auch kontrollieren). Bei Hashtabellen will man wenig Kolissionen für Muster (z.B. Sequenzen) in den Daten; bei Prüfsummen sollen Übertragunsfehler keine Kolissionen haben, und bei kryptologischen Hashfunktionen sollen Kolissionen möglichst wenig vorhersagbar sein (was impliziert, dass der Hashcode möglichst keinen Rückschluss auf die Eingabedaten erlauben sollte). --Chire 19:46, 29. Feb. 2012 (CET)
Besucher: Also die CRC-Fingerprint sind auch lustig, das Teil nennt sich Checksum Generator creats Fingerprints ;) Eine Übersetzung mit leo.org bringt folgende Ergbnisse Fingerprint -> der Fingerprint; das Daktylogramm; der Fingerabdruck; der Leitparameter. Freie Auswahl würde ich behaupten. (nicht signierter Beitrag von 79.243.51.26 (Diskussion) 14:58, 29. Feb. 2012 (CET))
"das Teil nennt sich Checksum Generator creats Fingerprints"??? CRC steht für "cyclic redundancy check". Technisch gesehen ist es ein "error detecting code" (kein "error correcting code", und auch kein "message authentication code"!). Aus keinem der Begriffe kann ich "Checksum Generator creats Fingerprints" herleiten. --Chire 19:46, 29. Feb. 2012 (CET)
Fakt ist, es gibt Bücher mit Titeln wie "Fingerprinting: Hash-based error detection in microprocessors" von der CMU. Zitat: "the ideal hash design from an aliasing perspective is the cyclic redundancy check (CRC)" [... aber andere Anforderungen werden nicht so gut erfüllt ...]. Auch wenn CRC für manche "nur" eine Prüfsumme ist, gibt es eben dennoch 300000 Treffer bei Google für "crc32 hash". Inklusive PHP und der Python "hashlib". Wir sollten nicht so tun, als ob Hashtabellen die einzigen "echten" Hashfunktionen wären. Also auf die schnelle habe ich nirgendwo (GNU trove z.B.) besonders trickreiche hashfunktionen gesehen. Es geht eigentlich ausschließlich um die Geschwindigkeit, etwas wie (x ^ (x >>32)) als "hashfunktion" ist keine Seltenheit (und die Hashtabelle intern hasht ein zweites Mal, mit (hashcode % Tabellenlänge) - auch kein großer Trick, sondern geradezu unvermeidlich um keinen Array overflow zu erhalten. Also: scheinen wir nicht die Hashtabellen-Hashfunktionen hier etwas zu überbewerten? --93.134.226.178 00:13, 1. Mär. 2012 (CET)
interessant, was fuer eigenschaften werden denn dort benutzt? die kompressionseigenschaft oder die fehlerkorrektur? koennte man dort theoretisch auch andere fehlerkorrigierende codes einsetzen? was du sagst ueber hashfunktionen sagst, entspricht genau meinem bild: schnell und simpel. das bedeutet aber nicht, dass man ihnen nicht doch mehr als zwei saetze widmen koennte.
@Chire: bei kryptologischen hashfunktionen soll es schwierig sein, kollisionen zu erzeugen, nicht sie vorherzusagen (darunter kann ich mir auch nichts vorstellen) und kollisionsresistenz impliziert 2nd-preimage-resistance, aber nicht die einwegeigenschaft (auch wenn in der praxis beides gefordert wird). ansonsten bin ich einverstanden, wir koennen gerne gemeinsamkeiten herausstellen, und die etwas komplexeren faelle behandeln (die Universelle Hash-Funktion faellt mir hierzu noch ein), wir sollten aber darauf achten, die unterschiede auch zu erwaehnen und nicht alles in einen topf werfen. letztenendes sind das alles verschiedene anwendungen mit verschiedenen anforderungen --Mario d 11:27, 1. Mär. 2012 (CET)

Neu anfangen?

Letzter Kommentar: vor 11 Jahren4 Kommentare3 Personen sind an der Diskussion beteiligt

Uah. Diesen Lemma ist so verworren. Hier werden kryptographischen Hashes vermengt mit Abbildungen, es gibt manches doppelt und dreifach, anderes wird gar nicht erklärt oder es gibt obskure hinweise auf elektrotechnische Verfahren. Können wir nicht einfach neu anfangen und den englischen Lemma übersetzen? Mindestens das Bild aus der WP:EN hierher holen, weil der spezieller Hash (kryptografischer Hash) total verwirrend ist für Anfänger. --WiseWoman (Diskussion) 14:03, 25. Dez. 2012 (CET)

ich stimme zu, dass der artikel stark verbesserungsbeduerftig ist. der englische artikel ueberzeugt mich aber auch nicht wirklich, seine struktur ist doch recht schwach. am besten waere es, den artikel anhand eines lehrbuchs umzuschreiben und dabei vielleicht weniger stark auf pruefsummen und kryptographische hashfunktionen einzugehen. das bild habe ich schonmal ersetzt. --Mario d 20:19, 5. Jan. 2013 (CET)
Ich denke, man kann den Artikel noch retten. Ihn anhand eines Lehrbuchs neu zu verfassen, halte ich für riskant, da ggf. dann einfach abgeschrieben wird, was möglicherweise dann wieder eine URV nach sich zieht.
Verstehe auch nicht, warum sich hier für die kryptologischen Anwendungen ergangen wird, wenn es dafür einen eigenen Artikel gibt?! Und vor allem dieses merkwürdige Beispiel darunter kann m. E. komplett raus. -- Plankton314 (Diskussion) 14:48, 11. Jan. 2013 (CET)
Ich habe den Artikel jetzt etwas gekürzt und einige fragwürdigen Formulierungen ersetzt.
Insgesamt fehlt etwas der rote Faden, aber das ist halt WP. Ansonsten fand ich die Beispiele garnicht schlecht für das Grundverständnis. -- Plankton314 (Diskussion) 15:32, 11. Jan. 2013 (CET)

Muss der Hashwert unbedingt kleiner sein ?

Letzter Kommentar: vor 9 Jahren2 Kommentare2 Personen sind an der Diskussion beteiligt

Muss der Hashwert unbedingt kleiner sein ? Es gibt durchaus Fälle, mit einer Eingabe von beliebiger Länge wo die Eingabe kleiner als die Ausgabe sein kann. Ein praktisches Beispiel sind Passwörter, die in Schlüssel umgerechnet werden. Hat man eine Hashfunktion, die beliebig lange Strings in 16 byte lange AES-Schlüssel umrechnet, so ist es trotzdem noch eine Hashfunktion, wenn das Passwort einen Buchtaben lang ist. Auch die 16 bit Prüfsumme eine 1 Byte großen Datei, oder die SHA1 Prüfsumme (20 Byte) einer 10 Byte großen Datei ist ein Beispiel für eine kleinere Eingabe. -- 79.225.98.95 20:51, 24. Aug. 2015 (CEST)

der hashwert muss nicht kleiner sein als die eingabe. die menge der eingaben ist größer als die menge der ausgaben. --Mario d 13:54, 27. Aug. 2015 (CEST)

"Universelle Menge an Hashfunktionen" nicht erwähnt.

Letzter Kommentar: vor 5 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

Ich konnte keine Erwähnung von "Universelle Menge an Hashfunktionen" oder "Universelles Hashing" finden. Aber sie wären erwähnenswert, da eine zufällige Auswahl von Hashfunktionen, die Schlüssel noch besser verteilt. (Siehe: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest & Clifford Stein: Algorithmen. Eine Einführung. 4. Auflage. Oldenbourg, München 2013, ISBN 978-3-486-74861-1, S. 267 ff.) (nicht signierter Beitrag von Landschaftsblick (Diskussion | Beiträge) 10:57, 23. Aug. 2019 (CEST))

nicht injektiv = surjektiv?

Letzter Kommentar: vor 4 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

Ist eine Funktion, die nicht injektiv ist, immer surjektiv? Falls ja, könnte man "nicht injektiv" durch "surjektiv" ersetzen.

Nein, das ist sie nicht. Surjektivität hat eine stärkere Anforderung (zu allen Hashwerten muss jeweils mind. ein Schlüssel existieren). Daher steht nicht injektiv als grundlegende Eigenschaft da, und Surjektivität als wünschenswertes Kriterium. --H3xc0d3r (Diskussion) 06:39, 15. Dez. 2019 (CET)

Einleitungssatz

Letzter Kommentar: vor 4 Jahren2 Kommentare2 Personen sind an der Diskussion beteiligt

Der Einleitungssatz,

Eine Hashfunktion (auch Streuwertfunktion) ist eine Abbildung, die eine große Eingabemenge (die Schlüssel) auf eine kleinere Zielmenge (die Hashwerte) abbildet.

, ist nicht richtig! Die Eingabemenge kann x-beliebig groß sein und die Zielmenge, ist je nach verwendeter Hashfunktion, ist immer nur eine bestimmte Zielmenge. Die Zielmengengröße wird bestimmt durch die Hashfunktion (definierte Größe der Zielmenge)!

Beispiel MD5 Hash: Eingabe kann beliebig(größer 0) groß sein aber die Zielmenge ist immer 32 alphanummerische Zeichen lang. (nicht signierter Beitrag von 87.175.18.109 (Diskussion) 20:09, 26. Feb. 2019 (CET))

Zitat: die Zielmenge ist immer 32 alphanummerische Zeichen lang. Das ist unglücklich formuliert. Jeder Wert dieser Menge ist immer 32 alphanummerische Zeichen lang. Es geht aber nicht um die Größe eines Hashwertes, sondern um die Größe der Menge. Das Repertoire an möglichen Schlüsseln ist i.d.R. größer als die Anzahl möglicher Hashwerte. Wieviel davon genutzt wird, ist irrelevant. Insofern ist der Satz richtig. --H3xc0d3r (Diskussion) 06:30, 15. Dez. 2019 (CET)

Abgerufen von „https://de.wikipedia.org/w/index.php?title=Diskussion:Hashfunktion/Archiv/1&oldid=237422836“