Задание на лабораторную работу
Лабораторная работа №3. Шифры перестановки (часть 2)
Теоретическая часть.
Шифр простой одинарной перестановки. Для шифрования и дешифрования используется таблица перестановок, аналогичная показанной на рис.1.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 2 | 4 | 1 | 7 | 6 | 5 | 3 |
Рис.1. Таблица перестановок
Например, если для шифрования исходного сообщения «АБРАМОВ» использовать таблицу, представленную на рис.1, то шифрограммой будет «РАВБОМА». Для использования на практике такой шифр не удобен, так как при больших значениях n приходится работать с длинными таблицами и для сообщений разной длины необходимо иметь свою таблицу перестановок.
Шифр блочной одинарной перестановки. При использовании этого шифра задается таблица перестановки блока символов, которая последовательно применяется до тех пор, пока исходное сообщение не закончится. Если исходное сообщение не кратно размеру блока, тогда оно при шифровании дополняется произвольными символами.
| 1 | 2 | 3 |
| 2 | 3 | 1 |
Рис.2. Таблица перестановок
Для примера выберем размер блока, равный 3, и примем таблицу перестановок, показанную на рис.2. Дополним исходное сообщение «АБРАМОВ» буквами Ь и Э, чтобы его длина была кратна 3. В результате шифрования получим «РАБОАМЭВЬ».
Количество ключей для данного шифра при фиксированном размере блока равно m!, где m – размер блока.
|
|
|
Шифр табличной маршрутной перестановки. Наибольшее распространение получили шифры маршрутной перестановки, основанные на таблицах. При шифровании в такую таблицу вписывают исходное сообщение по определенному маршруту, а выписывают (получают шифрограмму) - по другому. Для данного шифра маршруты вписывания и выписывания, а также размеры таблицы являются ключом.
Рис.3. Пример использования шифра маршрутной перестановки
Например, исходное сообщения «АБРАМОВ ИЛЬЯ СЕРГЕЕВИЧ» вписывается в прямоугольную таблицу размерами 4х6, маршрут вписывания – слева-направо сверху-вниз, маршрут выписывания – сверху-вниз слева-направо. Шифрограмма в этом случае выглядит «АВ_ЕБ_СВРИЕИАЛР ЧМЬГ_ОЯЕ_».
Шифр вертикальной перестановки. Является разновидностью предыдущего шифра. К особенностям шифра можно отнести следующие:
- количество столбцов в таблице фиксируется и определяется длиной ключа;
- маршрут вписывания - строго слева-направо сверху-вниз;
- шифрограмма выписывается по столбцам в соответствии с их нумерацией (ключом).
| Ключ | Д | Я | Д | И | Н | А |
| 2 | 6 | 3 | 4 | 5 | 1 | |
| Текст | А | Б | Р | А | М | О |
| В | _ | И | Л | Ь | Я | |
| _ | С | Е | Р | Г | Е | |
| Е | В | И | Ч | _ | _ |
Рис.4. Пример использования шифра вертикальной перестановки
|
|
|
В качестве ключа можно использовать слово или фразу. Тогда порядок выписывания столбцов соответствует алфавитному порядку букв в ключе. Например, если ключевым словом будет «ДЯДИНА», то присутствующая в нем буква А получает номер 1, Д – 2 и т.д. Если какая-то буква входит в слово несколько раз, то ее появления нумеруются последовательно слева направо. В примере первая буква Д получает номер 2, вторая Д – 3.
При шифровании сообщения «АБРАМОВ ИЛЬЯ СЕРГЕЕВИЧ» результат будет «ОЯЕ_АВ_ЕРИЕИАЛРЧМЬГ_Б_СВ».
Шифр «Поворотная решетка». В 1550 г. итальянский математик Джероламо Кардано, состоящий на службе у папы Римского, в книге «О тонкостях» предложил новую технику шифрования - решётку Кардано.
Изначально решетка Кардано представляла собой трафарет с прорезанными в нем отверстиями. В этих отверстиях на листе бумаги, который клали под решетку, записывались буквы, слоги и слова сообщения. Далее трафарет снимался, и свободное пространство заполнялось более или менее осмысленным текстом для маскировки секретного послания. Такой метод сокрытия информации относится к стеганографии.
|
|
|
Позднее был предложен шифр «поворотная решетка» или, как его еще называют, «решетка для вьющихся растений», поскольку она напоминала отверстия в деревянных решетках садовых строений. Этот шифр считают первым транспозиционным (геометрическим) шифром.
Несмотря на то, что между изначальным предложением Кардано и шифром «поворотная решетка» большая разница, методы сокрытия информации, основанные на использовании трафаретов, принято называть «решетками Кардано».
Для шифрования и дешифрования с помощью данного шифра изготовляется прямоугольный трафарет с четным количеством строк и столбцов. В трафарете вырезаются клетки таким образом, чтобы при наложении его на таблицу того же размера четырьмя возможными способами, его вырезы полностью покрывали все ячейки таблицы ровно по одному разу.
При шифровании трафарет накладывается на таблицу. В видимые ячейки таблицы выписываются буквы исходного текста слева-направо сверху-вниз. Далее трафарет поворачивается и вписывается следующая часть букв. Эта операция повторяется еще два раза. Шифрограмму выписывают из итоговой таблицы по определенному маршруту.
|
|
|
Таким образом, ключом при шифровании является трафарет, порядок его поворотов и маршрут выписывания.
Пример шифрования сообщения «АБРАМОВ+ДЯДИНА» показан на рис.5.8. Результат шифрования – «АДВ_МНРДБЯ+_ОААИ».
Рис.5. Пример использования шифра «поворотная решетка»
Данный метод шифрования применялся нидерландскими правителями для секретных посланий в 1740-x гr. Он также использовался в армии кайзера Вильгельма в Первую мировую войну. Для шифрования немцы использовали решетки разных размеров, которым французские криптоаналитики дали собственные кодовые имена: Анна (25 букв), Берта (36 букв), Дора (64 буквы) и Эмиль (81 буква). Однако использовались решетки очень недолго (всего четыре месяца) к огромному разочарованию французов, которые только-только начали подбирать к ним ключи.
Магические квадраты. Магическими квадратами называются квадратные таблицы со вписанными в их клетки последовательными натуральными числами начиная с 1, которые в сумме по каждому столбцу, каждой строке и каждой диагонали дают одно и то же число.
Впервые эти квадраты появились в Китае, где им и была приписана некоторая «магическая сила». По преданию, описанному в одной из пяти канонических книг Древнего Китая - Шу-Цзин (Книге записанных преданий), в 2200 году до н.э. из реки Ло вышла огромная черепаха (по другой версии - дракон), символ вечности. На ее панцире были видны пятна, образовывавшие удивительный рисунок.
Рис.6. Магический квадрат Ло Шу
Когда черепаха вышла из воды, высыхали лужи после недавнего ливня. Великий Юй взял эту черепаху и рассмотрел странный узор на ее панцире. Этот узор вдохновил его на создание трактата под названием «Хун Фань» («Великий план»), в котором говорилось о физике, астрологии, предсказаниях, морали, политике и религии.
Магические квадраты широко применялись для передачи секретной информации. При шифровании исходное сообщение вписывалось в квадрат по приведенной в них нумерации, после чего шифрограмма выписывалась по строкам. Количество возможных магических квадратов (ключей) быстро возрастает с увеличением их размера. Так, существует лишь один магический квадрат размером 3х3, если не принимать во внимание его повороты. Магических квадратов 4х4 насчитывается уже 880, а число магических квадратов размером 5х5 около 250000. Поэтому магические квадраты больших размеров могли быть хорошей основой для надежной системы шифрования того времени, потому что ручной перебор всех вариантов ключа для этого шифра был немыслим.
Рассмотрим квадрат размером 4х4. В него вписываются числа от 1 до 16. Его магия состоит в том, что сумма чисел по строкам, столбцам и полным диагоналям равняется одному и тому же числу - 34.
| 16 | 3 | 2 | 13 |
| 5 | 10 | 11 | 8 |
| 9 | 6 | 7 | 12 |
| 4 | 15 | 14 | 1 |
Рис.5.7. Магический квадрат 4х4
Шифрование по магическому квадрату производилось следующим образом. Например, требуется зашифровать фразу: «АБРАМОВДЯДИНА...». Буквы этой фразы вписываются последовательно в квадрат согласно записанным в них числам: позиция буквы в предложении соответствует порядковому числу. В пустые клетки ставится точка или любая буква.
| 16 . | 3 Р | 2 Б | 13 А |
| 5 М | 10 Д | 11 И | 8 Д |
| 9 Я | 6 О | 7 В | 12 Н |
| 4 А | 15 . | 14 . | 1 А |
Рис.5.8. Пример шифрования с помощью магического квадрата
После этого шифрованный текст записывается в строку (считывание производится слева-направо сверху-вниз, построчно) – «.РБАМДИДЯОВНА..А».
Шифр двойной перестановки. В таблицу по определенному маршруту записывается текст сообщения, затем переставляются столбцы, а потом переставляются строки. Шифрограмма выписывается по определенному маршруту.
Пример шифрования сообщения «АБРАМОВ+ДЯДИНА» показан на следующем рисунке. Результат шифрования – «ОАБЯ+_АИВ_РДМНАД».
Рис.5.9. Пример использования шифра двойной перестановки
Ключом к шифру являются размеры таблицы, маршруты вписывания и выписывания, а также порядки перестановки столбцов и строк. Если маршруты являются фиксированными величинами, то количество ключей равно n!*m!, n и m – количество столбцов и строк в таблице.
Несмотря на многоступенчатую процедуру шифрования, включая двойную перестановку, данный шифр может быть эквивалентно заменен шифром простой одинарной перестановки. На следующем рисунке приведена таблица эквивалентных одинарных перестановок для примера шифрования, приведенного на рис. 5.12.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| А | Б | Р | А | М | О | В | + | Д | Я | Д | И | Н | А | _ | _ |
| 15 | 3 | 11 | 7 | 13 | 1 | 9 | 5 | 16 | 4 | 12 | 8 | 14 | 2 | 10 | 6 |
| О | А | Б | Я | + | _ | А | И | В | _ | Р | Д | М | Н | А | Д |
Рис.5.10. Таблица эквивалентных одинарных перестановок
Аналогичную замену на шифр блочной одинарной перестановки можно выполнить и для других шифров: табличная маршрутная перестановка, «поворотная решетка», «магический квадрат» и др.
При оформлении отчета необходимо привести исходное сообщение (фамилию или фамилию и имя), таблицы, ключевые слова (выбираются произвольно), маршруты вписывания и выписывания, повороты решетки и зашифрованное сообщение.
Шифр «Перекресток» [43]. Для перемешивания букв могут использоваться фигуры специального вида. Один из таких способов носит название «перекресток». В приведенном ниже примере рисуют крестообразные фигуры в количестве, достаточном, чтобы разместить в них все буквы сообщения. Открытый текст записывают вокруг этих фигур заранее оговоренным способом - в нашем случае по часовой стрелке. Таким образом, сообщение «АБРАМОВ ИЛЬЯ СЕРГЕЕВИЧ» может выглядеть следующим образом:
Рис.5.11. Пример размещения открытого текста в шифре «Перекресток»
Буквы берутся построчно. Вначале берется оговоренное количество букв (N) из первой строки, затем удвоенное количество букв (2N) из второй и снова N букв из третьей строки. Например, при N = 3 шифрограмма будет выглядеть «БОЛАРМВИЬА_ЯСЕЧ_ЕГЕИ_РВ_».
Шифры с использованием треугольников и трапеций [43]. Помочь выполнить перестановки могут как треугольники, так и трапеции. Открытый текст вписывается в эти фигуры в соответствии с количеством слов и формой выбранной фигуры, которая может быть растянута или сжата, чтобы в ней поместилось сообщение. Для первой фигуры, треугольника, открытый текст записывается построчно от вершины до основания.
Рис.5.7. Пример использования шифра перестановки при вписывании в треугольник
Ниже записывается ключевое слово. Поскольку основание широкое, ключевое слово повторяется. Буквы строки с ключевым словом нумеруются последовательно согласно их алфавитному порядку. Зашифрованное сообщение выписывается по столбцам согласно выполненной нумерации. Таким образом, для открытого текста «АБРАМОВ ИЛЬЯ СЕРГЕЕВИ» и ключевого слова «ДЯДИНА» шифрограмма будет выглядеть «АМ_РВГРИЕЛВАЯЕБ_ЕИЬРС».
Задание на лабораторную работу
В лабораторной работе необходимо зашифровать свою фамилию (для первых двух шифров) или фамилию и имя (для остальных) с помощью следующих шифров:
- простой одинарной перестановки;
- блочной одинарной перестановки;
- табличной маршрутной перестановки;
- вертикальной перестановки;
- поворотной решетки;
- магический квадрат (размер квадрата - 4х4);
- двойной перестановки.
При оформлении отчета необходимо привести исходное сообщение (фамилию или фамилию и имя), таблицы, ключевые слова (выбираются произвольно), маршруты вписывания и выписывания, повороты решетки и зашифрованное сообщение.
Дополнительное задание. Зашифровать свою фамилию и имя с помощью шифров:
- шифра «Перекресток»;
- шифры с использованием треугольника.
Дата добавления: 2021-01-21; просмотров: 3512; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!