XOR-Verknüpfung
Eine exklusiv-ODER-Verknüpfung (auch XOR, EOR, Modulo-2 Addition, Antivalenz oder Kontravalenz) ist ein Begriff aus der Aussagenlogik. Die Gesamtaussage ist dann wahr, wenn entweder die erste Aussage oder die zweite Aussage wahr ist, aber nicht beide. Als Formelzeichen wird meist der Ausdruck xor oder das Zeichen verwendet.
Im Deutschen entspricht die Formulierung "Entweder A oder B (aber nicht beide)" am besten dem Ausdruck "A XOR B", also der XOR-Verknüpfung der Aussagen A und B.
Praktisch entspricht dies der Addition zweier Bits modulo 2 - ist die Summe eine gerade Zahl ergibt sich 0, ist sie ungerade 1
XOR-Verknüpfung zweier Bits: 0 0 = 0 0 1 = 1 1 0 = 1 1 1 = 0
Die Umkehrung der XOR-Funktion ist die XNOR-Verknüpfung.
Die XOR-Verknüpfung ist assoziativ und kommutativ.
Eine weitere Eigenschaft der XOR-Verknüpfung ist, dass die zweimalige Anwendung der Operation der Identität entspricht, d.h. sie ist selbstinvers. Dies wird u.a. in der Kryptographie (dadurch kann beim Verschlüsseln die gleiche Funktion verwendet werden wie beim Entschlüsseln) und beim RAID-System ausgenutzt:
101 XOR 011 = 110 110 XOR 011 = 101 110 XOR 101 = 011
Anwendungsbeispiel in der Kryptografie
Das nachweislich sichere Verschlüsselungsverfahren One-Time-Pad wird meist unter Zuhilfenahme einer XOR-Verknüpfung implementiert. Die zu verschlüsselnde Nachricht wird dazu zuerst als Bitfolge kodiert. Eine zweite zufällige Bitfolge, die genauso lang wie die Nachricht ist, wird als Schlüssel verwendet. Der Geheimtext entsteht indem das erste Bit der Nachricht mit dem ersten Bit des Schlüssels XOR-verknüpft wird, anschließend das zweite Bit mit dem Zweiten usw. Führt man anschließend die gleiche XOR-Verknüpfung mit dem Geheimtext und dem Schlüssel aus, so erhält man wieder die ursprüngliche Nachricht.
Anwendungsbeispiel im RAID-System
Wir haben zwei Bitfolgen 101 und 011, aus denen mittels XOR-Verknüpfung die Parität gebildet wird: 110 (erste Zeile). Geht nun die erste Bitfolge (101) verloren, so können wir sie wiederherstellen, indem wir die zweite Bitfolge (011) mit der Parität XOR-verknüpfen (zweite Zeile).