Exkluzivní disjunkce

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledá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]

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í).

B A A ⊕ B
0 0 0
0 1 1
1 0 1
1 1 0

Aplikace 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]