Математика и криптография. Тайны шифров и логическое мышление

Сразу видно, что тут что-то не то. Во-первых, можно обратить внимание на слово «ЕО» в первой строке (шестнадцатое слово). Такого слова нет в русском языке. Во-вторых, в тексте неоднократно встречается не до конца разгаданное слово «₋ЕО», причём на первом месте стоит один и тот же символ (это слово встречается четыре раза). Какие слова из трёх букв, подходящие под эту форму, есть в русском языке? Посмотрим: ГЕО (довольно редкое болгарское имя), ЛЕО (фамилия или имя из английского языка), НЕО (это из «Матрицы») и РЕО (город во Франции). Как видно, обычного русского слова нет ни одного, и можно предположить, что мы неверно расшифровали первые буквы. Впрочем, уже несуществующее слово «ЕО» позволяет отбросить гипотезу насчёт буквы «Е».

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

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

₋₋₋₋₋Н. _{−−−−−−−}, ₋НО ₋ Н_{−−− −−− −}О₋₋₋₋₋О₋₋, ₋ Н_{− −−}Н_{−−−− −}НОН Н₋₋₋Н. _{−−−− −}НО Н₋₋, НО _{− −}О_{−− −}О₋₋₋Н₋₋₋ НО₋О₋. ₋₋₋ Н₋ Н_{−−−−− −}О_{−−−−−−−}, _{−−−− −−}О₋НО_{− −}О₋₋Н₋₋О_{−−− −}О_{−−−−−−−}О _{−− −}О₋₋Н_{−− −−− −−−−−−−−−} Н_{−−− − −−−−−}НО₋. ₋О₋НО_{−− −−−}О_{−−− −− −− −}О_{−−−−−−−}. ₋ Н_{−−−−−− −−}Н_{− − −−−−− −−−−}Н₋₋ Н_{− −−−−−−−}, _{−−− −}О₋₋О ₋₋₋₋₋₋О₋₋Н_{− −−}О_{− −}О₋₋₋₋₋₋ Н₋₋, ₋НО_{−− −−−}НО _{−− −}О_{− −− −−−−−−}Н₋ (₋₋О₋₋ Н₋₋, ₋О₋₋ Н_{− −}О_{−−−−−− −−}О_{− −−−−−}Н₋). ₋НО ₋₋ Н_{−− −−}О₋₋О, Н_{−− −}НО ₋О_{−−−−−− − −−−−−−−−} Н_{−−−−−−−−}, ₋₋О₋О Н_{− −−− −−−−−− −−−}Н_{− − −−−}Н_{− −−−}О₋НО₋Н₋₋₋₋О.

Час от часу не легче. Но тут легко можно заметить одиннадцатое слово «₋НОН», причём первой буквой у него стоит та же, что и в слове «₋НО». В русском языке есть слово «ОНОН» (река в Сибири), но оно не подходит, поскольку букву «О» мы уже отгадали. То есть гипотеза о букве «Н» – некорректная. Попробуем следующую букву, и если она не подойдёт, то придется поставить под сомнение самую первую гипотезу о букве «О». Следующая по частоте буква – это буква «Т». Подставим:

₋₋₋₋₋Т. _{−−−−−−−}, ₋ТО ₋ Т_{−−− −−− −}О₋₋₋₋₋О₋₋, ₋ Т_{− −−}Т_{−−−− −}ТОТ Т₋₋₋Т. _{−−−− −}ТО Т₋₋, ТО _{− −}О_{−− −}О₋₋₋Т₋₋₋ ТО₋О₋. ₋₋₋ Т₋ Т_{−−−−− −}О_{−−−−−−−}, _{−−−− −−}О₋ТО_{− −}О₋₋Т₋₋О_{−−− −}О_{−−−−−−−}О _{−− −}О₋₋Т_{−− −−− −−−−−−−−−} Т_{−−− − −−−−−}ТО₋. ₋О₋ТО_{−− −−−}О_{−−− −− −− −}О_{−−−−−−−}. ₋ Т_{−−−−−− −−}Т_{− − −−−−− −−−−}Т₋₋ Т_{− −−−−−−−}, _{−−− −}О₋₋О ₋₋₋₋₋₋О₋₋Т_{− −−}О_{− −}О₋₋₋₋₋₋ Т₋₋, ₋ТО_{−− −−−}ТО _{−− −}О_{− −− −−−−−−}Т₋ (₋₋О₋₋ Т₋₋, ₋О₋₋ Т_{− −}О_{−−−−−− −−}О_{− −−−−−}Т₋). ₋ТО ₋₋ Т_{−− −−}О₋₋О, Т_{−− −}ТО ₋О_{−−−−−− − −−−−−−−−} Т_{−−−−−−−−}, ₋₋О₋О Т_{− −−− −−−−−− −−−}Т_{− − −−−}Т_{− −−−}О₋ТО₋Т₋₋₋₋О.

Вновь обратим внимание на слова «₋ТО» и «₋ТОТ», у которых первая буква одинаковая. Тут вариант один: первая буква – это «Э». Попробуем подставить:

₋₋₋₋₋Т. _{−−−−−−−}, ₋ТО ₋ Т_{−−− −−− −}О₋₋₋₋₋О₋₋, ₋ Т_{− −−}Т₋₋₋₋ ЭТОТ Т₋₋₋Т. ₋₋₋₋ ЭТО Т₋₋, ТО _{− −}О_{−− −}О₋₋₋Т₋₋₋ ТО₋О₋. ₋₋₋ Т₋ Т_{−−−−− −}О_{−−−−−−−}, _{−−−− −−}О₋ТО_{− −}О₋₋Т₋₋О_{−−− −}О_{−−−−−−−}О _{−− −}О₋₋Т_{−− −−− −−−−−−−−−} Т_{−−− − −−−−−}ТО₋. ₋ОЭТО_{−− −−−}О_{−−− −− −− −}О_{−−−−−−−}. ₋ Т_{−−−−−− −−}Т_{− − −−−−− −−−−}Т₋₋ Т_{− −−−−−−−}, _{−−− −}О₋₋О ₋₋₋₋₋₋О₋₋Т_{− −−}О_{− −}О₋₋₋₋₋₋ Т₋₋, ₋ТО_{−− −−−}ТО _{−− −}О_{− −− −−−−−−}Т₋ (₋₋О₋₋ Т₋₋, ₋О₋₋ Т_{− −}О_{−−−−−− −−}О_{− −−−−−}Т₋). ЭТО ₋₋ Т_{−− −−}О₋₋О, Т_{−− −}ТО ₋О_{−−−−−− − −−−−−−−−} Т_{−−−−−−−−}, ₋₋О₋О Т_{− −−− −−−−−− −−−}Т_{− − −−−}Т_{− −−−}О₋ТО₋Т₋₋₋₋О.

Пока всё нормально. Никаких противоречий на первый взгляд нет. Более того: в тексте встречается последовательность «₋ОЭТО₋₋». В этом слове из семи букв открыты четыре, так что можно попробовать догадаться, какое это слово. Поиск по словарю даёт только одно слово: «ПОЭТОМУ». Более того, перед «ПОЭТОМУ» часто пишется запятая, как и в этом случае. Получается, что мы сейчас смогли выдвинуть вполне правдоподобную гипотезу относительно ещё трёх скрытых символов. Пора составить новую таблицу и заполнить её:

Подставим-ка все известные на текущий момент символы в шифрограмму. Вот что получится:

П₋₋₋₋Т. _{−−−−−−−}, ₋ТО У Т_{−−− −−−} ПО₋У₋₋₋О₋₋, ₋ Т_{− −−}Т₋₋₋₋ ЭТОТ Т₋₋₋Т. ₋₋₋₋ ЭТО Т₋₋, ТО ₋ МО₋У ₋О₋₋₋Т₋₋₋ ТО₋О₋. ₋₋₋ Т₋ Т₋П₋₋₋ ПО₋₋М₋₋₋₋, ₋₋₋₋ П₋О₋ТО₋ ПО₋₋Т₋₋О_{−−− −}О_{−−−−−−−}О _{−− −}О₋₋Т_{−− −−− −−−−−−−−−} Т_{−−− − −−−−−}ТО₋. ПОЭТОМУ ₋₋₋О_{−−− −}М ₋₋ ПО₋₋₋У₋₋₋. ₋ Т_{−−−−−− −−}Т_{− − −−−−− −−−−}Т₋₋ Т₋ У₋₋₋₋₋₋, ₋₋₋ МО₋₋О ₋₋₋₋₋₋О₋₋Т_{− −−}О₋ ПО₋₋₋₋₋₋ Т₋₋, ₋ТО_{−− −−−}ТО ₋₋ МО_{− −− −−−−−−}Т₋ (₋₋ОМ₋ Т₋₋, ₋ОМУ Т_{− −}О_{−−−−−− −−}О_{− −−−−−}Т₋). ЭТО ₋₋ Т_{−− −−}О₋₋О, Т_{−− −}ТО ₋О_{−−−−−− − −−}П₋₋₋₋₋ Т₋₋П₋₋₋₋М, ₋₋О₋О Т_{− −−− −}У_{−−−− −−−}Т_{− −} УМ₋Т_{− −−}МО₋ТО₋Т₋₋₋₋О.

Сразу бросается в глаза первое слово. Ты ещё не догадываешься, что это за слово такое? Тогда подумай, какое слово из шести букв обычно ставят в начале письма, причём начинается оно на «П», а заканчивается на «Т»: «П₋₋₋₋Т». Ну, конечно же, это слово «ПРИВЕТ». Ура, у нас есть ещё четыре буквы. Давай внесём их в таблицу расшифровок:

Вот, что получается, если теперь подставить все эти буквы в шифрограмму:

ПРИВЕТ. ₋₋₋Е₋₋₋, ₋ТО У ТЕ₋₋ В₋₋ ПО₋У₋И₋О₋₋, И Т_{− −}ИТ₋Е₋₋ ЭТОТ ТЕ₋₋Т. Е₋₋И ЭТО Т₋₋, ТО ₋ МО₋У ₋ОР₋ИТ₋₋₋ ТО₋О₋. ₋₋₋ Т₋ ТЕПЕР₋ ПО₋ИМ₋Е₋₋, ₋И₋Р ПРО₋ТО₋ ПО₋₋Т₋₋ОВ₋И ₋ОВЕР₋Е₋₋О ₋Е ₋О₋ИТ_{−− −−− −−}Р₋В₋₋И₋ Т₋₋₋ И ₋Е₋РЕТОВ. ПОЭТОМУ ₋И₋О₋₋₋ ИМ ₋Е ПО₋₋₋У₋₋₋. В ТЕ₋Е₋ИЕ ₋ЕТ₋ И ₋₋₋И_{− −−−−}ТИ₋ Т₋ У₋₋₋Е₋₋, ₋₋₋ МО₋₋О ₋₋₋И₋РОВ₋Т_{− −}ВОИ ПО₋₋₋₋И₋ Т₋₋, ₋ТО_{−− −}И₋ТО ₋Е МО₋ И₋ Р₋₋₋Р₋Т₋ (₋РОМЕ ТЕ₋, ₋ОМУ Т_{− −}ОВЕРИ_{−− −}ВОИ ₋Е₋РЕТ₋). ЭТО ₋Е Т_{−− −−}О₋₋О, Т_{−− −}ТО ₋О₋ЕРИ₋₋ И ₋₋П₋₋И₋₋ ТЕРПЕ₋ИЕМ, ₋₋ОРО Т₋ В_{−− −}У₋Е_{−− −−−}Т₋ И УМЕТ_{− −−}МО₋ТО₋ТЕ₋₋₋О.

Что же, неплохо. Тут уже видно несколько слов, кроме тех, которые мы разгадали. Самые очевидные из них – «ТЕПЕР₋» (даёт «Ь»), «₋РОМЕ» (даёт «К») и «ТЕРПЕ₋ИЕМ» (даёт «Н»). Подставим новые буквы в шифрограмму и получим:

ПРИВЕТ. Н₋₋Е₋₋Ь, ₋ТО У ТЕ₋₋ В₋₋ ПО₋У₋И₋О₋Ь, И Т_{− −}ИТ₋Е₋Ь ЭТОТ ТЕК₋Т. Е₋₋И ЭТО Т₋К, ТО ₋ МО₋У ₋ОР₋ИТЬ₋₋ ТО₋О₋. К₋К Т₋ ТЕПЕРЬ ПОНИМ₋Е₋Ь, ₋И₋Р ПРО₋ТО₋ ПО₋₋Т₋НОВКИ ₋ОВЕР₋ЕННО НЕ ₋О₋ИТ_{−− −−− −}КР₋В₋НИ₋ Т₋₋Н И ₋ЕКРЕТОВ. ПОЭТОМУ НИКО₋₋₋ ИМ НЕ ПО₋Ь₋У₋₋₋. В ТЕ₋ЕНИЕ ₋ЕТ₋ И Н₋₋И_{− −−}Н₋ТИ₋ Т₋ У₋Н₋Е₋Ь, К₋К МО₋НО ₋₋₋И₋РОВ₋ТЬ ₋ВОИ ПО₋₋₋НИ₋ Т₋К, ₋ТО₋₋ НИКТО НЕ МО₋ И₋ Р₋₋КР₋ТЬ (КРОМЕ ТЕ₋, КОМУ Т_{− −}ОВЕРИ₋Ь ₋ВОИ ₋ЕКРЕТ₋). ЭТО НЕ Т₋К ₋₋О₋НО, Т₋К ₋ТО ₋О₋ЕРИ₋Ь И ₋₋П₋₋И₋Ь ТЕРПЕНИЕМ, ₋КОРО Т₋ В_{−− −}У₋Е₋Ь ₋Н₋ТЬ И УМЕТЬ ₋₋МО₋ТО₋ТЕ₋ЬНО.

Собственно, дальше ты сможешь всё доделать самостоятельно. Сообщение стало настолько прозрачным, что ни одна буква больше не утаится. Доделай то, что мы начали, до конца, и ты сможешь прочитать это тайное послание.

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

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

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

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

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

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

Неделя 2. Шифр многоалфавитной замены

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

Во-первых, давай считать пробел символом. Да, с математической точки зрения пробел – это такой же символ, как и любой другой. Я специально использую слово «символ», а не «буква», чтобы не путать. Итак, все буквы, цифры, пунктуационные знаки и даже пробел являются символами. Но главное – это понять, что пробел – не отсутствие символа, а отдельный символ. В предложении «ЭТА ФРАЗА СОДЕРЖИТ 3 °СИМВОЛОВ» действительно содержится 30 символов: 24 буквы, 2 цифры и 4 пробела.

Во-вторых, давай в дальнейшем для шифрования использовать только заглавные буквы русского алфавита и пробел, причём будем считать пары букв «Е» и «Ё», а также «Ъ» и «Ь» неразличимыми. Теперь в наших текстах и шифрограммах символ «Е» будет обозначать как букву «Е», так и букву «Ё», а символ «Ъ» будет обозначать буквы «Ъ» «Ь». Таким образом, весь алфавит теперь состоит из следующих символов:

Пробел А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Э Ю Я

Примечательность этого алфавита в том, что в нём содержится ровно 32 символа.

С каждым из этих символов мы сопоставим число от 0 до 31, которое назовём кодом. То есть «пробел» будет иметь код 0, буква «А» – код 1 и так далее – до буквы «Я», которой мы присвоим код 31.

После этого надо научиться складывать и вычитать особым образом (математики называют такие операции сложением и вычитанием с вычетами). Итак, у нас есть только тридцать два числа – от 0 до 31. Мы хотим складывать и вычитать при помощи этих чисел, и никакие другие числа нам использовать нельзя. Очень просто, например, сложить 5 и 8, поскольку получится 13. Но как быть, если нам надо сложить, скажем, 23 и 17? Обычная арифметика подсказывает, что 23 + 17 = 40, но у нас нет чисел, которые больше 31. Как быть? Всё просто. Если полученный результат больше 31, надо вычесть из него общее количество чисел, то есть 32. Другими словами, по правилам нашей новой арифметики (немного странной на первый взгляд) получается, что 23 + 17 = 40–32 = 8.

То же самое с вычитанием. Легко вычесть из 15, скажем, 12, поскольку получится 3. А как вычесть из меньшего числа большее, например, из 10–27? Тут тоже просто. Если из меньшего числа требуется вычесть большее, то сначала к меньшему надо прибавить 32. Таким образом: 10–27 = 10 + 32–27 = 15.

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

Мы узнали об этой новой арифметике для того, чтобы использовать её правило сложения для шифрования, а правило вычитания – для расшифровки. Ведь у каждой буквы есть числовой код от 0 до 31. При таком шифровании буквы открытого текста складываются со специально выбранными буквами (эти выбранные буквы называются «ключом» или «паролем»). Расшифровывают сообщение, вычитая из букв зашифрованного текста буквы ключа.

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

Давай попробуем зашифровать слово «БЕСПОРЯДОК» при помощи ключа «С». Начнём с первой буквы, «Б». Её код – 2, а код буквы «С» – 18. Если сложить буквы Б и С, то есть 2 и 18, то получится 20, а это буква «У». Далее, буква «Е», её код – 6. Опять складываем: 6 + 18 = 24, и это буква Ч. Продолжая так дальше, мы получаем слово «УЧГБАВРХАЭ». Расшифровывать это слово нужно при помощи вычитания. Берём букву «У» и её код 20, вычитаем из него код буквы «С»: 20–18 = 2, и получается буква «Б». Ну и так далее…

Итак, теперь мы знаем, какие математические правила используются для шифрования при помощи одноалфавитной замены. Тогда что же такое многоалфавитная замена? При одноалфавитной замене каждая буква открытого текста складывается с одной и той же буквой ключа. А при многоалфавитной замене символы ключа циклически изменяются. Это значит, что первая буква открытого текста шифруется первой буквой ключа, вторая буква – второй буквой, третья – третьей и так далее до, например, шестой буквы, которая снова шифруется первой буквой ключа, и цикл повторяется.

Как же выбираются эти буквы для шифрования? Как я уже сказал, для этого используется ключевое слово, ключ или пароль. Его длина определяет длину цикла многоалфавитной замены, то есть количество используемых алфавитов. А буквы ключа применяются для шифрования при помощи описанных выше правил арифметики вычетов. Давай рассмотрим пример. Пусть в качестве ключа используется слово «КЛЮЧ», тогда первая буква открытого текста шифруется через букву «К», вторая – через букву «Л» и так далее, а пятая буква открытого текста опять шифруется при помощи буквы «К».

Например:

Вот и получился зашифрованный текст:

«ЪЭЖНЩРЖЧТМАКЫМЮВКЫМЛП».

Уверен, что его не сможет разгадать никто из твоих друзей. Никто даже и браться за такое не будет.

Есть и более легкий метод шифрования этим способом. Для него требуется одна таблица. Она на следующем развороте.

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

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

Теперь давай научимся расшифровывать тексты, записанные шифрами многоалфавитной замены. Например, у тебя оказалось зашифрованное послание и ты знаешь, что оно зашифровано именно таким шифром. Как подступиться к расшифровке? Вот простейший метод:

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

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

Чтобы узнать длину ключа, используются два метода. Один из них очень трудоёмкий и требует множества вычислений (в наше время их можно поручить компьютеру, а раньше ими обычно занималась целая комната специально обученных сотрудников со счётами или счётными машинками). Но этот метод гарантированно определяет длину ключа. Ты можешь прочитать о нем в специальной литературе или справочниках – он называется «метод индекса совпадений».

А вот второй метод – именно что хитроумный, но не всегда работает. Его мы и изучим. Он называется «метод Фридриха Касиски^[1]». Идея заключается в том, что в обычном языке, на котором говорят люди, очень часто повторяются некоторые группы символов. Это коротенькие словечки или даже буквосочетания вроде многочисленных «ОРО» и «ОЛО» в русском языке. Грамотный шифровальщик избегает использования коротких словечек (об этом мы уже рассуждали на прошлой неделе), но вот с частыми буквосочетаниями это сделать сложно. Так что надо искать в шифрограмме такие повторяющиеся буквосочетания.

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