Основное содержание
XOR и одноразовый блокнот
Почему нужно использовать XOR?
Так ли важно, какой оператор — AND, OR или XOR мы используем с одноразовым блокнотом? Ответ — да, и очень важно понять, почему. Как вы помните из предыдущей статьи, оператор AND с вероятностью 75% даст 0 и с вероятностью 25% — 1. В то время, как оператор OR с вероятностью 25% даст 0 и с вероятностью 75% — 1. А оператор XOR с вероятностью 50% может дать и 0, и 1.
Давайте разберём один пример, чтобы увидеть различные последствия применения операторов AND, OR и XOR при шифровании изображения. Перед вами цифровой портрет Чарльза Бэббиджа:
Он состоит из тысяч крохотных разноцветных квадратов — пикселей. Каждый пиксель этого изображения, как было уже сказано в предыдущей статье, может быть представлен в виде 24-битной последовательности. Назовём его открытым изображением (или сообщением).
Сначала посмотрим, что произойдёт, если мы проделаем операцию AND («и») с каждым битом исходного изображения и последовательностью случайных битов.
Оператор AND («и»)
Обратите внимание, бОльшую часть оригинального сообщения отлично видно. Это происходит каждый раз когда применяется сдвиг 1 или в открытом тексте встречается 0:
Теперь давайте применим операцию OR («или») к каждому биту изображения и последовательности случайных битов.
Оператор OR («или»)
Обратите внимание, что изображение также хорошо различимо. Бит остаётся прежним, если он равнялся 1 или если к нему применялся сдвиг 0:
Наконец, применим оператор XOR («исключающее или») к исходному изображению и последовательности случайных битов.
(а теперь барабанная дробь …)
Оператор XOR («исключающее или»)
Куда делся Чарльз?
Обратите внимание, что исходные биты не меняются в 50% случаев, в результате чего образуется шум, поскольку каждый пиксель может с одинаковой вероятностью равняться как 0, так и 1.
В этом изображении нет информации об исходном изображении. Если мы не дадим получателю ключевую последовательность сдвигов, будет невозможно восстановить исходное изображение по зашифрованному. Можно перебрать все возможные последовательности, но они дадут все возможные изображения! Откуда знать, что мы зашифровали именно Бэббиджа? Это может оказаться ваш потрет или портрет любого другого человека.
Обратите внимание, что исходные биты не меняются в 50% случаев, в результате чего образуется шум, поскольку каждый пиксель может с одинаковой вероятностью равняться как 0, так и 1.
В этом изображении нет информации об исходном изображении. Если мы не дадим получателю ключевую последовательность сдвигов, будет невозможно восстановить исходное изображение по зашифрованному. Можно перебрать все возможные последовательности, но они дадут все возможные изображения! Откуда знать, что мы зашифровали именно Бэббиджа? Это может оказаться ваш потрет или портрет любого другого человека.
Разве не здорово? Я каждый раз улыбаюсь при виде этой картинки!
Теперь давайте поупражняемся в применении операторов XOR, OR и AND, а заодно узнаем ещё кое-какие интересные свойства…
Хотите присоединиться к обсуждению?
Пока нет ни одной записи.