Реализация и взлом шифра цезаря

Пример

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

Равнина: ABCDEFGHIJKLMNOPQRSTUVWXYZ

Шифр: XYZABCDEFGHIJKLMNOPQRSTUVW

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

Зашифрованный текст: QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD

Обычный текст: БЫСТРАЯ ЛИСА БРАУНА ПЕРЕПРЫГИВАЕТ ЧЕРЕЗ ЛЕНИВУЮ СОБАКУ

Шифрование может также быть представлено, используя модульную арифметику первым преобразованием писем в числа, согласно схеме, = 0, B = 1…, Z = 25. Шифрование письма изменением n может быть описано математически как,

Декодирование выполнено точно так же

(Есть различные определения для операции по модулю. В вышеупомянутом результат находится в диапазоне 0… 25. Т.е., если x+n или x-n не находятся в диапазоне 0… 25, мы должны вычесть или добавить 26.)

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

Шифр Цезаря

Итак, после небольшого введения в цикл, я предлагаю все-таки перейти к основной теме сегодняшней статьи, а именно к Шифру Цезаря.

Что это такое?

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

Какими особенностями он обладает?

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

Программная реализация

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

Начнем, пожалуй, с создания алфавита. Для этого вы можете скопировать приведенную ниже строку или написать все руками.

Далее, нам нужно обозначить программе шаг, то есть смещение при шифровании. Так, например, если мы напишем букву «а» в сообщении, тот при шаге «2», программа выведет нам букву «в».

Итак, создаем переменнуюsmeshenie, которая будет вручную задаваться пользователем, и message, куда будет помещаться наше сообщение, и, с помощью метода возводим все символы в нашем сообщении в верхний регистр, чтобы у нас не было ошибок. Потом создаем просто пустую переменную itog, куда мы буем выводить зашифрованное сообщение. Для этого пишем следующее:

Итак, теперь переходим к самому алгоритму шифровки. Первым делом создаем цикл, где мы определим место букв, задействованных в сообщении, в нашем списке alfavit, после чего определяем их новые места (далее я постараюсь насытить код с пояснениями):

Далее, мы создаем внутри нашего цикла условие , в нем мы записываем в список itog мы записываем наше сообщение уже в зашифрованном виде и выводим его:

Модернизация

Вот мы и написали программу, однако она имеет очень большой недостаток: «При использовании последних букв(русских), программа выведет вам английские буквы. Давайте это исправим.

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

Теперь нам надо создать условие, которое проверит выбранный язык и применит его, то есть обратится к нужному нам алфавиту. Для этого пишем само условие и добавляем алгоритм шифрования, с помощью которого будет выполнено шифрование:

Дешифровка сообщения

Возможно это прозвучит несколько смешно, но мы смогли только зашифровать сообщение, а насчет его дешифровки мы особо не задумывались, но теперь дело дошло и до неё.

По сути, дешифровка — это алгоритм обратный шифровке. Давайте немного переделаем наш код (итоговый вид вы можете увидеть выше).

Для начала, я предлагаю сделать «косметическую» часть нашей переделки. Для этого перемещаемся в самое начало кода:

Остальное можно оставить так же, но если у вас есть желание, то можете поменять названия переменных.

По большому счету, самые ‘большие’ изменения у нас произойдут в той части кода, где у нас находится алгоритм, где нам нужно просто поменять знак «+» на знак «-«. Итак, переходим к самому циклу:

Книжный шифр

Суть метода книжного шифра — это выбор любого текста из книги, и замена каждой буквы шифруемого слова номером слова в выбранном тексте, начинающегося на нужную букву. Можно заменять не на номер слова, а на координату буквы (строка, номер в строке). При этом одной исходной букве может соответствовать несколько разных кодов, ведь одна и та же буква может находиться в разных местах. Для кодирования обычно используют страницу из какой-то заранее оговоренной книги. Без знания кодовой страницы расшифровать такие зашифрованные послания практически невозможно.

Если же в качестве ключа использовать целую книгу (например, словарь), то можно зашифровывать не отдельные буквы, а целые слова и даже фразы. Тогда координатами слова будут номер страницы, номер строки и номер слова в строке. На каждое слово получится три числа. Можно также использовать внутреннюю нотацию книги — главы, абзацы и т.п. Например, в качестве кодовой книги удобно использовать Библию, ведь там есть четкое разделение на главы, и каждый стих имеет свою маркировку, что позволяет легко найти нужную строку текста. Правда, в Библии нет современных слов типа «компьютер» и «интернет», поэтому для современных фраз лучше, конечно, использовать энциклопедический или толковый словарь. Хотя если заранее договориться о некой применяемой фене, например, «смоковница» — это «компьютер», «грех» — это «байт» и т.п., то на основании Библии можно будет шифровать и современные тексты.

Это были шифры замены, в которых буквы заменяются на другие. А ещё бывают перестановочные шифры, в которых буквы не заменяются, а перемешиваются между собой.

Немного о проекте

Мне, лично, давно была интересна тема шифрования информации, однако, каждый раз погрузившись в эту тему, я осознавал насколько это сложно и понял, что лучше начать с чего-то более простого. Я, лично, планирую написать некоторое количество статей на эту тему, в которых я покажу вам различные алгоритмы шифрования и их реализацию в Python, продемонстрирую и разберу свой проект, созданный в этом направлении. Итак, начнем.

Для начала, я бы хотел рассказать вам какие уже известные алгоритмы мы рассмотрим, в моих статьях. Список вам представлен ниже:

• Шифр Цезаря

• Шифр Виженера

• Шифр замены

• Омофонический шифр

• RSA шифрование

Теоретические сведения

Для начала мы изучим один из простейших шифров — шифр Цезаря, названный в честь римского императора. В этом шифре каждая буква текста заменяется на другую, которая находится на фиксированное число букв дальше в алфавите. Это фиксированное число букв называется ключом. Так, ключ 1 переводит букву латиницы C в букву D, а Z — по циклу в A. Если ключ равен 3, то буква C перейдет в F, а Z — в C. 

Примеры: используем шифр Цезаря с ключом на слове .

Ключ = 7, слово = computer

Шифр Цезаря прост, но, увы, ненадёжен (это взаимосвязанные вещи!): для английского алфавита — всего 25 вариантов шифровки, перебрать все возможные варианты легко даже без компьютера. Тем не менее, шифр Цезаря часто используют в качестве шага в других шифрах, таких, как шифр Виженера (о нём — в следующем пункте).

«Математизируем» шифр Цезаря. Обозначим незашифрованный текст буквой p, а pi — буква в тексте p, которая находится на позиции с номером i. Назовем секретный ключ буквой k, с — зашифрованный текст, а ci — буква в шифрованном тексте, которая находится на позиции i. Тогда вычислить каждую букву шифра можно по формуле: 

Привыкайте к такой формализации, она позволяет программировать алгоритм и выражает смысл шифра точно и сжато.

Если ключ k = 13 а изначальный текст p — «Be sure to drink your Ovaltine!», вот какой шифр мы получим:

Обратите внимание, O (первая буква в шифрованном тексте) смещена на 13 позиций от буквы B (первая буква в оригинальном тексте). То же самое с буквой r (вторая буква в шифровке) смещена на 13 букв от e (вторая буква в оригинале)

Третья буква в шифровке, f, смещена на 13 букв от s (третья в оригинале), тут мы ходим по кругу от z до a.

Шифр Цезаря с ключом 13 имеет специальное название ROT13. Он симметричный: применив его дважды, мы вернемся к изначальному тексту. Конечно, есть еще и ROT26, этот вообще супер-секьюрный, но только если вы нечётко выражаете свои мысли =). 

Шифр Виженера

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

Пример:

Если число букв в сообщении не делится на ключ нацело, мы в последнем применении ключа используем только его часть:

Чтобы найти значение для смещения, используем позиции каждой буквы нашего ключа bacon в алфавите (от a до z). Считаем с нуля, как истинные программисты. И каждую букву в оригинальном тексте смещаем на заданное число, как в шифре Цезаря, возвращаясь при надобности после Z в начало алфавита. Таким образом, M сместится на 1, первая e вообще не сместится, а вторая сместится на 2 позиции. Ниже вы видите изначальное сообщение, расписанный ключ и результат его применения.

Шифр Виженера, конечно, понадежнее, но если вы знаете длину ключа, его сломать довольно просто. Как её выявить? Если оригинальный текст достаточно длинный, чтобы некоторые слова встречались в нем несколько раз, то вы увидите некоторые повторения:

Также можно использовать полный перебор, но вариантов немало: 26^n – 1 где n — длина неизвестного ключа. Но обычно это немало. Правда, для компьютера это не проблема.

А теперь — математика шифра:

Пусть р – некоторый текст, k — ключевое слово, kj — j-я буква ключа, pi — буква под номером i в оригинальном тексте, ci — буква под номером i в шифровке. Тогда:

История и применение[править | править код]

Шифр Цезаря назван в честь Гая Юлия Цезаря, который использовал его с левым сдвигом на 3

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

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

Есть доказательства, что Юлий Цезарь использовал также и более сложные схемы.

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

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

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

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

Ключевые слова короче чем сообщение (например, «Complete Victory», используемое Конфедерацией во время гражданской войны в США), вводят циклический образец, который мог бы быть обнаружен с помощью улучшенной версии частотного анализа.

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

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

Например, если внутреннее колесо повернуть так, чтобы символу A внешнего диска соответствовал символ D внутреннего диска, то мы получим шифр со сдвигом 3 влево.

Полиалфавитные шифры

Шифр Виженера

Естественным развитием шифра Цезаря стал шифр Виженера. В отличие от моноалфавитных это уже полиалфавитный шифр. Шифр Виженера состоит из последовательности нескольких шифров Цезаря с различными значениями сдвига. Для зашифровывания может использоваться таблица алфавитов, называемая «tabula recta» или «квадрат (таблица) Виженера». На каждом этапе шифрования используются различные алфавиты, выбираемые в зависимости от буквы ключевого слова.

Для латиницы таблица Виженера может выглядеть вот так:

Для русского алфавита вот так:

Легко заметить, что строки этой таблицы — это ROT-шифры с последовательно увеличивающимся сдвигом.

Шифруют так: под строкой с исходным текстом во вторую строку циклически записывают ключевое слово до тех пор, пока не заполнится вся строка. У каждой буквы исходного текста снизу имеем свою букву ключа. Далее в таблице находим кодируемую букву текста в верхней строке, а букву кодового слова слева. На пересечении столбца с исходной буквой и строки с кодовой буквой будет находиться искомая шифрованная буква текста.

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

Ниже приведён пример настоящих шифров на базе шифра Виженера, использовавшихся польскими шпионами на территории СССР перед войной.

Шифр Гронсвельда

Это вариация шифра Виженера, где вместо ключевого слова применяется ключевое число, цифры которого показывают, какой из ROT-шифров применять (на сколько позиций сдвигать букву).

Взлом шифра

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

1. Взломщик знает (или предполагает), что использовался простой шифр подстановки, но не знает, что это — схема Цезаря.
2. Взломщик знает, что использовался шифр Цезаря, но не знает значение сдвига.

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

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

Во втором случае взлом шифра является даже более простым. Существует не так много вариантов значений сдвига (26 для английского языка), все они могут быть проверены методом грубой силы.
Один из способов сделать это — выписать отрывок зашифрованного текста в столбец всех возможных сдвигов — техника, иногда называемая как «завершение простого компонента».
Рассмотрим пример для зашифрованного текста «EXXEGOEXSRGI»; открытый текст немедленно опознается глазом в четвертой строке.

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

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

Для обычного текста на естественном языке, скорее всего, будет только один вариант декодирования. Но, если использовать очень короткие сообщения, то возможны случаи, когда возможны несколько вариантов расшифровки с различными сдвигами. Например зашифрованный текст «MPQY» может быть расшифрован как «aden» так и как «know» (предполагая, что открытый текст написан на английском языке). Точно также «ALIIP» можно расшифровать как «dolls» или как «wheel»; «AFCCP» как «jolly» или как «cheer» (см. также расстояние единственности).

Многократное шифрование никак не улучшает стойкость, так как применение шифров со сдвигом a и b эквивалентно применению шифра со сдвигом a + b. В математических терминах шифрование с различными ключами образует группу.

Source code

dCode retains ownership of the online ‘Caesar Cipher’ tool source code. Except explicit open source licence (indicated CC / Creative Commons / free), any ‘Caesar Cipher’ algorithm, applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or any ‘Caesar Cipher’ function (calculate, convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (Python, Java, PHP, C#, Javascript, Matlab, etc.) and no data download, script, copy-paste, or API access for ‘Caesar Cipher’ will be for free, same for offline use on PC, tablet, iPhone or Android ! dCode is free and online.