Vennův diagram z |
Vennův diagram z |
Funkce XOR , často nazývané XOR (e x clusive OR ), nebo disjunkce exkluzivní nebo ⊻ v relační algebře , je logický operátor z booleovské algebry . Se dvěma operandy , z nichž každý může mít hodnotu TRUE nebo FALSE, přidruží výsledek, který sám má hodnotu TRUE, pouze pokud mají dva operandy odlišné hodnoty.
Tento operátor je široce používán v elektronice , počítačové vědě a také v kryptografii kvůli svým zajímavým vlastnostem.
Jeho symbolem je tradičně znaménko plus v kruhu: „⊕“
Říkejme A a B dva uvažované operandy. Souhlasíme, že jejich hodnotu budeme představovat takto:
1 = PRAVDAOperátor XOR je definován jeho pravdivostní tabulkou , která udává pro všechny možné hodnoty A a B hodnotu výsledku R:
Tabulka pravd XOR | ||
NA | B | R = A ⊕ B |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Jak vidíme, logický operátor XOR nebo výlučný OR lze definovat následující větou:
nebo
Výsledkem je PRAVDA, pokud mají dva operandy A a B odlišné hodnotynebo
Výsledkem je TRUE, pokud je lichý počet vstupů true (to platí zejména v případě, že jsou dva nebo více logických operátorů XOR kaskádově uspořádány ( paritní bitové generátory )Liší se od operátoru OR včetně, protože dává FALSE výsledek, když A a B jsou současně TRUE. Jeho symbol se také liší od operátoru včetně operátoru OR, jehož symbol je jednoduše „PLUS“: „+“.
Ve výpočetní technice lze tento operátor použít ke kombinaci dvou bitů , z nichž každý má hodnotu 0 nebo 1, použitím pravidel definovaných v předchozí tabulce, přičemž samotný výsledek je hodnota bitu .
U logických bran AND / OR je A XOR B = (A AND ne B) OR (ne A AND B).
Funkce XOR je příkladem paritní funkce .
Exkluzivní disjunkce , nebo J pq , lze vyjádřit pomocí spojky ("a logické", ), disjunkce ("nebo logické", ) a logické negace ( ) takto:
Exkluzivní disjunkce lze formulovat také takto:
Toto znázornění XOR může být užitečné při budování obvodu nebo sítě, protože má pouze jednu operaci a malý počet operací a . Důkaz této identity je uveden níže:
Někdy je užitečné si uvědomit následující:nebo:
Tuto rovnocennost lze zjistit uplatněním zákonů De Morgana dvakrát na čtvrtý řádek výše uvedeného důkazu.
Výhrada nebo je také ekvivalentem negace logické ekvivalence podle pravidel hmotné implikace.
Stručně řečeno, máme:
Zvažte digitální dokument, který chcete zašifrovat, sestává z řady bitů . V metodě šifrování streamu musí také existovat řada bitů stejné délky, zcela náhodná , která se nazývá šifrovací klíč . Bity dokumentu se zpracovávají jeden po druhém, a to kombinací s bitem se stejnou hodností šifrovacího klíče.
Nazvěme si jasný bit a B bit stejné hodnosti v náhodném pořadí.
Šifrování je výpočet bitové C o C = A ⊕ B . C je šifrované .
K dešifrování C znovu pomocí bitové B v náhodném pořadí a se vypočítá takto: C ⊕ B .
Výsledkem je A , bit clear, protože C ⊕ B = A ⊕ B ⊕ B = A ⊕ 0 = A , s použitím prvních dvou vlastností výše.
Tato metoda je jedním ze způsobů, jak provádět symetrické šifrování , kde se stejný klíč používá k šifrování a dešifrování.
Tento systém, i když je v zásadě velmi jednoduchý, se může ukázat jako nedotknutelný, pokud je sekvence bitů klíče skutečně náhodná. Ten druhý musí být také použit pouze jednou (mluvíme o jednorázové masce nebo dokonce o „jednorázové podložce“). V této větě je nejobtížněji realizovatelné především slovo „náhodný“. Ale když je klíč opravdu náhodný (technicky, že je vykreslen podle rovnoměrného rozdělení mezi všechny možné sekvence této délky), je tento systém naprosto bezpečný, v jistém smyslu přesně definovaném Claudem Shannonem v roce 1949 , v článku zakladatel „teorie komunikace systémů utajení“. Je třeba dodat, že toto je teoreticky jediné šifrování, které vede k absolutní bezpečnosti.
Viz také článek: jednorázová maska
Zde je numerický příklad předchozí metody:
M = 0110101011010100 (prostá textová zpráva)
K = 0101011011100110 (klíč; samozřejmě uchován v tajnosti)
Souhlasíme s tím, že symbol ⊕ zde představuje aplikaci operátoru XOR na každou z bitů
K šifrování musíte použít tabulku pravdivosti: „M“ je vaše zpráva a „K“ představuje tajný klíč.
Takže: M ⊕ K = C. „C“ představuje šifrovanou zprávu:
Šifrování: C = M ⊕ K = 0011110000110010 (šifrovaná zpráva)
Dešifrování: M = C ⊕ K = 0110101011010100 (dešifrovaná zpráva)
Tento šifrovací systém byl použit pro červený telefon , ve skutečnosti telex , který přímo spojoval Kreml s Bílým domem , klíče poté procházely diplomatickými taškami . Systém jednorázových masek používali také sovětští špioni. Některé masky byly použity více než jednou (někdy s roky pauzy), což umožnilo anglickým šifrovacím službám dešifrovat určité zprávy.
Všechny symetrické šifry používají operátor XOR. Symetrický kryptografický algoritmus s vysokou bezpečností AES ( Rijndael ) používá zejména velmi velké množství z nich.
Příklad použití: Integrovaný obvod 7486 TTL nebo integrovaný obvod CMOS 4070 integruje čtyři logické brány exkluzivního typu OR. Ilustrace: Příklad: Kontrolka se rozsvítí, pokud stisknete pouze „a“ nebo „b“, ale ne, pokud stisknete současně „a“ a „b“.
Diagram Rovnice Chronogram Symbol IEC Symbol ANSI (nazývaný také vojenský)Kromě použití souvisejících s kryptografií vám exkluzivní funkce OR umožňuje rychle vynulovat hodnotu proměnné (často registru ) na nulu.
Vezměte například kód sestavy, který používá výhradní OR k resetování hodnoty registru eax na nulu:
xor eax, eaxNa procesorech typu x86 je tato instrukce kratší (v počtu bajtů) než následující intuitivní kód:
mov eax, 0Umožňuje také nastavení na nulu proměnné, pokud podmínky neumožňují bajt 0x00 v binárním kódu ( shellcode ).
Můžete také použít exkluzivní OR k výměně dvou proměnných bez použití dočasné proměnné .
Jedna aplikace používaná výhradním logickým operátorem OR v domácí elektřině je v místnostech, kde lze žárovku zapnout nebo vypnout dvěma spínači umístěnými poblíž dvou vstupů. Každý ze dvou spínačů může žárovku zapnout nebo vypnout bez ohledu na polohu druhého spínače. Abychom získali takovou funkčnost, musíme spojit dva přepínače a vytvořit operátor XOR. Toto je takzvané " tam a zpět " shromáždění .