Практическое занятие №2 по дисцеплине Методы криптографической защиты

защиты информации»

Отличие этого типа шифра от шифров замены состоит в том,

что при зашифровании буква ai открытого текста переходит не в фиксированный знак алфавита, а в другую букву того же открытого текста, скажем аj, в результате чего буквы располагаются на новых местах, т.е. переставляются. Ключом для данного шифра также служит таблица замены, только не букв алфавита, а их индексов (номеров мест) в тексте, подлежащем зашифрованию. В общем случае размер таблицы замены равен длине открытого текста. Такие таблицы удобно формировать (и записывать) в виде так называемых подстановок, поэтому напомним вкратце их некоторые свойства.
Подстановкой называется взаимно-однозначное отображение конечного множества на себя. Обычно подстановки записывают в виде двух строк. Верхняя строка является операндом подстановки, а нижняя – результатом ее действия на операнд. Например, одна из подстановок, действующих на множестве из пяти элементов, может быть записана следующим образом:

Элементы конечного множества всегда можно перенумеровать, следовательно и операнд любой подстановки можно записать в виде 12...N, где N – количество элементов в операнде. Число N называется степенью подстановки. Указанная подстановка Т является, таким образом, подстановкой пятой степени и может быть записана так:

ней зашифровывается слово МОСКВА, то получится КОСВМА. Попробуйте расшифровать сообщение

НЧЕИУК, полученное в результате преобразования с помощью указанной выше подстановки.

Очевидно, различными подстановками одной степени можно воздействовать на исходное множество последовательно друг за другом. Результат последовательного действия подстановок Т1,Т2 называется их произведением и записывается обычно Т1Т2. Произведение двух подстановок определяется исходя из того, что если первая подстановка переводит j на место i, а вторая подстановка, переводит k на место j, то в произведении k переходит на место i. Таким образом, если

, то

и

,

однако скобки в произведениях можно расставлять произвольно. Существует «единичная» подстановка

I такая, что для всех T: IT=TI=T. Для нашего примера:

Также нетрудно видеть, что для любой подстановки Т существует обратная подстановка Т-1. такая, что Т-1Т=ТТ-1=I. Действительно, для построения Т-1 достаточно переставить местами строки в подстановке Т, а затем упорядочить колонки так, чтобы числа в верхней строке шли в возрастающем порядке. Перечисленных свойств вполне достаточно, чтобы классифицировать множество подстановок степени N, с указанной операцией умножения, как группу – одну из важнейших математических моделей. Заметим также, что в некотором смысле, подстановки степени N могут быть сконструированы из подстановок меньшей степени. Дело в том. что подстановки степени п

меньшей степени включаются во множество подстановок большей степени и, в

свою очередь, образуют теперь уже подгруппу по исходной операции умножения. Оказывается, каждую подстановку Т можно представить в виде произведения T=P1…Pk некоторых специальных подстановок, называемых циклами, причем, циклы P1…Pk попарно независимы. Последнее означает, что подстановки Pi и Pj. при PiPj, действуют на непересекающихся подмножествах операнда подстановки T, если не принимать во внимание элементы, остающиеся неподвижными. Поясним указанное свойство подстановок более конкретно.
Пусть 1

Здесь элементы 4 и 5 неподвижны, причем i1=1, i2=3, i3=2 . Ясно, что циклическая диаграмма переходов, может быть выписана, начиная с любого своего элемента, однако все эти записи соответствуют одной и той же подстановке. Обычно цикл записывают в виде, аналогичном диаграмме пе­реходов: (i1,i2,…,ik) единичную подстановку рассматривают как произведение одночленных циклов вида I=(i) где под i подразумевается любой элемент (от 1 до N). Для записи подстановки в виде произведения циклов достаточно выписать все различные диаграммы переходов. Например, подстановка может быть представлена как Т= (1679)(2354)(8), впрочем, одночленные циклы при записи часто опускаются.

два элемента. Такой двучленный цикл называется транспозицией. Оказывается, можно показать,

что если подстановка степени N разлагается в произведение r попарно независимых циклов (включая и одночленные циклы) то ее можно представить в виде произведения п-r транспозиций. Заметим, что указанные транспозиции не обязательно являются независимыми циклами.
Возвращаясь к шифрам перестановки, предположим, что номера букв открытого текста длиной в N знаков разбиты каким-либо способом на непересекающиеся множества M1,…,Mr. Воздействуя на каждое множество Mi своей подстановкой (циклом) Ti, мы реализуем процесс зашифрования шифром перестановки, причем соответствующая шифрпреобразованию подстановка равна Т1…Тr. Изменяя разбиение множества индексов и выбирая различными способами соответствующие подстановки T’j, мы будем получать различные преобразования открытого текста вида T’1,…T’S. Причем, рано или поздно, мы построим все подстановки степени N, поскольку любая подстановка разлагается в произведение циклов. То же самое можно сказать и по отношению к некоторому иному, более сложному процессу генерации подстановок, который, скажем, включает вышеуказанную процедуру в качестве одного из этапов. Отсюда вытекает, что удачный способ генерации подстановок мог бы, в принципе, обеспечить достаточно качественный шифр перестановки, при котором использовались бы подстановки степени меньшей, чем длина открытого текста. Последнее весьма важно, поскольку хранить и передавать ключи, длина которых равна длине открытого текста в данном случае невыгодно (существуют намного более совершенные шифры с аналогичными требованиями) и, кроме того, невозможно зашифровать шифром перестановки текст, длина которого меньше степени соответ­ствующей подстановки. Именно способами генерации подстановок и различаются различные виды шифров перестановки.

зашифрования и легкость запоминания ключа. Рассмотрим пример перестановочной криптограммы, для

которой подстановка задается неявно, в качестве ключевого слова – «лозунга».
Открытый текст криптограммы следующий: "В связи с создавшимся положением отодвигаем сроки возвращения домой Рамзай".
Для зашифрования шифром вертикальной перестановки построим прямоугольную таблицу, количество строк которой определяется длиной текста, а количество колонок равно шести. В качестве «лозунга» выберем слово "ЗАПИСЬ" (количество букв в ключевом слове должно равняться количеству колонок в нашей таблице).
Заменим теперь каждую букву ключевого слова на число от 1 до 6 таким образом, чтобы буква, имеющая меньший номер следования в алфавите, заменялась на меньшее число. Полученные числа (2,1,4,3,5,6) проставим подряд в начале соответствующих колонок таблицы и будем в дальнейшем считать их номерами этих колонок. Впишем открытый текст в таблицу, переходя обычным образом со строки на строку. В результате получим:

в начале которого стоит единица, затем – столбец, помеченный двойкой

и т.д.
В итоге, получим следующий шифртекст (представив его пятизначными группами знаков):

ссшои дмвщо мвсвп ноеиа даязм омирз ноаво илевс оемзз дсжог овийй иаяет акряр

Ясно, что шифртекст отличается от открытого текста лишь перестановкой букв и мы. таким образом, совместили процесс генерации подстановок с процессом зашифрования.
В криптографической практике, результат действия подстановки на последовательность номеров знаков открытого текста, являющийся рядом чисел, указывающим место очередных букв шифртекста в открытом тексте, называется шкалой разноски. Нетрудно видеть, что для расшифрования, т.е. перестановки знаков шифртекста на исходное место, необходимо воспользоваться подстановкой обратной шкале разноски, которая называется шкалой набора.
В зависимости от частного вида закона построения шкалы разноски, различают частные виды шифра перестановки – горизонтальную, вертикальную перестановки. В некоторых случаях шкала разноски строится как функция от двух независимых перестановок небольшой степени (двойная перестановка) или от перестановки и геометрической фигуры (так называемые шифры-решетки и лабиринты).

определяются размерами двух ключевых слов (скажем, "гевара" и "риск"), которые

выписываются при этом сверху и сбоку таблицы;
в таблицу по определенному маршруту (к примеру, "а") заносится исходный текст (таблица А), а неиспользованные места полностью заполняются любыми, но лучше всего часто встречающимися буквами (здесь: "с", "в", "и");
переместить столбцы в порядке, соответствующем расположению букв у верхнего ключа ("гевара") в обычном алфавите (таблица Б);
переместить все строки в соответствий с последовательностью букв второго ключевого слова ("риск") в алфавите (таблица В);
выписать последовательно буквы из получившейся таблицы, стандартно разбивая их на пятизнаковые группы, причем, если последняя из них окажется неполной, она дописывается любыми часто встречающимися буквами.

криптограммы следует действовать в обратном порядке:
шифртекст вписывается в таблицу определяемого

длинами ключей размера;
столбцы и строки в ней последовательно нумеруются, а избыток букв отбрасывается (так получается таблица В):
строки располагают в соответствии с порядком номеров букв бокового ключевого слова (так получается таблица Б);
столбцы переставляются согласно нумерации букв верхнего ключа (так получается таблица А);
буквы выписываются в строку, следуя обговоренному маршруту заполнения-чтения.
В заключение отметим, что зашифрование случайной, не обладающей закономерностями шкалой разноски, при достаточно большой длине сообщения делает дешифрование такой криптограммы весьма проблематичным.

используется не один, а несколько алфавитов. Обычно алфавиты для замены

образованы из символов исходного алфавита, записанных в другом порядке.
Примером многоалфавитной подстановки может служить схема, основанная на использовании таблицы Вижинера. Этот метод, известный уже в XVI веке, был описан французом Блезом Вижинером в "Трактате о шифрах", вышедшем в 1585 году.
В этом методе для шифрования используется таблица, представляющая собой квадратную матрицу с числом элементов NxN, где N – количество символов в алфавите (табл.). В первой строке матрицы записывают буквы в порядке очередности их в исходном алфавите, во второй – ту же последовательность букв, но с циклическим сдвигом влево на одну позицию, в третьей – со сдвигом на две позиции и т. д.
Для шифрования текста выбирают ключ, представляющий собой некоторое слово или набор символов исходного алфавита. Далее из полной матрицы выписывают подматрицу шифрования, включающую первую строку и строки матрицы, начальными буквами которых являются последовательно буквы ключа.

Й К Л М Н О П Р С Т

У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я
Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А
В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А Б
Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А Б В
Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А Б В Г
Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А Б В Г Д
Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А Б В Г Д Е
З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А Б В Г Д Е Ж
И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А Б В Г Д Е Ж З
Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А Б В Г Д Е Ж З И
К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А Б В Г Д Е Ж З И Й
Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А Б В Г Д Е Ж З И Й К
М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А Б В Г Д Е Ж З И Й К Л
Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А Б В Г Д Е Ж З И Й К Л М
О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н
П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О
Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П
С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р
Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С
У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т
Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У
Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф
Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х
Ч Ш Щ Ь Ы Ъ Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц
Ш Щ Ь Ы Ъ Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч
Щ Ь Ы Ъ Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш
Ь Ы Ъ Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ
Ы Ъ Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь
Ъ Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы
Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ
Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э
Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю

выбрано ключевое слово "АМБРОЗИЯ". Необходимо зашифровать сообщение "ПРИЛЕТАЮ СЕДЬМОГО".
Выпишем исходное

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

А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я
М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А Б В Г Д Е Ж З И Й К Л
Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А
Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П
О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н
З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А Б В Г Д Е Ж
И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю Я А Б В Г Д Е Ж З
Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Ъ Э Ю

слово.
Зашифровать ключевые слова (см. табл.) при помощи шифра перестановки.

текст одним из классическим шифром и выполнить обратное преобразование.