Введение

Жил да был в Древнем Риме наш герой, Гай Юлий Цезарь – да, да, тот самый, который выиграл в гражданской войне и стал императором, мог делать сразу несколько дел одновременно и сражался с Астериксом и Обеликсом. Что, что? Да, ещё салат есть такой (к которому наш Цезарь, между прочим, не имеет ни малейшего отношения). В те времена Цезарь наделал много шуму, и не был бы он так успешен, если бы не его харизма и необычайно острый ум – чего стоят одни его цитаты. Вот, поглядите.

Жзапэг, кщаыьг, жёшьыаг.

— Ъчб Хгаб Ньячзу

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

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

И с тех же древних времён люди задумались, а как бы эту информацию передать так, чтобы "свои" смогли её прочесть и купить пару биткойнов по выгодной цене, а "чужие", даже если перехватят гонца, увидят вместо сообщения непонятную мешанину и, покрутив пальцем у виска, отпустят гонца вместе с этой ерундой (конечно, гонцу категорически нельзя сообщать, что содержится в сообщении и как взломать шифр). Удобно, согласитесь? Вот так и возникли криптография и криптоанализ – науки о том, как скрыть то, что открыто, и открыть то, что скрыто.

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

Суть метода

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

Поздравляю, вы только что зашифровали свой текст! Теперь ваша информация будет в безопасности (какое-то время). Полученное зашифрованное сообщение принято называть шифртекстом, а то, с помощью чего был зашифрован исходный текст – ключом шифрования. Для метода Цезаря, зная ключ, можно с лёгкостью расшифровать сообщение (впрочем, не зная его, расшифровать тоже не составит труда, что мы покажем далее). Такой вид шифрования называется симметричным, поскольку и при шифровании, и при дешифровании используется один и тот же ключ. Попробуйте выбрать другое значения ключа и посмотрите, что получится.

А теперь сотрите всё, что вы там зашифровали, и введите в строку последовательно все буквы русского (английского) алфавита по порядку и выберите значение ключа. Только не говорите, что не помните алфавит на память. Ладно, так и быть, можете нажать на ссылки, и алфавиты вставятся сами ( русский, английский, кликабельно).

Обратите внимание, что шифртекст в точности совпадает с исходным текстом, но с одной особенностью – он как будто бы сдвинут влево на некоторое количество символов, а сдвинутые начальные символы переместились в конец шифртекста. Кажется, вы начинаете понимать, не так ли? Именно в этом и заключается суть метода шифрования Цезаря – каждый символ в исходном тексте заменяется символом, находящимся на некотором постоянном смещении от него в алфавите, а это смещение и есть ключ.

Сейчас будет немного математики, но не пугайтесь, она несложная, просто с помощью неё гораздо удобнее описать процесс шифрования/дешифрования (картинки честно украдены с Википедии):

где x – символ исходного сообщения, y – символ шифртекста, n – число букв в алфавите, k – ключ шифрования, mod – операция взятия остатка от деления. Как видите, всё очень просто.

Взлом

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

Но вот беда – решив сократить дорогу, гонец забредает в переулок, где его уже дожидается банда Зелёных Криптоманов (даже не спрашивайте). Они отбирают у гонца записку, видят там какую-то ерунду и начинают его допрашивать, но вскоре понимают, что он ничего не знает. И тут вожак банды соображает, что это не просто бессмысленный набор букв, а зашифрованное послание, и начинает вспоминать, как когда-то давно, ещё до того как его выгнали из института, на лекциях по криптозащите он слышал про какой-то метод...

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

Под "простым перебором" здесь имеется ввиду банальный перебор всех возможных ключей шифрования. Например, для английского языка это 25 ключей, для русского – 32, и т.д. (за пояснениями идите в спойлер в прошлом разделе). Причём перебирать все варианты необязательно, ведь как только шифртекст после очередного сдвига предстанет в осмысленном виде, то ключ был найден.

Пример: Бандиты ловят гонца, отбирают у него записку с шифртекстом "Юячруб, ычя!", чешут в затылке, пока кто-то не восклицает "Эврика! Да ведь это же шифр Цезаря!" и приступают к дешифрованию, последовательно сдвигая символы на 1 позицию влево:

1. Эюцпта, ъцю!
2. Ьэхося, щхэ!
3. Ыьфнрю, шфь!
4. Ъыумпэ, чуы!
5. Щътлоь, цтъ!
6. Шщскны, хсщ!
7. Чшрймъ, фрш!
8. Цчпилщ, упч!
9. Хцозкш, тоц!
10. Фхнжйч, снх!
11. Уфмёиц, рмф!
12. Тулезх, плу!
13. Сткджф, окт!
14. Рсйгёу, нйс!
15. Привет, мир!

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

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

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

Итак, мы добрались до самого интересного, а именно, частотного анализа. Тема эта очень обширная, и целиком рассматривать её здесь мы не будем, лишь ограничимся её применением для взлома шифра Цезаря. Наверняка вы замечали, что некоторые буквы в нашем алфавите повторяются в словах чаще других – например, гласные "а", "о", "и", "е" встречаются гораздо чаще, чем такая экзотика, как "ъ", "ц", "э". Про бедную-несчастную букву "ё" я вообще молчу, её старательно пытаются вывести из состава русского алфавита!

Естественно, невозможно точно посчитать частоту появления той или иной буквы, ведь язык постоянно меняется, появляются новые слова, поэтому обычно берут средние значения, анализируя тексты очень большого объёма (например, "Войну и мир", "Большую советскую энциклопедию", "Сборник анекдотов" за 1968 год и т.д.). Ниже в гистограмме приведена статистика частот появления букв русского языка.

Числа по вертикальной оси означают вероятность появления того или иного символа. То есть, если вы закроете глаза и ткнёте наугад в какую-нибудь букву в тексте, то именно с этой вероятностью вы попадёте именно в неё. Вы спросите, да причём здесь вообще какие-то вероятности? А очень даже причём – дело в том, что в сдвинутом алфавите вероятности появления букв... также сдвигаются! Причём на то же самое значение ключа. А из этого, как мы покажем дальше, для больших текстов можно с большой точностью определить ключ, просто посмотрев на распределение вероятностей, не перебирая все возможные значения ключей.

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

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

А теперь, внимание, самое интересное - как по этой гистограмме определить значение ключа? Да очень просто - продолжайте сдвигать её до тех пор, пока частота самой часто встречающейся буквы вашего текста не будет примерно равна частоте самой часто встречающейся буквы алфавита, на котором написано сообщение, а величина ключа будет находиться как разность позиций этих букв. Для данного примера, между "ё" и "я" расстояние равно 7, значит ключ будет равен 7.

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

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

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

Шифртексты

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