Шифр Цезаря

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

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

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

Новые понятия могут вас отпугнуть, но на самом деле все довольно банально:

открытый текст – это текст, который нужно зашифровать;

шифралфавит – буквы, которые подставляются за место открытого текста;

Текст превратился в «бессмысленный» набор букв «ТУМЕЗХ НГН ЖЗОГ»! Казалось бы, такой бессмысленный набор символов невозможно прочитать. Однако, это не совсем так.

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

В нашем случае количество возможных ключей настолько мало, что даже обычный человек, имея азбуку в руках за 10-20 минут сможет расшифровать данный шифртекст.

Математическая формулировка алгоритма цезаря выглядит настолько просто, что ее с легкостью поймет ученик 5 класса.

i + 3 = j где:

i – буква открытого алфавита;

j – буква шифралфавита;

Взлом шифра

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

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

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

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

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

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

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

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

Приложения

cp866: 

ansi:

Черный Рынок - название говорит само за себя. Оригинальная одежда и техника за половину стоимости.

Гражданская Оборона - самооборона от А до Я, обзоры травматического и огнестрельного оружия, самозащита в физическом и юридическом планах.

Дурман - наркотики и их медицинское употребление, увлекательные трип-репорты, виды веществ, их свойства и последствия употребления.