Битовая операция XOR

Если вы посмотрели урок об одноразовом блокноте, то знаете, что это — идеальный шифр сдвига. В нём используется случайный список сдвигов, равный длине сообщения. Важно понимать, почему шифр с одноразовым блокнотом невозможно взломать, иными словами, он абсолютно надёжен.

Чтобы понять, почему так, нам нужно узнать о битовых операциях AND («и»), OR («или») и XOR (исключающее «или»). Точнее, выяснить, почему именно операция XOR должна использоваться при шифровании с помощью одноразового блокнота на компьютере. Слово битовая означает, что эта операция выполняется с отдельными битами, то есть двоичными разрядами. В любых современных автоматизированных системах шифрования символы представляются в виде двоичных цифр. Если вы забыли, почему так, посмотрите видео о памяти компьютера

Начнём с наглядного примера шифрования цвета аватара Академии Хана — зелёного листика.

Как превратить цвет в число? Перед вами — HTML-цвета, определяемые цветовой моделью RGB. Это аддитивная цветовая модель, основанная на смешении красного (red), зелёного (green) и синего (blue) цветов.

Мы можем задать яркость КРАСНОГО, ЗЕЛЁНОГО и СИНЕГО цветов при помощи числа от 0 до 255. Чёрный получается, когда все цвета отключены, то есть (0, 0, 0), а белый — когда все цвета включены, то есть (255, 255, 255). Между ними лежат 16 миллионов возможных цветов (256×256×256). Теперь давайте узнаем числовое представление зелёного цвета с листочка Академии Хана в любой программе редактирования изображений:

Обратите внимание, что этот цвет хранится в виде: КРАСНЫЙ=156, ЗЕЛЁНЫЙ=181, СИНИЙ=58.

Если выразить эти числа в двоичной системе, получится:
КРАСНЫЙ=10011100, ЗЕЛЁНЫЙ=10110101, СИНИЙ=00111010.

Запишем все три значения подряд: 100111001011010100111010

Теперь представим, что мы сгенерировали последовательность сдвигов при помощи бросков монетки. В двоичном виде она будет выглядеть следующим образом:

Теперь давайте подумаем, как мы можем применить эту последовательность сдвигов к нашему цвету, чтобы зашифровать его при помощи одноразового блокнота:

Чтобы одноразовый блокнот сработал, необходимо выбрать подходящую операцию, чтобы в результате получилась последовательность, которая с одинаковой вероятностью может оказаться любым цветом. Давайте рассмотрим три разные операции: AND («и»), OR («или») и XOR («исключающее или»).

Оператор И называют логической конъюнкцией, он похож на умножение. 
Результатом конъюнкции будет 1, только если все операнды равны 1. Ниже представлена таблица истинности:

0 И 0 = 0

0 И 1 = 0

1 И 0 = 0

1 И 1 = 1

100111001011010100111010 И 010110100001101111011000 = 000110000001000100011000

В результате получился тёмно-фиолетовый цвет. Обратите внимание, что в результате оператора И двоичное число не может получиться больше изначальных операндов. В нашем случае многие оттенки отпадают, потому что оператор И сдвигает изначальный цвет в сторону чёрного.

Оператор ИЛИ называют логической дизъюнкцией. В результате дизъюнкции получается 1, если один или больше операндов равны 1. Ниже представлена таблица истинности:

0 или 0 = 0

0 или 1 = 1

1 или 0 = 1

1 или 1 = 1

100111001011010100111010 или 010110100001101111011000 = 110111101011111111111010

У нас получился светло-фиолетовый цвет. Обратите внимание, что в результате оператора ИЛИ двоичное число не может получиться меньше изначальных операндов. В нашем случае многие оттенки отпадают, потому что оператор ИЛИ сдвигает изначальный цвет в сторону белого.

Оператор XOR («исключающее или») даёт 1, если значения операндов не совпадают, то есть когда ровно один из двух операндов является истиной. Это эквивалентно сложению по модулю 2. Ниже представлена таблица истинности:

0 исключающее или 0 = 0

0 исключающее или 1 = 1

1 исключающее или 0 = 1

1 исключающее или 1 = 0

100111001011010100111010 исключающее или 010110100001101111011000 = 110001101010111011100010

У нас получился цвет чуть темнее, чем после применения операции ИЛИ. Обратите внимание, что в результате примения оператора XOR итоговая последовательность может оказаться любой. Это значит, что, получив зашифрованный цвет, мы знаем, что исходный может оказаться любым цветом с одинаковой вероятностью. Мы не получаем информацию, которая могла бы сузить полный перебор (1/16 млн).

Теперь давайте продемонстрируем, что мы сделали, чтобы понять принцип работы одноразового блокнота. А после этого мы можем получить ещё больше баллов энергии!