Маршрутные перестановки. Шифр вертикальной перестановки[править

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Записываем столбики в соответствии с номерами букв ключа:

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

Затем последовательность опять разбивается на пятерки:

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

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

Развитием этого шифра является шифр перестановки колонок с пропусками, которые располагаются в решетке тоже в соответствии с ключом (в нашем случае через 6-1-3-4-2-8-5-7 ... символов):

Шифрограмма будет такой:

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

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

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

ОТКРЫТЫЙ ТЕКСТ: пример маршрутной перестановки

КЛЮЧ: (3, 1, 4, 2, 5)

КРИПТОГРАММА: рмупткмрнрнпррйсвиатеаиешоео

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

Шифр вертикальной перестановки. Является разновидностью предыдущего шифра. К особенностям шифра можно отнести следующие:

Количество столбцов в таблице фиксируется и определяется длиной ключа;

Маршрут вписывания - строго слева-направо сверху-вниз;

Шифрограмма выписывается по столбцам в соответствии с их нумерацией (ключом).

Рис.5.5. Пример использования шифра вертикальной перестановки

В качестве ключа можно использовать слово или фразу. Тогда порядок выписывания столбцов соответствует алфавитному порядку букв в ключе. Например, если ключевым словом будет «ДЯДИНА», то присутствующая в нем буква А получает номер 1, Д – 2 и т.д. Если какая-то буква входит в слово несколько раз, то ее появления нумеруются последовательно слева направо. В примере первая буква Д получает номер 2, вторая Д – 3.

При шифровании сообщения «АБРАМОВ ИЛЬЯ СЕРГЕЕВИЧ» результат будет «ОЯЕ_АВ_ЕРИЕИАЛРЧМЬГ_Б_СВ».

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

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

Шифрование простой перестановкой (вертикальной перестановкой) осуществляется следующим образом:

1) выбирается ключевое слово с неповторяющимися символами;

2) шифруемый текст записывается последовательными строками под символами ключевого слова;

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

В качестве иллюстрации приведем пример шифрования способом простой перестановки сообщения: «БУДЬТЕ ОСТОРОЖНЫ С ПРЕДСТАВИТЕЛЕМ ФИРМЫ "ФЕНИКС". При этом применим цифровой ключ 5 – 8 – 1 – 3 – 7 – 4 – 6 – 2. В исходном тексте вместо пробелов используется буква а.

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

ДО ВФ НОЫСЕ ЬРП ИИИЕЖ ЕЕМСБ С ТМФ НДЛЫ TOPT РКУТС A E .

Расшифрование выполняется в следующем порядке:

1) подсчитываем число знаков в зашифрованном тексте и делим на число знаков ключа;

2) выписываем ключевое слово и под его знаками в соответствующей последовательности выписываем символы зашифрованного текста в определенном выше количестве;

3) по строкам таблицы читаем исходный текст.

Число ключей не более m!, где m - число столбцов таблицы.

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

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

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

Зашифрованный текст будет выглядеть так: ДОПР БСВИК РРТМ ОЫ Н ЕНСЕФ УТ И СС АФ И ЬОЕ ЕЫ Т МЕ ТЖ ДЛ .

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

Еще один вариант - шифр "Поворотная решетка" . предназначен для сообщений длины 4mk. Берется трафарет размером 2m*2k клеток, вырезается m*k клеток так, что при наложении его на лист бумаги того же размера 4 различными способами (поворачивая на 90°) его вырезы полностью покрывают всю площадь листа. Буквы сообщения последовательно вписываются в вырезы трафарета по строкам, в каждой строке слева направо, при каждом из 4-х его возможных положений в заранее установленном порядке. Число возможных трафаретов, т.е. количество ключей этого шифра составляет 4 mk (при размере трафарета 8*8 число вариантов превосходит 4 миллиарда).

Весьма высокую стойкость шифрования можно обеспечить усложнением перестановок по маршрутам типа гамильтоновских. При этом для записи символов шифруемого текста используются вершины некоторого гиперкуба, а знаки зашифрованного текста считываются по маршрутам Гамильтона, причем используется несколько различных маршрутов. Для примера рассмотрим шифрование по маршругам Гамильтона при n =3. Структура и три маршрута показаны на Рис. 7, а пример шифрования – на Рис. 8.

История

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

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

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

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

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

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

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

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

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

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

КРИПТОГРАММА: ешоеомрнрниатеаирмупткпррйсв

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

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

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

ОТКРЫТЫЙ ТЕКСТ: пример маршрутной перестановки

КЛЮЧ: (3, 1, 4, 2, 5)

КРИПТОГРАММА: рмупткмрнрнпррйсвиатеаиешоео

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

Шифр «поворотная решётка

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• "Гусетмснтмаяпоьсысаоттмсеринид".

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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