Математика и криптография

Итак, у нас есть три числа, три разницы: 460, 196 и 36. Рассмотрим наибольший общий делитель этих чисел. Он равен 4. В принципе, на этом можно остановиться, поскольку мы только что нашли длину ключа. Теоретически, ключ может быть длиной в 2 символа (поскольку 4 делится на 2), но можно предположить, что никто не будет кодировать сообщение при помощи такого короткого ключа. Если бы у нас в качестве наибольшего общего делителя получилось число 8, то нам пришлось бы проверить ещё и пятисимвольные сочетания, а потом и все остальные, чтобы убедиться, что длина ключа равна именно 8, а не 4.

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

ТИЪР

УЫМТ

УНРШ

АТПЮ

АКЧЧ

ЙАЙТ

ГЗУШ

МНОЧ

ЖАЧЗ

СЦСЮ

ЙЗЗЫ

ХШЮХ

АФЭБ

ДЦПЯ

…

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

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

А теперь, если ты внимательно изучишь таблицу, приведённую ранее, то увидишь, что у пробела — код 0. Это значит, что при сложении с ним символ не меняется. Получается, что самая часто встречающаяся буква в каждом столбце и есть буква ключа. Вот это да!

Давай подсчитаем. Вот первый столбец:

«ТУУААЙГМЖСЙХАДХУАЖУЖУШАЗППЕАТПЫБЫГСШГАПУОАХЙДПБАЭЛМ ОУОРПЛЙРМСШБУАОВПОЙЛЩПБАОЭЕБЯЩПНГОПУАЖИБУЛАЖОЖЕЙАВППФЗЙЭ ЖЗА ЙЕУБНБПАЖЫПРВХБАВОБВЯАИЭНЕБ».

Можно заметить, что чаще всего здесь встречается буква «А». Итак, первая буква ключа найдена. Я рекомендую тебе тщательно подсчитать в каждом столбце количество букв и определить наиболее часто встречающуюся, после чего понять ключ.

Если у тебя все получилось, то нашелся ключ — «АЗОТ» (это газ). И теперь можно легко расшифровать секретное послание. Как я уже писал, надо из шифрограммы вычесть ключ по модулю 32. Вот так:

Если всё сделано правильно, то проявится открытое сообщение: «САЛЮТУЮ ТЕБЕ. КАК ВИДИШЬ, В ДЕЛЕ ДЕШИФРОВКИ ШИФРОВ МНОГОАЛФАВИТНОЙ ЗАМЕНЫ ТАКЖЕ НЕТ НИЧЕГО СЛОЖНОГО. НЕОБХОДИМО ПРОСТО ОЧЕНЬ ТЩАТЕЛЬНО ВСЁ РАССЧИТЫВАТЬ, ВЫПОЛНЯТЬ МНОГО АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ И БЫТЬ КРАЙНЕ ВНИМАТЕЛЬНЫМ. ПОЭТОМУ, КАК И В ПРОШЛЫЙ РАЗ, Я ХОЧУ ЗАЯВИТЬ О ПОЛНОЙ БЕСПОЛЕЗНОСТИ ТАКИХ ШИФРОВ. КАКОЙ БЫ НИ БЫЛА ДЛИНА КЛЮЧА, ШИФРОГРАММА В КОНЕЧНОМ ИТОГЕ БУДЕТ ВЗЛОМАНА ТЕМ, КОМУ ИНТЕРЕСНО ЕЁ СОДЕРЖИМОЕ. НО БЛАГОДАРЯ ЭТОМУ УПРАЖНЕНИЮ ТЫ УЖЕ МОЖЕШЬ ПОНЯТЬ И ПОДУМАТЬ НА ТЕМУ, КАК МОЖНО ИЗМЕНИТЬ ЭТОТ СПОСОБ ШИФРОВАНИЯ, ЧТОБЫ ОН СТАЛ АБСОЛЮТНО НЕВЗЛАМЫВАЕМЫМ. ДЕРЗАЙ».

Что ж, ещё пара моментов:

1. Не всегда пробел будет самым частым символом в столбце. Если не удалось обнаружить ключ, то можно попробовать либо вычитать букву «О», либо попытаться использовать в качестве пробела второй по частоте символ. Ключ часто может быть каким-то словом.

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

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

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

Неделя 3. Стеганография и код Фрэнсиса Бэкона

Представь, что ты получаешь вот такое письмо: