Практическая работа №1 «Применение методов шифрования перестановкой»
Краткие теоретические и учебно-методические материалы по теме практической работы.
Исторически, изначально, методы шифрования были предназначены для преобразования текстовых сообщений. Поэтому, любой текст состоящий из некоторых символов, зависит от двух параметров присущих символам исходного текста, а именно:
- местоположения символа в слове;
- значения символа, как такового.
При изменении местоположения символа в тексте получится шифрование перестановкой.
При изменении значения символа получится шифрование заменой.
При изменении обоих параметров получится комбинированное шифрование.
ПРАВИЛО: При шифровании методом перестановки символы исходного текста могут поменять только местоположение, но не меняют значение символов.
Для зашифровывания исходного текста методом перестановки необходимо перемешать имеющиеся в нем символы. Насколько данный метод надежен и от чего это зависит? Безусловно, чем больше исходный текст, тем больше вариантов перемешивания.
Посчитаем возможное количество перестановок для слова содержащего 3 символа: исходный текст: КОТ.
Возможные варианты шифрования перестановкой: КТО, ОТК, ОКТ, ТКО, ТОК. 3 символа исходного текста – дают 6 вариантов перестановки.
Посчитаем возможное количество перестановок для слова содержащего 4 символа:
Исходный текст: МОСТ
Возможные варианты шифрования перестановкой:
МОТС, МТСО, МТОС, МСОТ, МСТО,
ОТСМ, ОТМС, ОМСТ, ОМТС, ОСТМ, ОСМТ,
ТОСМ, ТОМС, ТСМО, ТСОМ, ТМОС, ТМСО,
СОМТ, СОТМ, СТМО, СТОМ, СМОТ, СМТО.4 символа исходного текста – дают 24 варианта перестановки.
Математическая закономерность количества возможных перестановок вычисляется функцией факториал: 3! = (1*2*3) = 6
4! = (1*2*3*4) = 24
5! = (1*2*3*4*5) = 120ПРАВИЛО: Число различных преобразований шифра перестановки, можно посчитать с помощью математической функции факториал.
С увеличением числа n значение n! растет очень быстро. Приведем таблицу значений n! для первых 10 натуральных чисел:
n = 1 2 3 4 5 6 7 8 9 10
n! = 1 2 6 24 120 720 5040 40320 362880 3628800
ПРИМЕР:1.Найти количество возможных перестановок исходного текста (Пробелы исключить и не учитывать).
Исходный текст(ИТ): ИвановПетрФедорович
Количество символов ИТ: 19
Количество возможных перестановок: 19! = 121 645 100 408 832 000
(121 квадратильон 645триллионов 100миллиардов 408миллионов 832 тысячи) возможных комбинаций.
2.Посчитать время перебора всех комбинаций с помощью компьютера с производительностью 1 миллион комбинаций в секунду.
Исходное количество перестановок: 121 645 100 408 832 000
Время перебора всех комбинаций с применением компьютера:
121 645 100 408 832 000 : 1 000 000 = 121 645 100 408. 832 секунд
121 645 100 408. 832 : 60 = 2 027 418 340 минут
2 027 418 340 : 60 = 33 790 305.6 часов
33 790 305.6 : 24 = 1 407 929.4 суток
1 407 929.4 : 365 = 3 857.3 лет
Задание.
№1 Определить количество возможных перестановок в Фамилии Имени Отчестве студента, посчитать время перебора всех комбинаций с применением компьютера с производительностью 1 000 000 комбинаций в секунду.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ПРАВИЛО: Стойкость шифрования методом перестановки зависит от длины исходного текста и метода организации перестановки.
Все шифры перестановки делятся на два подкласса:
- шифры одинарной (простой) перестановки. При шифровании символы перемещаются с исходных позиций в новые один раз;
- шифры множественной (сложной) перестановки. При шифровании символы перемещаются с исходных позиций в новые несколько раз.
Шифры одинарной перестановки.
В общем случае для данного класса шифров при шифровании и дешифровании используется таблица перестановок.
|
1 |
2 |
3 |
… |
n |
|
I1 |
I2 |
I3 |
… |
In |
В первой строке данной таблицы указывается позиция символа в исходном сообщении, а во второй – его позиция в шифрограмме. Таким образом, максимальное количество ключей для шифров перестановки равно n!, где n – длина сообщения.
Шифр простой одинарной перестановки.
Метод обратного написания.
Простейшим методом шифрования перестановкой является написание ИТ в обратном порядке.
Например, при шифрования данным методом ИТ «ИВАНОВ», получим шифротекст (ШТ) – «ВОНАВИ».
Задание.
№2 Зашифровать собственные ФИО методом обратного написания.
|
ИТ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ШТ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Метод перестановки соседних букв.
В данном методе каждые две соседние буквы меняем местами.(Если ИТ имеет нечетное количество символов – дополняем ИТ следующей буквой по алфавиту)
Например, ИТ «СИДОРОВ» - количество символов 7, дополняем до четного получим ИТ «СИДОРОВГ», шифротекст – «ИСОДОРГВ».
Задание.
№3 Зашифровать собственные ФИО данным методом.
|
ИТ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ШТ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Метод «Штакетник» 2х-строчный.
ИТ записывается в 2 строки и переписывается последовательно друг за другом.
ИТ «СИСТЕМНЫЙ АДМИНИСТРАТОР»
Зашифровываем: С С Е Н Й Д И И Т А О
И Т М Ы А М Н С Р Т Р
ШТ «ССЕНЙДИИТАОИТМЫАМНСРТР»
Задание.
№4 Зашифровать собственные ФИО данным методом.
|
ИТ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ШТ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Метод «Штакетник» 3х-строчный
ИТ записывается в 3 строки и переписывается последовательно друг за другом.
ИТ «СИСТЕМНЫЙ АДМИНИСТРАТОР»Зашифровываем: С Т Н А И С А Р И Е Ы Д Н Т Т С С М Й М И Р О Т
ШТ «СТНАИСАРИЕЫДНТТССМЙМИРОТ»
Задание.
№5 Зашифровать собственные ФИО данным методом.
|
ИТ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ШТ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Шифры табличной маршрутной перестановки.
Широкое распространение получили шифры перестановки, использующие некоторую геометрическую фигуру (плоскую или объемную). Преобразования состоят в том, что в фигуру исходный текст вписывается по ходу одного маршрута, а выписывается по другому.
ИТ «ДОПОЛНИТЕЛЬНАЯ ИНФОРМАЦИЯ»
Заносим ИТ в последовательно в таблицу
|
Д |
О |
П |
О |
Л |
Н |
|
И |
Т |
Е |
Л |
Ь |
Н |
|
А |
Я |
И |
Н |
Ф |
О |
|
Р |
М |
А |
Ц |
И |
Я |
Зашифровываем начиная с левого верхнего угла, по диагонали, сверху вниз, справа налево ШТ «ДОИПТАОЕЯРЛЛИМНЬНАНФЦОИЯ»
Задание.
№6 Зашифровать собственные ФИО данным методом.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ШТ__________________________________________________________________
Шифры табличной маршрутной перестановки с ключом.
Ключ – «ОТДЕЛ» записываем в основание таблицы, нумеруем столбцы согласно алфавита. В таблицу вписываем ИТ «ОПЕРАЦИОННАЯ СИСТЕМА»
|
О |
Т |
Д |
Е |
Л |
|
4 |
5 |
1 |
2 |
3 |
|
О |
П |
Е |
Р |
А |
|
Ц |
И |
О |
Н |
Н |
|
А |
Я |
С |
И |
С |
|
Т |
Е |
М |
А |
Б |
Зашифровываем, переписывая столбцы ШТ «ЕОСМ РНИА АНСБ ОЦАТ ПИЯЕ»
Задание.
№7 Зашифровать собственные ФИО данным методом. Ключ взять из таблицы кодовых слов согласно порядковому номеру по классному журналу.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ШТ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
II. Шифры множественной перестановки.
В данном подклассе шифров используется идея повторного шифрования уже зашифрованного сообщения.
Шифр двойной перестановки. В таблицу по определенному маршруту записывается текст сообщения, затем переставляются столбцы, а потом переставляются строки. Шифрограмма выписывается по определенному маршруту.
Пример шифрования сообщения «АБРАМОВ+ДЯДИНА» показан на рис.1. Результат шифрования – «ОАБЯ+_АИВ_РДМНАД».
|
|
|
|
4 |
1 |
3 |
2 |
|
|
1 |
2 |
3 |
4 |
|
|
1 |
2 |
3 |
4 |
|
Маршрут вписывания |
|
3 |
А |
Б |
Р |
А |
|
3 |
Б |
А |
Р |
А |
|
1 |
О |
+ |
В |
М |
|
1 |
М |
О |
В |
+ |
|
1 |
О |
+ |
В |
М |
|
2 |
А |
_ |
_ |
Н |
||
|
4 |
Д |
Я |
Д |
И |
|
4 |
Я |
И |
Д |
Д |
|
3 |
Б |
А |
Р |
А |
||
|
2 |
Н |
А |
_ |
_ |
|
2 |
А |
_ |
_ |
Н |
|
4 |
Я |
И |
Д |
Д |
||
|
|
|
Исходная таблица |
|
Перестановка столбцов |
|
Перестановка строк |
||||||||||||
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
Маршрут выписывания |
||||||||||||
Рис. Пример использования шифра двойной перестановки
Ключом к шифру являются размеры таблицы, маршруты вписывания и выписывания, а также порядки перестановки столбцов и строк. Если маршруты являются фиксированными величинами, то количество ключей равно n!*m!, n и m – количество столбцов и строк в таблице.
Задание.
№8 Зашифровать собственные ФИО данным методом.
|
|
5 |
2 |
1 |
3 |
6 |
4 |
|
3 |
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
3 |
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
ШТ_________________________________________________________________
Задание.
№9 Расшифровать текст по таблице 15 столбцов по диагонали слева на право,снизу вверх :
«имтдаарутлаемиьвнсакяантлкнныасасийивркиноодитавйайрикшнмасииоафпофптаосррерлнпиеьоетзваоб»
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Контрольные вопросы к практической работе.
1.Продолжить фразу «Символы исходного текста зашифрованные методом перестановки меняют свое …, при этом сохраняя свое …» .
2.Продолжить фразу «Стойкость шифрования методом перестановки зависит от …».
3.Предложите методы усложнения методов шифрования перестановкой.