На этом шаге мы расскажем вам о старинной методике шифрования - шифре Цезаря, - с помощью которого сам Гай Юлий Цезарь делал личные
сообщения непонятными для врагов. К сожалению, шифр Цезаря слишком легко взламывается и никакой настоящей защиты не дает,
но часто служит для развлечения и скрытия содержимого форумов (тех, которые можно найти в интернете, а не в Древнем Риме), которое необходимо защитить от глаз наивных пользователей.
Общее описание
В основе шифра Цезаря лежит идея сдвига шифруемых символов на фиксированное количество позиций в алфавите. Далее мы рассмотрим один из частных случаев шифра Цезаря - алгоритм ROT13.
ROT13 - простой алгоритм шифрования, используемый на многих форумах (например, Reddit) для защиты от спойлеров или скрытия смысла дискуссии от новичков. Дешифровка алгоритма ROT13 проста - злоумышленник может взломать ваш код с помощью вероятностного анализа распределения букв в зашифрованном тексте, даже не зная, на сколько позиций сдвинуты символы. Никогда не следует использовать этот алгоритм для настоящего шифрования сообщений! Тем не менее существует немало приложений алгоритма ROT13:
- скрытие ответов на головоломки на интернет-форумах;
- скрытие возможных спойлеров на фильмы или книги;
- высмеивание других слабых алгоритмов шифрования: "56-битный алгоритм DES по крайней мере лучше, чем ROT13";
- скрытие адресов электронной почты на сайтах от 99,999% спам-ботов.
Таким образом, ROT13 - скорее популярная дежурная шутка в интернеткультуре и образовательный инструмент, а не серьезный шифр.
Этот алгоритм можно объяснить одной фразой: ROT13 = сдвиг шифруемой строки символов на 13 позиций (по модулю 26) в алфавите из 26 символов (рисунок 1).
Рис.1. Таблица на рисунке демонстрирует, как зашифровывается и расшифровывается каждый из символов алфавита при использовании
алгоритма ROT13
Другими словами, каждый символ сдвигается на 13 позиций по алфавиту. При выходе за пределы последнего символа, z, происходит переход к первому
символу алфавита, a.
Код
В примере 6.6 мы создаем однострочник для шифрования строки s с помощью алгоритма ROT13!
Пример 6.6. Однострочное решение для шифрования строки с помощью алгоритма ROT13
## Данные abc = "abcdefghijklmnopqrstuvwxyz" s = "xthexrussiansxarexcoming" ## Однострочник rt13 = lambda x: "".join([abc[(abc.find(c) + 13) % 26] for c in x]) ## Результат print(rt13(s)) print(rt13(rt13(s)))
Воспользуйтесь рисунком 1, чтобы взломать этот шифр: каковы результаты выполнения данного фрагмента кода?
Принцип работы
Наше однострочное решение шифрует каждую из букв по отдельности, сдвигая ее на 13 позиций вправо по алфавиту, хранящемуся в переменной abc, после чего создает список этих зашифрованных букв и объединяет элементы этого списка в целую зашифрованную фразу х.
Рассмотрим подробнее способ шифрования каждой из букв. Для создания списка зашифрованных букв используется списковое включение, каждая буква c заменяется буквой, расположенной на 13 позиций дальше в алфавите. При этом важно предотвратить выход за пределы алфавита для букв, где индекс >= 13. Например, при сдвиге буквы z с индексом 25 на 13 позиций получается недопустимый для алфавита индекс 25 + 13 = 38. Для решения этой проблемы мы используем оператор сложения по модулю, чтобы даже при выходе за максимальный индекс 25 для буквы z шифрование продолжалось, если индекс = 0 (буква а). И продолжаем сдвигать вправо на оставшиеся из 13 позиций, которые еще не были учтены до перехода в начало алфавита (рисунок 2).
Рис.2. Предотвращаем выход за пределы алфавита, начиная отсчет индекса заново с 0, в результате чего получается такая последовательность сдвига:
25 > 0 > 1 > > 12
Например, буква z сдвигается на 13 позиций до индекса 38 по модулю 26 (в виде кода Python: 38 % 26), то есть до индекса 12 (буквы m).
Вот главная часть кода, описывающая сдвиг каждого символа c на 13 позиций:
abc[(abc.find(c) + 13) % 26]
Во-первых, мы находим индекс символа c в алфавите abc. Во-вторых, сдвигаем этот индекс, прибавляя целое число 13 к индексу символа c в алфавите abc, с учетом нашего приема с модулем 26 (как пояснялось в предыдущих абзацах).
Результат выполнения кода однострочника выглядит следующим образом:
## Результат print(rt13(s)) # kgurkehffvnafknerkpbzvat print(rt13(rt13(s))) # xthexrussiansxarexcoming
Резюмируя: вы изучили частный случай шифра Цезаря, алгоритм ROT13, при котором каждая буква в строке сдвигается на 13 позиций в алфавите. При повторном сдвиге еще на 13 позиций индекса (13 + 13 = 26) получается исходная буква, так что для шифрования и дешифрования применяется один алгоритм.
На следующем шаге мы рассмотрим поиск простых чисел с помощью решета Эратосфена.
