XOR bitszintű művelet

Ha láttad a véletlen átkulcsolásról szóló videót, akkor tisztában vagy azzal, hogy ez a tökéletes eltolásos rendszer. Ehhez az üzenet hosszával megegyező véletlen eltolási listát használunk. Fontos megérteni, miért feltörhetetlen a véletlen átkulcsolás, azaz miért tökéletesen titkos.

Ennek megértéséhez először is bevezetjük az AND, OR illetve XOR bitszintű műveleteket, különös tekintettel arra, hogy miért XOR-t kell használni a számítógépes véletlen átkulcsolás megvalósításához. A bitszintű egyszerűen csak annyit jelent, hogy egyedi bitekkel foglalkozunk, azaz bináris számokkal. Minden modern számítógépes titkosítási eljárásban bináris formában ábrázoljuk a szimbólumokat. Ha nem világos miért, akkor nézd meg a számítógép memóriájáról szóló videót.

Kezdjük egy vizuális példával, a Khan Academy leveléhez használt zöld szín rejtjelezésével.

Hogyan csinálunk a színből számot? Most éppen a HTML színeket láthatod, amit az RGB színtérrel határozunk meg. Ez egy additív színmodell, ami a piros, zöld és kék színek különböző arányú keverésén alapul.

Pontosan megadjuk a RED, GREEN és BLUE (így hívják az alkalmazásokban a piros, zöld, illetve kék komponenseket) mennyiségét egy 0 és 255 közötti szám segítségével. A feketét úgy ábrázoljuk, hogy mindent kikapcsolunk (0,0,0), míg a fehérnél mindent bekapcsolunk (255,255,255). A kettő között 16 millió lehetséges szín van (256·256·256). Válasszuk ki a Khan Academy levelének zöld színét valamelyik képszerkesztő alkalmazásban:

Ahogy láthatod, RED=156, GREEN=181, BLUE=58 értékeket kaptunk.

Ezeket binárisan ábrázolva ezt kapjuk:
RED=10011100, GREEN=10110101, BLUE=00111010.

Egybeírva az eredmény: 100111001011010100111010

Tegyük fel, hogy az alábbi, binárisra konvertált pénzfeldobásokkal (F: fej, I: írás) generált eltolási szekvenciát használjuk:

Vizsgáljuk meg, hogyan használhatjuk ezt az eltolási listát véletlen átkulcsolással színünk titkosításához!

Ahhoz, hogy a véletlen átkulcsolást használjuk, meg kell választanunk a megfelelő műveletet ahhoz, hogy az eredmény egyenlő valószínűséggel tetszőleges szín lehessen. Vizsgáljunk meg három műveletet: AND, OR, XOR!

Az AND művelet logikai konjunkció néven is ismert, és úgy működik, mint a szorzás.
Az eredmény csak akkor 1, ha mindkét bemenet értéke 1. Íme az értéktáblázat:

0 AND 0 = 0

0 AND 1 = 0

1 AND 0 = 0

1 AND 1 = 1

100111001011010100111010 AND 010110100001101111011000 = 000110000001000100011000

Eredményül nagyon sötét lilát kapunk. Figyeld meg, hogy bármilyen bináris szám esetén az AND művelet eredményéül kapott szekvencia nem lehet nagyobb az eredeti számnál. Példánkban ez kizár egy csomó árnyalatot, és az eredményül kapott színt a fekete felé tolja el.

Az OR műveletet más néven logikai diszjunkciónak hívják. Eredménye akkor 1, ha egy vagy több bemenet értéke 1. Az értéktáblázat:

0 OR 0 = 0

0 OR 1 = 1

1 OR 0 = 1

1 OR 1 = 1

100111001011010100111010 OR 010110100001101111011000 = 110111101011111111111010

Az eredmény világoslila. Figyeld meg, hogy az OR művelet hatására az eredményül kapott bináris szekvencia nem lehet kisebb. Ez kizár egy csomó lehetőséget, mivel az eredményt a fehér felé tolja el.

Az XOR művelet 1-et ad eredményül akkor, ha a bemenetek eltérnek, ami akkor fordul elő, amikor a két bemenet közül csak az egyik igaz. Ez ugyanaz, mint az összeadás modulo 2. Az eredménytáblázat így néz ki:

0 XOR 0 = 0

0 XOR 1 = 1

1 XOR 0 = 1

1 XOR 1 = 0

100111001011010100111010 XOR 010110100001101111011000 = 110001101010111011100010

Az OR művelethez képest egy valamivel sötétebb lilát kapunk eredményül. Figyeld meg, hogy az XOR művelet végrehajtásakor az eredményül kapott szekvencia az összes lehetséges szekvenciák bármelyike lehet. Ha adva van egy rejtjelezett szín, csak annyit tudhatunk, hogy az eredeti „azonos valószínűséggel lehet bármelyik szín”. Nem áll rendelkezésre semmilyen olyan információ, ami a puszta találgatásnál jobb esélyt adna (1 a 16 millióhoz).

Végül nézzük meg a véletlen átkulcsolást működés közben egy szemléltető példán keresztül! Azután további pontokat gyűjthetsz!