Метод вертикальной перестановки. Шифры замены (подстановки) и перестановки

Блочные шифры

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

Одноключевые блочные шифры подразделяются на 3 группы:

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

Шифры замены (подстановки)

Составные шифры.

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

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

Пример простейшего шифра перестановки представлен на рис. 5.5.

Рис. 5.5. Простейший шифр перестановки.

Как видно из рис. 5.5, для того чтобы зашифровать сообщение «ЮСТАС АЛЕКСУ ВСТРЕЧАЙТЕ СВЯЗНОГО», последнее необходимо записать в виде таблицы, состоящей, например, их 5 строк и 6 столбцов. Текст сообщения записы­вается по столбцам, исключая пробелы. Если последний стол­бец оказывается неполным, он заполняется произвольно лю­быми буквами. Для получения зашифрованного сообщения ис­ходный текст считывается по­строчно (слева направо) и за­писывается группами, напри­мер, по 5 цифр. Последняя

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

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

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

«ЗАСЕДАНИЕ СОСТОИТСЯ ЗАВТРА ЮСТАС».

Для шифрования этого открытого текста запишем его без пробелов (уча­стие последних в процедуре шифрования, из-за их высокой частоты повто­рения, значительно ослабляет криптостойкость шифра) и выберем ключ шифрования, например, 245 136. Согласно этому ключу, состоящему из 6 цифр, поделим все информационное сообщение на блоки, каждый из кото­рых будет содержать по 6 букв текста. После деления на блоки у нас полу­чилось 4 блока, содержащих по 6 букв в каждом, и 1 блок - по 5 букв. В таких случаях последняя группа букв исходного сообщения произвольно дополняется различными символами до получения полного блока. В на­шем случае не достает только одной буквы, поэтому выбираем любую букву, например Ъ, и добавляем ее в конце пятого блока.

Рис. 5.6. Шифр простой перестановки

Далее, используя ключ 245 136, производится перестановка букв исходно­го открытого текста. Например, первая цифра ключа - 2, указывает на то, что в новом блоке первой буквой зашифрованного текста будет вторая буква бло­ка открытого текста, вторая цифра ключа - 4, показывает, что вторая буква шифротекста - это четвертая буква в блоке открытого текста и т. д.

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

Для упрощения запоминания ключа обычно используется ключевое слово. В данном случае - это слово «КОРЕНЬ». В нем цифре 1 ключа соответ­ствует буква Е, так как она первой из всех букв этого слова встречается в нашем алфавите, цифре 2 - буква К (по той же причине) и т. д.

То же сообщение можно зашифровать с использованием таблицы, состоя­щей, например, из 5 строк и 6 столбцов (по длине ключевого слова). Исход­ный текст записывается по столбцам и образует таблицу (рис. 5.7). Ключевое слово задает правило перестановки столбцов. Если в ключевом слове встре­чаются одинаковые буквы, то они нумеруются по порядку слева направо. По­лученный второй шифротекст, как это видно из рис. 5.7, совершенно не похож на первый.

Рис. 5.7. Шифрование с помощью таблицы

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

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

Шифр простой перестановки с использованием свойств таблиц, назы­ваемых магическими квадратами (рис. 5.8), использовался еще в средние века. Магическими квадратами называются равносторонние таблицы, все клетки которых заполнены натуральными числами, начиная от 1. При­чем эти числа в сумме дают по каждому столбцу, по каждой строке и по диагоналям магического квадрата одно и тоже число (в нашем случае - это число 34). Исходный текст - ЖДУ ВСТРЕЧИ ЮСТАС, при заполне­нии магического квадрата, вписывается по порядку следования натураль­ных чисел, например, число 1 заменялось 1 буквой исходного текста (Ж), число 12 - 12 буквой сообщения (С) и т.п. После записи открытого тек­ста содержимое таблицы считывается по строкам в результате чего и получался шифротскст с перестановкой букв.

Рис. 5.8. Магический квадрат

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

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

Зашифруем указанным выше способом фразу пример маршрутной перестановки, используя прямоугольную табли­цу размером 4х7:

Зашифрованная фраза выглядит следующим образом:

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

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

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

Пример (вертикальной перестановки)

Зашифруем фразу вот пример шифра вертикальной пере­становки, используя прямоугольник размером 6 х 7 и число­вой ключ (5,1,4,7,2,6,3).

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

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

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

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

В нашем примере 38=7×5+3, поэтому в заполненной таблице имеется 3 длинных и 4 коротких столбца.

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

История

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

Одно из древнейших известных нам шифровальные устройство - Скитала. Бесспорно известно, что скитала использовалась в войне Спарты против Афин в конце 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 столбцов и m строк и ключевая последовательность, которая формируется из натурального ряда чисел 1,2,...,n случайной перестановкой.

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

Шифруемый текст записывается последовательными строками под числами ключевой последовательности, образуя блок шифрования размером n*m.

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

Заполняется новый блок и т.д.

Например, зашифруем текст

ГРУЗИТЕ_АПЕЛЬСИНЫ_БОЧКАХ

блоком размером 8*3 и ключом 5-8-1-3-7-4-6-2.

Таблица простой перестановки будет иметь вид:

Зашифрованное сообщение:

УЕБ_НХЗЛОЕСЛГАЫЕИАИЬЧРП_

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

Из зашифрованного текста выделяется блок символов размером n*m.

Этот блок разбивается на n групп по m символов.

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

Выделяется новый блок символов и т.д.

Перестановка, усложненная по таблице

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

При шифровании текста в неиспользуемые элементы не заносятся символы текста и в зашифрованный текст из них не записываются никакие символы - они просто пропускаются. При расшифровке символы зашифрованного текста также не заносятся в неиспользуемые элементы.

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

Перестановка, усложненная по маршрутам

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

Струкрура трехмерного гиперкуба представлена на рисунке 6.

Рисунок 6. Трехмерный гиперкуб

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

Рисунок 7. Маршруты Гамильтона

Последовательность перестановок символов в шифруемом блоке для первой схемы 5-6-2-1-3-4-8-7, а для второй 5-1-3-4-2-6-8-7. Аналогично можно получить последовательность перестановок для других маршрутов: 5-7-3-1-2-6-8-4, 5-6-8-7-3-1-2-4, 5-1-2-4-3-7-8-6 и т.д.

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

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

Шифрование по методу магических квадратов.

Магическими квадратами называют квадратные таблицы с вписанными в их клетки последовательными натуральными числами, начиная от 1, которые дают в сумме по каждому столбцу, строке и диагонали одно и то же число.

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

Зашифруем фразу «МАГИЧЕСКАЯ СИЛА» с помощью магического квадрата размером 4х4. Для этого выберем один из 880 вариантов магических квадратов заданного размера (рисунок 8а). Затем вписываем каждую букву сообщения в отдельную ячейку таблицы с номером, соответствующим порядковому номеру буквы в исходной фразе (рисунок 8б). При считывании заполненной таблицы по строкам получаем шифротекст: «_ГАИАЕССЧЯ_КИАЛМ».

Рисунок 8. Пример шифрования с помощью магических квадратов

Шифр, преобразования из которого изменяют только порядок следования символов исходного текста, но не изменяют их самих, называется шифром перестановки

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

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

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

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

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

примерах шифров перестановки. Ответы помещены в конце раздела.

Читатель, знакомый с методом математической индукции, может легко убедиться в том, что существует (обозначается читается факториал») вариантов заполнения нижней строки таблицы (6). Таким образом, число различных преобразований шифра перестановки, предназначенного для зашифрования сообщений длины меньше либо равно (заметим, что в это число входит и вариант преобразования, оставляющий все символы на своих местах!).

С увеличением числа значение растет очень быстро. Приведем таблицу значений для первых 10 натуральных чисел:

(см. скан)

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

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

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

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

Зашифруем, например, указанным способом фразу:

используя прямоугольник размера

(см. скан)

Зашифрованная фраза выглядит так:

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

Ниже приводятся описания трех разновидностей шифров перестановки, встречавшихся в задачах олимпиад.

Шифр «Сцитала». Одним из самых первых шифровальных приспособлений был жезл («Сцитала»), применявшийся еще во времена войны Спарты против Афин в V веке до н. э. Это был цилиндр, на который виток к витку наматывалась узкая папирусная лента (без просветов и нахлестов), а затем на этой ленте вдоль его оси записывался необходимый для передачи текст. Лента сматывалась с цилиндра и отправлялась адресату, который, имея цилиндр точно такого же диаметра, наматывал ленту на него и прочитывал сообщение. Ясно, что такой способ шифрования осуществляет перестановку местами букв сообщения.

Шифр «Сцитала», как видно из решения задачи 2.1, реализует не более перестановок по прежнему, - длина сообщения). Действительно, этот шифр, как нетрудно видеть, эквивалентен следующему шифру маршрутной перестановки: в таблицу, состоящую из столбцов, построчно записывают сообщение, после чего выписывают буквы по столбцам. Число задействованных столбцов таблицы не может превосходить длины сообщения.

Имеются еще и чисто физические ограничения, накладываемые реализацией шифра «Сцитала». Естественно предположить, что диаметр жезла не должен превосходить 10 сантиметров. При высоте строки в 1 сантиметр на одном витке такого жезла уместится не более 32 букв Таким образом, число перестановок, реализуемых «Сцита-лой», вряд ли превосходит 32.

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

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

Поясним процесс шифрования на примере. Пусть в качестве ключа используется решетка приведенная на рис. 1.

Зашифруем с ее помощью текст

Наложив решетку на лист бумаги, вписываем первые 15 (по числу

вырезов) букв сообщения: Сняв решетку, мы увидим текст, представленный на рис. 2. Поворачиваем решетку на 180°. В окошечках появятся новые, еще не заполненные клетки. Вписываем в них следующие 15 букв. Получится запись, приведенная на рис. 3. Затем переворачиваем решетку на другую сторону и зашифровываем остаток текста аналогичным образом (рис. 4, 5).

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

Можно доказать, что число возможных трафаретов, то есть количество ключей шифра «решетка», составляет (см. задачу 1.1). Этот шифр предназначен для сообщений длины Число всех перестановок в тексте такой длины составит что во много раз

больше числа Однако, уже при размере трафарета число возможных решеток превосходит 4 миллиарда.

Широко распространена разновидность шифра маршрутной перестановки, называемая «шифром вертикальной перестановки» (ШВП). В нем снова используется прямоугольник, в который сообщение вписывается обычным способом (по строкам слева направо). Выписываются буквы по вертикали, а столбцы при этом берутся в порядке, определяемом ключом. Пусть, например, этот ключ таков: (5,4,1,7,2,6,3), и с его помощью надо зашифровать сообщение:

Впишем сообщение в прямоугольник, столбцы которого пронумерованы в соответствии с ключом:

(см. скан)

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

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

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

В случае, когда ключ ШВП не рекомендуется записывать, его можно извлекать из какого-то легко запоминающегося слова или предложения. Для этого существует много способов. Наиболее распространенный состоит в том, чтобы приписывать буквам числа в соответствии с обычным алфавитным порядком букв. Например, пусть ключевым словом будет Присутствующая в нем буква А получает номер 1. Если какая-то буква входит несколько раз, то ее появления нумеруются последовательно слева направо. Поэтому второе вхождение буквы А получает номер 2. Поскольку буквы в этом слове нет, то буква В получает номер 3 и так далее. Процесс продолжается до тех

пор, пока все буквы не получат номера. Таким образом, мы получаем следующий ключ:

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

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

Эти варианты имеют прямо противоположный смысл и в имеющихся условиях у нас нет возможности определить, какой из вариантов истинный.

Иногда, за счет особенностей реализации шифра, удается получить информацию об использованном преобразовании (перестановке). Рассмотрим шифр «Сцитала» из задачи 2.1. Выше уже рассматривался вопрос о количестве перестановок, реализуемых «Сциталой». Их оказалось не более 32. Это число невелико, поэтому можно осуществить перебор всех вариантов. При достаточной длине сообщения, мы, скорее всего, получим единственный читаемый вариант текста. Однако, используя информацию о расположении линий, оставленных шифровальщиком, удается определить диаметр стержня, а значит, и возникающую перестановку букв (см. задачу 2.1).

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

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

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

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

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

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

В заключение рассказа о шифрах перестановки приведем историю с зашифрованным автографом А. С. Пушкина, описанную в романе В. Каверина «Исполнение желаний».

Главный герой романа - студент-историк Трубачевский, - занимавшийся работой в архиве своего учителя - академика Бауэра С. И., - нашел в одном из секретных ящиков пушкинского бюро фрагмент недописанной X главы «Евгения Онегина». Это был перегнутый вдвое полулист плотной голубоватой бумаги с водяным знаком 1829 года. На листе было написано следующее.

(см. скан)

(см. скан)

Без особых усилий Трубачевский прочитал рукопись, и ничего не понял. Он переписал ее, получилась бессвязная чепуха, в которой одна строка, едва начавшая мысль, перебивается другой, а та - третьей, еще более бессмысленной и бессвязной. Он попробовал разбить рукопись на строфы, - опять не получилось. Стал искать рифмы, - как будто и рифм не было, хотя на белый стих все это мало похоже. Просчитал строку - четырехстопный ямб, размер, которым написан «Евгений Онегин».

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

Прошло время. Однажды, когда он смотрел на светлые пятна окон подходящего к перрону поезда, каким-то внутренним зрением он

увидел перед собой всю рукопись - и с такой необыкновенной отчетливостью, как это бывает только во сне.