Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
(светлым — в статье по компьютерной тематике; темным — в тексте программы на языке Паскаль)
Помимо криптографии частотные характеристики открытых сообщений существенно используются и в других сферах. Например, клавиатура компьютера, пишущей машинки или линотипа — это замечательное воплощение идеи ускорения набора текста, связанное с оптимизацией расположения букв алфавита относительно друг друга в зависимости от частоты их применения.
449
Приложение 2
Пример
Рассмотрим криптограмму, текст которой расположен в строках табл. 1 (см. стр. 454).
Для успешного решения задачи найдем частотные характеристики криптограммы, построив соответствующую матрицу биграмм (см. табл. 2 на стр. 455). Обратим при этом внимание на то, что в данном тексте используется обычный русский алфавит, состоящий из 30 букв. Поэтому матрица будет иметь размеры 30x30, строки и столбцы которой занумерованы буквами 30-буквенного алфавита.
В табл. 1 текст криптограммы выписан построчно с интервалом в две строки. Промежуточная строка потребуется далее для записи букв открытого текста под соответствующими буквами шифрованного текста.
Построим диаграмму встречаемости букв криптограммы.
Подсчет дает следующие значения относительных частот букв (в процентах):
А Б В Г Д E Ж 3 И К Л M H О
1,80 7,54 6,9 11 2,1 8,9 4,1 6,1 5,1 1,5 3,6 0,2 9,5 2
П P С T У Ф X Ц Ч ш щ ы ь э Ю я
0 6,4 3,4 4,6 1,2 1 0 1,5 LO CD CO CO 0 1 3,8 0,5 1,3 Л I
На основании этих данных получаем такую картину (рис. 1)
450
І Іример
Буквы алфавита
Рис. L Диаграмма встречаемости букв криптограммы
Построенная диаграмма очень близка по характеру к диаграмме открытого текста (см. рис. 1 Приложения 1). Кроме того, матрица биграмм является достаточно рельефной. Это свидетельствует о том, что скорее всего использован шифр простой замены. Нам ничто не мешает проверить эту гипотезу*
В матрице биграмм имеется ярко выраженный лидер: биграмма ЗИ встретилась 11 раз. Естественно предположить, что она заменяет биграмму CT открытого текста (наиболее часто встречающуюся в русском литературном тексте). Явным лидером по частоте встречаемости является буква Г. Предположим, что она заменяет букву О.
Проверим эти гипотезы, сделав соответствующие замены букв криптограммы. В результате получим картину, отраженную в табл. 3 (см. стр. 456).
451
І Іриложение г
Обратим внимание на некоторые получившиеся фрагменты открытого текста: 0?0?0ТТ и CT? (15-я строка), ?СТО (6-я строка), СОС? (26-я строка), на основании которых можно выдвинуть гипотезы о том, что вторая по частоте буква шифр-текста H — гласная (причем совпадающая с одной из букв И, Е, А), а пятая по частоте буква шифртекста В — согласная (и поэтому она, скорее всего Н, так как С и T уже задействованы).
Обратим также внимание на два частых удвоения: ЕЕ (4 раза) и BB (6 раз). Самыми частыми в открытом тексте являются удвоения ИИ, HH, ОО, CC. Это дает основание полагать, что В заменяет букву H открытого текста.
Буква E — третья по частоте в криптограмме, поэтому вполне вероятно, что она заменяет одну из букв И, E или А открытою текста. Учитывая сделанное замечание об удвоениях, сделаем предположение о том, что E заменяет букву И.
Дополним последнюю таблицу новыми предположениями о заменах (см. табл. 4 на стр. 457).
Обратим внимание на то, что биграмма ВБ встречается в криптограмме 9 раз. По нашему предположению В заменяет в криптограмме букву открытого текста Н. Согласно таблице биграмм открытого текста (см. табл. 11 Приложения 1), самыми частыми биграммами с первой буквой H являются HO, НА, НИ. Буквы О и И уже задействованы, поэтому оправдана гипотеза о том, что ВБ заменяет биграмму открытого текста НА.
Мы уже замечали, что H заменяет одну из букв А, Е, И открытого текста. С учетом предыдущего остается лишь одна возможность: H заменяет букву Е.
Внесем полученные результаты в табл. 5 (см. стр. 458).
Здесь лавинообразно определяются многие другие буквы. Так, из второй строки легко заметить, что UI заменяет букву Д открытого текста, T — букву Л. Из рассмотрения четвертой строки следует, что Б заменяет М, из восьмой строки — что P
452
Пример
заменяет В, а С — букву К, из восемнадцатой — что Ж заменяет P и т. д.
Теперь легко закончить работу, убедившись в том, что наши гипотезы оправдались (см. табл. 6 на стр. 459).
В рассмотренном примере достаточно точно сработала статистика. Это объясняется большой длиной сообщения, содержащего в нашем случае 611 знаков. Нам не понадобились многие стандартные приемы, применяющиеся при решении подобных задач для текстов меньшей длины, о которых было упомянуто в комментариях к алгоритму 1.
Ключом использованного в примере шифра является следующий подстановочный алфавит:
А Б В Г д E ж 3 и К Л M H о п
Б А P ы ш H я к E С T ь в г д
P с T У ф X ц ч ш щ ы ь э ю я
ж 3 и л M о п У ф X M ч щ э ю
составленный на основе ключевой фразы БАРЫШНЯ КРЕСТЬЯНКА, совпадающей с названием одноименной повести А.С. Пушкина. Заметим, что особенности таких (систематически перемешанных) алфавитов существенно помогают в восстановлении текстов. Соответствующая технология подробно изложена в [КаЬ67]. Там же содержится пример вскрытия простой замены, использующий значительно более тонкие рассуждения, чем приведенные в нашем примере.
