stringtranslate.com

шифр Цезаря

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

В криптографии шифр Цезаря , также известный как шифр Цезаря , сдвиговый шифр , код Цезаря или сдвиг Цезаря , является одним из самых простых и широко известных методов шифрования . Это тип подстановочного шифра , в котором каждая буква в открытом тексте заменяется буквой на некоторое фиксированное количество позиций вниз по алфавиту . Например, при сдвиге влево на 3, D будет заменена на A , E станет B и так далее. Метод назван в честь Юлия Цезаря , который использовал его в своей частной переписке.

Шаг шифрования, выполняемый шифром Цезаря, часто включается как часть более сложных схем, таких как шифр Виженера , и до сих пор имеет современное применение в системе ROT13 . Как и все одноалфавитные шифры замены, шифр Цезаря легко взломать, и в современной практике он по сути не обеспечивает никакой безопасности связи .

Пример

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

При шифровании человек ищет каждую букву сообщения в «чистой» строке и записывает соответствующую ей букву в «зашифрованной» строке.

Открытый текст: БЫСТРАЯ КОРИЧНЕВАЯ ЛИСА ПЕРЕПРЫГАЕТ ЧЕРЕЗ ЛЕНИВУЮ СОБАКУЗашифрованный текст: QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD

Расшифровка производится в обратном порядке, со сдвигом вправо на 3.

Шифрование также можно представить с помощью модульной арифметики , сначала преобразуя буквы в числа по схеме A → 0, B → 1, ..., Z → 25. [1] Шифрование буквы x сдвигом n можно математически описать как, [2]

Расшифровка выполняется аналогично,

(Здесь «mod» относится к операции по модулю . Значение x находится в диапазоне от 0 до 25, но если x + n или x − n не находятся в этом диапазоне, то следует прибавить или вычесть 26.)

Замена остается одинаковой на протяжении всего сообщения, поэтому шифр классифицируется как тип моноалфавитной замены , в отличие от полиалфавитной замены .

История и использование

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

Шифр Цезаря назван в честь Юлия Цезаря , который, по словам Светония , использовал его со сдвигом на три (A становилась D при шифровании, а D становилась A при расшифровке) для защиты сообщений военного значения. [3] Хотя Цезарь был первым зарегистрированным использованием этой схемы, известно, что ранее использовались и другие шифры подстановки. [4] [5]

«Если он хотел сказать что-то конфиденциальное, он записывал это шифром, то есть, меняя порядок букв алфавита так, что нельзя было разобрать ни слова. Если кто-то хочет расшифровать их и понять их смысл, он должен заменить А на четвертую букву алфавита, а именно D, и так с остальными».

—  Светоний , Жизнь Юлия Цезаря 56

Его племянник Август также использовал этот шифр, но со сдвигом вправо на одну букву и без перехода к началу алфавита:

«Всякий раз, когда он писал шифром, он писал B вместо A, C вместо B, а остальные буквы по тому же принципу, используя AA вместо Z».

—  Светоний , Жизнь Августа 88

Существуют доказательства того, что Юлий Цезарь также использовал более сложные системы [6] , и один писатель, Авл Геллий , ссылается на (ныне утерянный) трактат о его шифрах:

«Существует даже довольно остроумно написанный трактат грамматика Проба о тайном значении букв в составе посланий Цезаря».

—  Авл Геллий , Аттические ночи 17.9.1–5

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

Часть текста, зашифрованная в еврейской версии шифра Цезаря, иногда встречается на обороте еврейских свитков мезузы . Когда каждая буква заменяется на букву, стоящую перед ней в еврейском алфавите, текст переводится как « YHWH , наш Бог, YHWH», цитата из основной части свитка. [8] [9]

В 19 веке раздел личных объявлений в газетах иногда использовался для обмена сообщениями, зашифрованными с использованием простых схем шифрования. Дэвид Кан (1967) описывает в The Times случаи, когда любовники занимались секретной перепиской, зашифрованной с использованием шифра Цезаря . [10] Даже в 1915 году шифр Цезаря использовался: русская армия использовала его в качестве замены более сложным шифрам, которые оказались слишком сложными для их войск; немецкие и австрийские криптоаналитики без труда расшифровывали их сообщения. [11]

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

Шифры Цезаря сегодня можно найти в детских игрушках, таких как секретные декодирующие кольца . Сдвиг Цезаря на тринадцать также выполняется в алгоритме ROT13 , простом методе запутывания текста, широко распространенном в Usenet и используемом для запутывания текста (например, шуточных кульминаций и спойлеров историй ), но не используемом всерьез как метод шифрования. [12]

Шифр Виженера использует шифр Цезаря с различным сдвигом в каждой позиции текста; значение сдвига определяется с помощью повторяющегося ключевого слова. [13] Если ключевое слово имеет такую ​​же длину, как и сообщение, выбирается случайным образом , никогда не становится известным кому-либо еще и никогда не используется повторно, то это шифр одноразового блокнота , доказано невзламываемый. Однако проблемы, связанные с использованием случайного ключа такой же длины, как сообщение, делают одноразовый блокнот сложным для использования на практике. Ключевые слова короче сообщения (например, « Полная победа », использовавшаяся Конфедерацией во время Гражданской войны в США ), вводят циклический шаблон, который может быть обнаружен с помощью статистически продвинутой версии частотного анализа. [14]

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

В 2011 году Раджиб Карим был осужден в Соединенном Королевстве за «террористические преступления» после использования шифра Цезаря для общения с исламскими активистами Бангладеш, обсуждавшими планы взорвать самолеты British Airways или нарушить работу их ИТ-сетей. Хотя стороны имели доступ к гораздо лучшим методам шифрования (сам Карим использовал PGP для хранения данных на компьютерных дисках), они решили использовать свою собственную схему (реализованную в Microsoft Excel ), отвергнув более сложную программу-код под названием Mujahedeen Secrets , «потому что „кафиры“, или неверующие, знают о ней, поэтому она должна быть менее безопасной». [16]

Взлом шифра

Шифр Цезаря может быть легко взломан даже в сценарии только с зашифрованным текстом . Поскольку существует только ограниченное количество возможных сдвигов (25 в английском языке), злоумышленник может провести атаку методом грубой силы , расшифровав сообщение или его часть, используя каждый возможный сдвиг. Правильным описанием будет то, которое имеет смысл как английский текст. [17] Справа показан пример для зашифрованного текста " exxegoexsrgi "; кандидат открытого текста для сдвига четыре " attackatonce " - единственный, который имеет смысл как английский текст. Другой тип атаки методом грубой силы - это написать алфавит под каждой буквой зашифрованного текста, начиная с этой буквы. Опять же, правильным расшифровыванием является то, которое имеет смысл как английский текст. Этот метод иногда называют "завершением компонента простого текста". [18] [19]

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

Другой подход заключается в сопоставлении частотного распределения букв. Построив график частот букв в зашифрованном тексте и зная ожидаемое распределение этих букв в исходном языке открытого текста, человек может легко определить значение сдвига, посмотрев на смещение определенных особенностей графика. Это известно как частотный анализ . Например, в английском языке частоты открытого текста букв E , T (обычно наиболее частые) и Q , Z (обычно наименее частые) особенно различимы. [20] Компьютеры могут автоматизировать этот процесс, оценивая сходство между наблюдаемым распределением частот и ожидаемым распределением. Этого можно достичь, например, с помощью использования статистики хи-квадрат [21] или минимизации суммы квадратов ошибок между наблюдаемым и известным языковым распределением. [22]

Расстояние уникальности для шифра Цезаря составляет около 2, что означает, что в среднем для определения ключа требуется не менее двух символов шифртекста. [23] В редких случаях может потребоваться больше текста. Например, слова « река » и « арена » можно преобразовать друг в друга с помощью сдвига Цезаря, что означает, что они могут производить один и тот же шифртекст с разными сдвигами. Однако на практике ключ почти наверняка можно найти, используя не менее 6 символов шифртекста. [24]

С шифром Цезаря многократное шифрование текста не обеспечивает дополнительной безопасности. Это потому, что два шифрования, скажем, сдвига A и сдвига B , будут эквивалентны одному шифрованию со сдвигом A + B. В математических терминах набор операций шифрования под каждым возможным ключом образует группу под композицией . [25]

Смотрите также

Wikifunctions имеет функцию шифрования Цезаря на основе латинского алфавита .

Примечания

  1. ^ Лучано, Деннис; Гордон Причетт (январь 1987 г.). «Криптология: от шифров Цезаря до криптосистем с открытым ключом». The College Mathematics Journal . 18 (1): 2–17. CiteSeerX  10.1.1.110.6123 . doi :10.2307/2686311. JSTOR  2686311.
  2. ^ Вобст, Рейнхард (2001). Криптология разблокирована. Wiley. стр. 19. ISBN 978-0-470-06064-3.
  3. ^ Светоний . «56,6». Vita Divi Julii (на латыни).
  4. ^ "Cracking the Code". Центральное разведывательное управление . Архивировано из оригинала 26 декабря 2020 года . Получено 21 февраля 2017 года .
  5. ^ Сингх, Саймон (2000). Книга кодов . Ведущий. С. 289-290. ISBN 0-385-49532-3.
  6. ^ Рейнке, Эдгар С. (декабрь 1962 г.). «Классическая криптография». The Classical Journal . 58 (3): 114.
  7. ^ Сингх, Саймон (2000). Книга кодов . Ведущий. С. 14–20. ISBN 0-385-49532-3.
  8. ^ Айзенберг, Рональд Л. (2004). Еврейские традиции (1-е изд.). Филадельфия: Еврейское издательское общество. стр. 582. ISBN 9780827610392.
  9. ^ Самет, Марк (2020). Имя: история двуполого еврейского имени Бога . Юджин, Орегон: Wipf & Stock. стр. 5–6. ISBN 9781532693830.
  10. ^ Кан, Дэвид (1967). Взломщики кодов . стр. 775–6. ISBN 978-0-684-83130-5.
  11. ^ Кан, Дэвид (1967). Взломщики кодов . стр. 631–2. ISBN 978-0-684-83130-5.
  12. ^ Вобст, Рейнхард (2001). Криптология разблокирована. Wiley. стр. 20. ISBN 978-0-470-06064-3.
  13. ^ Кан, Дэвид (1967). Взломщики кодов . стр. 148–149. ISBN 978-0-684-83130-5.
  14. ^ Кан, Дэвид (1967). Взломщики кодов . стр. 398–400. ISBN 978-0-684-83130-5.
  15. ^ Лейден, Джон (2006-04-19). "Босс мафии уничтожен неуклюжим криптографом". The Register . Получено 2008-06-13 .
  16. ^ "BA jihadist полагался на шифрование эпохи Иисуса". The Register . 2011-03-22 . Получено 2011-04-01 .
  17. ^ Бойтельспехер, Альбрехт (1994). Криптология . Математическая ассоциация Америки . стр. 8–9. ISBN 0-88385-504-6.
  18. ^ Лейтон, Альберт К. (апрель 1969). «Тайное общение между греками и римлянами». Технология и культура . 10 (2): 139–154. doi :10.2307/3101474. JSTOR  3101474.
  19. ^ Синков, Абрахам ; Пол Л. Ирвин (1966). Элементарный криптоанализ: математический подход . Математическая ассоциация Америки. стр. 13–15. ISBN 0-88385-622-0.
  20. ^ Сингх, Саймон (2000). Книга кодов. Ведущий. С. 72–77. ISBN 0-385-49532-3.
  21. ^ Саварезе, Крис; Брайан Харт (2002-07-15). "Шифр Цезаря". Тринити-колледж . Получено 2008-07-16 .
  22. ^ Эйзель, Роберт (18 мая 2007 г.). «Расшифровка шифра Цезаря» . Проверено 2 апреля 2024 г.
  23. ^ Lubbe, Jan CA (12 марта 1998 г.). Основные методы криптографии . Cambridge University Press. стр. 47–8. ISBN 9780521555593.
  24. ^ Пардо, Хосе Луис Гомес (19 декабря 2012 г.). Введение в криптографию с Maple . Springer Berlin Heidelberg. стр. 5. ISBN 9783642321665.
  25. ^ Вобст, Рейнхард (2001). Криптология разблокирована. Wiley. стр. 31. ISBN 978-0-470-06064-3.

Библиография

Дальнейшее чтение

Внешние ссылки

На Викискладе есть медиафайлы по теме «Шифры Цезаря» .