Математика и криптография

Как видно, эта же шифрограмма «нанесена» на обычные слова в начале предыдущего абзаца, при этом использовались все символы для нанесения (то есть и цифры, и знаки препинания). Неподготовленный читатель даже не обратит внимания на такое странное начертание текста. Но грамотный криптоаналитик, конечно же, всё сразу поймёт, этим никого не удивишь. Поэтому обычно используют более тонкие свойства, которые не так тривиальны и не видны невооружённым глазом.

Таким образом, на третьей неделе обучения надо составить и написать письмо, шифрограмма в котором будет скрыта. При составлении текста, подлежащего сокрытию, необходимо иметь в виду, что для его кодирования с помощью жирных начертаний требуется в пять раз больше символов. Я рекомендовал бы написать обычное письмо, в тексте которого не ведётся речь о шифровании вообще. А вот в скрываемом тексте можно использовать какие-нибудь нравоучения на тему, как хорошо знать и уметь заниматься шифрованием и дешифровкой.

Необходимо быть крайне внимательным при кодировании текста. Нет ничего страшного в том, что в каком-нибудь одном месте будет изменён один бит (0 на 1 или 1 на 0), поскольку это всего лишь приведёт к появлению единичной ошибки в дешифрованном открытом тексте. Намного хуже будет, если в какой-то момент будет пропущен бит. Это приведёт к сдвигу, в результате которого после расшифровки получится бессмыслица. Нет, в конце концов, её тоже можно будет расшифровать, поскольку это будет довольно структурированная бессмыслица. Но её вид вызовет у ребёнка недоумение, поскольку он подумает, что идёт по неправильному пути.

Поэтому я рекомендую воспользоваться компьютером, чтобы подготовить и затем проверить кодирование скрытого текста. Затем можно будет перенести его в письмо, которое, как мы договорились, лучше писать от руки. Соответственно, при кодировании скрытого текста надо внимательно относиться к жирности букв, поскольку для образовательных целей нужно, чтобы два состояния символов отличались друг от друга.

Неделя 4. Операция XOR

Четвёртая неделя знаменуется изучением важнейшей для криптографии математической операции, которая называется «Исключающее ИЛИ» и обозначается символом «⊕». Эта операция работает на битах: на вход она принимает два бита, а возвращает один. В результате получается значение 0 тогда, когда оба входных бита одинаковы, и 1, когда входные биты различны. Другими словами, таблица истинности этой операции выглядит следующим образом:

Эта операция обладает одним важным свойством. Если повторно применить эту операцию с тем же самым вторым операндом к одному биту, то в результате вернется первоначальное значение этого бита. Другими словами: (x ⊕ y) ⊕ y = x Это свойство вытекает из ассоциативности операции и того наблюдения, что её применение к двум одинаковым значениям всегда возвращает 0, каким бы ни были эти значения, а если применить эту операцию с некоторым битом и нулём, то в результате получится этот бит. То есть: (x ⊕ y) ⊕ y = x ⊕ (y ⊕ y) = x ⊕ 0 = x.

Как происходит использование этой операции в шифровании? Пусть x — бит открытого текста, а y — бит ключа. Тогда z = (x ⊕ y) — это бит шифрограммы. Как же теперь расшифровать шифрограмму и получить обратно открытый текст? Абсолютно также: x = (z ⊕ y), то есть повторно применить ключ к шифрограмме. Это крайне удобно, поскольку для шифрования и расшифровывания нужна одна и та же операция.

Теперь давайте вспомним способ кодирования, который мы ввели на прошлой неделе. Каждая буква открытого текста была представлена пятью символами 0 и 1, то есть пятью битами. Что интересно, операцию «Исключающее ИЛИ» можно производить побитно, её можно даже применять «в столбик»:

Другими словами, побитное применение операции обозначает, что мы можем применять её к каждому биту, не обращая внимания на остальные, и результат всё равно будет правильным. Здесь нет переносов между разрядами, как при умножении или сложении. Каждая битовая позиция отвечает сама за себя.

Это даёт очень простой способ шифрования текста. Если при помощи двоичного кода перевести открытое сообщение в последовательность нулей и единиц, а потом побитно применить операцию «Исключающее ИЛИ» к этому длинному числу вместе с циклическим ключом, то получится ещё одно длинное двоичное число. Это число можно всё так же перевести назад в буквы, и это получится не что иное, как многоалфавитная замена. Впрочем, ключ можно сделать произвольной длины, в том числе и не кратной числу 5, тогда количество алфавитов в многоалфавитной замене сильно увеличится. Сейчас мы узнали ещё один, причём довольно простой, метод делать то, что мы уже умеем. При этом уже нет никакого резона заниматься арифметикой вычетов или использовать огромную таблицу.

Например, пусть надо закодировать фразу «ЖДИ СИГНАЛ ВО ВТОРНИК» при помощи ключа «ОГОНЬ». В этом случае надо взять и выписать одно под другим два больших числа, а потом применить к ним операцию «Исключающее ИЛИ»: