Exkluzivní disjunkce

Exkluzivní disjunkce (někdy též vylučovací nebo úplná disjunkce, exkluzivní OR či XOR) je logická operace, jejíž hodnota je pravda, právě když každá vstupní hodnota nabývá, v porovnání s ostatními vstupy, unikátní hodnotu.

XOR je někdy též označován jako nonekvivalence (NEQ), což je ale nepřesné a zavádějící: Taková identita platí pouze pro dvě proměnné dvouhodnotové logiky, jak snadno ukáže Karnaughova mapa.

Definice

Pravdivostní tabulka funkce XOR
B	A	A ⊕ B
0	0	0
0	1	1
1	0	1
1	1	0

V logice a matematice je exkluzivní disjunkce označením pro „buď …, anebo …“. Například „Počítač je buď zapnutý, anebo vypnutý.“ je exkluzivní disjunkce.

Pro vstupy A a B vypadá pravdivostní tabulka exkluzivní disjunkce následovně (0 označuje nepravdivé tvrzení, 1 označuje pravdivé tvrzení).

Použití v informatice

Funkce XOR se používá na tzv. „maskování“, které lze například použít v jednoduché hře, kde je potřeba zobrazit postavičku na předem daném pozadí. První maskování postavičku do pozadí inverzně vloží a druhé maskování vrátí pozadí do původní podoby (jedničky v masce nejprve bity překlopí, pak je vrátí do původní podoby).

Použití v kryptografii

V kryptografii se často používá bitová funkce XOR, která je obvykle vestavěna přímo v procesoru a ten ji tak může provádět efektivně. XOR používají například šifry DES či AES^[1], ale i různé hashovací funkce^[2]. V nejnovějších návrzích hashovacích funkcí je dokonce operace XOR tou nejdůležitější.^[3]

Můžeme také využít jednoduchou šifru XOR, kdy máme na vstupu binární řetězec a klíč. Na tyto vstupy aplikujeme operaci XOR. Ukázka:

Vstupní text: 0111011010101
Klíč:         1011000100100
Výsledek XOR: 1100011110001

Pokud výsledek XOR, což je ve skutečnosti zašifrovaný text, znovu aplikujeme XOR s klíčem, dostaneme původní text:

Výsledek XOR: 1100011110001
Klíč:         1011000100100
Vstupní text: 0111011010101

Zajímavé je, že pokud provedeme výsledek XOR vstupní text, dostaneme původní klíč:

Výsledek XOR: 1100011110001
Vstupní text: 0111011010101
Klíč:         1011000100100

Odkazy

Reference

↑ Srovnání standardu AES s algoritmy 3DES a IDEA
↑ is.mendelu.cz: Hashovací funkce
↑ Crypto-World, Sešit 2/2009: Vlastimil Klíma, citace ze strany 10: „Technologickým nástrojem většiny rychlých algoritmů soutěže jsou pouze operace ADD a XOR moderních procesorů!“

Související články

Externí odkazy

Obrázky, zvuky či videa k tématu exkluzivní disjunkce na Wikimedia Commons

[1] Srovnání standardu AES s algoritmy 3DES a IDEA

[2] s.mendelu.cz: Hashovací funkce

[3] Crypto-World, Sešit 2/2009: Vlastimil Klíma, citace ze strany 10: „Technologickým nástrojem většiny rychlých algoritmů soutěže jsou pouze operace ADD a XOR moderních procesorů!“

[1]

[2]

[3]