11. Вопросы криптоанализа простейших шифров замены.

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

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

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

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

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

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

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

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

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

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

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