шифр Цезаря
В криптографии шифр Цезаря , также известный как шифр Цезаря , шифр сдвига , код Цезаря или сдвиг Цезаря , является одним из самых простых и широко известных шифрования методов . Это тип шифра замены , в котором каждая буква открытого текста заменяется буквой, находящейся в определенном количестве позиций в алфавите . Например, при сдвиге влево на 3, D будет заменен на А , Э стал бы Б и так далее. Метод назван в честь Юлия Цезаря , который использовал его в своей частной переписке. [1]
Этап шифрования, выполняемый шифром Цезаря, часто включается как часть более сложных схем, таких как шифр Виженера , и до сих пор имеет современное применение в системе ROT13 . Как и все одноалфавитные шифры замены, шифр Цезаря легко взломать и в современной практике практически не обеспечивает безопасности связи .
Пример
[ редактировать ]Преобразование можно представить путем выравнивания двух алфавитов; шифралфавит — это простой алфавит, повернутый влево или вправо на некоторое количество позиций. Например, вот шифр Цезаря, использующий вращение на три позиции влево, что эквивалентно сдвигу вправо на 23 (в качестве ключа используется параметр сдвига ):
| Простой | А | Б | С | Д | И | Ф | Г | ЧАС | я | Дж | К | л | М | Н | ТО | П | вопрос | Р | С | Т | В | V | В | Х | И | С |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Шифр | Х | И | С | А | Б | С | Д | И | Ф | Г | ЧАС | я | Дж | К | л | М | Н | ТО | П | вопрос | Р | С | Т | В | V | В |
При шифровании человек просматривает каждую букву сообщения в «простой» строке и записывает соответствующую букву в «зашифрованную» строку.
Plaintext: THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG Ciphertext: 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]
Шифры Цезаря сегодня можно найти в детских игрушках, таких как секретные кольца-декодеры . Сдвиг Цезаря на тринадцать также выполняется в ROT13 алгоритме — простом методе запутывания текста, широко распространенном в Usenet и используемом для скрытия текста (например, шуточных изюминок и спойлеров историй ), но серьезно не используемом в качестве метода шифрования. [12]
Шифр Виженера использует шифр Цезаря с разным сдвигом в каждой позиции текста; значение сдвига определяется с помощью повторяющегося ключевого слова. [13] Если ключевое слово имеет длину, равную длине сообщения, выбирается случайным образом , никогда не становится известным никому другому и никогда не используется повторно, то это одноразовый шифр блокнота, доказавший свою неуязвимость. Однако проблемы, связанные с использованием случайного ключа, пока сообщение делает одноразовый блокнот трудным для использования на практике. Ключевые слова короче сообщения (например, « Полная победа », использованная Конфедерацией во время Гражданской войны в США ), вводят циклический паттерн, который можно обнаружить с помощью статистически продвинутой версии частотного анализа. [14]
В апреле 2006 года беглый мафии босс Бернардо Провенцано был схвачен на Сицилии отчасти потому, что некоторые из его сообщений, неуклюже написанных разновидностью шифра Цезаря, были взломаны. В шифре Провенцано использовались цифры, так что «А» записывалось как «4», «Б» — как «5» и так далее. [15]
В 2011 году Раджиб Карим был осужден в Соединенном Королевстве за «террористические преступления» после использования шифра Цезаря для общения с бангладешскими исламскими активистами, обсуждавшими заговоры с целью взрыва самолетов British Airways или нарушения работы их ИТ-сетей. Хотя стороны имели доступ к гораздо более совершенным методам шифрования (сам Карим использовал PGP для хранения данных на компьютерных дисках), они предпочли использовать собственную схему (реализованную в Microsoft Excel ), отказавшись от более сложной кодовой программы под названием « Секреты моджахедов », «потому что «кафры» или неверующие знают об этом, поэтому это должно быть менее безопасно». [16]
Взлом шифра
[ редактировать ]| Расшифровка сдвиг |
Открытый текст кандидата |
|---|---|
| 0 | exxegoexsrgi |
| 1 | dwwdfndwrqfh |
| 2 | cvvcemcvqpeg |
| 3 | buubdlbupodf |
| 4 | атаковать один раз |
| 5 | zsszbjzsnmbd |
| 6 | ырриайырмлак |
| ... | |
| 23 | хааджрхавуджл |
| 24 | gzzgiqgzutik |
| 25 | мойфхпфитшж |
Шифр Цезаря можно легко взломать даже в случае использования только зашифрованного текста . Поскольку количество возможных сдвигов ограничено (25 на английском языке), злоумышленник может провести атаку методом перебора , расшифровав сообщение или его часть, используя каждый возможный сдвиг. Правильным описанием будет то, которое имеет смысл в виде текста на английском языке. [17] Справа показан пример зашифрованного текста " exxegoexsrgi "; открытый текст-кандидат на четвертую смену" Attackatonce » — единственное, что имеет смысл в английском тексте. Другой тип атаки методом перебора — это выписывание алфавита под каждой буквой зашифрованного текста, начиная с этой буквы. Опять же, правильная расшифровка — это та, которая имеет смысл в английском тексте. Этот метод иногда называют «завершением простого компонента». [18] [19]
Другой подход — согласовать частотное распределение букв. Построив график частот букв в зашифрованном тексте и зная ожидаемое распределение этих букв на исходном языке открытого текста, человек может легко определить значение сдвига, глядя на смещение определенных особенностей графа. Это известно как частотный анализ . Например, в английском языке частоты букв в открытом тексте И , T , (обычно наиболее часто) и Вопрос , Z (обычно реже всего) особенно характерны. [20] Компьютеры могут автоматизировать этот процесс, оценивая сходство между наблюдаемым распределением частот и ожидаемым распределением. Этого можно достичь, например, за счет использования статистики хи-квадрат. [21] или путем минимизации суммы квадратов ошибок между наблюдаемым и известным языковыми распределениями. [22]
Расстояние уникальности шифра Цезаря составляет около 2, что означает, что в среднем для определения ключа требуется не менее двух символов зашифрованного текста. [23] В редких случаях может потребоваться больше текста. Например, слова « река " и " arena » могут быть преобразованы друг в друга с помощью сдвига Цезаря, что означает, что они могут создавать один и тот же зашифрованный текст с разными сдвигами. Однако на практике ключ почти наверняка можно найти как минимум с 6 символами зашифрованного текста. [24]
При использовании шифра Цезаря многократное шифрование текста не обеспечивает дополнительной безопасности. что два шифрования, скажем, сдвиг A и сдвиг B будут эквивалентны одному шифрованию со сдвигом A + B. Это связано с тем , С математической точки зрения набор операций шифрования под каждым возможным ключом образует группу под составом . [25]
См. также
[ редактировать ]Примечания
[ редактировать ]- ^ Светоний, Жизнь божественного Юлия 56.6.
- ^ Лучано, Деннис; Гордон Причетт (январь 1987 г.). «Криптология: от шифров Цезаря к криптосистемам с открытым ключом». Математический журнал колледжа . 18 (1): 2–17. CiteSeerX 10.1.1.110.6123 . дои : 10.2307/2686311 . JSTOR 2686311 .
- ^ Вобст, Рейнхард (2001). Криптология разблокирована . Уайли. п. 19. ISBN 978-0-470-06064-3 .
- ^ «Взлом кода» . Центральное разведывательное управление . Архивировано из оригинала 26 декабря 2020 года . Проверено 21 февраля 2017 г.
- ^ Сингх, Саймон (2000). Кодовая книга . Якорь. стр. 289-290 . ISBN 0-385-49532-3 .
- ^ Рейнке, Эдгар К. (декабрь 1962 г.). «Классическая криптография». Классический журнал . 58 (3): 114.
- ^ Сингх, Саймон (2000). Кодовая книга . Якорь. стр. 14–20 . ISBN 0-385-49532-3 .
- ^ Айзенберг, Рональд Л. (2004). Еврейские традиции (1-е изд.). Филадельфия: Еврейское издательское общество. п. 582. ИСБН 9780827610392 .
- ^ Самет, Марк (2020). Имя: история двуполого еврейского имени Бога . Юджин, Орегон: Wipf & Stock. стр. 5–6. ISBN 9781532693830 .
- ^ Кан, Дэвид (1967). Взломщики кодов . стр. 775–6. ISBN 978-0-684-83130-5 .
- ^ Кан, Дэвид (1967). Взломщики кодов . стр. 631–2. ISBN 978-0-684-83130-5 .
- ^ Вобст, Рейнхард (2001). Криптология разблокирована . Уайли. п. 20. ISBN 978-0-470-06064-3 .
- ^ Кан, Дэвид (1967). Взломщики кодов . стр. 148–149. ISBN 978-0-684-83130-5 .
- ^ Кан, Дэвид (1967). Взломщики кодов . стр. 398–400. ISBN 978-0-684-83130-5 .
- ^ Лейден, Джон (19 апреля 2006 г.). «Босс мафии уничтожен неуклюжей криптографией» . Регистр . Проверено 13 июня 2008 г.
- ^ «Джихадист BA полагался на шифрование времен Иисуса» . Регистр . 22 марта 2011 г. Проверено 1 апреля 2011 г.
- ^ Бойтельспехер, Альбрехт (1994). Криптология . Математическая ассоциация Америки . стр. 8–9. ISBN 0-88385-504-6 .
- ^ Лейтон, Альберт К. (апрель 1969 г.). «Тайная связь между греками и римлянами». Технологии и культура . 10 (2): 139–154. дои : 10.2307/3101474 . JSTOR 3101474 .
- ^ Синьков, Авраам ; Пол Л. Ирвин (1966). Элементарный криптоанализ: математический подход . Математическая ассоциация Америки. стр. 13–15. ISBN 0-88385-622-0 .
- ^ Сингх, Саймон (2000). Кодовая книга . Якорь. стр. 72–77 . ISBN 0-385-49532-3 .
- ^ Саварезе, Крис; Брайан Харт (15 июля 2002 г.). «Шифр Цезаря» . Тринити-колледж . Проверено 16 июля 2008 г.
- ^ Эйзель, Роберт (18 мая 2007 г.). «Расшифровка шифра Цезаря» . Проверено 2 апреля 2024 г.
- ^ Люббе, Январь, Калифорния (12 марта 1998 г.). Основные методы криптографии . Издательство Кембриджского университета. стр. 47–8. ISBN 9780521555593 .
- ^ Пардо, Хосе Луис Гомес (19 декабря 2012 г.). Введение в криптографию с Maple . Шпрингер Берлин Гейдельберг. п. 5. ISBN 9783642321665 .
- ^ Вобст, Рейнхард (2001). Криптология разблокирована . Уайли. п. 31. ISBN 978-0-470-06064-3 .
Библиография
[ редактировать ]- Кан, Дэвид (1996). Взломщики кодов: История тайного письма (пересмотренная редакция). Нью-Йорк. ISBN 0-684-83130-9 . ОСЛК 35159231 .
{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) - Крис Саварезе и Брайан Харт, Шифр Цезаря , Тринити-колледж , 1999 г.
Дальнейшее чтение
[ редактировать ]- Бауэр, Фридрих Людвиг (2000). Расшифрованные секреты: методы и принципы криптологии (2-е и расширенное изд.). Берлин: Шпрингер. ISBN 3-540-66871-3 . OCLC 43063275 .
Внешние ссылки
[ редактировать ]
| |||||||||||||||||||||||||
