Шифр перестановки
Шифр перестановки — это класс криптографических методов, при которых символы открытого текста меняются местами по определённому правилу, но сами символы остаются неизменными. В отличие от шифров замены, где буквы заменяются на другие символы, в шифрах перестановки сохраняется алфавит исходного сообщения, но изменяется порядок следования знаков. Такие шифры относятся к симметричным криптосистемам, где для зашифрования и расшифрования используется один и тот же ключ.
История
Шифры перестановки известны с глубокой древности. Одним из первых исторически зафиксированных примеров является скитала — шифровальный прибор, использовавшийся в Древней Греции (V век до н. э.). Он представлял собой цилиндр определённого диаметра, на который наматывалась полоска пергамента. Текст писали вдоль оси цилиндра, после чего полоску снимали — буквы оказывались переставленными. Расшифровать сообщение можно было только с помощью цилиндра того же диаметра.
В Средние века шифры перестановки применялись в дипломатической переписке и военном деле. В эпоху Возрождения итальянский архитектор и криптограф Леон Баттиста Альберти в трактате «О шифрах» (1466 год) описал несколько методов перестановки, включая решётку Кардано — трафарет с прорезями, через который писали текст, а затем заполняли пустые места.
В XIX—XX веках, с развитием телеграфа и радио, шифры перестановки стали использоваться в комбинации с шифрами замены для создания более стойких систем (например, в шифровальных машинах «Энигма» и «Лоренц»). В современной криптографии перестановки применяются как один из этапов в блочных шифрах (например, в алгоритме AES — Advanced Encryption Standard).
Классификация
Шифры перестановки делятся на несколько основных типов в зависимости от способа изменения порядка символов.
### Простая перестановка
Самый простой метод — запись текста в таблицу по строкам, а затем чтение по столбцам в заданном порядке. Ключом выступает размер таблицы (количество строк и столбцов) и порядок считывания столбцов. Например, сообщение «ПРИВЕТ» при записи в таблицу 2×3 и чтении по столбцам может дать «ПВИРЕТ».
### Перестановка с ключом
Используется ключевое слово, которое определяет порядок перестановки столбцов или строк. Ключ записывается над таблицей, его буквы нумеруются по алфавитному порядку. Затем столбцы таблицы переставляются в соответствии с этими номерами. Например, для ключа «КЛЮЧ» буквы нумеруются как К=1, Л=2, Ю=3, Ч=4, и столбцы меняются местами согласно этой последовательности.
### Решётка Кардано
Трафарет с прорезями, который накладывается на лист бумаги. В прорези вписываются буквы открытого текста, затем решётку поворачивают (обычно на 90 градусов) и вписывают следующие буквы. После заполнения всех прорезей в четырёх положениях получается шифротекст. Расшифрование возможно только при наличии такой же решётки.
### Маршрутная перестановка
Текст записывается в таблицу по определённому маршруту (например, «змейкой» по строкам, по спирали, по диагонали), а затем считывается по другому маршруту. Ключом является форма таблицы и порядок обхода. Этот метод использовался в некоторых шифрах Первой мировой войны.
### Двойная перестановка
Применяется дважды — сначала переставляются столбцы, затем строки (или наоборот). Это значительно увеличивает стойкость, так как количество возможных ключей растёт экспоненциально. Например, для таблицы 5×5 с двойной перестановкой число вариантов составляет (5! × 5!) = 14400.
Устройство и принцип работы
Любой шифр перестановки можно описать математически как биективное отображение множества позиций символов открытого текста на множество позиций шифротекста. Формально, если открытый текст состоит из n символов, то шифр перестановки задаёт перестановку σ из симметрической группы S<sub>n</sub>. Зашифрование: c<sub>i</sub> = m<sub>σ(i)</sub>, расшифрование: m<sub>i</sub> = c<sub>σ⁻¹(i)</sub>, где m — открытый текст, c — шифротекст.
Ключом шифра является либо сама перестановка σ, либо правило, по которому она вычисляется (например, размер таблицы, ключевое слово, форма решётки). Для практического использования ключ должен быть известен обеим сторонам и храниться в секрете.
Применение
Шифры перестановки находят применение в различных областях:
- Криптография: как самостоятельный метод для защиты сообщений (например, в классических шифрах), так и в составе современных алгоритмов (например, в блочных шифрах для перемешивания битов).
- Стеганография: перестановка может использоваться для скрытия факта передачи сообщения, если текст записывается в виде таблицы, а затем считывается в другом порядке, маскируясь под случайный набор символов.
- Компьютерные науки: перестановки применяются в алгоритмах сортировки, хеширования и генерации псевдослучайных последовательностей.
- Логические игры и головоломки: шифры перестановки лежат в основе многих криптографических задач и ребусов.
Криптостойкость
Стойкость шифров перестановки зависит от длины сообщения и сложности ключа. Для коротких сообщений (до 10–15 символов) возможен полный перебор всех перестановок, что делает такие шифры уязвимыми. Для длинных сообщений (сотни символов) число вариантов становится астрономическим, однако существуют методы криптоанализа, основанные на частотном анализе биграмм и триграмм: в перестановках сохраняются частоты отдельных букв, но нарушаются естественные сочетания.
Наиболее эффективным методом взлома является атака на основе известного открытого текста: если злоумышленник знает часть сообщения, он может восстановить перестановку. Для повышения стойкости шифры перестановки часто комбинируют с шифрами замены (например, в шифре Виженера или в современных блочных шифрах).
Примеры
Пример 1: Простая столбцовая перестановка
Открытый текст: «КРИПТОГРАФИЯ» (12 букв). Записываем в таблицу 3×4:
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | К | Р | И | П |
| 2 | Т | О | Г | Р |
| 3 | А | Ф | И | Я |
Считываем по столбцам в порядке 2, 4, 1, 3: «РФРПЯКАТИГИ». Шифротекст: «РФРПЯКАТИГИ».
Пример 2: Перестановка с ключом
Ключ: «КЛЮЧ» (4 буквы). Нумерация по алфавиту: К=1, Л=2, Ю=3, Ч=4. Открытый текст: «ШИФРПЕРЕСТАНОВКИ» (16 букв). Записываем в таблицу 4×4:
| 1 (К) | 2 (Л) | 3 (Ю) | 4 (Ч) | |
|---|---|---|---|---|
| 1 | Ш | И | Ф | Р |
| 2 | П | Е | Р | Е |
| 3 | С | Т | А | Н |
| 4 | О | В | К | И |
Переставляем столбцы в порядке ключа: 1, 2, 3, 4 (без изменений). Считываем по строкам: «ШИФРПЕРЕСТАНОВКИ». Если бы ключ был, например, «ЧЮЛК» (Ч=4, Ю=3, Л=2, К=1), то столбцы переставлялись бы в порядке 4, 3, 2, 1, и шифротекст был бы «РФИШЕРЕПНАТСИКОВ».
Интересные факты
- В Древнем Риме шифры перестановки использовались для передачи военных приказов. Историк Полибий описывал систему, где буквы записывались в таблицу 5×5, а затем считывались по координатам.
- В 1917 году американский криптограф Уильям Фридман разработал метод двойной перестановки, который использовался в шифровальной системе M-94 армии США.
- Современный стандарт шифрования AES (Advanced Encryption Standard) включает этап перестановки байтов (ShiftRows), который является разновидностью маршрутной перестановки.
- Шифры перестановки лежат в основе некоторых головоломок, например, «криптограммы» в газетах, где нужно восстановить порядок букв в зашифрованной фразе.
Источники
- Кан, Д. «Взломщики кодов» (The Codebreakers), 1967.
- Шнайер, Б. «Прикладная криптография», 1996.
- Молдовян, А. А., Молдовян, Н. А. «Криптография: от примитивов до синтеза алгоритмов», 2004.
- Сингх, С. «Книга шифров» (The Code Book), 1999.
- Материалы лекций по криптографии Московского государственного университета им. М. В. Ломоносова.
BFOmetr — база данных и аналитика по компаниям России.
На главную BFOmetr →