stringtranslate.com

шифр Цезаря

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

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Взлом шифра

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

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

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

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

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


Клавиатурный шифр Цезаря

получается определенным сдвигом на клавиатуре компьютера. Например, «один сдвиг вправо», a->s (что подразумевает q -> w), преобразует имя

«ДжонСмит» в пароль

'KpjmD,ойж'

Эти коды легко взломать при использовании более длинных образцов, но они могут служить полезным инструментом для запоминания паролей из 8–12 символов.


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

Примечания

  1. ^ Светоний, Vita Divi Julii 56.6
  2. ^ Лучано, Деннис; Гордон Причетт (январь 1987 г.). «Криптология: от шифров Цезаря к криптосистемам с открытым ключом». Математический журнал колледжа . 18 (1): 2–17. CiteSeerX  10.1.1.110.6123 . дои : 10.2307/2686311. JSTOR  2686311.
  3. ^ Вобст, Рейнхард (2001). Криптология разблокирована. Уайли. п. 19. ISBN 978-0-470-06064-3.
  4. ^ «Взлом кода». Центральное Разведывательное Управление . Архивировано из оригинала 26 декабря 2020 года . Проверено 21 февраля 2017 г.
  5. ^ Сингх, Саймон (2000). Кодовая книга . Якорь. стр. 289-290. ISBN 0-385-49532-3.
  6. ^ Рейнке, Эдгар К. (декабрь 1962 г.). «Классическая криптография». Классический журнал . 58 (3): 114.
  7. ^ Сингх, Саймон (2000). Кодовая книга . Якорь. стр. 14–20. ISBN 0-385-49532-3.
  8. ^ Айзенберг, Рональд Л. (2004). Еврейские традиции (1-е изд.). Филадельфия: Еврейское издательское общество. п. 582. ИСБН 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). Криптология разблокирована. Уайли. п. 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. ^ Лейден, Джон (19 апреля 2006 г.). «Босс мафии уничтожен неуклюжей криптографией» . Регистр . Проверено 13 июня 2008 г.
  16. ^ «Джихадист BA полагался на шифрование эпохи Иисуса» . Регистр . 22 марта 2011 г. Проверено 1 апреля 2011 г.
  17. ^ Бойтельспехер, Альбрехт (1994). Криптология . Математическая ассоциация Америки . стр. 8–9. ISBN 0-88385-504-6.
  18. ^ Лейтон, Альберт К. (апрель 1969 г.). «Тайная связь между греками и римлянами». Технологии и культура . 10 (2): 139–154. дои : 10.2307/3101474. JSTOR  3101474.
  19. ^ Синьков, Авраам ; Пол Л. Ирвин (1966). Элементарный криптоанализ: математический подход . Математическая ассоциация Америки. стр. 13–15. ISBN 0-88385-622-0.
  20. ^ Сингх, Саймон (2000). Кодовая книга. Якорь. стр. 72–77. ISBN 0-385-49532-3.
  21. ^ Саварезе, Крис; Брайан Харт (15 июля 2002 г.). «Шифр Цезаря». Тринити-колледж . Проверено 16 июля 2008 г.
  22. ↑ Люббе, январь, Калифорния (12 марта 1998 г.). Основные методы криптографии . Издательство Кембриджского университета. стр. 47–8. ISBN 9780521555593.
  23. ↑ Пардо, Хосе Луис Гомес (19 декабря 2012 г.). Введение в криптографию с помощью Maple . Шпрингер Берлин Гейдельберг. п. 5. ISBN 9783642321665.
  24. ^ Вобст, Рейнхард (2001). Криптология разблокирована. Уайли. п. 31. ISBN 978-0-470-06064-3.

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

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

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

Викискладе есть медиафайлы, связанные с шифрами Цезаря .