Эта статья входит в число добротных статей

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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

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

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

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

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

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

1 2 3 ... n
I_1 I_2 I_3 ... I_n

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

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

Скитала

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

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

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

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

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

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

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

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

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

Магический квадрат[править | править вики-текст]

Фрагмент гравюры Дюрера «Меланхолия»

Магический квадрат — это квадратная таблица n\times n, заполненная натуральными числами от 1 до n^2 таким образом, что сумма чисел в каждой строке, каждом столбце и на обеих диагоналях одинакова.

Магический квадрат 4 × 4, изображённый на гравюре Альбрехта Дюрера «Меланхолия», считается самым ранним в европейском искусстве[7]. Два средних числа в нижнем ряду указывают дату создания гравюры (1514).

Шифрование по магическому квадрату производится следующим образом. Буквы открытого текста вписываются последовательно в квадрат, причём позиция буквы в предложении соответствует номеру ячейки, в которую она ставится[8].

ОТКРЫТЫЙ ТЕКСТ: шифр перестановки
16. И 3. Ф 2. И 13. О
5. П 10. Т 11. А 8. Е
9. С 6. Е 7. Р 12. Н
4. Р 15. К 14. В 1. Ш

Выписывается шифрограмма построчно.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ОТКРЫТЫЙ ТЕКСТ: двойная перестановка
МАРШРУТ ВПИСЫВАНИЯ: слева - направо
МАРШРУТ ВЫПИСЫВАНИЯ: сверху - вниз
СТОЛБЦЫ: ( 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 к в д
КРИПТОГРАММА: аавркопйстндевняоед

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

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

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

  • А. П. Алферов, А. Ю. Зубов, А. С. Кузьмин, А. В. Черёмушкин. Основы криптографии. — Гелиос АРВ, 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.

Ссылки[править | править вики-текст]