В криптографии , шифр Цезаря , также известный как шифр Цезаря , то сдвиг шифр , код Цезаря или Цезарь сдвиг , это один из самых простых и широко известных шифровальных методов. Это тип шифра подстановки, в котором каждая буква в открытом тексте заменяется буквой на фиксированное количество позиций в алфавите . Например, при сдвиге влево 3, D будет заменено на A , E станет B и так далее. Метод назван в честь Юлия Цезаря., который использовал его в своей личной переписке. [1]
Этап шифрования, выполняемый шифром Цезаря, часто включается как часть более сложных схем, таких как шифр Виженера , и до сих пор имеет современное применение в системе ROT13 . Как и все одноалфавитные подстановочные шифры, шифр Цезаря легко взламывается и в современной практике практически не обеспечивает безопасности связи .
Пример [ править ]
Преобразование может быть представлено выравниванием двух алфавитов; шифралфавит - это простой алфавит, повернутый влево или вправо на некоторое количество позиций. Например, вот шифр Цезаря, использующий вращение влево на три позиции, что эквивалентно сдвигу вправо, равному 23 (параметр сдвига используется в качестве ключа ):
Простой | А | B | C | D | E | F | грамм | ЧАС | я | J | K | L | M | N | О | п | Q | р | S | Т | U | V | W | Икс | Y | Z |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Шифр | Икс | Y | Z | А | B | C | D | E | F | грамм | ЧАС | я | J | K | L | M | N | О | п | Q | р | S | Т | U | V | W |
При шифровании человек просматривает каждую букву сообщения в «простой» строке и записывает соответствующую букву в строке «шифр».
Открытый текст: БЫСТРАЯ КОРИЧНЕВАЯ ЛИСА ПЫГАЕТ НА ЛЕНИВУЮ СОБАКЗашифрованный текст: QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD
Расшифровка производится в обратном порядке, со сдвигом вправо на 3.
Шифрование также может быть представлено с помощью модульной арифметики путем преобразования букв в числа в соответствии со схемой A → 0, B → 1, ..., Z → 25. [2] Шифрование буквы x сдвигом n математически можно описать как, [3]
Расшифровка производится аналогично,
(Существуют разные определения для операции по модулю . В приведенном выше примере результат находится в диапазоне от 0 до 25; то есть, если x + n или x - n не находятся в диапазоне от 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] В то время нет никаких записей о каких-либо методах решения простых подстановочных шифров. Самые ранние сохранившиеся записи относятся к работам Аль-Кинди 9-го века в арабском мире с открытием частотного анализа . [8]
Шифр Цезаря со сдвигом на единицу используется на обратной стороне мезузы для шифрования имен Бога . Это может быть пережитком более ранних времен, когда евреям не разрешалось есть мезузот. Сами буквы криптограммы содержат религиозно значимое «божественное имя», которое, согласно православной вере, сдерживает силы зла. [9]
В 19 веке раздел личной рекламы в газетах иногда использовался для обмена сообщениями, зашифрованными с использованием простых схем шифрования. Кан (1967) описывает случаи, когда любовники участвовали в секретных сообщениях, зашифрованных с помощью шифра Цезаря в The Times . [10] Даже в 1915 году шифр Цезаря использовался: русская армия использовала его как замену более сложным шифрам, которые оказались слишком трудными для освоения их войсками; Немецким и австрийским криптоаналитикам не составило труда расшифровать свои сообщения. [11]
Шифры Цезаря сегодня можно найти в детских игрушках, таких как секретные кольца-декодеры . Сдвиг Цезаря на тринадцать также выполняется в алгоритме ROT13 , простом методе обфускации текста, широко распространенном в Usenet и используемом для затемнения текста (например, анекдотов и спойлеров рассказов ), но серьезно не используемого в качестве метода шифрования. [12]
Шифр Виженера использует шифр Цезаря с другим сдвигом в каждой позиции в тексте; значение сдвига определяется с помощью повторяющегося ключевого слова. Если длина ключевого слова равна длине сообщения, оно выбрано случайным образом , никогда не становится известно никому и никогда не используется повторно, это одноразовый блокнотный шифр, который доказал свою нерушимость. Условия настолько трудны, что на практике они никогда не достигаются. Ключевые слова короче сообщения (например, « Полная победа », использовавшаяся Конфедерацией во время Гражданской войны в США ), вводят циклический паттерн, который может быть обнаружен с помощью статистически продвинутой версии частотного анализа. [13]
В апреле 2006 года беглый босс мафии Бернардо Провенцано был схвачен на Сицилии отчасти из-за того, что некоторые из его сообщений, неуклюже написанных с использованием шифра Цезаря, были взломаны. В шифре Провенцано использовались числа, так что «A» записывалась как «4», «B» как «5» и так далее. [14]
В 2011 году Раджиб Карим был осужден в Соединенном Королевстве за «террористические преступления» после того, как использовал шифр Цезаря для связи с бангладешскими исламскими активистами, обсуждая заговоры с целью взорвать самолеты British Airways или нарушить работу их ИТ-сетей. Хотя стороны имели доступ к гораздо более совершенным методам шифрования (сам Карим использовал PGP для хранения данных на дисках компьютеров), они решили использовать свою собственную схему (реализованную в Microsoft Excel ), отказавшись от более сложной программы кода под названием «Секреты моджахедов», «потому что кафры «или неверующие знают об этом, поэтому он должен быть менее безопасным». [15] Это представляло собой применение безопасности через безвестность .
Взлом шифра [ править ]
Сдвиг дешифрования | Открытый текст кандидата |
---|---|
0 | exxegoexsrgi |
1 | dwwdfndwrqfh |
2 | cvvcemcvqpeg |
3 | buubdlbupodf |
4 | атака сразу |
5 | zsszbjzsnmbd |
6 | yrryaiyrmlac |
... | |
23 | haahjrhavujl |
24 | gzzgiqgzutik |
25 | fyyfhpfytshj |
Шифр Цезаря может быть легко взломан даже при использовании только зашифрованного текста . Можно рассмотреть две ситуации:
- злоумышленник знает (или догадывается), что был использован какой-то простой шифр подстановки, но не специально, что это схема Цезаря;
- злоумышленник знает, что используется шифр Цезаря, но не знает значения сдвига.
В первом случае шифр может быть взломан с использованием тех же методов, что и для обычного простого шифра подстановки, такого как частотный анализ или шаблонные слова. [16] В процессе решения злоумышленник, вероятно, быстро заметит закономерность в решении и сделает вывод, что шифр Цезаря - это конкретный используемый алгоритм.
Во втором случае сломать схему еще проще. Поскольку существует только ограниченное количество возможных сдвигов (25 на английском языке), каждый из них может быть протестирован по очереди с помощью грубой силы . [17] Один из способов сделать это - записать фрагмент зашифрованного текста в таблицу всех возможных сдвигов [18] - метод, иногда известный как «завершение простого компонента». [19] Данный пример относится к зашифрованному тексту EXXEGOEXSRGI"; открытый текст мгновенно распознается на глаз при сдвиге в четыре раза. Другой способ просмотра этого метода заключается в том, что под каждой буквой зашифрованного текста весь алфавит записывается в обратном порядке, начиная с этой буквы. Эту атаку можно ускорить, используя набор полосок, подготовленных с использованием алфавита, записанного в обратном порядке. Затем полосы выравниваются, чтобы сформировать зашифрованный текст вдоль одной строки, а открытый текст должен появиться в одной из других строк.
Другой подход грубой силы - сопоставление частотного распределения букв. Графически отображая частотность букв в зашифрованном тексте и зная ожидаемое распределение этих букв в исходном языке открытого текста, человек может легко определить значение сдвига, глядя на смещение конкретных элементов графика. Это называется частотным анализом . Например, в английском языке частоты открытого текста букв E , T (обычно наиболее частые) и Q , Z (обычно наименее частые) особенно различимы. [20]Компьютеры также могут делать это, измеряя, насколько хорошо фактическое распределение частот совпадает с ожидаемым распределением; например, можно использовать статистику хи-квадрат . [21]
Для открытого текста на естественном языке обычно будет только одно правдоподобное дешифрование, хотя для очень коротких открытых текстов возможно несколько кандидатов. Например, зашифрованный текст MPQY может быть правдоподобно расшифрован как « аден » или « знать » (при условии, что открытый текст на английском языке); аналогично « АЛИИП » с « куклами » или « колесом »; и « AFCCP » до « Jolly » или « приветствие » (смотри также Юнисити расстояние ).
С шифром Цезаря многократное шифрование текста не обеспечивает дополнительной безопасности. Это потому , что две шифровки, скажем, сдвиг А и сдвиг B , будет эквивалентна одному шифрования со сдвигом A + B . С математической точки зрения, набор операций шифрования под каждым возможным ключом образует группу по составу . [22]
См. Также [ править ]
- Scytale
Заметки [ править ]
- ^ Светоний, Vita Divi Julii 56,6
- ^ Лучано, Деннис; Гордон Причетт (январь 1987 г.). «Криптология: от шифров Цезаря к криптосистемам с открытым ключом». Журнал математики колледжа . 18 (1): 2–17. CiteSeerX 10.1.1.110.6123 . DOI : 10.2307 / 2686311 . JSTOR 2686311 .
- ^ Wobst Рейнхард (2001). Криптология разблокирована . Вайли. п. 19. ISBN 978-0-470-06064-3.
- ^ «Взломать код» . Центральное разведывательное управление . Архивировано из оригинального 26 декабря 2020 года . Проверено 21 февраля 2017 года .
- ^ Сингх, Саймон (2000). Кодовая книга . Якорь. С. 289-290 . ISBN 0-385-49532-3.
- ^ Рейнка, Эдгар С. (декабрь 1962). «Классическая криптография». Классический журнал . 58 (3): 114.
- ^ Пиепшик, Йозеф; Томас Харджоно; Дженнифер Себери (2003). Основы компьютерной безопасности . Springer. п. 6. ISBN 3-540-43101-2.
- ^ Сингх, Саймон (2000). Кодовая книга . Якорь. С. 14–20 . ISBN 0-385-49532-3.
- ^ Александр Полторак. «Мезуза и астрология» . chabad.org . Проверено 13 июня 2008 .
- ^ Кан, Дэвид (1967). Взломщики кодов . С. 775–6. ISBN 978-0-684-83130-5.
- ^ Кан, Дэвид (1967). Взломщики кодов . С. 631–2. ISBN 978-0-684-83130-5.
- ^ Wobst Рейнхард (2001). Криптология разблокирована . Вайли. п. 20. ISBN 978-0-470-06064-3.
- ^ Кан, Дэвид (1967). Взломщики кодов . ISBN 978-0-684-83130-5.
- ^ Лейден, Джон (2006-04-19). «Босс мафии уничтожен неуклюжей криптовалютой» . Реестр . Проверено 13 июня 2008 .
- ^ "Джихадист BA полагался на шифрование времен Иисуса" . Реестр . 2011-03-22 . Проверено 1 апреля 2011 .
- ^ Beutelspacher, Альбрехт (1994). Криптология . Математическая ассоциация Америки . С. 9–11. ISBN 0-88385-504-6.
- ^ Beutelspacher, Альбрехт (1994). Криптология . Математическая ассоциация Америки . С. 8–9. ISBN 0-88385-504-6.
- Перейти ↑ Leighton, Albert C. (апрель 1969). «Тайное общение между греками и римлянами». Технологии и культура . 10 (2): 139–154. DOI : 10.2307 / 3101474 . JSTOR 3101474 .
- ↑ Синьков, Авраам ; Пол Л. Ирвин (1966). Элементарный криптоанализ: математический подход . Математическая ассоциация Америки. С. 13–15. ISBN 0-88385-622-0.
- ^ Сингх, Саймон (2000). Кодовая книга . Якорь. С. 72–77 . ISBN 0-385-49532-3.
- ^ Саварезе, Крис; Брайан Харт (2002-07-15). «Шифр Цезаря» . Проверено 16 июля 2008 .
- ^ Wobst Рейнхард (2001). Криптология разблокирована . Вайли. п. 31. ISBN 978-0-470-06064-3.
Библиография [ править ]
- Ф.Л. Бауэр , « Расшифрованные секреты» , 2-е издание, 2000 г., Springer. ISBN 3-540-66871-3 .
- Дэвид Кан , Взломщики кодов: история тайного письма , пересмотренное изд. 1996. ISBN 0-684-83130-9 .
- Крис Саварезе и Брайан Харт, Цезарь Шифр , 1999
Внешние ссылки [ править ]
Викискладе есть медиафайлы, связанные с шифрами Цезаря . |
- Вайсштейн, Эрик В. «Метод Цезаря» . MathWorld .