Шифр Цезаря — Википедия

Шифр Цезаря (лат. notae Caesarianae), шифр сдвига, код Цезаря, схема Цезаря — шифр, при использовании которого каждая буква из открытого текста заменяется на такую букву, которая в алфавите находится на некотором постоянном числе позиций левее или правее от рассматриваемой буквы. Например, при сдвиге букв русского алфавита вправо на 3 позиции

• буква «А» заменяется на букву «Г»,
• буква «Б» заменяется на букву «Д»,
• и так далее,
• буква «Ь» заменяется на букву «Я»,
• буква «Э» заменяется на букву «А»,
• буква «Ю» заменяется на букву «Б»,
• буква «Я» заменяется на букву «В».

Шифр Цезаря относится к шифрам подстановки, к моноалфавитным шифрам, к аффинным шифрам. Шифр Цезаря назван в честь римского полководца Гая Юлия Цезаря, использовавшего его для шифрования текстов при переписке со своими военачальниками. Шифрование шифром Цезаря часто является промежуточным шагом при шифровании более сложными шифрами, например, шифром Виженера. Для текстов на английском языке всё ещё применяется шифр ROT13 — шифр Цезаря со сдвигом на 13 букв. Шифр Цезаря, как и все моноалфавитные шифры, легко взламывается, от чего почти не применяется на практике, но тем не менее известен как один из самых простых методов шифрования.

Математическая модель[править | править код]

Пусть

• ${\displaystyle p}$ — номер в алфавите той буквы, которая была взята из открытого текста (plain text);
• ${\displaystyle c}$ — номер в алфавите той буквы, которая была взята из шифрованного текста (cipher text) буквы;
• ${\displaystyle n}$ — количество имеющихся в алфавите букв, мощность алфавита;
• ${\displaystyle k}$ — ключ, сдвиг (отрицательное число — сдвиг влево; ноль — отсутствие сдвига; положительное число — сдвиг вправо).

Если буквы алфавита занумеровать числами, начиная с числа 0, то шифрование и дешифрование можно выразить следующими формулами модульной арифметики^[1][2]:

• шифрование:

${\displaystyle c=(p+k)\ \mod \ n;}$

• дешифрование:

${\displaystyle p=(c-k)\ \mod \ n.}$

Пусть

${\displaystyle c=\mathrm {rot} _{k}\left(p\right).}$

С точки зрения математики шифр Цезаря является частным случаем аффинного шифра.

Многократное шифрование никак не улучшает стойкость. Например, сначала шифрование со сдвигом a и затем шифрование со сдвигом b эквивалентно шифрованию со сдвигом (a+b):

${\displaystyle \mathrm {rot} _{b}\left(\mathrm {rot} _{a}\left(p\right)\right)=\mathrm {rot} _{a+b}\left(p\right).}$

В математических терминах шифрование с различными ключами образует группу^[3].

Если число k кратно числу n, то шифрование эквивалентно отсутствию шифрования:

${\displaystyle \mathrm {rot} _{0}\left(p\right)=p,}$

${\displaystyle \mathrm {rot} _{n}\left(p\right)=p,}$

${\displaystyle \mathrm {rot} _{2\cdot n}\left(p\right)=p,}$

…;

${\displaystyle \mathrm {rot} _{k\cdot n}\left(p\right)=p,}$ где ${\displaystyle k\in \mathbb {N} }$.

Если текст зашифрован со сдвигом k, то для расшифровки можно использовать шифрование со сдвигом -k:

${\displaystyle c=\mathrm {rot} _{k}\left(p\right),}$

${\displaystyle p=\mathrm {rot} _{-k}\left(c\right),}$

ведь

${\displaystyle \mathrm {rot} _{-k}\left(\mathrm {rot} _{k}\left(p\right)\right)=\mathrm {rot} _{k-k}\left(p\right)=\mathrm {rot} _{0}\left(p\right)=p.}$

Пример[править | править код]

Шифрование с использованием ключа ${\displaystyle k=3}$. Алфавит записывается на полоске бумаги; концы полоски соединяются — получается кольцо. Выбирается буква из открытого текста. Палец (указатель) указывает на выбранную букву алфавита. Палец сдвигается (перемещается) на ${\displaystyle k=3}$ букв по часовой стрелке по кольцу. Выбранная буква заменяется на указываемую пальцем букву. Так, буква «А» заменяется на букву «Г», буква «Б» заменяется на букву «Д», …, буква «Е» — на букву «З», …, твёрдый знак — на букву «Э», …, буква «Я» — на букву «В». Таблица соответствия букве «до шифрования» букве «после шифрования»:

А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В 

Пусть требуется зашифровать следующий текст:

Съешь же ещё этих мягких французских булок да выпей чаю. 

Шифрованный текст получается путём замены каждой буквы оригинального текста соответствующей буквой шифрованного алфавита:

Фэзыя йз зьи ахлш пвёнлш чугрщцкфнлш дцосн жг еютзм ъгб. 

Заменяются только буквы алфавита. Пробелы, цифры, знаки пунктуации и прочие символы не изменяются.

Пример для языков программирования[править | править код]

Python[править | править код]

Код написан и выполняется для 2 языков: русского и английского.

  # Текст, который пользователь хочет ввести text = input("Введите текст, который хотите зашифровать: ") # Пользователь вводит ключ k = int(input("Укажите ключ: ")) # Пользователь вводит язык текста, который будет зашифрован language = input("На каком языке текст, который вы ввели (русский, английский): ")  # Функция шифрования с тремя параметрами: текст, ключ, язык def ceaser_cipher(user, key, lang):     # Переменная результата шифрования; переменная, определяющая верхний и нижний регистр     res, n = [], ""      # Проверка пользователем выбранного языка      # Проверка выбран ли русский язык (регистр букв, вводимых пользователем, не важен)     if lang.lower() in ["русский", "russian"]:         # Двум переменным присваиваются русская азбука нижнего и верхнего регистра соответственно         dictionary, dictionary_upper = "абвгдеёжзийклмнопрстуфхцчшщъыьэюя", "АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ"     # Проверка выбран ли английский язык (регистр букв, вводимых пользователем, не важен)     elif lang.lower() in ["английский", "english"]:         # Двум переменным присваиваются английской азбука нижнего и верхнего регистра соответственно         dictionary, dictionary_upper = "abcdefghijklmnopqrstuvwxyz", "ABCDEFGHIJKLMNOPQRSTUVWXYZ"     else:         return "Такого языка нет в опции"      # Цикл проверки, где каждую итерацию будет обрабатываться один символ из текста последовательно     for i in range(len(user)):         # Проверка символа на верхний или нижний регистр          # Принадлежит ли символ нижнему регистру         if user[i] in dictionary:             n = dictionary         # Принадлежит ли символ верхнему регистру         elif user[i] in dictionary_upper:             n = dictionary_upper         # Символ не принадлежит ни нижнему ни верхнему регистру (символ не является буквой)         else:             res.append(user[i])          # Если символ есть в списке n (является буквой), то будет происходить его зашифровка         if user[i] in n:             # Цикл перебора азбуки             for j in range(len(n)):                 # Если порядковый номер буквы + ключ находятся  в диапазоне от 0 до конца азбуки                 # и если буква из текста совпадает с буквой из азбуки, то:                 if 0 <= j + key < len(n) and user[i] == n[j]:                     # В результат добавляется буква со сдвигом key (зашифрованная буква)                     res.append(n[j + key])                 # Если порядковый номер буквы + ключ выходит из диапазона азбуки, превышая его                 # и если буква из текста совпадает с буквой из азбуки, то:                 elif j + key >= len(n) and user[i] == n[j]:                     # В результат добавляется буква со сдвигом key,                     # при этом преводя порядковый номер буквы к диапазону азбуки (зашифрованая буква)                     res.append(n[(1 - j - key) % (len(n) - 1)])                 # Если порядковый номер буквы + ключ выходит из диапазона азбуки, недотягивает до него                 # и если буква из текста совпадает с буквой из азбуки, то:                 elif j + key < 0 and user[i] == n[j]:                     # В результат добавляется буква со сдвигом key,                     # при этом приводя порядковый номер буквы к диапазону азбуки (зашифрованная буква)                     res.append(n[(j + key) % len(n)])      # Функция возвращает зашифрованный текст     return ''.join(res)  # Вывод зашифрованного текста print(ceaser_cipher(text, k, language)) 

История и применение[править | править код]

Шифр Цезаря назван в честь Гая Юлия Цезаря. Согласно книге Светония «Жизни двенадцати цезарей» Цезарь использовал шифр со сдвигом вправо на 3 буквы для шифрования военных сообщений. Цезарь стал первым описанным в книгах человеком, использовавшим шифр Цезаря. Другие шифры подстановки, как известно, использовались и ранее.

Племянник Цезаря, Август, для шифрования использовал следующий алгоритм: для первых букв алфавита использовал шифрование шифром Цезаря со сдвигом вправо на одну букву, а последнюю букву алфавита заменял на «AA»:

Имеются^[5] доказательства того, что Юлий Цезарь использовал и более сложные схемы.

Неизвестно, насколько эффективным был шифр Цезаря во времена Цезаря, но, вероятно, был разумно безопасен, не в последнюю очередь благодаря тому, что большинство врагов Цезаря были неграмотны и многие предполагали, что сообщения были написаны на неизвестном им иностранном языке^[6]. Нет никаких свидетельств того времени, связанных с методоми взлома простых шифров подстановки. Самые ранние сохранившиеся записи о частотном анализе — работы Ал-Кинди 9-го века об открытии частотного анализа^[7].

Шифром Цезаря со сдвигом на одну букву зашифрована надпись на обратной стороне мезузы. Надпись содержит имена Бога. Это может быть пережитком с раннего времени, когда еврейскому народу не разрешали иметь мезузы^[8].

В XIX веке личная секция рекламных объявлений в газетах иногда использовалась для обмена сообщениями, зашифрованными простыми шифрами. Например, Кан в 1967 году описал^[9] случаи, в которых любители через газету «Таймс» обменивались сообщениями, зашифрованными шифром Цезаря. В 1915 году российская армия использовала^[10] шифр Цезаря, так как сочла более сложные шифры слишком сложными для войск; при расшифровке зашифрованных сообщений немецкие и австрийские криптоаналитики испытывали лишь небольшие трудности.

Шифр ROT13 — шифр Цезаря со сдвигом на 13 букв (влево или вправо). Алглийский алфавит содержит 26 букв. 13 = 26/2. Сдвиг влево на 13 букв эквивалентен сдвигу вправо на 13 букв:

${\displaystyle \mathrm {rot} _{13}\left(p\right)=\mathrm {rot} _{-13}\left(p\right).}$

Некоторые люди шифровали^[11] тексты шифром ROT13 перед публикацией в usenet, но не для сохранения секретности, а скорее для сокрытия спойлеров.

При шифровании шифром Виженера в роли ключа используется строка s. Сначала с использованием строки s определяется значение k. Затем применяется шифрование шифром Цезаря со сдвигом на k букв.

Шифр Вернама (схема одноразовых блокнотов) — шифр (система шифрования), для которого верно следующее. Строка s сгенерирована случайным образом, держится в тайне и используется однократно. Длина строки s равна длине открытого текста. Шифр Вернама — единственный шифр, для которого доказана абсолютная криптографическая стойкость^[12].

Если длина строки s меньше длины открытого текста, возникают циклические образцы. Циклические образцы могут быть обнаружены с помощью улучшенной версии частотного анализа^[13]. Например, во времена гражданской войны в США Конфедерация в качестве ключа использовала строку «Complete Victory», которая временами оказывалась короче открытого текста.

В апреле 2006 года сбежавщий босс сицилийской мафии Бернардо Провенцано был пойман в Сицилии частично из-за криптоанализа его сообщений, написанных с использованием разновидности шифра Цезаря. При шифровании Провенцано сначала заменял буквы на числа — порядковые номера букв в алфавите, а затем к полученной последовательности чисел применял шифр Цезаря. Так, при сдвиге на три символ «A» заменялся на символ «4», символ «B» — на символ «5», и так далее^[14].

Часто для удобства использования шифра Цезаря используют два насаженных на общую ось диска (колеса) разного диаметра с нарисованными по краям дисков буквами алфавита. Изначально диски поворачиваются так, чтобы напротив каждой буквы алфавита внешнего диска находилась та же буква алфавита малого диска. Если теперь повернуть внутренний диск на несколько букв, то получится соответствие между буквами внешнего диска и буквами внутреннего диска — шифр Цезаря. Получившийся диск можно использовать как для шифрования, так и для расшифровки^[15]. Например, если внутренний диск повернуть так, чтобы букве «A» внешнего диска соответствовала буква «D» внутреннего диска, то получится шифр Цезаря со сдвигом на 3 буквы влево.

Взлом шифра[править | править код]

Шифр Цезаря может быть легко взломан, даже если взломщик знает только зашифрованный текст. Рассмотрим два случая.

1. Взломщик знает (или предполагает), что использовался простой шифр подстановки, но не знает, что использовался шифр Цезаря.
2. Взломщик знает, что использовался шифр Цезаря, но не знает k (значение сдвига).

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

Во втором случае взлом шифра проще, чем в первом. Количество возможных значений k равно (n-1). Например, для английского алфавита существует n-1 = 26-1 = 25 возможных значений k. Можно 25 раз расшифровать зашифрованный текст и среди расшифрованных текстов поискать осмысленный текст. Метод называется методом грубой силы^[16].

Используя метод грубой силы, можно составить таблицу, содержащую два столбца. В 1-й столбец записать возможные значения k. Во 2-й столбец записать строки, полученные в результате расшифровки отрывка зашифрованного текста с использованием соответствующего значения k. Эта техника иногда называется^[17] «завершением простого компонента».

Рассмотрим пример. Пусть требуется расшифровать текст «exxegoexsrgi». Составим таблицу.

Открытый текст немедленно опознается глазом в строке, для которой k = 4.

Используя метод грубой силы, можно поступить иначе. Записать шифрованый текст в одну строку. Под каждой буквой шифрованного текста в столбик записать буквы алфавита в алфавитном порядке, начиная с буквы шифрованого текста. Читать строки строка за строкой в поисках осмысленного текста. Метод можно ускорить, если заранее написать буквы алфавита в столбик на вертикальных полосках бумаги и положить полоски так, чтобы в одной из строк читался шифрованный текст. Тогда в некоторой другой строке найдётся открытый текст.

Можно проверить частотности букв — провести частотный анализ. Изобразить диаграмму частотности букв обычного текста на рассматриваемом языке (узнать ожидаемое распределение). Изобразить диаграмму частотности букв шифрованного текста (узнать фактическое распределение). Сравнить две диаграммы — по смещению некоторых характерных черт на диаграммах определить сдвиг (k). Например, в текстах на английском языке буквы «E» и «T» обычно встречаются чаще букв «Q» и «Z»^[18]. Процесс можно автоматизировать — заставить компьютерную программу оценивать, насколько хорошо фактическое распределение частотностей соответствует ожидаемому распределению. Например, может использоваться критерий хи-квадрат^[19].

Для текста, записанного на естественном языке и зашифрованного, существует, скорее всего, только один вариант расшифровки (декодирования). Но, если шифрованые текст короткий, то возможно несколько вариантов расшифровки (с различными k (сдвигами)). Например, шифрованный текст «mpqy» может быть расшифрован (предполагая, что открытый текст написан на английском языке) и как «adem» (k=12), и как «know» (k=2). Шифрованый текст «aliip» может быть расшифрован и как «dolls» (k=-3), и как «wheel» (k=4). Шифрованый текст «afccp» может быть расшифрован и как «jolly» (k=-9), и как «cheer» (k=-2) (смотрите расстояние единственности).

Примечания[править | править код]

Литература[править | править код]

• Гай Светоний Транквилл. Жизнь двенадцати цезарей = De vita XII caesarvm. — М.: Издательство «Наука», 1964. — 374 с. — (Литературные памятники).
• Kahn D. The Codebreakers (англ.): The Story of Secret Writing — Macmillan, 1967. — 1164 p. — ISBN 978-0-684-83130-5
• Singh S. The Code Book, Histoire des codes secrets (англ.): The Science of Secrecy from Ancient Egypt to Quantum Cryptography, De l'Égypte des pharaons à l'ordinateur quantique — New York City: Doubleday, Knopf Doubleday Publishing Group, 1999. — 416 p.
• Фомичёв В. М. Дискретная математика и криптология: Курс лекций / под ред. Н. Д. Подуфалов — М.: Диалог-МИФИ, 2013. — 397 с. — ISBN 978-5-86404-185-7
• Wobst R. Cryptology Unlocked (англ.) / A. Shafir — Chichester: John Wiley & Sons Ltd, 2007. — 554 p. — ISBN 978-0-470-06064-3

Ссылки[править | править код]

• Caesar cipher — реализация шифра Цезаря на разных языках на Rosetta Code^[en].
• Шифр Цезаря - шифрование и дешифровка

Эта статья входит в число добротных статей русскоязычного раздела Википедии.