Перестановки: скитала, забор, столбцы

Спарта, конец V века до нашей эры. Полководец Лисандр воюет далеко за морем, у берегов Малой Азии. Однажды к нему прибывает гонец и передаёт узкую кожаную ленту, исписанную буквами. Прочесть её нельзя: буквы стоят вперемешку, слов не видно. Лисандр берёт свою палочку — точно такую же, как та, что осталась в Спарте у правителей-эфоров, — наматывает на неё ленту виток к витку, и вдоль палочки складываются строки. Приказ короткий: немедленно вернуться домой.

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

Две большие семьи шифров

В первых уроках мы меняли буквы: Цезарь сдвигал алфавит, простая замена подставляла вместо каждой буквы другую. Такие шифры называют шифрами замены. Буква «А» превращается во что-то другое, но стоит на своём месте.

Шифры перестановки делают наоборот. Каждая буква остаётся самой собой, зато переезжает на другое место. Слово «ШИФР» может стать «ФРШИ» или «ИШРФ». Ключ здесь — не таблица замен, а правило, по которому буквы перемешивают. Зная правило, их можно вернуть по местам.

Вот самый простой пример, который каждый придумывал в детстве: написать слово задом наперёд. «Встреча» — «ачертсВ». Это тоже перестановка, только очень слабая: правило одно на всех, и ключа нет вовсе. Настоящий шифр перестановки прячет правило в ключе, который знают только двое.

Скитала: ключ, который можно подержать в руках

Устройство скиталы очень простое. Берётся палочка, на неё по спирали наматывается узкая лента, виток к витку, без зазоров. Потом вдоль палочки пишут сообщение: строка за строкой, поворачивая палочку после каждой строки. Ленту снимают — и буквы расходятся по ней вразбивку. На ленте рядом оказываются буквы из разных строк.

Чтобы прочесть, нужна палочка той же толщины. На толстой палочке один виток вмещает больше букв, на тонкой — меньше. Если толщина не совпала, буквы одной строки ложатся наискосок и смешиваются с соседними. Совпала — и строки встают на место. Значит, ключ скиталы — толщина палочки, а точнее, сколько букв приходится на один её оборот.

Присмотритесь к ленте. Каждый виток — это несколько букв подряд, и из каждого витка к вам повёрнута ровно одна. Строка, которую вы видите на палочке, — это каждая четвёртая (или пятая, или третья) буква ленты. Вот и весь секрет: скитала читает ленту через шаг, а шаг задаётся толщиной.

Отсюда видно и слабое место. Разумных толщин немного: на палочку в руку толщиной помещается от двух до десятка букв. Противник, перехвативший ленту, может намотать её на конус — палочку, которая постепенно утолщается, — и просто сдвигать ленту вдоль него, пока буквы не сложатся в слова. Даже без конуса хватит карандаша и бумаги: выписать каждую вторую букву, каждую третью, каждую четвёртую… Это тот же перебор ключей, что ломал шифр Цезаря.

«Забор»: текст зигзагом

Скитала требует палочки. Но ту же идею — читать текст через шаг — можно воплотить на бумаге. Самый известный бумажный вариант называется шифром «забор», по-английски rail fence, «изгородь из жердей».

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

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

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

Столбцы и ключевое слово

У «забора» и скиталы ключ — число, и чисел мало. Следующий шаг напрашивается сам: сделать ключом не число, а порядок. Так устроена столбцовая перестановка — рабочая лошадка военных шифровальщиков XIX и XX века.

Договоримся о ключевом слове, например «ЗАМОК». Пишем его буквы в строку — это заголовки столбцов. Под ними строка за строкой записываем сообщение, по одной букве в клетку. Теперь нумеруем столбцы по алфавиту букв ключа: А раньше всех — это первый столбец, за ней З — второй, К — третий, М — четвёртый, О — пятый. И выписываем столбцы в этом порядке, каждый сверху вниз.

Скитала — частный случай этого шифра: столбцы читаются по порядку, слева направо, без всякого ключевого слова. Ключевое слово добавляет к ней перемешивание столбцов. Если в ключе пять разных букв, порядков 120; если семь — уже 5040. Само слово при этом не важно, важен только порядок, который оно задаёт: «ЗАМОК» и, скажем, «ВБЕЖГ» дают одну и ту же шифровку.

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

Как ломают перестановку

Представьте, что вы в «чёрном кабинете» и на стол легла перехваченная шифровка. Первый вопрос — что перед вами, замена или перестановка? Ответ даёт простой подсчёт букв. В перестановке буквы те же, что в открытом тексте, поэтому частоты как у обычного языка: много О, Е, А, Н, Т, мало Ф, Щ, Ъ. Если картина такая — значит, буквы просто перетасовали, и дальше нужно искать маршрут.

Второй шаг — угадать форму таблицы. Длина шифровки подсказывает, сколько может быть столбцов: 24 буквы ложатся в 4 столбца по 6 или в 6 по 4, и так далее. Если последняя строка была неполной, вариантов больше, но не намного.

Третий шаг — самый красивый. Шифровку режут на куски-столбцы и выписывают каждый кусок на отдельную полоску бумаги. Потом полоски двигают и прикладывают друг к другу, глядя на пары букв, которые получаются в строках. Если рядом стоят СТ, НО, ЕН, ПР — полоски, скорее всего, соседи. Если ЪЫ или ЙЬ — точно нет. Пара за парой, полоска за полоской, и столбцы встают в нужный порядок. Этот приём называют анаграммированием: вы ищете перестановку, при которой буквы снова складываются в слова.

Компьютер делает то же самое, только быстрее. Для короткого ключа он просто пробует все порядки столбцов, а каждый результат оценивает по тому, сколько в нём привычных сочетаний букв. Так работает блок «Если ключ неизвестен» в утилите «Перестановка по столбцам»: для ключей до семи букв он проверяет 5912 порядков и почти всегда ставит правильный первым.

Что взять с собой

• Шифры делятся на две большие семьи: замена меняет буквы, перестановка — их порядок.
• Скитала читает ленту через шаг; её ключ — толщина палочки, то есть число букв на оборот. «Забор» пишет текст зигзагом, его ключ — число рельсов.
• Столбцовая перестановка делает ключом порядок столбцов, заданный ключевым словом. Для пяти столбцов это 120 вариантов, для семи — 5040.
• Перестановку выдают частоты букв: они как у обычного языка. Взламывают её, подбирая маршрут, при котором соседние буквы снова складываются в привычные пары.

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