Operacja bitowa XOR

Jeśli obejrzeliście lekcję na temat szyfru z kluczem jednorazowym, wiecie już, że jest on najmocniejszym szyfrem przesuwającym. Polega on na stosowaniu losowej listy przestawień, której długość jest równa liczbie znaków występujących w wiadomości. Warto dokładnie zrozumieć, dlaczego szyfr ten jest niemożliwy do złamania, tj. doskonale tajny

W celu poznania tajników tego szyfrowania, najpierw musimy wprowadzić pojęcie operatorów bitowych AND, OR oraz XOR. Dowiemy się też dlaczego operator XOR musi zostać użyty w trakcie szyfrowania kluczem jednorazowym na komputerze. Przymiotnik bitowe oznacza, że mamy do czynienia z pojedynczymi bitami, lub liczbami binarnymi. W każdym nowoczesnym/skomputeryzowanym schemacie szyfrowania symbole reprezentowane są binarnie. Jeśli nie pamiętasz, dlaczego, możesz zerknąć na ten film o pamięci komputerowej

Zacznijmy od przykładu. Zaszyfrujmy kolor zielonego liścia w logo Khan Academy.

Jak zamieniamy kolor w liczbę? Teraz patrzysz na kolory HTML, które są zdefiniowany za pomocą modelu RGB. Jest to model addytywny, oparty na zmieszaniu w ustalonych proporcjach barwczerwonej, zielonej oraz niebieskiej

Możemy dokładnie określić ilość koloru CZERWONEGO, ZIELONEGO oraz NIEBIESKIEGO przy użyciu liczb z przedziału od 0 do 255. Czarny to wszystkie wiązki światła wyłączone: (0,0,0). Kolor biały to wszystkie wiązki światła włączone: (255,255,255). W całym zbiorze kolorów istnieje 16 milionów kombinacji barw (256 * 256 * 256). Teraz pobierzmy próbkę koloru zielonego z liścia w logo Khan Academy przy użyciu dowolnego programu do przetwarzania obrazu:

Zauważmy, że kolor przechowywany jest jako CZERWONY=156, ZIELONY=181 oraz NIEBIESKI=58.

Zapisujac te liczby w systemie dwójkowym, otrzymamy:
CZERWONY=10011100, ZIELONY=10110101, NIEBIESKI=00111010.

Zapisując te liczby jedna za drugą, otrzymamy liczbę: 100111001011010100111010

Powiedzmy teraz, że utworzyliśmy ciąg przesunięć za pomocą rzutów monetą zapisanych binarnie jako:

Zastanówmy się, jak moglibyśmy zadziałać tym ciągiem operacji na nasz kolor, tak by otrzymać szyfrowanie kluczem jednorazowym:

By szyfrowanie działało poprawnie, musimy wybrać takie działanie, przy którym powstały ciąg będzie z równym prawdopodobieństwem odpowiadał dowolnemu kolorowi. Przyjrzyjmy się trzem różnym działaniom, AND, OR, XOR.

Operator AND, nazywany koniunkcją, zachowuje się jak zwyczajne mnożenie.
Przyjmuje wartość 1 na wyjściu wyłącznie, gdy otrzyma 1 na wszystkich wejściach. Oto jego tablica prawdy:

0 AND 0 = 0

0 AND 1 = 0

1 AND 0 = 0

1 AND 1 = 1

100111001011010100111010 AND 010110100001101111011000 = 000110000001000100011000

Otrzymaliśmy ciemny odcień purpury. Zauważmy, że zastosowanie operatora AND na danej liczbie zapisanej binarnie nie może dać liczby większej. W naszym przykładzie wyklucza to wiele możliwych odcieni, przesuwając barwę w kierunku czerni.

Operator OR nazywany jest alternatywą. Przybiera wartość 1 na wyjściu, gdy otrzyma 1 na przynajmniej jednym wejściu. Oto jego tablica prawdy:

0 OR 0 = 0

0 OR 1 = 1

1 OR 0 = 1

1 OR 1 = 1

100111001011010100111010 OR 010110100001101111011000 = 110111101011111111111010

Otrzymaliśmy jasny odcień purpury. Zauważmy, że zastosowanie operatora OR na danej liczbie zapisanej binarnie nie może dać liczby mniejszej. W naszym przykładzie wyklucza to wiele odcieni, przesuwając barwę w kierunku bieli.

Operator XOR przyjmuje wartość 1 na wyjściu, gdy wartości na wejściach są różne, a więc gdy dokładnie jedno z dwu wejść niesie logiczną wartość prawdy. Dokładnie tak samo działa dodawanie modulo 2. Oto jego tablica prawdy:

0 XOR 0 = 0

0 XOR 1 = 1

1 XOR 0 = 1

1 XOR 1 = 0

100111001011010100111010 XOR 010110100001101111011000 = 110001101010111011100010

Otrzymaliśmy nieco ciemniejszy odcień, niż przy zastosowaniu operatora OR. Zauważmy, że wykonując operację XOR na danym ciągu binarnym możemy otrzymać dowolny inny ciąg. Mając dany pewien zaszyfrowany kolor, możemy jedynie stwierdzić, że kolor wyjściowy mógł “z równym prawdopodobieństwem być dowolną barwą”. Nie posiadamy żadnej informacji, która pozwoliłaby na coś więcej, niż losowe zgadywanie (1/16 milionów).

Na koniec zaprezentujemy szyfrowanie z kluczem jednorazowym w akcji. Możemy wtedy zdobyć więcej punktów energii!