5 Что такое шифрование методом перестановки

Шифр перестано́вки — это метод симметричного шифрования, в котором элементы исходного открытого текста меняют местами. Элементами текста могут быть отдельные символы (самый распространённый случай), пары букв, тройки букв, комбинирование этих случаев и так далее. Типичными примерами перестановки являются анаграммы. В классической криптографии шифры перестановки можно разделить на два класса:

  • Шифры одинарной (простой) перестановки — при шифровании символы открытого текста перемещаются с исходных позиций в новые один раз.
  • Шифры множественной (сложной) перестановки — при шифровании символы открытого текста перемещаются с исходных позиций в новые несколько раз.

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

Содержание

История [ править | править код ]

Точное время появления шифра перестановки не известно. Вполне возможно, что писцы в древности переставляли буквы в имени своего царя ради того, чтобы скрыть его подлинное имя или в ритуальных целях [1] .

Одно из древнейших известных нам шифровальных устройств — Скитала. Бесспорно известно, что скитала использовалась в войне Спарты против Афин в конце V века до н. э. [2] [3]

Прародителем анаграммы считают поэта и грамматика Ликофрона, который жил в Древней Греции в III веке до н. э. Как сообщал византийский автор Иоанн Цец, из имени царя Птоломея он составил первую из известных нам анаграмм: Ptolemaios — Аро Melitos, что в переводе означает «из мёда», а из имени царицы Арсинои — как «Ion Eras» (фиалка Геры) [4] .

Шифры простой перестановки [ править | править код ]

Как правило, при шифровании и дешифровании шифра простой перестановки используется таблица перестановок:

Первая строка — позиция символа в открытом тексте, вторая строка — позиция в шифрограмме. Таким образом, при длине сообщения n <displaystyle n> символов существует ровно n ! <displaystyle n! > ключей.

Шифры маршрутной перестановки [ править | править код ]

Широкое распространение получили так называемые маршрутные перестановки, использующие некоторую геометрическую фигуру (плоскую или объемную). Преобразования состоят в том, что отрезок открытого текста записывается в такую фигуру по некоторой траектории, а выписывается по другой траектории. Пример данного шифра — шифр Скиталы.

Шифр табличной маршрутной перестановки [ править | править код ]

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

приме
рмарш
рутно
йпере
стано
вки

Обращение описанных шагов не представит труда при расшифровании [5] .

Шифр вертикальной перестановки [ править | править код ]

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

31425
приме
рмарш
рутно
йпере
стано
вки

Заполнять последнюю строку таблицы «нерабочими» буквами нецелесообразно, так как криптоаналитик, получивший данную криптограмму, получает сведения о длине числового ключа [6] .

Шифр «поворотная решётка» [ править | править код ]

В 1550 году итальянский математик Джероламо Кардано (1501—1576) в книге «О тонкостях» предложил новую технику шифрования сообщений — решётку.

Изначально решётка Кардано представляла собой трафарет с отверстиями, в которые записывали буквы, слоги или слова сообщения. Затем трафарет убирали, а свободное место заполняли более или менее осмысленным текстом. Такой метод сокрытия информации относится к стеганографии.

Позднее был предложен шифр «поворотная решётка» — первый транспозиционный (геометрический) шифр. Несмотря на то, что существует большая разница между изначальным предложением Кардано и шифром «поворотная решётка», методы шифрования, основанные на трафаретах, принято называть «решётками Кардано».

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

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

Шифрограмму выписывают из получившейся таблицы по определённому маршруту. Ключом являются трафарет, маршрут вписывания и порядок поворотов.

Данный метод шифрования использовался для передачи секретной информации нидерландскими правителями в 1740-х годах. Во время Первой мировой войны армия кайзера Вильгельма использовала шифр «поворотная решётка». Немцы использовали решётки разных размеров, однако очень недолго (четыре месяца), к огромному разочарованию французских криптоаналитиков, которые только-только начали подбирать к ним ключи. Для решёток разных размеров французы придумали собственные кодовые имена: Анна (25 букв), Берта (36 букв), Дора (64 буквы) и Эмиль (81 буква) [1] [7] .

Шифры сложной перестановки [ править | править код ]

В данном классе шифров перестановки используется идея многократной перестановки символов или повторного шифрования уже зашифрованного сообщения.

Шифр двойной перестановки [ править | править код ]

При шифровании шифром двойной перестановки в таблицу по определённому маршруту записывается текст, затем переставляются столбцы и строки. Далее по определённому маршруту выписывается шифрограмма.

Ключом к шифру являются размер таблицы, маршруты вписывания и выписывания, порядки перестановки столбцов и строк. Если маршруты являются фиксированными величинами, то количество ключей равно n ! m ! <displaystyle n!m!> , где n <displaystyle n> и m <displaystyle m> — количество строк и столбцов в таблице [8] .

3142
3двой
2наяп
4ерес
1тано
5вка
12343вйдо2апня4рсее1аотн5ква
12341аотн2апня3вйдо4рсее5ква

Криптоанализ [ править | править код ]

При дешифровании текста используют частотные характеристики открытого текста. Однако для получения устойчивой картины длина послания должна быть существенно больше ключа. Одной из наиболее устойчивых характеристик осмысленного текста является отсутствие запретных биграмм (пара соседних букв). Например, биграммы «Ъ + Ь», «гласная + Ь», «пробел + Ь». Знание и использование частотной диаграммы открытого текста значительно упростит дешифрование шифра перестановки [9] .

Аатбаш, шифр Сцитала, решетка Кардано — известные способы скрыть информацию от чужих глаз. В классическом смысле шифр перестановки представляет собой анаграмму. Его суть заключается в том, что буквы открытого текста меняются по определенному правилу позициями. Иными словами, ключом шифра является смена очередности следования символов в открытом сообщении. Однако зависимость ключа от длины шифруемого текста породила множество неудобств для использования этого вида шифров. Но умные головы нашли интересные хитрые решения, которые описываются в статье.

Перевернутые группы

Для ознакомления с шифрованием методом перестановки упомянем один из простейших примеров. Алгоритм его заключается в разделение сообщения на n блоков, которые затем переворачиваются задом наперед и меняются местами. Рассмотрим пример.

  • "День уходил, и неба воздух темный".

Разделим это сообщение на группы. В данном случае n = 6.

  • "Деньух одили небав озд ухтем ный".

Теперь развернем группы, записав каждую с конца.

  • "хуьнед вабен дзо метху йын".

Переставим определенным образом местами.

  • "илидо метху йын хуьнед вабен дзо".

Для незнающего человека в таком виде сообщение представляет собой не более чем белиберду. Но, разумеется, тот, кому адресовано сообщение, ведает алгоритмом расшифровки.

Серединная вставка

Алгоритм данного шифрования немного сложнее шифрования методом перестановки:

  1. Разделить сообщение на группы с четным количеством символов.
  2. В середину каждой группы вставить дополнительные буквы.

Рассмотрим на примере.

"Земные твари уводил ко сну".

"Земн ыетв ариу води лкосну".

"Зеамн ыеабтв араиу воабди лкоасну".

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

Шифрограмма "Сэндвич"

Еще один занимательный и простой пример шифрования методом перестановки. Для его использования нужно открытый текст разделить на 2 половины и одну из них посимвольно вписать между букв другой. Покажем на примере.

  • "От их трудов; лишь я один, бездомный".

Разделим на половины с равным количеством букв.

Теперь запишем первую половину сообщения с большим интервалом между буквами.

  • "О т и х т р у д о в л и ш ь".

И в этих промежутках разместим буквы второй половины.

Наконец сгруппируем буквы в своего рода слова (необязательная операция).

  • "Оятои дхи тнрбуе дзодвол миншыьй".

Зашифровать текст этим методом очень легко. Полученную строку-белиберду непосвященному придется разгадывать некоторое время.

Перестановки по "маршруту"

Такое название получили шифры, широко применявшиеся в древности. Маршрутом в их построении выступала какая-либо геометрическая фигура. Открытый текст записывался в такую фигуру по определенной схеме, а извлекался по обратной ей. Например, одним из вариантов может быть запись в таблицу открытого текста по схеме: змейка ползает в ячейках по часовой стрелке, а зашифрованное сообщение составляется путем списывания столбцов в одну строку, с первого по последний. Это также является шифрованием методом перестановки.

Покажем на примере, как зашифровать текст. Попробуйте сами определить маршрут записи и маршрут составления шифрограммы.

"Приготовлялся выдержать войну".

Будем записывать сообщение в таблицу размерами 3×9 клеток. Размерность таблицы можно определить, исходя из длины сообщения, или использовать некоторую фиксированную таблицу несколько раз.

приготовл
редывясля
жатьвойну

Шифр будем составлять, начиная с правого верхнего угла таблицы.

Обращение описанных шагов не представляет труда. Достаточно просто сделать все наоборот. Данный способ является крайне удобным, потому что позволяет легко запомнить процедуру шифрования и расшифровки. А также он является интересным, потому что использовать для шифра можно любую фигуру. Например, спираль.

Вертикальные перестановки

Этот вид шифров также является вариантом маршрутной перестановки. Интересен он в первую очередь наличием ключа. Данный способ был широко распространен в прошлом и также использовал таблицы для шифрования. Сообщение записывается в таблицу обычным образом — сверху вниз, а шифрограмма выписывается по вертикалям, при этом соблюдается порядок, указанный ключом или паролем. Посмотрим на образец такого шифрования.

"И с тягостным путем, и с состраданьем"

Используем таблицу размерностью 4х8 клеток и запишем в нее наше сообщение обычным образом. А для шифровки используем ключ 85241673.

истягост
нымпутем
иссостра
даньем

Ключ приведен ниже.

85241673

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

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

Обратная расшифровка вертикальной перестановки

Вертикальная перестановка представляет интерес тем, что расшифровка сообщения не является простым следованием алгоритму от обратного. Тому, кто знает ключ, известно, сколько в таблице столбцов. Чтобы дешифровать сообщение, нужно определить число длинных и коротких строк в таблице. Это позволит определить начало, откуда начинать записывать шифрограмму в таблицу, чтобы прочитать открытый текст. Для этого разделим длину сообщения на длину ключа и получим 30/8=3 и 6 в остатке.

Таким образом, нам стало известно, что в таблице 6 длинных столбцов и 2 коротких, заполненных буквами не до конца. Посмотрев на ключ, мы видим, что шифрование началось с 5-го столбца, и он должен быть длинным. Так мы находим, что первые 4 буквы шифрограммы соответствуют пятому по счету столбцу таблицы. Теперь можно записать все буквы по местам и прочесть тайное послание.

Решетка Кардано

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

Трафарет Кардано изготавливается по следующему принципу: вырезанные ячейки при повороте на 90° не должны перекрывать друг друга. То есть после 4 поворотов трафарета вокруг своей оси прорези в нем не должны совпадать ни разу.

Используем для примера простую решетку Кардано (на рисунке ниже).

Используя этот трафарет, зашифруем фразу "О Музы, к вам я обращусь с воззваньем".

ОМ
У
ЗЫ
К
ВА
М

Заполняем ячейки трафарета буквами по правилу: сначала справа налево, а затем сверху вниз. Когда ячейки кончатся, поворачиваем трафарет на 90° по часовой стрелке. Таким способом получаем следующую таблицу.

Я
ОБР
АЩ
у
СЬ

И еще раз поворачиваем на 90°.

С
ВО
З
ВА
Н
ЬЕ

И последний поворот.

После объединения 4 таблиц в одну получаем итоговое зашифрованное послание.

ЯОММГС
ВОУБОР
ГЗАЗЩЫ
ВГКГАУ
ГВГНГА
МСЬЬЕГ

Хотя послание может остаться и таким, но для передачи удобнее будет получить привычную на вид шифрограмму. Для этого пустые ячейки можно заполнить случайными буквами и выписать столбцы в одну строку:

  • "ЯВГВГМ ООЗГВС МУАКГЬ МБЗГНЬ ГОЩАГЕ СРЫУАГ"

Для того чтобы расшифровать это послание, получатель должен обладать точной копией трафарета, который был использован для шифрования. Данный шифр долгое время считался достаточно устойчивым. Также у него существует множество вариаций. Например, применение сразу 4 решеток Кардано, каждая из которых вращается своим образом.

Анализ шифров перестановки

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

Этот метод заключается в том, что символы шифруемого текста переставляются по определенным правилам внутри шифруемого блока символов. Рассмотрим некоторые наиболее часто встречающиеся разновидности этого метода, которые могут быть использованы в автоматизированных системах.

Самая простая перестановка — написать исходный текст задом наперед и одновременно разбить шифрограмму на пятерки букв. Например, из фразы:

ПУСТЬ БУДЕТ ТАК, КАК МЫ ХОТЕЛИ,

получится такой шифртекст:

ИЛЕТО ХЫМКА ККАТТ ЕДУБЬ ТСУП

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

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

ОИЛЕТ ОХЫМК АККАТ ТЕДУБ ЬТСУП

Кажется ничего сложного, но при расшифровке возникнут серьезные неудобства.

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

После этого вертикальные столбцы по порядку писали в строку с разбивкой на пятерки букв:

ПКУМС ЫТХЬО БТУЕД ЛЕИТК ТЛАМК НКОАП

Вариант этого шифра: сначала исходную фразу записать в столбики:

Потом разбить строки на пятерки букв:

ПСЬУЕ ТКАМХ ТЛАВД УТБДТ АККЫО ЕИБГЕ

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

Для примера возьмем решетку 6х6 (причем количество строк может увеличиваться или уменьшаться в зависимости от длины исходного сообщения) и заполним ее по строкам:

Если шифровать по стрелкам (диагоналям) сверху вниз с левого верхнего угла, то в итоге получится такая шифрограмма:

П УУ СДК ТЕКХ ЬТАОА БТКТБМ АМЕВЛ ЫЛГК ИДИ ЕЗ Ж

Для окончательного оформления шифртекст может быть разбит на группы по 6 символов:

ПУУСДК ТЕКХЬТ АОАБТК ТБМАМЕ ВЛЫЛГК ИДИЕЗЖ

Очень часто используют перестановки с ключом. Тогда правила заполнения решетки и шифрования из нее упрощаются, становятся стандартными. Единственное, что надо помнить и знать — это ключ, которым может быть любое слово, например, РАДИАТОР. В соответствии с расположением букв в алфавите, буква А получает номер 1, вторая буква А — 2, следующая по алфавиту буква Д — 3, потом И — 4, О – 5; первая буква Р — 6, вторая Р — 7 и буква Т — 8. Заполняем решетку:

Оцените статью
Ремонт оргтехники
Добавить комментарий