Эта статья входит в число добротных статей

Шифр Цезаря

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Шифрование шифром Цезаря со сдвигом вправо на 3 буквы:
  • замена буквы «A» на букву «D»;
  • замена буквы «B» на букву «E»;
  • и так далее;
  • замена буквы «Z» на букву «C»

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

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

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

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

Пусть

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

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

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

Пусть

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

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

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

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

…;
где .

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

ведь

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

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

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

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

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

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

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

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

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

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 буквы

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

Если у него было что-либо конфиденциальное для передачи, то он записывал это шифром, то есть так изменял порядок букв алфавита, что нельзя было разобрать ни одно слово. Если кто-либо хотел дешифровать его и понять его значение, то он должен был подставлять по следующему принципу: «A» вместо «D», и так далее, с другими буквами.
Гай Светоний Транквилл Жизнь двенадцати цезарей, Книга первая, глава 56[4]

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

Всякий раз, когда он записывал шифром, он записал «B» для «A», «C» для «B», и остальной части букв на том же самом принципе, используя «AA» для «X».
Гай Светоний Транквилл Жизнь двенадцати цезарей, Книга вторая, глава 88[4]

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

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

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

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

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

Некоторые люди шифровали[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 Открытый текст
0 exxegoexsrgi
1 dwwdfndwrqfh
2 cvvcemcvqpeg
3 buubdlbupodf
4 attackatonce
5 zsszbjzsnmbd
6 yrryaiyrmlac
23 haahjrhavujl
24 gzzgiqgzutik
25 fyyfhpfytshj

Открытый текст немедленно опознается глазом в строке, для которой 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) (смотрите расстояние единственности).

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

  1. Luciano D., Prichett G. Cryptology: From Caesar Ciphers to Public-Key Cryptosystems (англ.) // The College Mathematics JournalMAA, Taylor & Francis, 1987. — Vol. 18, Iss. 1. — P. 2—17. — ISSN 0746-8342; 1931-1346doi:10.2307/2686311
  2. Wobst, 2007, pp. 19.
  3. Wobst, 2007, pp. 31.
  4. 1 2 Жизнь двенадцати цезарей, 1964.
  5. Reinke E. C. Classical Cryptography (англ.) // The Classical JournalClassical Association of the Middle West and South, 1962. — Vol. 58, Iss. 3. — P. 113—121. — ISSN 0009-8353; 2327-5812
  6. Pieprzyk J., Hardjono T., Seberry J. Fundamentals of Computer Security (англ.)Springer Science+Business Media, 2003. — P. 6. — 677 p. — ISBN 978-3-540-43101-5
  7. Singh, 1999, pp. 14–20.
  8. Alexander Poltorak. Mezuzah and Astrology. chabad.org. Дата обращения: 13 июня 2008. Архивировано 2 июня 2008 года.
  9. Kahn, 1967, pp. 775–6.
  10. Kahn, 1967, pp. 631–2.
  11. Wobst, 2007, pp. 20.
  12. Фомичёв, 2003, с. 239-246.
  13. Kahn, 1967.
  14. Leyden, John (2006-04-19). "Mafia boss undone by clumsy crypto". The Register. Архивировано из оригинала 12 декабря 2010. Дата обращения: 13 июня 2008.
  15. Reynard, Robert. Secret Code Breaker: A Cryptanalyst's Handbook (англ.). — 1996. — P. 92—51. — ISBN 1-889668-00-1).
  16. Beutelspacher, Albrecht  (англ.). Cryptology (неопр.). — Mathematical Association of America, 1994. — С. 8—9. — ISBN 0-88385-504-6.
  17. Sinkov A. Elementary Cryptanalysis (англ.): A Mathematical ApproachMAA, 1998. — P. 13—15. — 232 p. — ISBN 978-0-88385-622-2
  18. Singh, 1999, pp. 72–77.
  19. Savarese, Chris; Brian Hart.: The Caesar Cipher (15 июля 2002). Дата обращения: 16 июля 2008. Архивировано 24 мая 2020 года.

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

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