Математика и криптография : тайны шифров и логическое мышление | страница 21

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

Да, действительно, не всё. Математики придумали огромное количество операций , которые можно производить над различными математическими объектами. И те операции над числами, которые изучают в школе, — лишь капля в океане чистого математического знания. Но мы не будем изучать весь океан, а рассмотрим только одну новую математическую операцию (которая очень нравится всем криптографам и криптоаналитикам). Эта операция называется «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 к этим двум числам. Проверь себя: этот результат должен читаться одинаково как справа налево, так и слева направо. Сможешь объяснить почему?