Exkluzivní disjunkce
Exkluzivní disjunkce (někdy též vylučovací nebo, exkluzivní OR či zkratkou 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.
Obsah |
[editovat] Definice
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 |
[editovat] Aplikace 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
[editovat] Odkazy
[editovat] 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ů!“
