Математики, шпионы и хакеры. Кодирование и криптография

16 = 4? 2 = 14? Это не ошибка и не какая-то странная система счисления. Работа шифра Цезаря может быть проиллюстрирована теорией, которая привычна для математики и в еще большей степени для криптографии — модульной арифметикой, иногда называемой часовой арифметикой. Эта теория появилась еще в работах греческого математика Евклида (325–265 гг. до н. э.) и является одной из основ современной информационной безопасности. В этом параграфе мы расскажем о базовых математических понятиях, связанных с этим особым типом арифметики.

Возьмите в качестве примера обычные часы со стрелками и сравните их с цифровыми часами. На часах со стрелками циферблат разделен на 12 частей, которые мы обозначим числами 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, И. В следующей таблице можно видеть, как время на аналоговом циферблате соответствует времени после полудня на экране цифровых часов.

Когда мы говорим, например, что сейчас 14:00, мы можем также сказать, что сейчас два часа дня. Тот же принцип применяется и в случае измерения углов. Угол в 370 градусов равен углу в 10 градусов, потому что от первого значения мы должны вычесть полный оборот в 360 градусов. Заметим, что 370 = (1 х 360) + 10, то есть 10 является остатком от деления 370 на 360. Какой угол эквивалентен углу в 750 градусов? Вычитая соответствующее количество полных оборотов, мы получим, что угол в 750 градусов равен углу в 30 градусов. Мы видим, что 750 = (2 х 360) + 30, то есть 30 является остатком от деления 750 на 360. В математике это обозначается так:

750  30 (mod 360)

Мы говорим: «750 сравнимо с 30 по модулю 360». В случае с часами мы бы написали

14  2 (mod 12).

Мы также можем представить себе часы с отрицательными числами. В этом случае который будет час, когда стрелка показывает на —7? Или, другими словами, с каким числом сравнимо число —7 по модулю 12? Давайте посчитаем, учитывая, что на наших часах с циферблатом, разделенным на 12 частей, значение 0 соответствует 12.

— 7 = —7 + 0 = —7 + 12 = 5.

* * *

ОТЕЦ АНАЛИТИЧЕСКОЙ КРИПТОГРАФИИ

Основная работа Евклида Александрийского, «Начала», состоит из 13 томов, в которых излагаются основные факты планиметрии, теории пропорций, свойства чисел, сведения об иррациональных числах и стереометрии. Чаще всего ассоциируемые с этой последней теорией, работы греческого математика, связанные с арифметическими операциями на конечных числовых множествах, или операциями по модулю, являются одним из столпов современной теории криптографии. Известные и почитаемые еще арабскими учеными, работы Евклида впервые были изданы в Венеции в 1482 г. Вовсе не случайно, что и арабы, и венецианцы были великими мастерами криптографии.

* * *

ОПЕРАЦИИ ПО МОДУЛЮ

Как посчитать 231 по модулю 17 на калькуляторе?

Сначала мы разделим 231 на 17 и получим 13,58823529.

Затем найдем произведение 13 x 17 = 221. Таким образом мы избавимся от дробной части.

Наконец, найдем разность 231–221 = 10, получив остаток отделения.

Итак, 231 по модулю 17 равно 10. Этот результат записывается как 231  10 (mod 17).

* * *

Математика для расчетов на наших часах со стрелками, циферблат которых разделен на 12 частей, называется арифметикой по модулю 12. В общем случае мы говорим, что a  b (mod m), если остаток от деления а на m равен b, при условии что а, b и m — целые числа. Число b сравнимо с остатком от деления а на m. Следующие утверждения эквивалентны:

a  b (mod m)

b  a (mod m)

а — b  0 (mod m)

а — b кратно m

Вопрос «Которому часу на часах со стрелками соответствует время 19 часов?» эквивалентен в математических терминах следующему вопросу: «С каким числом сравнимо число 19 по модулю 12?» Чтобы ответить на этот вопрос, мы должны решить уравнение

19  х (mod 12).

Разделив 19 на 12, мы получим частное 1 и остаток 7, поэтому

19  7 (mod 12).

А в случае 127 часов? Разделив 127 на 12, мы получим частное 10 и остаток 7, поэтому

127  7 (mod 12).

Чтобы повторить изученное до сих пор, давайте рассмотрим следующие операции по модулю 7: