Математики, шпионы и хакеры. Кодирование и криптография - Гомес Жуан - Страница 5

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

Шифр Цезаря заменяет каждую букву другой, находящейся в алфавите на некоторое фиксированное число позиций правее. Как писал великий историк Светоний в книге «Жизнь двенадцати цезарей», Юлий Цезарь использовал для своей личной переписки следующий алгоритм подстановки: каждая буква исходного сообщения сдвигалась по алфавиту на три позиции, а именно, буква А заменялась на D, В — на Е, и так далее. Буква W превращалась в Z, а X, Y и Z возвращались к А, В и С.

* * *

* * *

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

Рассмотрим теперь этот процесс подробнее. В таблице ниже мы видим изначальный алфавит из 26 букв и алфавит, преобразованный шифром Цезаря, где каждая буква сдвинута на три позиции вправо (верхний ряд — алфавит открытого сообщения, а нижний — шифроалфавит).

Когда два алфавита, оригинальный (или алфавит открытого сообщения) и шифроалфавит, расположены таким образом, шифрование любого сообщения сводится к замене букв из первого алфавита буквами из второго. Ключ к такому шифру получает название по букве, соответствующей зашифрованному значению буквы А (первой буквы оригинального алфавита). В нашем случае это буква D. Известное выражение AVE CAESAR («Радуйся, Цезарь») будет зашифровано как DYH FDHVDU. Обратно, если зашифрованное сообщение выглядит как WUHH, то расшифрованный текст будет TREE («Дерево»). В случае с только что описанным шифром Цезаря криптоаналитик, который перехватил сообщение и знает используемый алгоритм, но не знает ключ к шифру, должен будет перебрать все возможные сдвиги алфавита, пока не найдет сообщение, имеющее смысл. Для этого он должен будет, в худшем случае, попробовать все возможные ключи или сдвиги. В алфавите, состоящем из n букв, существует n возможных сдвигов, то есть n ключей.

* * *

Всевидящий глаз компьютера HAL 9000 из фильма «Космическая одиссея 2001 года»

16 = 4. Модульная арифметика и математика шифра Цезаря

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

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

14

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

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

* * *

* * *