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

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

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

Неделя 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.

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