Лабораторная работа №1
«Защита данных с помощью шифров перестановки»
1.1 Цель работы: изучить, освоить и программно реализовать алгоритмы перестановочного шифрования.
Теоретическое введение
Шифры перестановки
Шифр – это метод или способ преобразования (шифрования) информации с целью ее защиты от незаконных пользователей. Дешифрование – процесс, обратный шифрованию, т. е. преобразование шифрованного сообщения в защищаемую информацию с помощью определенных правил, содержащихся в шифре. Защищаемая информация называется открытым текстом, полученное в результате шифрования сообщение называется шифр – текстом или криптограммой.
Шифр перестановки (ШП) – это шифр, преобразования при помощи которого изменяют только порядок следования символов исходного текста, не изменяя их самих. Простейшим ШП является подстановка степени n. И шифрование, и дешифрование осуществляется при помощи следующей таблицы:
Шифрование проводится следующим образом: первый символ открытого текста заменяется i 1–м символом из этого же текста, второй – i 2-м и т. д. Дешифрование производится аналогично при помощи этой же таблицы.
Маршрутная перестановка – это ШП, использующий некоторую геометрическую фигуру. Исходный текст записывается в фигуру по ходу одного «маршрута», а затем выписывается из нее по ходу другого.
Пример: будем вписывать исходное сообщение в прямоугольную таблицу по горизонтали, начиная с левого верхнего угла, поочередно слева направо и справа налево. Выписывать сообщение будем по вертикали, начиная с верхнего правого угла и двигаясь поочередно сверху вниз и снизу вверх. Зашифруем, например, указанным способом фразу: ПРИМЕР – МАРШРУТНОЙПЕРЕСТАНОВКИ. Используя прямоугольник размера 4х7, получим следующий шифртекст: МАСТАЕРРЕШРНОЕРМИУПВКЙТРПНОИ
|
П | Р | И | М | Е | Р | М |
Н | Т | У | Р | Ш | Р | А |
О | Й | П | Е | Р | Е | С |
И | К | В | О | Н | А | Т |
Шифр перестановки «Сцитала». Одним из самых первых шифровальных приспособлений был жезл (“Сцитала”). Это был цилиндр, на который виток к витку наматывалась узкая папирусная лента (без просветов и нахлестов), а затем на этой ленте вдоль его оси записывался необходимый для передачи текст. Лента сматывалась с цилиндра и отправлялась адресату, который, имея цилиндр того же диаметра, наматывал ленту на него и прочитывал сообщение. Такой способ шифрования осуществляет перестановку местами букв сообщения. Этот шифр эквивалентен следующему шифру маршрутной перестановки: в таблицу, состоящую из n столбцов, построчно записывают сообщение, после чего выписывают буквы по столбцам. Число задействованных столбцов в таблице не может превышать длины сообщения.
Шифр «Поворотная решетка». Для использования этого шифра изготовляется трафарет из прямоугольного листа клетчатой бумаги размера 2m x 2k клеток. В трафарете вырезано mk клеток так, чтобы при наложении его на чистый лист бумаги того же размера четырьмя возможными
Рис. 3
|
способами его вырезы полностью покрывают всю площадь листа. Буквы из сообщения последовательно вписываются в вырезы трафарета (по строкам, в каждой строке слева направо) при каждом из четырех его возможных положений заранее в установленном порядке. Поясним процесс шифрования на примере. Пусть в качестве ключа используется решетка 6х10, приведенная на рис 3. Зашифруем с ее помощью текст: ШИФРРЕШЕТКАЯВЛЯЕТСЯЧАСТНЫМСЛУЧАЕМШИФРАМАРШРУТНОЙПЕРЕСТАНОВКИ
Ш | Е | Ш | Т | С | Я | |||||||||||||||||||||||||||||
И | Ф | Р | Р | И | Ф | Р | Р | Ч | ||||||||||||||||||||||||||
Е | Ш | Е | Е | А | Ш | С | Е | |||||||||||||||||||||||||||
Т | К | Т | Т | Н | К | Ы | ||||||||||||||||||||||||||||
А | А | М | С | Л | У | |||||||||||||||||||||||||||||
Я | В | Л | Я | Я | В | Л | Ч | Я | ||||||||||||||||||||||||||
Рис. 4 | Рис.5 | |||||||||||||||||||||||||||||||||
Е | Ш | А | Т | С | Е | М | Я | Ш | Е | Ш | А | Т | С | Е | М | Я | Н | Ш | ||||||||||||||||
И | И | Ф | Р | Р | Ч | И | И | О | Й | Ф | П | Р | Р | Ч | Е | |||||||||||||||||||
Е | А | Ф | Ш | С | Р | Е | Р | Е | А | Ф | Е | Ш | С | Р | С | Е | ||||||||||||||||||
Т | А | Т | Н | М | К | Ы | А | Т | А | Т | Т | Н | М | А | К | Ы | А | |||||||||||||||||
Р | А | М | С | Ш | Л | Р | У | У | Р | А | М | С | Ш | Л | Р | У | Н | У | ||||||||||||||||
Т | Я | В | Л | Ч | Я | О | Т | Я | В | К | В | Л | И | Ч | Я | |||||||||||||||||||
Рис.6 | Рис.7 | |||||||||||||||||||||||||||||||||
|
Наложив решетку на лист бумаги, вписываем первые 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, которые дают в сумме по каждому столбцу, каждой строке, и каждой диагонали одно и то же число. Шифруемый текст вписывается в магический квадрат в соответствии с нумерацией его клеток. Если затем выписать содержимое такой таблицы по строкам, то получится шифртекст, сформированный благодаря перестановке букв исходного сообщения. Пример магического квадрата и его заполнение сообщением ПРИЛЕТАЮ ВОСЬМОГО, показан на рисунке. Полученный шифртекст имеет вид: ОИРМЕОСЮВТАЬЛГОП
Порядок выполнения работы
Зашифровать входную последовательность символов методом перестановки, используя подстановку длиной в четыре символа. Использовать файлы в качестве источника исходной и приемника шифрованной информации.