Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
I N E T О А S R - -
В К V D L W С M X F
Y G P Z U H Q J /
При зашифровании открытый текст записывается со знаком пробела между словами. Точка, встретившаяся в тексте, считается отдельным словом. После этого производится замена шифрвеличин на шифробозначения согласно таблице, при этом цифровые данные не изменяются.
§ 5.2. Криптоанализ поточного шифра простой замены
Рассмотрим сначала простейший случай — однобуквенной замены.
105
Г лава 5
Любой метод вскрытия шифра простой однобуквенной замены основан на том обстоятельстве, что с точностью до переобозначений частотные характеристики т -грамм шифр-текста и открытого текста одинаковы. При этом существенно используются априорные частотные характеристики предполагаемого открытого текста, получаемые с учетом “характера переписки”. Как отмечено в Приложении 1, такие характеристики являются более “рельефными” для литературных текстов и менее “рельефными” для формализованных электронных текстов. Чем менее рельефно распределение знаков текста, тем сложнее задача вскрытия шифра простой замены. Для открытых текстов с “почти равномерным” распределением знаков эта задача становится практически не решаемой. Это следует учитывать и не питать иллюзий о простоте вскрытия простой замены, о которой часто упоминается в популярных книгах по защите информации. Методы “рандомизации” или “сжатия” открытых текстов, например, с использованием компьютерных архиваторов значительно усложняют задачу вскрытия шифра простой замены.
Как будет ясно из дальнейшего (гл. 7), рельефность диаграммы текста тесно связана с такой его важной теоретикоинформационной характеристикой, как избыточность. Далее мы будем решать задачу вскрытия простой замены лишь при условии, что предполагаемые открытые тексты — это литературные тексты с “приличной” избыточностью. Кроме того, мы будем считать, что при дешифровании мы располагаем достаточно большим числом знаков шифртекста, чтобы опираться не на “фокусы”, использованные, например, в известных произведениях Э. А. По и А. Конан Дойля, а в большей степени на “статистику”.
Алгоритм вскрытия простой замены по тексту криптограммы достаточно сложно формализовать. При любой попытке формализации теряется какой-нибудь важный нюанс. Поэтому мы укажем лишь основные идеи, лежащие в основе
106
Шифры замены
такого алгоритма. Обычно выделяют следующие этапы алгоритма:
Алгоритм 1
1. Подсчет частот встречаемости шифробозначений, а также некоторых их сочетаний, например биграмм и триграмм подряд идущих знаков.
2. Выявление шифробозначений, заменяющих гласные и согласные буквы.
3. Выдвижение гипотез о значениях шифробозначений и их проверка. Восстановление истинного значения шифробозначений.
Сделаем ряд замечаний и уточнений.
Если длина текста достаточно велика, то найденные на этапе 1 частоты окажутся близкими к табулированным значениям частот знаков (соответственно — биграмм или триграмм). Проведенная на этом этапе работа служит основанием для выдвижения гипотез о значениях шифрвеличин, соответствующих данным шифробозначениям. При этом учитывается, что каждая буква имеет группу предпочтительных связей (см. Приложение 1), которые составляют ее наиболее характерную особенность. Как правило, такие гипотезы подтверждаются не полностью. Хорошим критерием при этом является “читаемость” восстанавливаемого открытого текста. Выделение шифробозначений, отвечающих гласным и согласным, основано на характерных свойствах этих букв, указанных в Приложении 1. Добавим к ним следующие соображения (относимые к большинству европейских языков). Если шифробозначение часто встречается, равномерно располагается по шифртексту, в отдельных местах чередуется через 1, 2 или 3 знака, сочетается со средними и редкими (по частоте) шифробозначениями, то это дает основания полагать, что такое шифробозначение скрывает гласную букву. Удвоение гласных в открытом тексте происходит реже, чем согласных. Если некоторое шифробозначение признано гласной, то бук-
107
І лава 5
ва, часто сочетающаяся с ней, скорее всего согласная. В открытом тексте чрезвычайно редко встречаются три и более подряд идущие гласные. Четыре и более подряд идущие согласные также редки. Важно учитывать также процентное соотношение чисел гласных и согласных в открытом тексте.
При проверке гипотез о значениях шифробозначений полезен поиск в шифртексте слов с характерной структурой, которые часто встречаются в открытом тексте. Для русского языка — это, например, слова сколько, которое, что и т. п. Для английского языка — слова every, that, look, the и т. п. Такие слова выделяются в шифртексте посредством интервалов между повторяющимися частыми буквами, характерными сочетаниями гласных и согласных.
Если с помощью приведенных соображений произведено несколько идентификаций шифробозначений, то дальнейшая работа по вскрытию текста криптограммы не представляет особого труда.
Пример вскрытия шифра простой однобуквенной замены приведен в Приложении 2.
Задача дешифрования еще более упрощается, если известно, что использовался сдвиговый или аффинный шифр. Так, для аффинного шифра бывает достаточно идентифицировать лишь пару шифробозначений с тем, чтобы полностью восстановить открытый текст (см., например, [Сал96]).
