Порядок выполнения работы

Лабораторная работа №1

«Защита данных с помощью шифров перестановки»

1.1 Цель работы: изучить, освоить и программно реализовать алгоритмы перестановочного шифрования.

Теоретическое введение

Шифры перестановки

Шифр – это метод или способ преобразования (шифрования) инфор­мации с целью ее защиты от незаконных пользователей. Дешифрование – процесс, обратный шифрованию, т. е. преобразо­вание шифрованного сооб­щения в защищаемую информацию с помо­щью определенных правил, со­держащихся в шифре. Защищаемая информация называется открытым тек­стом, полученное в результате шифрования сообщение называется шифр – текстом или криптограммой.

Шифр перестановки (ШП) – это шифр, преобразования при помощи которого изменяют только порядок следования символов исходного текста, не изменяя их самих. Простейшим ШП является подстановка степени n. И шифрование, и дешифрование осуществляется при помощи следующей таблицы:

Шифрование проводится следующим образом: первый символ открытого текста заменяется i ₁–м символом из этого же текста, второй – i ₂-м и т. д. Дешифрование производится аналогично при помощи этой же та­блицы.

Маршрутная перестановка – это ШП, использующий некоторую геомет­рическую фигуру. Исходный текст записывается в фигуру по ходу одного «маршрута», а затем выписывается из нее по ходу другого.

Пример: будем вписывать исходное сообщение в прямоугольную та­блицу по горизонтали, начиная с левого верхнего угла, поочередно слева направо и справа налево. Выписывать сообщение будем по вертикали, на­чиная с верхнего правого угла и двигаясь поочередно сверху вниз и снизу вверх. Зашифруем, например, указанным способом фразу: ПРИМЕР – МАРШРУТНОЙПЕРЕСТАНОВКИ. Используя прямоугольник размера 4х7, получим следующий шифртекст: МАСТАЕРРЕШРНОЕРМИУПВ­КЙТРПНОИ

Шифр перестановки «Сцитала». Одним из самых первых шифровальных приспособлений был жезл (“Сцитала”). Это был цилиндр, на который ви­ток к витку наматывалась узкая папирусная лента (без просветов и нахле­стов), а затем на этой ленте вдоль его оси записывался необходимый для передачи текст. Лента сматывалась с цилиндра и отправлялась адресату, ко­торый, имея цилиндр того же диаметра, наматывал ленту на него и прочи­тывал сообщение. Такой способ шифрования осуществляет перестановку местами букв сообщения. Этот шифр эквивалентен следующему шифру маршрутной перестановки: в таблицу, состоящую из n столбцов, построчно записывают сообщение, после чего выписывают буквы по столбцам. Число задействованных столбцов в таблице не может превышать длины сообще­ния.

Шифр «Поворотная решетка». Для использования этого шифра изготов­ляется трафарет из прямоугольного листа клетчатой бумаги размера 2m x 2k клеток. В трафарете вырезано mk клеток так, чтобы при наложении его на чистый лист бумаги того же размера четырьмя возможными

Рис. 3

способами его вырезы полностью покрывают всю площадь листа. Буквы из сообщения последовательно вписываются в вырезы трафарета (по строкам, в каждой строке слева направо) при каждом из четырех его возможных по­ложений заранее в установленном порядке. Поясним процесс шифрования на примере. Пусть в качестве ключа используется решетка 6х10, приведен­ная на рис 3. Зашифруем с ее помощью текст: ШИФРРЕШЕТКАЯВЛЯЕТ­СЯЧАСТНЫМСЛУЧАЕМШИФРАМАРШРУТНОЙПЕРЕСТАНОВКИ

Наложив решетку на лист бумаги, вписываем первые 15 (по числу вы­резов) букв сообщения: ШИФРРЕШЕТКАЯВЛЯ. Сняв решетку, мы уви­дим текст, представленный на рисунке 4. Поворачиваем решетку на 180. В окошечках появятся новые, еще не заполненные клетки. Вписываем в них следующие 15 букв. Получится запись, приведенная на рис.5. Затем переворачиваем решетку на другую сторону и зашифровываем остаток тек­ста аналогичным образом (рис. 6, 7). Получатель сообщения, имеющий точно такую же решетку, без труда прочтет исходный текст, наложив ре­шетку на шифротекст по порядку четырьмя способами. Можно доказать, что число возможных трафаретов, то есть количество ключей шифра «ре­шетка», составляет T=4mk. Этот шифр предназначен для сообщений длины n=4mk. Число всех перестановок в тексте такой длины составит (4mk), что во много раз больше числа T. Однако уже при размере трафарета 8 x 8 чис­ло возможных решеток превосходит 4 миллиарда.

Шифр вертикальной перестановки (ШВП) – В нем используется прямо­угольник, в который сообщение вписывается по строкам слева направо. Выписываются буквы по вертикали, столбцы при этом берутся в порядке, определяемом ключом. Пусть, например, этот ключ таков: (5,4,1,7,2,6,3), и с его помощью надо зашифровать сообщение: ВОТПРИМЕРШИФРА – ВЕРТИКАЛЬНОЙПЕРЕСТАНОВКИ. Впишем сообщение в прямо­угольник, столбцы которого пронумерованы в соответствии с ключом. Выбирая столбцы в порядке, заданном ключом, и выписывая последова­тельно буквы каждого из них сверху вниз, получаем: ОРЕЬЕКРФИЙА-МААЕОТШРНСИВЕВЛРВИРКПНПИТОТ

Ключ ШВП можно извлекать из какого-то легко запоминающегося слова или предложения. Например, можно приписывать буквам числа в со­ответствии с обычным алфавитным порядком букв. Например, пусть клю­чевым словом будет ПЕРЕСТАНОВКА. Присутствующая в нем буква А получает номер 1. Если какая-то буква входит несколько раз, то ее появле­ния нумеруются последовательно слева направо. Поэтому второе вхожде­ние буквы А получает номер 2. Поскольку буквы Б в этом слове нет, то буква В получает номер 3 и так далее. Процесс продолжается до тех пор, пока все буквы не получат номера. Таким образом, получаем следующий ключ:

Для обеспечения дополнительной скрытности можно повторно за­шифровать сообщение, которое уже прошло шифрование. Такой метод шифрования называется двойной перестановкой. В этом случае переста­новки определяются отдельно для столбцов и отдельно для строк. Сначала в таблицу записывается текст сообщения, а потом поочередно перестав­ляются столбцы, а затем строки. При расшифровании порядок перестано­вок должен быть обратным. Однако двойная перестановка не отличается высокой стойкостью и сравнительно просто взламывается при любом раз­мере таблицы шифрования.

Применение магических квадратов. Магическими квадратами называют квадратные таблицы с вписанными в их клетки последовательными нату­ральными числами, начиная от 1, которые дают в сумме по каждому столб­цу, каждой строке, и каждой диагонали одно и то же число. Шифруемый текст вписывается в магический квадрат в соответствии с нумерацией его клеток. Если затем выписать содержимое такой таблицы по строкам, то по­лучится шифртекст, сформированный благодаря перестановке букв исход­ного сообщения. Пример магического квадрата и его заполнение сообще­нием ПРИЛЕТАЮ ВОСЬМОГО, показан на рисунке. Полученный шифр­текст имеет вид: ОИРМЕОСЮВТАЬЛГОП

Порядок выполнения работы

Зашифровать входную последовательность символов методом переста­новки, используя подстановку длиной в четыре символа. Использовать файлы в качестве источника исходной и приемника шифрованной инфор­мации.