XOR-Verknüpfung < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:07 Di 28.06.2005 | | Autor: | tuxracer |
Hi,
ich beschäftige mich gerade mit Kryptographie und hänge etwas an der XOR-Verknüpfung. Von Seiten der Logik und Funktionsweise ist mir die Verknüpfung völlig klar, ich komme nur noch nicht dahinter, weshalb es die sicherste ist.
In vielen Verfahren wird XOR verwendet (z.B. One-Time-Pad). Ich hatte ein wenig gesucht und bin auf einen interessanten Wikipedia-Artikel gestoßen. Dort liest man "Die XOR Verschlüsselung ist die sicherste bekannte Verschlüsselungsmethod" (Quelle: http://de.wikipedia.org/wiki/XOR-Verkn%C3%BCpfung ). Ich frage mich nun weshalb das so ist. Welche algebraische Struktur besitzt die Verknüpfung die sie so sicher macht?! Wahrscheinlich sehe ich den Wald vor lauter Bäumen nicht...
Die Sache mit der im Wikipediaartikel angesprochenen Symmetrie:
"Der Vorteil der XOR-Verknüpfung ist, dass sie umkehrbar (symmetrisch) ist. Dies wird u.a. in der Kryptographie (dadurch kann beim Verschlüsseln die gleiche Funktion verwendet werden wie beim Entschlüsseln) [...]" leuchtet mir ja ein, jedoch ist das doch nur ein rein praktischer Vorteil.
Meine Vermutung tendiert momentan etwas zur 'Gleichverteilung' der Bits. Beispielsweise ist ja UND genau dann wahr, wenn beide Parameter wahr sind. Demnach sind Wahr oder Falsch ja nicht unbedingt gleich verteilt. Doch was wäre dann mit der aussagenlogischen Äquivalenz?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:28 Mi 29.06.2005 | | Autor: | Zyllyn |
Moin,
Zeichne einfach mal ein Diagramm für die XOR-Verknüpfung (und am besten auch gleich für OR und AND). Also an die Achsen jeweils 0 und 1 und in das Diagramm die Ergebnisse der Verknüpfung.
Ein Algorithmus zum Dekodieren wird versuchen Zuordnung der Orginaldaten zu den verschlüsselten Daten irgendwie zu erraten, statistisch, über Klassifizierung, wie auch immer.
Wenn du nun versucht in den Diagrammen die Bereiche der Nullen von denen der Eisen zu trennen, dann reicht bei OR und AND eine Gerade, bei XOR brauchst du zwei. Dieser kleine Unterschied macht es schwerer (quasi doppelt so schwer) eine XOR Verknüpfung zu finden und aufzulösen. Daher die Bevorzugung von XOR gegenüber OR und AND. Einzig die Äquivalenz hat die gleiche Eigenschaft wie das XOR, allerdings ist der Nutzen der Äquivalenz für eine Kodierung sehr zweifelhaft :)
Also so würde ich mir das zusammenreimen.
Was die Aussage sicherste bekannte Methode angeht, da wäre ich vorsichtig
diese Aussage würde ich in dem Kontext nur im Vergleich mit anderen logischen, zweistelligen Operatoren sehen.
Karsten
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:30 Mi 29.06.2005 | | Autor: | tuxracer |
Okay, es zielt also darauf ab, dass nur die Äquivalenz und XOR nicht linear separierbar sind. Man kann keine Trennebene angeben um die W bzw. F Werte in zwei Klassen zu separieren. Das hat mir jetzt schonmal ne ganze Menge weitergeholfen. Danke!
|
|
|
|
