Diskussion:Einwegfunktion

Telefonbuch-Analogon

Ich bin mit dem Analogon am Schluss nicht einverstanden:

"Eine Falltürfunktion kann mit einem Telefonbuch verglichen werden. Kennt man den Namen, findet man sehr schnell die dazugehörige Telefonnummer. Wenn man aber nur die Nummer ohne den dazugehörigen Namen kennt, ist es fast unmöglich, diesen alleine mit Hilfe des Telefonbuches zu finden. In einer Datenbank mit Hilfe des Computers, oder auch mit eine großen, endlichen Zahl von Mitarbeitern deren Lohn gegen Null geht wäre diese Problematik leicht zu lösen."

Weder die Datenbank noch der Computer noch die Mitarbeiter entsprechen der "Geheiminformation", die die Umkehrung der Funktion effizient erlaubt. Das Analogon bezieht sich damit nur auf eine normale Einwegfunktion. Ich werde die zunächst mal ändern.

Wie wäre es mit folgendem als Analogon zur Falltürfunktion: Das Einstecken eines Briefes in den Briefkasten entspricht dem Anwenden der Funktion f. Ohne Schlüssel ist der Brief nur mit viel Zeit (und Gewalt) wieder herauszubekommen, d.h. das Invertieren von f ist schwer. Hat man jedoch einen Schlüssel zum Briefkasten (die Geheiminformation), so kann man den Brief wieder sehr leicht herausholen.

Vorletzte Version

Habe aus Versehen die vorletzte Version editert. Die Änderungen der vorigen Version sind in dieser Version wieder aufgenommen, leider ist nun der vorige Benutzer aus der History rausgefallen! Ich weiß leider nicht mehr wer das war, Sorry. --213.23.26.125 23:29, 26. Jun 2004 (CEST)

Echte Einwegfunktionen

Ich habe den Satz "Echte Einwegfunktionen lassen sich nicht umkehren" zurückgesetzt. Offenbar liegt hier ein Missverständnis vor. Bei jeder Rechenvorschrift, die aus x ein f(x) berechnet, kann man bei gegebenem f(x) auch einen passenden Wert für x angeben und sei es, indem man den gesamten Definitionsbereich ausprobiert. Es ist eben nur eine Frage des Aufwandes und der soll bei Einwegfunktionen eben möglichst groß sein. Der P = NP Zusatz besagt, dass eine nichtdeterministische Maschine den passenden Wert raten und dann schnell bestätigen kann, da ja die Bestätigung per definitionem leicht sein soll.

Die oft vermutete aber nie bestätigte Hintertür bei DES hat nichts mit den hier behandelten Trapdoor-Einwegfunktionen zu tun. --Rat 21:46, 19. Aug 2004 (CEST) Bitte beim Editieren nicht die Unterschriften und Datumsangaben anderer entfernen, sondern stattdessen die eigenen setzen, danke --Rat 16:04, 8. Mär 2006 (CET)

Sorry, aber da liegst du falsch, z.B. kann aus einem Hashwert das x nicht nicht mehr berechnet werden, da es mehrere(unendlich viele) Möglichkeiten gibt, also ist der Begriff der echten Einwegfunktion sehr wohl richtig und durchaus auch gebräuchlich. --159.149.57.14 19:10, 1. Mär 2006 (CET) Unterschrift nachgetragen

Nein, darin liegt nicht der Sinn von Einwegfunktionen. Nach dem, was mein Vorschreiber geschrieben hat, wäre jede konstante Funktion als echte Einwegfunktion zu klassifizieren.

Dass eine Funktion nicht injektiv ist, macht sie längst nicht zur Einwegfunktion. Es sollte schwierig sein, zu gegebenem y ein x zu finden mit f(x)=y, nicht ein ganz bestimmtes x.

--141.2.6.22 15:31, 8. Mär 2006 (CET)

Es gibt ein Problem mit der Nennung von MD5 als Kandidat für Einwegfunktionen. MD5 ist nicht mehr sicher, somit stellt MD5 auch keine Einwegfunktion mehr dar, da es sich mit geringem Aufand attackieren lässt (ich meine 200 Playstation3, 3 Tage). Somit sollte MD5 entfernt werden. Darüber hinaus liegt SHA-1 derzeit auch unter Beschuss und steht im Verdacht unsicher zu sein. Dies sollte man wohl im Text anmerken und die entsprechenden Quellen suchen und zitieren.

--88.76.46.49 15:04, 21. Jan. 2009 (CET)

übersetzung trapdoor

warum soll das denn falsch übersetzt sein, wenn man trapdoor mit Falltür übersetzt? Wörterbücher geben das als exakte Übersetzung an.

Könnte generell auf die Trapdoor-Funktionen eingegangen werden? Ich verstehe nicht, wofür die gut sein soll.

Danke, --Abdull 20:59, 17. Jan 2005 (CET)

Falltür ist in der Tat eine unglückliche (wenn auch wörtliche) Übersetzung, da im Englischen trapdoor auch manchmal die Bedeutung einer Geheimtür trägt. Dies entspricht viel mehr dem, was eine Trapdoor-Funktion ist: Sie ist schwer zu öffnen (d.h. y=f(x) invertieren), so lange man das Geheimnis nicht kennt, aber leicht zu öffnen, wenn man es kennt. --MRA 17:52, 25. Jul 2005 (CEST)

Das stimmt nicht. "Geheimtür" heißt auf Englisch "secret door". Ich habe bei dict.leo.org und in zwei gedruckten Wörterbüchern (Langenscheidt Taschenwörterbuch und Duden Oxford Großwörterbuch) nachgeschaut: "trapdoor" wird überall mit "Falltür" und nirgends mit "Geheimtür" übersetzt (und "Geheimtür" überall nur mit "secret door"). Man mag das Bild für ungeschickt halten, aber die Übersetzung ist einwandfrei. Ich entferne daher die entsprechende Bemerkung (siehe WP:Q, WP:TF, WP:NPOV). --80.129.93.77 17:35, 27. Sep. 2007 (CEST)

Kandidaten für Einwegfunktionen

Ist die Bezeichnung von MD5 und SHA-1 (und ähnlichen Hashfunktionen) als Kandidaten für Einwegfunktionen gerechtfertigt? Diese Funktionen können doch rein formell betrachtet aufgrund ihrer Kompressionseigenschaft keine Einwegfunktionen sein. Der Ausgaberaum ist endlich und daher kann man mit entsprechend viel Speicherplatz einen Algorithmus bauen, der für jeden Hashwert in konstanter Zeit ein Urbild liefert, indem man einfach alle möglichen Eingabestrings durchläuft bis man alle Werte hat (vorausgesetzt, dass es für alle Werte ein Urbild gibt, aber das ist nebensächlich, weil man für jeden Wert beweisen kann, ob es eines gibt). Für die Praxis ist das zwar wegen des begrenzten Speicherplatzes nicht relevant, aber formell sind es doch keine Einwegfunktionen. 78.52.216.106 20:22, 7. Mär. 2009 (CET)

Da niemand Einwände erhoben hat, werde ich mal die Behauptung entfernen. -- 92.226.134.40 17:01, 3. Apr. 2009 (CEST)

Der Artikel ist etwas theoretisiert. Es ist unbekannt, ob Einwegfunktionen existieren bezieht sich auf die beweisbar komplexitätstheoretische Definition. Praktisch wird als Einwegfunktion bezeichnet, was den Angriffen zahlreicher Kryptologen bisher standgehalten hat. Ich revertier das mal und formulier das um. Der md5 ist zwar in Teilen geknackt, für viele Anwendungen als Einwegfunktion dennoch hinreichend. --Suricata 21:43, 3. Apr. 2009 (CEST)

OK, die Idee halte ich für gut. Wenn man nur die formale Definition aufführt, werden Leser verwirrt, die auf die informelle Verwendung stoßen. Bloß die Formulierung ("im Allgemeinen") halte ich für nicht sauber genug.

Es handelt sich dabei um eine leider häufige, aber trotzdem einfach nur falsche Verwendung des Wortes "allgemein". Wenn etwas im Allgemeinen gilt, gilt es im Speziellen erst recht. Es wird aber oft so verwendet, um zu sagen, dass etwas in einem Speziallfall nicht gilt, aber in "vielen" anderen Fällen (die der Sprecher üblicherweise für die einzig bedeutenden hält) eben doch. Ich ändere das mal um in "in einem erweiterten Sinne", damit es dann auch mit dem unteren Absatz konsistent ist.

Mit meiner Behauptung zu den komprimierenden Einwegfunktionen im mathematischen Sinne (78.52.216.106) liege ich ja richtig, oder? Wenn ich hier so aus dem Handgelenk die Konstruktion hinbekomme, gibt es da ja sicher was in der Literatur wo das formal sauber bewiesen wird. Und damit ist dann eben doch eine effiziente Umkehrung bekannt, die aber nicht praktisch umsetzbar ist.

Die Sicherheit von kryptographischen Hashfunktionen beruht darauf, dass der Umkehrungsaufwand in der Länge des Hashes (nach derzeitigem Wissensstand) exponentiell wächst und eine feste Länge gewählt wird, die für heute übliche Computer praktisch nicht umkehrbar ist. Das hat aber mit Einwegfunktionen im formellen Sinn weniger zu tun.

Ich hätte noch einen Vorschlag: Vielleicht sollten wir hier tatsächlich nur die formale Definition besprechen, aber darauf hinweisen, dass die Sache eng mit Hashfunktionen verknüpft ist und oft synonym verwendet wird. -- 78.54.168.200 14:30, 14. Apr. 2009 (CEST)

Nicht jede Einwegfunktion ist eine Hashfunktion und umgekehrt. Hashfunktionen zur Kollisionsvermeidung in Datenbanken brauchen keine Einwegfunktionen zu sein. Umgekehrt ist der RSA eine Einwegfunktion aber bijektiv, also keine Hashfunktion. Somit ist die jetzige Themenverteilung schon korrekt. --Suricata 15:39, 14. Apr. 2009 (CEST)

Sorry, hab mich ein bisschen uneindeutig geäußert. Ich meinte jetzt nur Hashfunktionen der Art von SHA-x&Co. mit einer festen Ausgabelänge. Das meinte ich mit komprimierend. -- 78.51.69.203 (13:33, 16. Apr. 2009 (CEST), Datum/Uhrzeit nachträglich eingefügt, siehe Hilfe:Signatur)

formale Definition 'schwer invertierbar'

Meiner Meinung sollte die Definition von 'schwer invertierbar' formaler und exakter formuliert werden. Zum Beispiel so wie in der englischen Wikipedia. Im Moment wird nicht klar, dass diese Eigenschaft für einen Zufälligen Wert des Wertebereiches gelten muss. Auch wird nicht klar, dass nur gefordert wird dass die Wahrscheinlichkeit dass der Angreifer A gewinnt, klein ist. Denn ist sehr wohl erlaubt mit einer sehr sehr glücklichen Wahl von x den Wert f(x) mit einem Schritt zu bestimmen.

Wenn ich mal Zeit hab, werd ich dass mal überarbeiten, aber hab auch nichts dagegen wenn mir jemand zuvorkommt. Den eigentlich müsste man in der dt. Wikipedia einen Artikel zu 'negligible' Funktionen anlegen... Was ich gerne vorher machen würde.--Schönen Gruß "Wohingenau" 19:46, 3. Apr. 2010 (CEST)

Frage zur Existenz

Hallo,

ich habe eine Frage zum Artikel: Es wird nach der Existenz einer Einwegfunktion gesucht.

Die Wurzelfunktion für die Menge R ist nicht polynomiell implementierbar. Die Quadrierung jedoch schon. Ist der Einwand, dass R im Zuge der Reduktion auf double reduziert ist und deshalb in endlich vielen Schritten die Wurzel auf Fließkommagenauigkeit berechnet werden kann, dann gilt eben diese Eigenschaft für jeden Algorithmus und jeder Algorithmus würde in konstanter Zeit laufen.

Will man mit polynomieller Zeit eine Eingabelänge n in N fordern, so ist n die Anzahl der Digits der Zahl. Ihr Quadrat liegt dann in n*log(n)^2 (Schönhage-Strassen) und ihre Wurzel liegt in inf, (Newton, Householder, etc.).

Ich freue mich über Rückmeldungen. Vielleicht klärt sich dann auch meine Frage zur Sinnhaftigkeit der Frage P=NP?, deren Falschheit ich für natürlich halte, weil ich ja allein durch Problemkonstruktion eine (Rechen-)Aufgabe stellen kann, die nur in exponentieller Zeit gelöst werden kann (zB nichtlineare Funktionen hintereinander auf Tupeln des Vorergebnisses und der nächsten Eingabe eines Arrays berechnen, wobei sämtliche Permutationen am Ende zu addieren sind O(n!) ). Gibt es vielleicht gute Definitionen dieser Komplexitätsklassen? (nicht signierter Beitrag von 88.78.123.73 (Diskussion) 18:39, 29. Okt. 2013 (CET))

hallo, deine frage koennen wir hier auf der diskussionsseite nicht beantworten. diskussionen auf dieser seite sollen der verbesserung des artikels dienen (WP:D), fuer diskussionen ueber deine theorien oder zur beantwortung deiner fragen gibt es andere foren im internet. im artikel selbst sollen nur bereits in fachzeitschriften veroeffentlichte ergebnisse wiedergegeben werden (WP:Q). --Mario d 11:57, 30. Okt. 2013 (CET)

one-way-function sollte nicht mit Einwegfunktion übersetzt werden...

one-way-function heißt eher so viel wie Einbahnfunktion, während das deutsche Einweg- häufig für nur einmal zu benutzende sachen genutzt... Einwegfunktion könnte daher und dahingegen irreführend sein. (nicht signierter Beitrag von Admain Dragon-Map (Diskussion | Beiträge) 16:25, 8. Jun. 2015 (CEST))

wir müssen uns hier am sprachgebrauch orientieren und da überwiegt eindeutig "Einwegfunktion". --Mario d 11:30, 10. Jun. 2015 (CEST)

weblink

Beim weblink kriege ich vom browser eine Sicherheitswarnung. --Alex1011 (Diskussion) 09:56, 2. Okt. 2019 (CEST)