Перестановочный шифр

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

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

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

ИсторияПравить

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

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

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

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

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

$\text{[math]}$ $\text{[math]}$ $1$	$\text{[math]}$ $\text{[math]}$ $2$	$\text{[math]}$ $\text{[math]}$ $3$	...	$\text{[math]}$ $\text{[math]}$ $n$
$\text{[math]}$ $\text{[math]}$ $I_{1}$	$\text{[math]}$ $\text{[math]}$ $I_{2}$	$\text{[math]}$ $\text{[math]}$ $I_{3}$	...	$\text{[math]}$ $\text{[math]}$ $I_{n}$

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

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

Скитала

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

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

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

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

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

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

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

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

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

ОТКРЫТЫЙ ТЕКСТ: пример маршрутной перестановки
КЛЮЧ:           (3, 1, 4, 2, 5)

3	1	4	2	5
п	р	и	м	е
р	м	а	р	ш
р	у	т	н	о
й	п	е	р	е
с	т	а	н	о
в	к	и

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

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

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

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

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

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

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

Четыре позиции решётки

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

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

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

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

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

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

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

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

Ключом к шифру являются размер таблицы, маршруты вписывания и выписывания, порядки перестановки столбцов и строк. Если маршруты являются фиксированными величинами, то количество ключей равно $\text{[math]}$ $\text{[math]}$ $n! m!$ , где $\text{[math]}$ $\text{[math]}$ $n$ и $\text{[math]}$ $\text{[math]}$ $m$ — количество строк и столбцов в таблице^[8].

ОТКРЫТЫЙ ТЕКСТ: двойная перестановка
МАРШРУТ ВПИСЫВАНИЯ: слева - направо
МАРШРУТ ВЫПИСЫВАНИЯ: сверху - вниз
СТОЛБЦЫ: ( 3, 1, 4, 2)
СТРОКИ: ( 3, 2, 4, 1, 5)

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

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

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

КРИПТОГРАММА: аавркопйстндевняоеа

КриптоанализПравить

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

ПримечанияПравить

↑ ¹ ² Фред Б. Риксон, 2011.
↑ Фукидид. История I 131, 1.
↑ Дориченко, 1994, с. 16—17.
↑ Lives of the Hellenistic Poets Архивная копия от 20 января 2008 на Wayback Machine // Attalus: Sources for Greek and Roman history. (англ.)
↑ Алферов, 2002, с. 96.
↑ Алферов, 2002, с. 97.
↑ Бабаш, 2007.
↑ Алферов, 2002.
↑ Бабаш, 2007, с. 136.

ЛитератураПравить

А. П. Алферов, А. Ю. Зубов, А. С. Кузьмин, А. В. Черёмушкин. Основы криптографии. — Гелиос АРВ, 2002. — ISBN 5-85438-137-0.
А. В. Бабаш, Г. П. Шанкин. Криптография. — М. СОЛОН-ПРЕСС, 2007. — ISBN 5-93455-135-3.
Фред Б. Риксон. Коды, шифры, сигналы и тайная передача информации. — Астрель, 2011. — ISBN 978-5-17-074391-9.
Дориченко С. А., Ященко В. В. 25 этюдов о шифрах: Популярно о современной криптографии. — Теис, 1994. — ISBN 5-7218-0014-3.

[_b367f47666e5af99-1] ¹ ² Фред Б. Риксон, 2011.

[2] Фукидид. История I 131, 1.

[_e823cf9a8c5488e0-3] Дориченко, 1994, с. 16—17.

[4] Lives of the Hellenistic Poets Архивная копия от 20 января 2008 на Wayback Machine // Attalus: Sources for Greek and Roman history. (англ.)

[_25e1b436675ef03e-5] Алферов, 2002, с. 96.

[_25e1b436675ef03f-6] Алферов, 2002, с. 97.

[_98c250bb1c5e6cb9-7] Бабаш, 2007.

[_c10e46e2c5c3fa1b-8] Алферов, 2002.

[_87be9208a20c9641-9] Бабаш, 2007, с. 136.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

3	1	4	2	5
п	р	и	м	е
р	м	а	р	ш
р	у	т	н	о
й	п	е	р	е
с	т	а	н	о
в	к	и

3	1	4	2	5
п	р	и	м	е
р	м	а	р	ш
р	у	т	н	о
й	п	е	р	е
с	т	а	н	о
в	к	и

3	1	4	2	5
п	р	и	м	е
р	м	а	р	ш
р	у	т	н	о
й	п	е	р	е
с	т	а	н	о
в	к	и