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

* * *

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

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

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

* * *

ШИФРЫ В ФИЛЬМАХ

В классическом научно-фантастическом фильме режиссера Стэнли Кубрикапо мотивам повести Артура Кларка«Космическая одиссея 2001 года» (1968) наделенный сознанием суперкомпьютер космического корабля HAL 9000 сходит с ума и пытается убить человеческий экипаж.

Теперь предположим, что слово HALзакодировано шифром Цезаря со сдвигом на одну позицию. Тогда буква Нсоответствует букве I, Асоответствует В, a L— букве М; другими словами, получается I BM, в то время крупнейший в мире производитель компьютеров. О чем пытался рассказать этот фильм: об опасностях искусственного интеллекта или об угрозах бесконтрольной коммерческой монополии? Или это просто совпадение?

Всевидящий глаз компьютера 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. В математике это обозначается так: