4.4.2. Криптоанализ поточного шифра простой замены

Рассмотрим сначала простейший случай – однобуквенной замены.

Любой метод вскрытия шифра простой однобуквенной замены основан на том обстоятельстве, что с точностью до переобозначений частотные характеристики т-грамм шифртекста и открытого текста одинаковы. При этом существенно используются априорные частотные характеристики предпо­лагаемого открытого текста, получаемые с учетом "характера переписки". Такие характери­стики являются более "рельефными" для литературных тек­стов и менее "рельефными" для формализованных электрон­ных текстов. Чем менее рельефно распределение знаков тек­ста, тем сложнее задача вскрытия шифра простой замены. Для открытых текстов с "почти равномерным" распределени­ем знаков эта задача становится практически не решаемой. Это следует учитывать и не питать иллюзий о простоте вскрытия простой замены, о которой часто упоминается в популярных книгах по защите информации. Методы "рандо­мизации" или "сжатия" открытых текстов, например, с ис­пользованием компьютерных архиваторов значительно ус­ложняют задачу вскрытия шифра простой замены.

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

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

Алгоритм 1

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

2. Выявление шифробозначений, заменяющих гласные и согласные буквы.

3. Выдвижение гипотез о значениях шифробозначений и их проверка. Восстановление истинного значения шифробо­значений.

Сделаем ряд замечаний и уточнений. Если длина текста достаточно велика, то найденные на этапе I частоты окажутся близкими к табулированным значе­ниям частот знаков (соответственно – биграмм или три­грамм). Проведенная на этом этапе работа служит основанием для выдвижения гипотез о значениях шифрвеличин, соответ­ствующих данным шифробозначениям. При этом учитывает­ся, что каждая буква имеет группу предпочтительных связей, которые составляют ее наиболее харак­терную особенность. Как правило, такие гипотезы подтвер­ждаются не полностью. Хорошим критерием при этом явля­ется "читаемость" восстанавливаемого открытого текста. Вы­деление шифробозначений, отвечающих гласным и соглас­ным, основано на характерных свойствах этих букв. Добавим к ним следующие соображе­ния (относимые к большинству европейских языков). Если шифробозначение часто встречается, равномерно располага­ется по шифртексту, в отдельных местах чередуется через 1, 2 или 3 знака, сочетается со средними и редкими (по частоте) шифробозначениями, то это дает основания полагать, что такое шифробозначение скрывает гласную букву. Удвоение гласных в открытом тексте происходит реже, чем согласных. Если некоторое шифробозначение признано гласной, то буква, часто сочетающаяся с ней, скорее всего согласная. В от­крытом тексте чрезвычайно редко встречаются три и более подряд идущие гласные. Четыре и более подряд идущие со­гласные также редки. Важно учитывать также процентное со­отношение чисел гласных и согласных в открытом тексте.

При проверке гипотез о значениях шифробозначений по­лезен поиск в шифртексте слов с характерной структурой, которые часто встречаются в открытом тексте. Для русского языка – это, например, слова сколько, которое, что и т. п. Для английского языка – слова every, that, look, the и т.п. Такие слова выделяются в шифртексте посредством интерва­лов между повторяющимися частыми буквами, характерными сочетаниями гласных и согласных.

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

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

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

Мерой близости служит следующая "целевая функция" f(t), связывающая матрицы (t) и В:

(1)

Будем исходить из того естественного предположения, что если у – данная криптограмма и D_k – правило расшиф­рования на ключе k данного шифра простой замены, то для истинного ключа k_u значение

должно быть минимальным.

Идея основного шага алгоритма состоит в том, чтобы ис­ходя из некоторого первичного "приближения" k для ключа k_u, основанного, например, на диаграмме частот букв, не­много его изменять неким "разумным" способом, уменьшая значение целевой функции f(t).

Приведем теперь формальное описание алгоритма.

Алгоритм 2

1. Построить начальный вариант ключа k на основе сравне­ния частот знаков криптограммы и открытого текста.

2. Положить v = f(D_k(у)).

3. Положить k'= k.

4. Поменять местами в нижней строке подстановки k' неко­торую пару букв, скажем а и .

5. Положить v'=f(D_k(y)).

6. Если v' < v, то положить k = k', v'=v и перейти к 4.

7. Перейти к шагу 3.

Алгоритм заканчивается, когда условие v'<v не выпол­няется в течение некоторого числа итераций, например 100.

Переход на шаге 4 от k к k', связанный с транспозицией пары символов, имеет под собой следующее основание. На шаге 5 вычисляется величина

где ¹(t) – матрица, полученная из матрицы (t) путем перестановки в ней столбцов с номерами а и , а также строк с теми же номерами.

В силу отмеченного свойства на шаге 5 алгоритма не нужно проводить трудоемкую операцию вычисления матри­цы биграмм _ij(D_k(y)) непосредственно по "расшифрован­но­му" тексту D_k(y). Достаточно вычислить лишь матрицу (D_k(у)), а на следующих шагах алгоритма производить в ней одноименные перестановки строк и столбцов.

Выбор транспозиции (a, ) на шаге 4 можно произво­дить, например, следующим естественным образом. Пусть s=(s₁,s₂,...,s_n) – вектор, образованный буквами крипто­граммы, упорядоченными по убыванию частот. Тогда после­довательность транспозиций можно выбрать такой:

(s₁,s₂), (s₂,s₃),…,(s_n-2,s_n-1), (s_n-1,s_n),

(s₁,s₃), (s₂,s₄),…,(s_n-2,s_n),

………………………………

(s₁,s_n).

Алгоритм 2 является достаточно эффективным.

Отметим некоторые особенности вскрытия равнозначных и разнозначных шифров простой замены.

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

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

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

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

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