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

 

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

Во‑первых, давай считать пробел символом. Да, с математической точки зрения пробел – это такой же символ, как и любой другой. Я специально использую слово «символ», а не «буква», чтобы не путать. Итак, все буквы, цифры, пунктуационные знаки и даже пробел являются символами. Но главное – это понять, что пробел – не отсутствие символа, а отдельный символ. В предложении «ЭТА ФРАЗА СОДЕРЖИТ 3 °CИМВОЛОВ» действительно содержится 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]. Идея заключается в том, что в обычном языке, на котором говорят люди, очень часто повторяются некоторые группы символов. Это коротенькие словечки или даже буквосочетания вроде многочисленных «ОРО» и «ОЛО» в русском языке. Грамотный шифровальщик избегает использования коротких словечек (об этом мы уже рассуждали на прошлой неделе), но вот с частыми буквосочетаниями это сделать сложно. Так что надо искать в шифрограмме такие повторяющиеся буквосочетания.

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

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

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

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

Давай потренируемся во всем этом на практике. Представь себе, что ты видишь такое послание:

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

Если сделать здесь частотный анализ, то получится вот такая таблица:

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

Что делают настоящие криптоаналитики для анализа подобной ситуации? Они строят графики. Вот два графика (они называются «гистограммами»):

Гистограмма частот символов в шифрограмме

Гистограмма частот букв русского языка

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

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

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

Быстрый просмотр шифрограммы показывает, что есть одно семисимвольное сочетание «ЗЗЫХШЮХ», которое встречается в шифрограмме дважды. При этом повторяющихся восьмисимвольных сочетаний нет. (Надо отметить, что чем больше в повторяющихся сочетаниях символов, тем лучше). Проверим, на каких позициях стоят эти буквосочетания. Первое стоит на позиции 49, а второе – на 509. Разница: 509 – 49 = 460. Запомним.

Больше семисимвольных сочетаний нет, поэтому посмотрим на шестисимвольные. Есть четыре таких буквосочетания, но первые два из них – это префикс и суффикс семисимвольного сочетания, рассмотренного ранее, поэтому учитывать их не будем. Другие – это «ЛЕПФВТ» и «ТЩРГГП». Первое из этих двух буквосочетаний встречается на позициях 225 и 421. Их разница: 421–225 = 196. Второе стоит на позициях 294 и 330, и разница составляет 330–294 = 36.

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

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

ТИЪР

УЫМТ

УНРШ

АТПЮ

АКЧЧ

ЙАЙТ

ГЗУШ

МНОЧ

ЖАЧЗ

СЦСЮ

ЙЗЗЫ

ХШЮХ

АФЭБ

ДЦПЯ

…

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

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

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

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

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

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

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

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

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

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

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

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

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