Bitová operace XOR

Pokud jsi viděl lekci o Vernamově šifře, tak víš, že je to ultimátní posunovací šifra. Zahrnuje aplikaci náhodného seznamu posunů, který je roven délce šifrované zprávy. Je důležité porozumět tomu, jak přesně a proč je Vernamova šifra nerozluštitelná, tedy dokonale tajná.

K pochopení „proč“ musíme zavést bitové operace AND, OR a XOR. Konkrétně proč musí být použit XOR při provedení Vernamovy šifry na počítači. Bitová operace jednoduše znamená, že pracujeme s jednotlivými bity, nebo binárními čísly. V každém moderním/počítačovém šifrovacím schématu vyjadřujeme symboly pomoci binárních čísel. Pokud jsi zapomněl proč, podívej se na toto video: Paměť počítače.

Začněme s vizuálním příkladem – zašifrování barvy lístku Khan Academy.

Jak udělat z barvy číslo? Nu, právě se díváš na HTML barvy, které jsou definované pomocí RGB modelu barev. To je aditivní model založený na míchání nějakého množství červeného, zeleného a modrého světla.

Pomocí čísel 0-255 můžeme přesně definovat, kolik ČERVENÉ, ZELENÉ a MODRÉ chceme. Černá je vše na nule (0,0,0), zatímco bílá je vše naplno (255,255,255). V rozmezí mezi tím je 16 milionů možných barev (256 * 256 * 256). Najděme tedy zelenou barvu z lístku loga Khan Academy v nějakém programu:

Všimni si, že tato barva má složení ČERVENÁ=156, ZELENÁ=181 a MODRÁ=58.

Vyjádříme-li tato čísla v binární soustavě:
ČERVENÁ=10011100, ZELENÁ= 10110101, MODRÁ=00111010.

To můžeme srazit dohromady na: 100111001011010100111010

Řekněme, že jsme vygenerovali posloupnost posunutí pomocí hodu kostkou převedenou do binární soustavy:

Zamysleme se nad tím, jak bychom mohli aplikovat tuto posloupnost posunutí na naši barvu, abychom ji zašifrovali pomocí Vernamovy šifry:

Aby nám Vernamova šifra fungovala, musíme zvolit vhodnou operaci, aby výsledné číslo mohlo být se stejnou pravděpodobností libovolnou barvou. Podívejme se na tři různé operace: AND, OR, XOR.

Operátor AND je také znám jako logická konjunkce nebo bitový součin a funguje zrovna jako násobení. 
Výstupem je 1 pouze tehdy, pokud jsou všechny vstupy 1. Zde je pravdivostní tabulka:

0 AND 0 = 0

0 AND 1 = 0

1 AND 0 = 0

1 AND 1 = 1

100111001011010100111010 AND 010110100001101111011000 = 000110000001000100011000

Výsledkem je velmi tmavá fialová. Všimni si, že když působíme operací AND na binární číslo, výsledné číslo nemůže být větší. V našem příkladu s barvami to vyřadí několik možných odstínů, neboť barvu posouvá k černé.

Operátor OR, známý také jako logická disjunkce nebo bitový součet. Výstupem je 1, pokud na alespoň jednom vstupu je 1. Zde je pravdivostní tabulka:

0 OR 0 = 0

0 OR 1 = 1

1 OR 0 = 1

1 OR 1 = 1

100111001011010100111010 OR 010110100001101111011000 = 110111101011111111111010

Výsledkem je světle fialová. Všimni si, že když působíme operací OR na binární číslo, výsledné číslo nemůže být menší. To vyřazuje mnoho možných odstínů, neboť barvu posouvá k bílé.

Operátor XOR, známý také jako bitová nonekvivalence, má na výstupu 1 pokud vstupy nejsou stejné, což nastane, je-li jeden ze vstupů jako jediný pravdivý. To je stejné jako sčítání mod 2. Zde je pravdivostní tabulka:

0 XOR 0 = 0

0 XOR 1 = 1

1 XOR 0 = 1

1 XOR 1 = 0

100111001011010100111010 XOR 010110100001101111011000 = 110001101010111011100010

Výsledkem je oproti operaci OR trochu tmavší fialová. Všimni si, že při působení operací XOR na binární číslo může být výsledné číslo jakékoliv . Budeme-li mít nějakou zašifrovanou barvu, víme jen, že původní barva „může být se stejnou pravděpodobností jakákoliv barva“. Nemáme žádnou informaci, která by zlepšila slepý odhad (1/16 milionů).

Pusťme se do vizuální ukázky, abychom viděli Vernamovu šifru v akci. Pak si zasloužíme nějaké energetické body!