Лабораторная работа 1.2 Криптоанализ шифров табличной перестановки
Описание задания
В шифрах табличной перестановки криптограмма (зашифрованный текст) может быть получена разными способами. Для открытого текста длиной N подбирается таблица размером тх п,т п> N, символы текста записываются в ячейки таблицы. Запись может производиться как построчно, так и в столбец. В простейшем варианте текст из таблицы считывается в направлении, отличном от записи (например, по столбцам, если записывался по строкам).
Для усиления шифра перед считыванием текста из таблицы возможны перестановка столбцов/строк таблицы либо совместная перестановка строк и столбцов (двойная перестановка). Порядок считывания текста в этом случае может и не меняться.
Пусть текст записывается в таблицу построчно, затем производится перестановка столбцов таблицы, текст из таблицы считывается также построчно. Ключом такого шифра будет размер шифрующей таблицы и порядок следования ее столбцов.
При решении задачи криптоанализа необходимо восстановить начальный порядок следования букв текста. Таким образом, необходимо произвести действия, обратные шифрованию.
Для выяснения правильного порядка следования столбцов может быть использован частотный анализ буквосочетаний. Например, для русского языка характерно чередование гласных и согласных букв: после гласной чаще встречается согласная, а после согласной — гласная буква. Таблицы сочетаемости букв русского языка, чередования гласных и согласных, частотные таблицы биграмм можно найти в литературе[1].
Знание частот встречаемости пар букв (биграмм) позволяет легко вскрывать шифры табличной перестановки. Истинный порядок следования столбцов/строк в таблице можно восстановить, рассматривая и исключая маловероятные сочетания букв. Кроме того, на основе вероятностей появления биграмм можно рассчитать вероятность следования одного столбца (строки) шифрующей таблицы за другим.
Чтобы оценить вероятностьp(i,j) следования столбцаj непосредственно за столбцом /, надо для каждой строки рассмотреть сочетания символов из этих столбцов. Получим т вероятностей p(eki, ек)) биграмм, где т — число строк шифрующей таблицы; ekj9 ек- — символы, стоящие в шифрующей таблице на пересечении строки k и столбца i9j соответственно. Окончательно получим
Пользуясь этой формулой, можно вычислить вероятности следования друг за другом всех возможных пар столбцов p(i9j), i ф j: i,j = 1,..., пуп — число столбцов шифрующей таблицы. Если в исходном тексте столбец у действительно стоит после /-го, то вероятность p(i>j) должна быть, в принципе, больше вероятностей p(i, k), k ф] и p(k,j), k ф i. Руководствуясь этими соображениями, для таблиц небольшого размера несложно восстановить истинный порядок следования столбцов.
Предположим теперь, что в шифрующей таблице была произведена перестановка не только столбцов, но и строк. Ключом такого шифра будет размер шифрующей таблицы, порядок следования ее столбцов и строк. Тогда при дешифровании следует сначала восстановить исходный порядок следования столбцов. Получив фрагменты связного текста внутри каждой строки, можно восстановить порядок следования самих строк.
Задание
Дешифровать криптограммы, полученные методом столбцовой и двойной перестановки. Известно, что запись и считывание текста осуществляется построчно, пробелы в тексте сохранены и обозначены знаком подчеркивания. Численные оценки возможности взаимного следования столбцов шифрующей таблицы считаются известными (заданы).
Технология выполнения задания
Задание 1. Дешифровать криптограмму, полученную шифром столбцовой перестановки.
1. Выбрать криптограмму и соответствующую ей таблицу оценок взаимного следования столбцов шифрующей таблицы согласно выбранному варианту (от 1 до 5) из приведенного ниже списка.
Вариант № 1. Криптограмма: опдебирт_едоедж_уп_оорсут (табл. 1.11).
Вариант № 2. Криптограмма: ксереат_янясьзвр_вопеаанл (табл. 1.12).
Вариант №3. Криптограмма: орснчс оемтин едокз ищаыт (табл. 1.13).
Вариант № 4. Криптограмма: аевш_аазднени_евп_ыоннлео (табл. 1.14).
Вариант № 5. Криптограмма: ч_юлкятрпспо_наирк_домчип (табл. 1.15).
Таблица 1.11
Таблица оценок, вариант № 1
|
Следующий столбец |
||||||
|
1 |
2 |
3 |
4 |
5 |
||
|
Предыдущий столбец |
1 |
- |
6743 |
|
0 |
1995 |
|
2 |
|
- |
0 |
6328 |
0 |
|
|
3 |
|
13 |
- |
301 |
0 |
|
|
4 |
0 |
3903 |
|
- |
137 |
|
|
5 |
6816 |
0 |
0 |
|
- |
|
Таблица оценок, вариант № 2
|
Следующий столбец |
||||||
|
1 |
2 |
3 |
4 |
5 |
||
|
Предыдущий столбец |
1 |
- |
11 |
0 |
1588 |
113 |
|
2 |
7330 |
3174 |
0 |
7744 |
||
|
3 |
14 |
3228 |
- |
3868 |
572 |
|
|
4 |
18 |
435 |
0 |
- |
0 |
|
|
5 |
2849 |
158 |
0 |
144 |
||
Таблица 1.13
Таблица оценок, вариант № 3
|
Следующий столбец |
||||||
|
1 |
2 |
3 |
4 |
5 |
||
|
Предыдущий столбец |
1 |
- |
715 |
59 |
0 |
356 |
|
2 |
60 910 |
793 |
0 |
0 |
||
|
3 |
0 |
2465 |
- |
0 |
2512 |
|
|
4 |
3223 |
0 |
0 |
- |
58 |
|
|
5 |
0 |
0 |
0 |
7651 |
||
Таблица 1.14
Таблица оценок, вариант № 4
|
Следующий столбец |
||||||
|
1 |
2 |
3 |
4 |
5 |
||
|
Предыдущий столбец |
1 |
- |
127 |
0 |
11 824 |
178 717 |
|
2 |
0 |
0 |
80 |
650 733 |
||
|
3 |
25 519 |
42 721 |
- |
0 |
30 091 |
|
|
4 |
1772 |
21 830 |
0 |
- |
5 |
|
|
5 |
23 814 |
45 927 |
0 |
0 |
- |
|
Таблица 1.15
Таблица оценок, вариант № 5
|
Следующий столбец |
||||||
|
1 |
2 |
3 |
4 |
5 |
||
|
Предыдущий столбец |
1 |
577 |
0 |
0 |
15 |
|
|
2 |
1215 |
- |
25 |
668 |
19 |
|
|
3 |
0 |
0 |
- |
0 |
0 |
|
|
4 |
2 |
0 |
3536 |
- |
43 |
|
|
5 |
0 |
0 |
0 |
87 |
- |
|
Выполнить анализ криптограммы аналогично рассмотренному далее примеру.
Пример 1.9
Дешифровать криптограмму «канозлии_чыпатсяив_нрско_» (табл. 1.16).
Таблица 1.16
Таблица оценок
|
Следующий столбец |
||||||
|
1 |
2 |
3 |
4 |
5 |
||
|
Предыдущий столбец |
1 |
- |
130 |
0 |
70 268 |
1 |
|
2 |
54 |
5267 |
0 |
143 |
||
|
3 |
0 |
576 |
- |
975 927 |
0 |
|
|
4 |
3757 |
1066 |
180 587 |
- |
243 189 |
|
|
5 |
0 |
38 609 |
131 |
5393 |
||
2. Создать книгу MS Excel «Перестановка» для ускорения расчетов.
Поскольку размер криптограммы составляет 25 символов, можно предположить, что она была записана с помощью шифрующей таблицы размера 5 X 5.
На листе книги MS Excel выделить (разлиновать) таблицу размером 5x5 для записи криптограммы, пронумеровать ее столбцы и строки. Ниже выделить еще одну таблицу такого же размера, пронумеровать ее столбцы и строки (рис. 1.45);
Рис. 1.45. Пример форматирования таблиц книги «Перестановка»
В ячейку второй таблицы занести функцию ИНДЕКС, которая будет заполнять значениями вторую таблицу, осуществляя поиск символа верхней таблицы по заданному номеру строки и столбца:
- • в качестве значения первого параметра функции {Массив) назначить ссылку на таблицу с текстом криптограммы, сделать ссылку абсолютной, нажав клавишу F4;
- • в качестве значения второго параметра функции {Номер строки) указать адрес ячейки с текущим номером строки второй таблицы, зафиксировать указатель столбца, трижды нажав клавишу F4;
Рис. 1.46. Пример заполнения второй таблицы
- • в качестве значения третьего параметра функции (Номер_столбца) указать адрес ячейки с текущим номером столбца второй таблицы, зафиксировать указатель строки, дважды нажав клавишу F4, например =ИНДЕКС($С$4:$С$8;$В13;С$12), скопировать созданную формулу на весь диапазон ячеек второй таблицы (рис. 1.46). Теперь появится возможность переставлять столбцы второй таблицы, просто изменяя их номера.
- 3. Занести побуквенно криптограмму в строки первой таблицы. Текст криптограммы без изменений должен отобразиться во второй таблице.
- 4. Проанализировать таблицу оценок и высказать гипотезы об истинном порядке следования столбцов шифрующей таблицы. В таблице оценок заливкой выделены максимальные оценки, определяющие наиболее вероятный порядок следования столбцов, однако оценки могут быть не точны и приводить к противоречиям. Критерием верности гипотезы о порядке следования столбцов шифрующей таблицы является получение осмысленного текста.
Для рассматриваемого примера как наиболее вероятный может быть определен следующий порядок следования столбцов: 1 — 4, 4 — 5, 5 — 2, 2 — 3, 3 — 4. Заметим однако, что также весьма вероятны последовательности 4 — 3, 5 — 4, не исключены также другие варианты. Предположим, что последовательность столбцов следующая: 5 — 2 — 3 — 4 — 1.
Изменим номера столбцов второй таблицы в книге «Перестановка» в соответствии с выдвинутой гипотезой (табл. 1.17).
При анализе первой строки полученной таблицы (см. табл. 1.17) «заонк» маловероятным выглядит сочетание двух подряд идущих гласных «ао»
Таблица 1.17
Порядок следования столбцов, гипотеза 1
|
1 |
2 |
3 |
4 |
5 |
|
|
1 |
3 |
а |
о |
и |
к |
|
2 |
ч |
и |
и |
л |
|
|
3 |
с |
п |
т |
а |
ы |
|
4 |
II |
и |
в |
я |
|
|
5 |
с |
О |
к |
р |
и согласных «нк». При анализе строки 4 «ни_вя» сочетание «вя» также маловероятно, однако можно предположить, что строка содержит окончание слова — «ния», тогда строка 4 может выглядеть как «ния_в». Переставим столбцы, руководствуясь этими соображениями. Новый порядок следования столбцов: 5 — 2—1—4 — 3.
Изменим номера второй таблицы в книге «Перестановка» в соответствии с новой гипотезой (табл. 1.18).
Таблица 1.18
Порядок следования столбцов, гипотеза 2
|
1 |
2 |
3 |
4 |
5 |
|
|
1 |
3 |
а |
к |
о |
п |
|
2 |
ч |
и |
л |
и |
|
|
3 |
с |
п |
ы |
т |
а |
|
4 |
н |
и |
я |
13 |
|
|
5 |
с |
р |
О |
к |
Текст в таблице читается, значит, последняя гипотеза о порядке следования столбцов шифрующей таблицы верна.
Получен открытый текст «закончил_испытания_в_срок».
Задание 2. Дешифровать криптограмму, полученную шифром двойной перестановки.
5. Выбрать криптограмму и соответствующую ей таблицу оценок взаимного следования столбцов шифрующей таблицы согласно выбранному варианту (от 1 до 5) из приведенного ниже списка.
Вариант № 1. Криптограмма: ш_оен_нсяу_нолкрьлторешпо (табл. 1.19).
Вариант №2. Криптограмма: ыбс_тмоалнраопл_оврзб_ыьл (табл. 1.20).
Таблица 1.19
Таблица оценок, вариант № 1
|
Следующий столбец |
||||||
|
1 |
2 |
3 |
4 |
5 |
||
|
Предыдущий столбец |
1 |
2084 |
46 |
83 |
15 805 |
|
|
2 |
8 |
- |
0 |
0 |
32 |
|
|
3 |
0 |
17 533 |
- |
0 |
205 |
|
|
4 |
15 200 |
2 087 |
0 |
- |
0 |
|
|
5 |
0 |
0 |
10 153 |
95 |
- |
|
Таблица 1.20
Таблица оценок, вариант № 2
|
Следующий столбец |
||||||
|
1 |
2 |
3 |
4 |
5 |
||
|
Предыдущий столбец |
1 |
273 |
12 374 |
0 |
7 |
|
|
2 |
82 238 |
- |
0 |
0 |
0 |
|
|
3 |
50 |
7 |
- |
0 |
1815 |
|
|
4 |
0 |
43 112 |
0 |
- |
0 |
|
|
5 |
0 |
739 |
408 |
0 |
- |
|
Вариант № 3. Криптограмма: ацпиелипшрвнио_аслтисоо_г (табл. 1.21). Вариант № 4. Криптограмма: стоенчине_вср_т_ивезесомт (табл. 1.22). Вариант № 5. Криптограмма: угирзачикм_тнеаьеилс_ноыб (табл. 1.23). Выполнить анализ криптограммы аналогично рассмотренному далее примеру.
Таблица 1.21
Таблица оценок, вариант № 3
|
Следующий столбец |
||||||
|
1 |
2 |
3 |
4 |
5 |
||
|
Предыдущий столбец |
1 |
- |
1627 |
273 |
0 |
0 |
|
2 |
50 |
- |
0 |
8845 |
414 |
|
|
3 |
1733 |
0 |
- |
0 |
94 936 |
|
|
4 |
3128 |
1973 |
0 |
- |
0 |
|
|
5 |
0 |
13 154 |
2453 |
212 |
||
Таблица 1.22
Таблица оценок, вариант № 4
|
Следующий столбец |
||||||
|
1 |
2 |
3 |
4 |
5 |
||
|
1 э “ с *3 — 3 |
1 |
- |
54 706 |
844 |
21 045 |
214 |
|
2 |
4643 |
- |
4258 |
1107 |
227 957 |
|
|
3 |
366 |
9614 |
6822 |
590 |
||
|
4 |
93 072 |
790 |
6 636 |
- |
16 953 |
|
|
5 |
3345 |
851 |
86 041 |
163 |
- |
|
Таблица 1.23
Таблица оценок, вариант № 5
|
Следующий столбец |
||||||
|
1 |
2 |
3 |
4 |
5 |
||
|
Предыдущий столбец |
1 |
- |
459 |
363 |
0 |
737 |
|
2 |
0 |
105 |
547 |
0 |
||
|
3 |
0 |
0 |
- |
0 |
2615 |
|
|
4 |
68 360 |
0 |
719 |
- |
0 |
|
|
5 |
126 |
3 |
128 |
9 |
- |
|
Пример 1.10
Дешифровать криптограмму «ыа_рз_ыфвенлысапеон_члекю» (табл. 1.24).
Таблица 1.24
Таблица оценок, пример 1.10
|
Следующий столбец |
||||||
|
1 |
2 |
3 |
4 |
5 |
||
|
Предыдущий столбец |
1 |
0 |
14 740 |
7 |
0 |
|
|
2 |
0 |
- |
0 |
44 |
2484 |
|
|
3 |
0 |
0 |
- |
0 |
0 |
|
|
4 |
0 |
1750 |
0 |
- |
0 |
|
|
5 |
3701 |
0 |
0 |
211 |
- |
|
- 6. Модифицировать книгу MS Excel «Перестановка» для ускорения расчетов:
- • сохранить ранее созданную книгу «Перестановка» под именем «Двойная перестановка»;
- • добавить третью таблицу размером 5x5, предназначенную для перестановки строк. Строки таблицы пронумеровать;
- • в качестве номеров столбцов таблицы указать ссылки на ячейки, содержащие номера столбцов второй таблицы (например, =С12). Теперь при перестановке столбцов второй таблицы автоматически будут меняться номера столбцов третьей таблицы;
- • в ячейку третьей таблицы занести функцию ИНДЕКС, которая будет заполнять значениями третью таблицу, осуществляя поиск символа исходной таблицы по заданному номеру строки и столбца, например =ИНДЕКС($С$4:$С$8;$В21;С$20) (рис. 1.47).
Рис. 1.47. Пример заполнения третьей таблицы
Теперь при изменении номеров столбцов второй таблицы и номеров строк третьей таблицы их содержимое будет автоматически переставляться.
- 7. Занести побуквенно криптограмму в строки первой таблицы. Текст криптограммы без изменений должен отобразиться во второй и третьей таблицах.
- 8. Аналогично заданию 1 восстановить истинный порядок следования столбцов шифрующей таблицы:
- • при анализе таблицы оценок можно определить следующий порядок следования столбцов: 1— 3,2 — 5,5 — 1,4 — 2. Сформируем следующую последовательность столбцов: 4 — 2 — 5—1— 3;
- • изменить номера столбцов второй таблицы в соответствии с высказанной гипотезой о порядке следования столбцов (см. табл. 1.25).
В строках таблицы получены осмысленные фрагменты текста, значит, высказанная гипотеза о порядке следования столбцов верна.
- 9. Анализируя полученную таблицу, восстановить истинную последовательность строк таким образом, чтобы текст читался во всей таблице. Такой порядок строк: 5 — 2 — 1—4 — 3.
- 10. Изменить номера строк третьей таблицы в соответствии с восстановленной последовательностью (рис. 1.48).
Порядок следования столбцов двойной перестановки
|
4 |
2 |
5 |
1 |
3 |
|
|
1 |
Р |
а |
3 |
ы |
|
|
2 |
в |
е |
ф |
||
|
3 |
с |
л |
а |
н |
ы |
|
4 |
н |
е |
п |
О |
|
|
5 |
к |
л |
ю |
ч |
е |
Рис. 1.48. Восстановленная последовательность столбцов и строк
шифрующей таблицы
Получен исходный текст: «ключевые фразы не посланы».
- [1] Васильева И. Н. Криптографическая защита информации : практикум. СПб.: СПбГИЭУ,2011; Жданов О. Н., Куденкова И. А. Криптоанализ классических шифров : лаб. практикумдля студ. спец. 090105, 090106. Красноярск : Сибирский государственный аэрокосмичесикйуниверситет, 2009; О жиганов А. А. Основы криптоанализа симметричных шифров : учеб, пособие. СПб.: СПбГУ ИТМО, 2008.
