Математика и криптография. Тайны шифров и логическое мышление - Роман Душкин

Давай вновь обратимся к полученному сообщению. Итак, в нём использованы обычные и жирные буквы. Что, если обычная буква обозначает «0», а жирная — «1»? Надо попробовать декодировать шифр таким способом. Если подставить цифры 0 и 1 вместо обычных и жирных букв, то получится вот такая кодограмма (я сразу же разделил поток символов на группы по пять цифр, чтобы было удобно, и тебе советую сразу научиться всегда делать именно так):

00010 00110 10001 00110 00100 01001 10010 11011 00000 00010 00001 00010 10100 11001 01011 10100 00000 01111 01110 00001 00000 01001 01110 01111 10000 01100 00001 01110 00110 10011 11111 01110 01011 00001

Оставляю тебе возможность потренироваться в раскодировании текста. Тем более что здесь его не так уж и много.

Чему же мы научились на этой неделе? Мы научились очень важной вещи. Оказывается, можно скрывать информацию в другой информации так, что найти её сможет только тот, кто знает, как искать. Это как спрятать иголку в стоге сена. Более того, в стогу вообще мало кто будет искать иголку! Добиться этого — и есть основная задача стеганографии , то есть науки о сокрытии информации. Если криптография шифрует смысл текста, то стеганография скрывает само присутствие тайны. Получается, криптография и стеганография — очень близкие науки. Одна прячет смысл сообщения, а другая — само сообщение. А метод, который мы с тобой сейчас изучаем, называется методом Фрэнсиса Бэкона.

Фрэнсис Бэкон — английский философ, историк, политик. Создал метод кодирования и сокрытия информации, из-за которого в дальнейшем произошло множество интересных случаев с поиском скрытых сообщений там, где их нет. Например, последователи этого метода пытались доказать, что все пьесы Уильяма Шекспира на самом деле были написаны Бэконом.

Ещё мы можем сделать вывод, что любое свойство, которое позволяет разделить буквы на два класса, можно использовать для сокрытия информации таким способом. Например, можно использовать заглавные и строчные буквы. Можно использовать чёрные и красные буквы. Можно, наконец, использовать не только обычное и жирное начертание, но и обычное и курсивное. Можно придумать ещё много всяких вариантов деления букв на два типа. К тому же при использовании нескольких способов деления вполне можно спрятать в одном и том же тексте несколько разных тайных сообщений. Например, одновременно использовать обычные и жирные буквы и заглавные и строчные буквы.

Рекомендую тебе потренироваться в кодировании и декодировании тайных сообщений таким способом. Это поможет хорошо понять изученный нами метод сокрытия информации. К тому же ты научишься свободно использовать двоичную систему счисления. Это в любом случае пригодится в будущем, кем бы тебе ни довелось стать.

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

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

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

Да, действительно, не всё. Математики придумали огромное количество операций , которые можно производить над различными математическими объектами. И те операции над числами, которые изучают в школе, — лишь капля в океане чистого математического знания. Но мы не будем изучать весь океан, а рассмотрим только одну новую математическую операцию (которая очень нравится всем криптографам и криптоаналитикам). Эта операция называется «XOR», или, по-русски, «Исключающее ИЛИ», и обозначается значком ⊕. Ее выполняют не над числами, а над битами. На прошлой неделе мы уже выяснили, что такое бит — это «0» или «1».

Что ж, давай кратко изучим, что такое булевая логика, которая определяет операции над битами. Объектами в булевой логике являются биты, то есть два числа 0 и 1. Их можно рассматривать как значения истинности, когда 0 обозначает ЛОЖЬ, а 1 — ИСТИНА. Над такими значениями истинности определены различные операции. Например, самыми известными операциями являются НЕ (обозначается как ~), И (обозначается как ⊕) и ИЛИ (обозначается как |). У каждой операции есть так называемая таблица истинности. Рассмотрим их.

Операция НЕ:

— 0 = 1

— 1 = 0

Операция И:

0 ⊕ 0 = 0

0 ⊕ 1 = 0

1 ⊕ 0 = 0

1 ⊕ 1 = 1

Операция ИЛИ:

0 | 0 = 0

0 | 1 = 1

1 | 0 = 1

1 | 1 = 1

Вернёмся к операции ИСКЛЮЧАЮЩЕЕ ИЛИ, которая определяется очень просто. Выучи наизусть следующую таблицу истинности:

0 ⊕ 0 = 0

0 ⊕ 1 = 1

1 ⊕ 0 = 1

1 ⊕ 1 = 0

Эту операцию можно применять и к длинным двоичным числам. В этом случае она просто выполняется над каждым битом числа. Если выписать два двоичных числа в столбик друг под другом, то операция XOR выглядит очень просто:

Другими словами, операция XOR выполняется для каждого столбца по отдельности; тут нет необходимости переносить что-либо между разрядами числа, как это делается при сложении или умножении.

Чтобы лучше понять эту новую математическую операцию, можешь проделать такой опыт. Возьми монетку и подкинь её 100 раз (если ты хочешь схитрить и прочитать это число в двоичной системе счисления, чтобы делать меньше работы, то, так и быть, подкинь монетку 99 раз). Каждый раз записывай результат. «Орёл» обозначай битом 0, а «решка» — 1. Запиши это длинное число в одну строку. Во второй строке прямо под первым числом запиши это же самое число, но задом наперёд. Затем проведи длинную горизонтальную линию и под ней вычисли результат применения операции XOR к этим двум числам. Проверь себя: этот результат должен читаться одинаково как справа налево, так и слева направо. Сможешь объяснить почему?