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

Неделя 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 к этим двум числам. Проверь себя: этот результат должен читаться одинаково как справа налево, так и слева направо. Сможешь объяснить почему?

А теперь я расскажу, почему эта операция так полюбилась криптографам. Всё просто. Пусть у тебя есть два различных числа – X и Y. Если применить операцию XOR к этим числам, то получится новое число Z = (X ⊕ Y). А если теперь к числу Z снова применить операцию XOR c числом Y, то результатом будет не что иное, как X!

Для примера давай вернемся к паре чисел, что мы рассматривали немного выше. Возьмем результат выполнения над ними операции XOR (10010), и теперь применим к нему эту операцию с тем же самым числом 11011:

Что получилось? Правильно, первое число – 01001.

Это важное свойство обратимости результата постоянно используется в криптографии. Давай посмотрим почему.

Напомню, что на прошлой неделе мы ввели новый алфавит, состоящий из тридцати двух символов, включая пробел. Каждому символу было сопоставлено пятизначное двоичное число от 00000 до 11111. Собственно, после этого уже было все понятно: мы же можем применять к кодам символов операцию XOR! Действительно, такое применение – просто другой способ использования шифра подстановки. Но этот способ намного проще: не надо искать соответствия в таблицах, а можно просто применить операцию XOR. Причём и для шифрования, и для расшифровки необходимы одинаковые действия.

Давай рассмотрим этот процесс на примере. Пусть нам необходимо зашифровать слово «ОГОНЬ». В качестве ключа возьмём единственную букву «Р». Вот что получится:

Так из слова «ОГОНЬ» получилось слово «ЮФЮЯЙ». Расшифровка происходит таким же образом:

Математически это можно записать так: «ОГОНЬ ⊕ РРРРР = ЮФЮЯЙ» и «ЮФЮЯЙ ⊕ РРРРР = ОГОНЬ». Как ты понимаешь, сейчас мы использовали просто шифр подстановки с одноалфавитной заменой. Это неинтересно. Интересно здесь то, что шифрование и расшифровка происходят при помощи одного и того же действия.

Теперь рассмотрим иной пример. Пусть нам опять надо зашифровать слово «ОГОНЬ», но теперь в качестве ключа мы будем использовать слово «МАГИЯ». Что получится? А вот что:

Абсолютно так же производится расшифровка:

Получается, что мы теперь можем «складывать» друг с другом целые слова: «ОГОНЬ ⊕ МАГИЯ = БДКЖГ». Это действительно какая-то магия. Только что мы при помощи этой прекрасной операции XOR применили шифр многоалфавитной замены, который изучали на второй неделе. Одна и та же операция позволяет применять сразу два шифра, которые мы уже изучили. Это прекрасно!

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

У этой таблицы много примечательных свойств. Если ты внимательно её изучишь, то найдёшь в ней разнообразные закономерности. Обрати, например, внимание на то, как в таблице располагаются буквы А, В, Ж, О и Я, а потом посмотри на их двоичное представление. И таких узоров в ней большое количество. Это – следствие разных свойств, которыми обладают двоичные числа и двоичная система счисления.

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

«ПРИВеТ МОЙ ДороГОй ДРУГ СеГОдНЯ Я хОЧу РАССКаЗаТь ТЕбе оДну ЗаниМАТеЛьНуЮ ИстоРию КОТОрАЯ СлучилАСЬ сО МНоЙ мНого Лет НАзад КоГДА я бЫЛ Ещё СОвСем мАЛЕНьким Я ТоГдА Жил в ДаЛёкОй ДЕРевНЕ и БЫл нАмноГо БЛИЖЕ к пРИрОДе чем СЕЙЧАс и ВоТ Однажды я шёл по лесу и увидел за деревьями яркий красный свет также было слышно странное жужжание подкравшись поближе я увидел марсиан».

Как ты уже понимаешь, на самом деле здесь два текста. Первый текст – это «обманка», призванная затуманить секрет. Странная история про марсиан. На самом-то деле скрытое послание закодировано в размере букв. Так как конец текста полностью состоит из строчных букв, можно предположить, что именно строчная буква обозначает бит 0. А заглавная буква, соответственно, обозначает бит 1. Если ты тщательно проделаешь операцию декодирования, то должно получиться следующее:

11110 11111 00011 01111 10110 11101 10111 11010 10110 00100 10001 11010 10110 00100 11110 11100 00011 10111 01010 00100 11000 10111 00111 00110 10001 11100 00110 10110 00101 11001 10110 01000 10111 11001 10110 00011 11100 10110

Использование уже известной тебе таблицы для преобразования двоичных чисел в буквы даёт такой текст:

«ЮЯВОХЭЦЩХГРЩХГЮЫВЦЙГЧЦЖЕ РЫЕХДШХЗЦШХВЫХ».

На первый взгляд выглядит странно, и первая мысль, которая приходит в голову, – возможно, в процессе декодирования мы допустили ошибку.

Но вдруг это закодированная шифрограмма? Что, если автор послания использовал метод стеганографии для сокрытия не простого текста, а зашифрованного? Почему бы и нет? Это вполне возможно. Что же тут можно сделать?

Помнишь, как на второй неделе мы оценивали шифр при помощи гистограммы частот символов? Конечно, на таком малом объёме текста нормально посчитать частоты затруднительно. Но тем не менее, если ты это сделаешь, а потом построишь гистограмму, то увидишь, что она примерно соответствует гистограмме частот символов в русском языке. Значит, перед нами шифр одноалфавитной замены!

Как быть дальше? Есть три возможных пути:

1. Провести частотный анализ, как мы делали это на первой неделе. Это универсальный путь, он всегда дает решение.

2. Поскольку мы столкнулись с двоичным кодированием символов, спрятанных потом в тексте-обманке, то резонно предположить, что для шифрования воспользовались операцией XOR. Так что можно последовательно проверить каждый код из тридцати одного (первый код проверять смысла нет, это код 00000, соответствующий пробелу, он не меняет текста). В итоге ты найдёшь тот код, которым зашифровано послание. Попробуй.

3. А можно поступить ещё более хитро и объединить эти два метода. Самый частый символ в тексте на русском языке – пробел. В шифрограмме самый частый встречающийся символ – Х. Однако Х стоит в конце шифрограммы, так что вряд ли это пробел (какой резон ставить пробел в конец текста?). Второй по частоте символ в шифрограмме – Ц. В таких коротких текстах часто случается, что символы меняются местами по частоте. Так что попробуй применить операцию XOR к шифрограмме с ключом Ц.

Если ты всё правильно сделал, то в результате должен получиться текст «ИЗУЧАЙ МАТЕМАТИКУ ЭТО ПРЕКРАСНАЯ НАУКА». По-моему, это отличное послание для любого человека.

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

1. Придумай текст, который ты хочешь зашифровать, длиной не менее 50 символов.

2. Придумай секретный ключ, при помощи которого ты будешь шифровать текст.

3. Теперь придумай открытое сообщение длиной не менее 250 символов (помни, что для кодирования одного символа тайного текста требуется 5 символов открытого сообщения).

4. Зашифруй тайное послание при помощи ключа, используя для этого операцию XOR.

5. Теперь закодируй полученную шифрограмму методом Фрэнсиса Бэкона (который мы изучили на прошлой неделе).

Пошли это письмо кому-нибудь (например, мне по адресу [email protected]).

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

Неделя 5. Тарабарская грамота

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

Заметь: всё, что мы изучили до сих пор, не подходит под это понимание. Если мы используем шифр одноалфавитной замены, то это можно понять по самому виду текста. Более того, частотный анализ с построением гистограммы сразу же полностью раскрывает метод шифрования (и мы с тобой уже тоже научились это делать). С многоалфавитной заменой – всё то же самое. Достаточно только предположить, что текст зашифрован при помощи многоалфавитной замены, чтобы применить к нему метод расшифровки, который мы использовали на второй неделе. И если этот метод найдёт длину ключа, то тайна сразу же перестаёт быть тайной.

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

Другими словами, если криптоаналитик узнаёт метод шифрования, получение открытого текста из шифрограммы становится делом техники и очень внимательных и точных подсчётов. Но на этой неделе мы изучим пару методов, которые в целом лишены такого недостатка.

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

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

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

Или, например, попробуй расшифровать, что написано в этом тексте:

RIП ZWОN ЛУJVU IЧLИSS JЛWОZR СIILЬ QУРWАN

Если у тебя ничего не выходит, и никаких идей в голову не приходит, то попробуй вычеркнуть из этого набора букв те, которые не входят в русский алфавит. Получилось?

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

Для тренировки можно выполнить такие упражнения. Придумай какое-нибудь слово, не короткое и не длинное. Например, это может быть слово «ПЛАМЯ». Теперь тебе надо придумать фразу из пяти слов, которые начинаются на буквы «П», «Л», «А», «М», и «Я». Например: «Подо Льдом Араб Мучил Янычара». Теперь ты понимаешь, что такое неадекватность текста? А теперь придумай фразу из пяти слов, где слово «ПЛАМЯ» будет читаться по вторым буквам. Например: «сПособ пЛавания рАзработан уМным дЯдей». Как видишь, эта задача не так проста, как кажется на первый взгляд, и здесь требуются многочисленные тренировки.

Но это всё ещё не очень хороший метод. Давай замахнёмся на что-нибудь посерьёзней. Представь, что тебе в руки попала следующая шифрограмма:

ARK NANTONG CELL TREC ISOHY KNAV BAR IPS EXES PISIDIE UXQUELS HABEN KANBUN WORLD BE XERM SOME TEXIS YRS BELLIC

На первый взгляд она выглядит как довольно странный набор английских слов, многие из которых – очень редкие и встречаются только в специализированной литературе, а некоторые вообще написаны с ошибками. Сразу же приходит на ум вычленить из этого бессмысленного набора символов только те, которые похожи своим начертанием на буквы русского алфавита (таких букв 12: A, B, C, E, H, K, M, O, P, T, X, Y). Вот что получается:

AKATOCETECOHYKABAPEXEPEXEHABEKABOBEXEMOMETEXYBEC

Что с этим делать дальше? Здесь я рекомендую тебе прервать дальнейшее чтение и попробовать самостоятельно найти в этом наборе букв какие-либо закономерности. Попробуй «загрузить» эту последовательность к себе в голову, после чего погоняй её туда-сюда день или два. Если ничего не получится найти, то продолжай чтение. Если получится, то сравни свой результат с тем, что написано дальше.

1. В этой строке на нечётных местах всегда стоит буква, обозначающая гласную, а на чётных – согласную. Другими словами, гласные и согласные идут одна за другой.

2. Различных гласных четыре: A, E, O, Y. Согласных – восемь: B, C, H, K, M, P, T, X. Произведение 4 и 8 даёт 32.

3. Прошлые две недели мы использовали алфавит, содержащий 32 символа.

Не много ли совпадений для такого небольшого кусочка шифрованного текста? Действительно, многовато. Это значит, что их нужно проверить. Ведь криптоаналитик всегда пытается зацепиться за разного рода закономерности. Когда в шифрограмме обнаруживаются закономерности, это значит, что она потенциально поддается взлому. Самый неуязвимый шифр похож на «белый шум» – никаких закономерностей, абсолютный хаос.

Давай попробуем проверить догадку, которая заключается в том, что в представленной шифрограмме за каждый символ секретного текста отвечают сразу гласная и согласная. При этом 32 символа нашего алфавита можно разделить на четыре группы, и каждую группу обозначить гласной. Внутри же групп символы (которых по восьми в группе) обозначаются согласными. Таким образом, чтобы получить код символа, надо взять гласную его группы и согласную самого символа в группе. Предположим, что кодировка была простейшей (если нет, то необходимо применить частотный анализ, используя в качестве символов, частоты которых подсчитываются, пары букв «Гласная + Согласная»). Простейшая кодировка обозначает, что гласные и согласные использовались просто по порядку. В итоге получается такая таблица:

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

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

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

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

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

И у нас есть частоты встречаемости букв русского алфавита в тексте. Их можно совместить так, чтобы наиболее часто встречающимся русским буквам соответствовали наиболее часто встречающиеся пары английских букв. Для этого надо рассчитать частоты для пар. Это сделать просто – чтобы получить частоту для пары, достаточно перемножить частоты двух букв (честно говоря, это не совсем корректно с точки зрения языка, но для нашей задачи подойдёт). Выбрав только латинские буквы A, B, C, E, H, K, M, O, P, T, X, Y, мы получим следующую таблицу:

Теперь надо расположить двухбуквенные комбинации по убыванию их частоты:

ET EH AT OT AH OH EC EM EP AC OC AM EB OM YT AP OP AB YH OB EK AK OK YC YM YP YB EX YK AX OX YX

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

Давай попробуем зашифровать что-нибудь с помощью этого кода. Так, фраза «ПРИЕДУ ЗАВТРА» в переложении на код будет выглядеть так: «YTACAHATOMAPETOBOTOCECACOT». Теперь, зная, что в двухбуквенных сочетаниях буквы можно менять местами, попробуй подобрать английские слова для сокрытия этой шифрограммы.

Если попытаться сделать это, то может получиться что-то вроде такого:

STYLUS CALLAHAN TROMP ARES TOROID BIT ROW CENSUS CARD CITO

Подобрать этот набор слов было намного-намного проще, чем предыдущий (мне даже практически не пришлось открывать словарь). Выглядит этот набор как список каких-то слов, возможно, кодов. Криптоаналитик будет ломать над ним голову намного дольше, поскольку здесь нет необычностей.

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

Напоследок – пара советов:

1. Чем больше в системе шифрования закономерностей, тем проще криптоаналитику расшифровать шифрограмму. Поэтому любыми средствами избегай простых закономерностей, которые позволят зацепиться за них и распутать клубок тайны.

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

Вот и всё. До следующей недели.