Этюды для программистов

Из групп G_i и G_j построим новую супергруппу G_ij, положив величину f_{ij, α} равной f_{i, α} + f_{i, α+r}. Отбросим из рассмотрения группы G_i и G_j, заменив их группой G_ij, и повторим описанный в последних двух абзацах процесс. После k − 1 повторений станут известны относительные сдвиги для всех k алфавитов. Кроме того, будет найдено обобщенное распределение частот. Для того чтобы найти исходные эквиваленты букв шифрованного текста, переупорядочим последние согласно их частотам. В результате буквы шифрованного текста должны расположиться в том же порядке, что и буквы русского алфавита (см. рис. 24.5). Теперь нетрудно восстановить весь квадрат Виженера и расшифровать текст. Ключевое слово можно найти, перебрав 32 набора из к букв, относительные расстояния между которыми соответствуют найденным сдвигам алфавитов. Возможно, что некоторые редко встречающиеся буквы окажутся не на своих местах. Эту ситуацию можно поправить при помощи визуального исследования полученного текста. Следует восстановить и смешанный алфавит, и ключевое слово, поскольку они оба могут иметь некоторую психологическую связь с содержанием сообщения и их выявление поможет дополнительно убедиться в правильности решения. Между прочим, что же написала мисс Хари?

Таблица 24.1. Распределения для сообщения с рис. 24.1 при k = 7
G1		G2		G3		G4		G5		G6		G7
A	5	A	0	A	3	A	2	A	8	A	0	A	3
Б	1	Б	7	Б	0	Б	1	Б	0	Б	1	Б	3
В	19	В	5	В	6	В	4	В	1	В	1	В	8
Г	0	Г	13	Г	2	Г	10	Г	5	Г	2	Г	8
Д	1	Д	0	Д	0	Д	4	Д	0	Д	0	Д	5
Е	4	Е	3	Е	1	Е	0	Е	2	Е	2	Е	11
Ж	10	Ж	8	Ж	3	Ж	7	Ж	3	Ж	2	Ж	1
3	3	3	7	3	9	3	2	3	2	3	5	3	4
И	2	И	3	И	4	И	4	И	2	И	0	И	3
Й	4	Й	0	Й	0	Й	1	Й	6	Й	1	Й	0
К	2	К	9	К	4	К	9	К	1	К	4	К	3
Л	3	Л	6	Л	4	Л	2	Л	1	Л	7	Л	3
М	5	М	1	М	0	М	5	М	4	М	14	М	0
Н	1	Н	6	Н	9	Н	3	Н	2	Н	3	Н	1
О	0	О	4	О	2	О	8	О	1	О	1	О	4
Л	1	Л	0	Л	1	Л	4	Л	9	Л	4	Л	0
Р	1	Р	2	Р	12	Р	2	Р	2	Р	0	Р	5
С	5	С	0	С	0	С	0	С	2	С	6	С	1
Т	1	Т	0	Т	5	Т	0	Т	3	Т	1	Т	1
У	2	У	7	У	6	У	1	У	9	У	4	У	2
Ф	0	Ф	1	Ф	9	Ф	4	Ф	5	Ф	5	Ф	5
X	4	X	0	X	0	X	0	X	4	X	3	X	2
Ц	3	Ц	0	Ц	1	Ц	3	Ц	8	Ц	1	Ц	3
Ч	10	Ч	0	Ч	0	Ч	2	Ч	8	Ч	0	Ч	1
Ш	5	Ш	8	Ш	2	Ш	4	Ш	2	Ш	1	Ш	2
Щ	0	Щ	0	Щ	4	Щ	0	Щ	0	Щ	1	Щ	8
Ъ	0	Ъ	6	Ъ	4	Ъ	4	Ъ	0	Ъ	9	Ъ	5
Ы	3	Ы	0	Ы	1	Ы	8	Ы	2	Ы	8	Ы	0
Ь	1	Ь	5	Ь	9	Ь	5	Ь	4	Ь	2	Ь	0
Э	8	Э	0	Э	0	Э	0	Э	4	Э	0	Э	6
Ю	1	Ю	0	Ю	1	Ю	3	Ю	4	Ю	5	Ю	4
Я	1	Я	5	Я	4	Я	3	Я	1	Я	12	Я	3

Значение R_{1, 0, 2} равно 333, а значение R_{3, 6, 12} равно 335. Значение R_{3, 6, 12} получается перемножением чисел появлений букв от А до У для G₃ на числа появлений букв от М до Я для G₆ и чисел появлений букв от Ф до Я для G₃ на числа появлений букв от А до Л для G₆ и сложением всех этих произведений.

Тема. Напишите программу, которая в качестве входных данных воспринимает шифрованное сообщение и, в предположении, что оно зашифровано по схеме Виженера, печатает расшифрованный текст. Программа должна также печатать квадрат Виженера и ключевое слово, которые она вычисляет в процессе решения задачи. Специальные входные параметры должны управлять выводом промежуточных результатов, таких, как, например, все возможные длины ключевого слова, распределения частот букв для отдельных алфавитов, значения ИС и т. д., которые нужны для контроля. Эти результаты могут быть полезны при отладке, а также в тех, к сожалению, вполне реальных ситуациях, когда предложенное машиной решение оказалось не совсем точным. Четкость оформления выводных данных имеет большое значение: бестолковые распечатки лишь затрудняют работу интуиции специалиста по расшифровке сообщений.

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