Знаете ли вы, что может объединять шпионов и математиков? Почему говорят, что победу во второй мировой войне одержали математики? Благодаря чему стремительно развивается электронная коммерция? ответы на эти вопросы ищите в криптографии — древнейшем разделе математики. Правда, для этого нам нужно на время стать секретными агентами и начать атаку на секретные шрифты.
Мир полон секретов
Наверное, вам приходилось передавать другу сообщение так, что бы никто кроме него не знал содержания послания? Забегая вперёд отмечу, вы не одиноки: с подобной задачей человечество сталкивается с давних пор.
Причин для этого было много: купцы скрывали истинные размеры богатства (им нужно было избежать налогов), пираты скрывали места на карте, где прятали награбленные сокровища (что бы никто кроме них не знал это место), мастера шифровали рецепты изготовления сплавов (от них не отставали знахари и алхимики), военные шифровали сообщения друг другу (что бы противник не узнал о планах).
Иначе говоря, мир полон секретов и тех, кто хочет их разгадать. Так как же люди «прятали» секреты? Тайники? Но рано или поздно они обнаружатся. Специальные чернила, невидимые при свете дня? После обработки раствором запись появлялась. Опять же реагентов для таких фокусов не так много, и подобрать нужный не так сложно. Приведённые примеры либо дороги, либо непрактичны либо недостаточны для сохранения тайны.
Бедные владельцы секретов устали от бесконечной борьбы с теми, кто пытался разузнать их тайны. Нужен был быстрый и дешёвый способ сохранить или «упрятать» секрет. В результате длительные раздумья над этим вопросом привели к мысли о тайнописи, использования тайного языка, который могли бы понимать только те, кому адресовано сообщение. Это и было рождением криптографии (от греч. «скрытно» и «пишу»). Но любопытные, пытающиеся раскрыть секреты, не сдались и придумали криптоанализ. Конечно, в последнем замешана серьёзная математика.
Начало криптографии: придумаем свой шифр!
Вернёмся к нашей задаче. Мы уже поняли, что будет очень сложно скрыть само сообщение. Следовательно, будем исходить из того, что наше сообщение непременно будет прочитано. На языке военных это означает, что сообщение будет перехвачено. Но мы можем изменить содержание сообщения, чтобы никто кроме получателя не смог его понять!
Как этого добиться? Давайте пропустим наше сообщение через «мясорубку», которая заменит в сообщении все буквы. В итоге мы получим бессмысленный набор букв, который вряд ли кто сможет понять. Но абы как заменять буквы нельзя, ведь мы должны сами суметь прочитать своё же сообщение. Простейший из известных примеров — шифр Цезаря. Перепишем сообщение по следующему правилу: каждую букву заменим на букву следующую за ней через 3 буквы в алфавите. Мы произвели «сдвиг» (рис. 1).
Математическая кухня
Для простоты будем использовать буквы = 1). На выходе мы получаем некое число, которое будет новым номером шифруемой буквы. Приведём пример использования этой функции (таб. 1)
Аналогично мы можем написать функцию дешифровки: Dn(x) = (x−n) mod 26
Что будет, если «сдвиг» будет равен 26?
Исходный алфавит не изменится. Это интересное следствие, которое поможет нам разобраться во «взломе» этого шифра.
Поимка главаря итальянской мафии Бернардо Провенцано
В 2006 году в Сицилии был пойман самый опасный из крёстных отцов итальянской мафии, которого по праву считали боссом боссов всей сицилийской мафии Бернардо Провенцано. За Бернардо охотились более 40 лет. Итальянская полиция смогла перехватить и расшифровать секретные послания мафиози, и тем самым узнала, где он скрывался. Бернардо использовал разновидность шифра Цезарь Если бы он был столь же продвинутым сколько и коварным, он бы знал, что шифр цезаря легко «взламывается» и не следует им пользоваться.
Этим шифром пользовался Юлий Цезарь, в будущем все разновидности подобных шифров будут носить его имя. Достоверно известно, что Цезарь использовал тайнопись в переписках со своими генералами. Кажется ли вам этот шифр надёжным? Неподготовленный человек, увидев зашифрованное сообщение, ничего не понял бы, возможно, он принял бы это сообщение за ошибку или шутку. Но человеку, который знаком с шифрованием, не составит труда взломать его.
Начало криптоанализа: взломаем шифр!
Lопустим, вы получили текст и уверены, что в нём зашифровано некое сообщение: Khos ph! Hqhqb dw wkh Jdwhv!
Как к нему подступиться? Допустим, мы знаем, что текст зашифровал Бернардо Провенцано, который был не искушён в тайнописи и использовал простой метод Цезаря. Но мы не знаем, какой именно «сдвиг» он использовал. Давайте посчитаем, сколько существует вариантов «сдвига»? Например, первую букву а (0) мы можем заменить на b (1), с (2) и так далее до z (25), очевидно, что дальше следует повторение. Иначе говоря, существует всего 25 способов «сдвинуть» алфавит (таб. 2).
Метод первый: грубая сила!
Теперь мы должны перебрать все 25 вариантов. Это означает, что, используя функцию дешифровки, необходимо перебрать все значения сдвигов (их в нашем случае насчитывается 25 штук), то есть получить расшифровки (таб. 3). Из всех 25 вариантов выбираем тот, который имеет смысл, то есть вариант со сдвигом на 3.
Подобный подход, когда перебираются все возможные варианты называется «перебором» или атакой «грубой силы» (brute force). В примере мы смогли перебрать все варианты, которых, скажем прямо, было не так много. В шифрах, используемых сейчас, прямой метод перебора практически неосуществим, по причине того, что это займёт у вас миллионы лет.
Метод второй: частный анализ
Каждый из нас замечал, что язык, на котором мы говорим, будь то казахский, русский или английский, имеет свои особенaности? Вы сразу же припомните, что есть отличия того, как мы произносим слова, как их пишем, как расставляем знаки препинания и прочее. Эти особенности при шифровании так же сохраняются! На примере шифра Цезаря видно, что если в исходном сообщение была допущена ошибка, шифр сохранит» эту ошибку.
Или зададимся таким вопросом: как часто вы используете слово «энцефалография»? Если вы не врач, специализирующийся на снимках головного мозга, наверняка не часто. Значит, в нашей речи есть слова, которые мы используем чаще, и есть слова, которые используем реже. Давайте сделаем ещё один шаг, задумывались ли вы над тем, какие буквы мы используем чаще?
Анализ нашего языка показал, что некоторые буквы мы используем чаще! Например, в русском языке самая часто встречающаяся буква — это буква «о», которая встречается в 10% всех слов, на втором месте буква — «е» (8% всех слов) и на третьем месте буква — «а» (7%). Частота появления букв сохранена и в английском языке.
Что же это нам даёт? Очень много. Допустим, мы получили зашифрованное сообщение. Посчитаем, сколько раз встречается каждая буква. Допустим буква «g» встречается чаше других, значит с большой вероятностью эта буква в исходном тексте шифрует букву «e». Если бы это был шифр Цезаря, вы бы догадались что «сдвиг» равен 3.
Заглавное изображение: Unsplash
