Шифр цезаря - Caesar cipher

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

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

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

пример

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

Обычный: ABCDEFGHIJKLMNOPQRSTUVWXYZ Шифр: XYZABCDEFGHIJKLMNOPQRSTUVW

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

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

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

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

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

(Есть разные определения для операция по модулю. В приведенном выше примере результат находится в диапазоне от 0 до 25; т.е. если Икс + п или Икс − п не находятся в диапазоне от 0 до 25, мы должны вычесть или добавить 26.)

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

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

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

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

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

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

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

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

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

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

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

— Авл Геллий, Мансардные ночи 17.9.1–5

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

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

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

Конструкция из двух вращающихся дисков с шифром Цезаря может использоваться для шифрования или дешифрования кода.

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

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

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

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

Взлом шифра

Расшифровка
сдвиг		Открытый текст кандидата
0exxegoexsrgi
1dwwdfndwrqfh
2cvvcemcvqpeg
3buubdlbupodf
4атака сразу
5zsszbjzsnmbd
6yrryaiyrmlac
...
23haahjrhavujl
24gzzgiqgzutik
25fyyfhpfytshj

Шифр Цезаря легко взломать даже в сценарий только зашифрованного текста. Можно рассмотреть две ситуации:

  1. злоумышленник знает (или догадывается), что был использован какой-то простой шифр подстановки, но не специально, что это схема Цезаря;
  2. злоумышленник знает, что используется шифр Цезаря, но не знает значения сдвига.

В первом случае шифр можно взломать, используя те же методы, что и для обычного простого шифра подстановки, например частотный анализ или шаблонные слова.[16] В процессе решения злоумышленник, вероятно, быстро заметит регулярность решения и сделает вывод, что шифр Цезаря - это конкретный используемый алгоритм.

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

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

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

Для открытого текста на естественном языке обычно существует только одно правдоподобное дешифрование, хотя для очень коротких открытых текстов возможно несколько кандидатов. Например, зашифрованный текст MPQY может, вероятно, расшифровать до "аден" или "знать"(предполагается, что открытый текст на английском языке); аналогично,"АЛИИП"к"куклы" или "рулевое колесо"; и "AFCCP"к"весёлый" или "приветствовать" (смотрите также расстояние уникальности ).

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

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

Заметки

  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. ^ «Взломать код». Центральное Разведывательное Управление. Получено 21 февраля 2017.
  5. ^ Сингх, Саймон (2000). Кодовая книга. Якорь. стр.289-290. ISBN  0-385-49532-3.
  6. ^ Рейнке, Эдгар С. (декабрь 1962 г.). «Классическая криптография». Классический журнал. 58 (3): 114.
  7. ^ Пиепшик, Йозеф; Томас Харджоно; Дженнифер Себери (2003). Основы компьютерной безопасности. Springer. п. 6. ISBN  3-540-43101-2.
  8. ^ Сингх, Саймон (2000). Кодовая книга. Якорь. стр.14–20. ISBN  0-385-49532-3.
  9. ^ Александр Полторак. «Мезуза и астрология». chabad.org. Получено 2008-06-13.
  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). Взломщики кодов. ISBN  978-0-684-83130-5.
  14. ^ Лейден, Джон (19 апреля 2006 г.). «Босс мафии уничтожен неуклюжей криптовалютой». Реестр. Получено 2008-06-13.
  15. ^ «Джихадист из БА полагался на шифрование времен Иисуса». Реестр. 2011-03-22. Получено 2011-04-01.
  16. ^ Бойтельшпахер, Альбрехт (1994). Криптология. Математическая ассоциация Америки. С. 9–11. ISBN  0-88385-504-6.
  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. ^ Саварезе, Крис; Брайан Харт (2002-07-15). "Шифр Цезаря". Получено 2008-07-16.
  22. ^ Вобст, Рейнхард (2001). Криптология разблокирована. Вайли. п. 31. ISBN  978-0-470-06064-3.

Список используемой литературы

  • Ф. Л. Бауэр, Расшифрованные секреты, 2-е издание, 2000 г., Springer. ISBN  3-540-66871-3.
  • Дэвид Кан, Взломщики кодов: история тайного письма, Перераб. 1996 г. ISBN  0-684-83130-9.
  • Крис Саварезе и Брайан Харт, Шифр Цезаря, 1999

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