Exkluzivní disjunkce

Z Wikipedie, otevřené encyklopedie
(přesměrováno z Exklusivní disjunkce)
Skočit na navigaci Skočit na vyhledávání

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.

Naopak, 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[editovat | editovat zdroj]

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ď …, nebo …“. Například „Počítač je buď zapnutý, nebo 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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

  1. Srovnání standardu AES s algoritmy 3DES a IDEA
  2. is.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ů!“

Související články[editovat | editovat zdroj]