Share to: share facebook share twitter share wa share telegram print page

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

  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

Externí odkazy
Kembali kehalaman sebelumnya