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

Перестановка представляет собой способ шифрования, при котором для получения шифрограммы буквы исходного сообщения меняют местами. Типичным примером перестановки являются анаграммы, ставшие популярными в XVII в. Анаграмма (греч. ανα - «снова» и γράμμα «запись») - литературный приём, состоящий в перестановке букв или звуков определённого слова (или словосочетания), что в результате даёт другое слово или словосочетание [17]. Например: апельсин - спаниель, полковник - клоповник, горилка - рогалик, лепесток - телескоп. Прародителем анаграммы однако считают поэта и грамматика Ликофрона, который жил в Древней Греции в III веке до н. э. Как сообщал византийский автор Иоанн Цец, из имени царя Птоломея он составил первую из известных нам анаграмм: Ptolemaios - Аро Melitos, что в переводе означает «из мёда», а из имени царицы Арсинои: Arsinoe - Ion Eras («фиалка Геры»). В XVII—XIX вв. среди естествоиспытателей было принято зашифровывать свои открытия в виде анаграмм, что служило двум нуждам: скрыть гипотезу до её окончательной проверки и утвердить авторство на открытие, когда оно будет подтверждено. Так, в 1610 г. Галилео Галилей для закрепления авторства на открытие спутников Сатурна зашифровал латинскую фразу «Altissimun planetam tergeminum observavi» («Высочайшую планету тройную наблюдал») следующим образом: «Smaismrmilmepoetaleumibunenugttauiras» (буквы «v» и «u» в латинских текстах часто считались 1 взаимозаменяемыми) . Доподлинно не известно, когда появился шифр перестановки, но вполне возможно, что писцы в древности переставляли буквы в имени своего царя ради того, чтобы скрыть его подлинное имя или в ритуальных целях [43]. Все шифры перестановки делятся на два подкласса: - шифры одинарной (простой) перестановки. При шифровании символы перемещаются с исходных позиций в новые один раз; - шифры множественной (сложной) перестановки. При перемещаются с исходных позиций в новые несколько раз. шифровании символы 1 В те времена самой дальней из известных («высочайшей») планет был Сатурн. В действительности, в силу несовершенства телескопа, используемого Галилеем, он наблюдал не спутники, а кольца Сатурна, которые выступали по краям планеты. Эти выступы («ушки») и были приняты им за спутники. Свою гипотезу о них в виде анаграммы Галилей отослал Иоганну Кеплеру, который, потратив множество сил, перевел ее как «Salve umbistineum geminatum Martia proles» (лат., «Возрадуйтесь, два протуберанца - сыны Марса»). Кеплер не обратил внимание на то, что в его переводе была лишняя буква, т.к. по его соображениям у Марса должны были быть два спутника, неоткрытые на тот момент. Спутники Марса (Фобос и Деймос) были открыты американским астрономом Асафом Холлом позже - в 1877 г. [54]. 5.2. Шифры одинарной перестановки В общем случае для данного класса шифров при шифровании и дешифровании используется таблица перестановок. 1 2 3 … n I1 I2 I3 … In Рис.5.1. Таблица перестановок В первой строке данной таблицы указывается позиция символа в исходном сообщении, а во второй – его позиция в шифрограмме. Таким образом, максимальное количество ключей для шифров перестановки равно n!, где n – длина сообщения. Шифр простой одинарной перестановки. Для шифрования и дешифрования используется таблица перестановок, аналогичная показанной на рис.5.2. 1 2 3 4 5 6 7 2 4 1 7 6 5 3 Рис.5.2. Таблица перестановок Например, если для шифрования исходного сообщения «АБРАМОВ» использовать таблицу, представленную на рис.5.2, то шифрограммой будет «РАВБОМА». Для использования на практике такой шифр не удобен, так как при больших значениях n приходится работать с длинными таблицами и для сообщений разной длины необходимо иметь свою таблицу перестановок. Шифр блочной одинарной перестановки. При использовании этого шифра задается таблица перестановки блока символов, которая последовательно применяется до тех пор, пока исходное сообщение не закончится. Если исходное сообщение не кратно размеру блока, тогда оно при шифровании дополняется произвольными символами. 1 2 3 2 3 1 Рис.5.3. Таблица перестановок Для примера выберем размер блока, равный 3, и примем таблицу перестановок, показанную на рис.5.3. Дополним исходное сообщение «АБРАМОВ» буквами Ь и Э, чтобы его длина была кратна 3. В результате шифрования получим «РАБОАМЭВЬ». Количество ключей для данного шифра при фиксированном размере блока равно m!, где m – размер блока. Шифры маршрутной перестановки. Широкое распространение получили шифры перестановки, использующие некоторую геометрическую фигуру (плоскую или объемную). Преобразования состоят в том, что в фигуру исходный текст вписывается по ходу одного маршрута, а выписывается по другому. Один из таких шифров – шифр «Сцитала» - упоминался ранее. Некоторые из них приводятся ниже. Шифр табличной маршрутной перестановки. Наибольшее распространение получили шифры маршрутной перестановки, основанные на таблицах. При шифровании в такую таблицу вписывают исходное сообщение по определенному маршруту, а выписывают (получают шифрограмму) - по другому. Для данного шифра маршруты вписывания и выписывания, а также размеры таблицы являются ключом. Рис.5.4. Пример использования шифра маршрутной перестановки Например, исходное сообщения «АБРАМОВ ИЛЬЯ СЕРГЕЕВИЧ» вписывается в прямоугольную таблицу размерами 4х6, маршрут вписывания – слева-направо сверху-вниз, маршрут выписывания – сверху-вниз слева-направо. Шифрограмма в этом случае выглядит «АВ_ЕБ_СВРИЕИАЛР ЧМЬГ_ОЯЕ_». Шифр вертикальной перестановки. Является разновидностью предыдущего шифра. К особенностям шифра можно отнести следующие: - количество столбцов в таблице фиксируется и определяется длиной ключа; - маршрут вписывания - строго слева-направо сверху-вниз; - шифрограмма выписывается по столбцам в соответствии с их нумерацией (ключом). Ключ Д Я Д И Н А 2 6 3 4 5 1 А Б Р А М О Текст В _ И Л Ь Я _ С Е Р Г Е Е В И Ч _ _ Рис.5.5. Пример использования шифра вертикальной перестановки В качестве ключа можно использовать слово или фразу. Тогда порядок выписывания столбцов соответствует алфавитному порядку букв в ключе. Например, если ключевым словом будет «ДЯДИНА», то присутствующая в нем буква А получает номер 1, Д – 2 и т.д. Если какая-то буква входит в слово несколько раз, то ее появления нумеруются последовательно слева направо. В примере первая буква Д получает номер 2, вторая Д – 3. При шифровании сообщения «ОЯЕ_АВ_ЕРИЕИАЛРЧМЬГ_Б_СВ». «АБРАМОВ ИЛЬЯ СЕРГЕЕВИЧ» результат будет Шифр «Перекресток» [43]. Для перемешивания букв могут использоваться фигуры специального вида. Один из таких способов носит название «перекресток». В приведенном ниже примере рисуют крестообразные фигуры в количестве, достаточном, чтобы разместить в них все буквы сообщения. Открытый текст записывают вокруг этих фигур заранее оговоренным способом в нашем случае по часовой стрелке. Таким образом, сообщение «АБРАМОВ ИЛЬЯ СЕРГЕЕВИЧ» может выглядеть следующим образом: Рис.5.6. Пример размещения открытого текста в шифре «Перекресток» Буквы берутся построчно. Вначале берется оговоренное количество букв (N) из первой строки, затем удвоенное количество букв (2N) из второй и снова N букв из третьей строки. Например, при N = 3 шифрограмма будет выглядеть «БОЛАРМВИЬА_ЯСЕЧ_ЕГЕИ_РВ_». Шифры с использованием треугольников и трапеций [43]. Помочь выполнить перестановки могут как треугольники, так и трапеции. Открытый текст вписывается в эти фигуры в соответствии с количеством слов и формой выбранной фигуры, которая может быть растянута или сжата, чтобы в ней поместилось сообщение. Для первой фигуры, треугольника, открытый текст записывается построчно от вершины до основания. А Б А В Ь Р М О И _ Я Г Р С _ Е Л Е Е В И Д Я Д И Н А Д Я Д И Н 2 10 3 6 8 1 4 11 5 7 9 Рис.5.7. Пример использования шифра перестановки при вписывании в треугольник Ниже записывается ключевое слово. Поскольку основание широкое, ключевое слово повторяется. Буквы строки с ключевым словом нумеруются последовательно согласно их алфавитному порядку. Зашифрованное сообщение выписывается по столбцам согласно выполненной нумерации. Таким образом, для открытого текста «АБРАМОВ ИЛЬЯ СЕРГЕЕВИ» и ключевого слова «ДЯДИНА» шифрограмма будет выглядеть «АМ_РВГРИЕЛВАЯЕБ_ЕИЬРС». Шифр «Поворотная решетка» [14, 17, 43]. В 1550 г. итальянский математик Джероламо 2 Кардано , состоящий на службе у папы Римского, в книге «О тонкостях» предложил новую технику шифрования - решётку Кардано. Изначально решетка Кардано представляла собой трафарет с прорезанными в нем отверстиями. В этих отверстиях на листе бумаги, который клали под решетку, записывались буквы, слоги и слова сообщения. Далее трафарет снимался, и свободное пространство заполнялось более или менее осмысленным текстом для маскировки секретного послания. Такой метод сокрытия информации относится к стеганографии. Позднее был предложен шифр «поворотная решетка» или, как его еще называют, «решетка для вьющихся растений», поскольку она напоминала отверстия в деревянных решетках садовых строений. Этот шифр считают первым транспозиционным (геометрическим) шифром. Несмотря на то, что между изначальным предложением Кардано и шифром «поворотная решетка» большая разница, методы сокрытия информации, основанные на использовании трафаретов, принято называть «решетками Кардано». Для шифрования и дешифрования с помощью данного шифра изготовляется прямоугольный трафарет с четным количеством строк и столбцов. В трафарете вырезаются клетки таким образом, чтобы при наложении его на таблицу того же размера четырьмя возможными способами, его вырезы полностью покрывали все ячейки таблицы ровно по одному разу. При шифровании трафарет накладывается на таблицу. В видимые ячейки таблицы выписываются буквы исходного текста слева-направо сверху-вниз. Далее трафарет поворачивается и вписывается следующая часть букв. Эта операция повторяется еще два раза. Шифрограмму выписывают из итоговой таблицы по определенному маршруту. Таким образом, ключом при шифровании является трафарет, порядок его поворотов и маршрут выписывания. Пример шифрования сообщения «АБРАМОВ+ДЯДИНА» показан на рис.5.8. Результат шифрования – «АДВ_МНРДБЯ+_ОААИ». Рис.5.8. Пример использования шифра «поворотная решетка» Данный метод шифрования применялся нидерландскими правителями для секретных посланий в 1740-x гr. Он также использовался в армии кайзера Вильгельма в Первую мировую войну. Для шифрования немцы использовали решетки разных размеров, которым французские криптоаналитики дали собственные кодовые имена: Анна (25 букв), Берта (36 букв), Дора (64 буквы) и Эмиль (81 буква). Однако использовались решетки очень недолго (всего четыре месяца) к огромному разочарованию французов, которые только-только начали подбирать к ним ключи. Магические квадраты. Магическими квадратами называются квадратные таблицы со вписанными в их клетки последовательными натуральными числами начиная с 1, которые в сумме по каждому столбцу, каждой строке и каждой диагонали дают одно и то же число. Впервые эти квадраты появились в Китае, где им и была приписана некоторая «магическая сила». По преданию, описанному в одной из пяти канонических книг Древнего Китая - Шу-Цзин (Книге записанных преданий), в 2200 году до н.э. из реки Ло вышла огромная черепаха (по другой версии - дракон), символ вечности. На ее панцире были видны пятна, образовывавшие удивительный рисунок. Рис.5.9. Магический квадрат Ло Шу Когда черепаха вышла из воды, высыхали лужи после недавнего ливня. Великий Юй взял эту черепаху и рассмотрел странный узор на ее панцире. Этот узор вдохновил его на создание трактата под названием «Хун Фань» («Великий план»), в котором говорилось о физике, астрологии, предсказаниях, морали, политике и религии [53]. Магические квадраты широко применялись для передачи секретной информации. При шифровании исходное сообщение вписывалось в квадрат по приведенной в них нумерации, после чего шифрограмма выписывалась по строкам. Количество возможных магических квадратов (ключей) быстро возрастает с увеличением их размера. Так, существует лишь один магический квадрат размером 3х3, если не принимать во внимание его повороты. Магических квадратов 4х4 насчитывается уже 880, а число магических квадратов размером 5х5 около 250000. Поэтому магические квадраты больших размеров могли быть хорошей основой для надежной системы шифрования того времени, потому что ручной перебор всех вариантов ключа для этого шифра был немыслим [17]. Рассмотрим квадрат размером 4х4. В него вписываются числа от 1 до 16. Его магия состоит в том, что сумма чисел по строкам, столбцам и полным диагоналям равняется одному и тому же числу - 34. 16 3 2 13 5 10 11 8 9 6 7 12 4 15 14 1 Рис.5.10. Магический квадрат 4х4 Шифрование по магическому квадрату производилось следующим образом. Например, требуется зашифровать фразу: «АБРАМОВДЯДИНА...». Буквы этой фразы вписываются последовательно в квадрат согласно записанным в них числам: позиция буквы в предложении соответствует порядковому числу. В пустые клетки ставится точка или любая буква. 16 . 3 Р 2 Б 13 А 5 М 10 Д 11 И 8 Д 9Я 6О 7 В 12 Н 4 А 15 . 14 . 1 А Рис.5.11. Пример шифрования с помощью магического квадрата После этого шифрованный текст записывается в строку (считывание производится слеванаправо сверху-вниз, построчно) – «.РБАМДИДЯОВНА..А». 2 Джелорамо Кардано (1501 – 1576 гг.) - итальянский математик, инженер, философ, медик и астролог. В его честь названы открытые Сципионом дель Ферро формулы решения кубического уравнения (Кардано первым их опубликовал) и карданный вал (известного ещё Леонардо да Винчи). Написал около 240 книг (131 из них была опубликована, 111 остались в виде рукописей) [43]. 5.3. Шифры множественной перестановки В данном подклассе шифров используется идея повторного шифрования уже зашифрованного сообщения или многократной перестановки символов исходного сообщения перед попаданием в итоговую шифрограмму. Шифр двойной перестановки. В таблицу по определенному маршруту записывается текст сообщения, затем переставляются столбцы, а потом переставляются строки. Шифрограмма выписывается по определенному маршруту. Пример шифрования сообщения «АБРАМОВ+ДЯДИНА» показан на следующем рисунке. Результат шифрования – «ОАБЯ+_АИВ_РДМНАД». Рис.5.12. Пример использования шифра двойной перестановки Ключом к шифру являются размеры таблицы, маршруты вписывания и выписывания, а также порядки перестановки столбцов и строк. Если маршруты являются фиксированными величинами, то количество ключей равно n!*m!, n и m – количество столбцов и строк в таблице. Несмотря на многоступенчатую процедуру шифрования, включая двойную перестановку, данный шифр может быть эквивалентно заменен шифром простой одинарной перестановки. На следующем рисунке приведена таблица эквивалентных одинарных перестановок для примера шифрования, приведенного на рис. 5.12. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 А Б Р А М О В + Д Я Д И Н А _ _ 15 3 11 7 13 1 9 5 16 4 12 8 14 2 10 6 О А Б Я + _ А И В _ Р Д М Н А Д Рис.5.13. Таблица эквивалентных одинарных перестановок Аналогичную замену на шифр блочной одинарной перестановки можно выполнить и для других шифров: табличная маршрутная перестановка, «поворотная решетка», «магический квадрат» и др. 3.1.1 Шифры перестановки В шифрах средних веков часто использовались таблицы, с помощью которых выполнялись простые процедуры шифрования, основанные на перестановке букв в сообщении. Ключами в этих алгоритмах являются размеры таблицы и порядок перестановки. Пример данного метода шифрования текста «И БУМАЖКОЙ ПРИКРОЕМ БРЕШЬ» показан в таблицах на рис 3.1. Сначала в таблицу записывается текст сообщения (рис 3.1, а), а потом поочередно переставляются столбцы в определенном порядке (на рис 3.1, б) в первой строке, а затем строки (на рис 3.1, в) в последнем столбце. При расшифровке порядок перестановок был обратный. Пример данного метода шифрования показан в следующих таблицах: 1 2 3 4 5 1 И А Р Б 2 Ж П О Р 3 Б К Р Е Е 4 У О И М Ш а) 5 М Й К Ь 4 У О И М Ш 2 Ж П О Р 1 И А Р Б б) 3 Б К Р Е Е 5 М Й К Ь И М Ш О У П О Р Ж Р Б А И в) Р Е Е К Б К Ь Й М 3 4 5 2 1 Рис. 3.1. Двойная перестановка столбцов и строк В результате перестановки текста «И БУМАЖКОЙ ПРИКРОЕМ БРЕШЬ» получена шифровка «ИП РКМОРЕ ШРБЕЬОЖАКЙУ ИБМ». Ключом к шифру служат номера столбцов 4 2 1 3 5 и номера строк 3 4 5 2 1 исходной таблицы. Для удобства запоминания ключей можно использовать в их качестве слова. При этом порядок перестановки определяется нумерацией букв в слове в алфавитном порядке. В приведенном примере использованы Ключ1 – «СПОРТ», буквы в алфавите располагаются в порядке 4 2 1 3 5 (ОПРСТ – 12345) и Ключ2 – «СТУЖА», буквы в алфавите располагаются в порядке 3 4 5 2 1 (АЖСТУ–12345). Число вариантов двойной перестановки достаточно быстро возрастает с увеличением размера таблицы: для таблицы 3 х 3 их 36, для 4 х 4 их 576, а для 5 х 5 их 14400. Для обеспечения дополнительной защиты можно повторно шифровать сообщение, которое уже было зашифровано. Для этого размер второй таблицы подбирают так, чтобы длины ее строк и столбцов отличались от длин строк и столбцов первой таблицы. При этом размеры второй таблицы должны быть взаимно простыми с размерами первой таблицы. Для шифрования применялись магические квадраты – квадратные таблицы с вписанными в их клетки последовательными натуральными числами, начиная с единицы, которые дают в сумме по каждому столбцу, каждой строке и каждой диагонали одно и то же число. Свойство магического квадрата используется для повышения эффективности шифра при данном алгоритме шифрования. Для шифрования необходимо вписать исходный текст «ЧИСЛОШЕСТНАДЦАТЬ» по приведенной в магическом квадрате нумерации и затем переписать содержимое таблицы по строкам (рис 3.2). В результате получается шифротекст «ЬСИЦОНАСТШЕДЛТАЧ», перестановке букв исходного сообщения. сформированный благодаря Исходный текст: Ч И С Л О Ш Е С Т Н А Д Ц А Т Ь Ч 1 И 2 С 3 Л 4 О 5 Ш 6 Е 7 С 8 Магический квадрат 16 5 9 4 3 10 6 15 2 11 7 14 Т 9 Н 10 А 11 Д 12 Ц 13 А 14 Т 15 Ь 16 Шифрование 13 8 12 1 Ь О Т Л С Н Ш Т И А Е А Ц С Д Ч Шифротекст: Ь С И Ц О Н А С Т Ш Е Д Л Т А Ч Рис. 3.2. Шифрование с помощью магического квадрата Дешифровка шифротекста происходит в обратном порядке: вначале текст вписывается последовательно слева направо в квадрат, затем буквы с квадрата выбираются в порядке, определенном в магическом квадрате. 7.3. Шифры перестановки Шифр, преобразования из которого изменяют только порядок следования символов исходного текста, но не изменяют их самих, называется шифром перестановки (ШП). Рассмотрим преобразование из ШП, предназначенное для зашифрования сообщения длиной символов. Его можно представить с помощью таблицы (6) где - номер места шифртекста, на которое попадает первая буква исходного сообщения при выбранном преобразовании, - номер места для второй буквы и т.д. В верхней строке таблицы выписаны по порядку числа от 1 до , а в нижней - те же числа, но в произвольном порядке. Такая таблица называется подстановкой степени . Зная подстановку, задающую преобразование, можно осуществить как зашифрование, так и расшифрование текста. Например, если для преобразования используется подстановка и в соответствии с ней зашифровывается слово МОСКВА, то получится КОСВМА. Попробуйте расшифровать сообщение НЧЕИУК, полученное в результате преобразования с помощью указанной выше подстановки. В качестве упражнения читателю предлагается самостоятельно выписать подстановки, задающие преобразования в описанных ниже трех примерах шифров перестановки. Ответы помещены в конце раздела. Читатель, знакомый с методом математической индукции, может легко убедиться в том, что существует (обозначается , читается `` факториал'') вариантов заполнения нижней строки таблицы (6). Таким образом, число различных преобразований шифра перестановки, предназначенного для зашифрования сообщений длины , меньше либо равно (заметим, что в это число входит и вариант преобразования, оставляющий все символы на своих местах!). С увеличением числа значение растет очень быстро. Приведем таблицу значений для первых 10 натуральных чисел: 1 2 3 4 5 6 7 8 9 10 1 2 6 24 120 720 5040 40320 362880 3628800 При больших для приближенного известной формулой Стирлинга где вычисления можно пользоваться . Примером ШП, предназначенного для зашифрования сообщений длины , является шифр, в котором в качестве множества ключей взято множество всех подстановок степени , а соответствующие им преобразования шифра задаются, как было описано выше. Число ключей такого шифра равно . Для использования на практике такой шифр не удобен, так как при больших значениях приходится работать с длинными таблицами. Широкое распространение получили шифры перестановки, использующие некоторую геометрическую фигуру. Преобразования из этого шифра состоят в том, что в фигуру исходный текст вписывается по ходу одного ``маршрута'', а затем по ходу другого выписывается с нее. Такой шифр называют маршрутной перестановкой. Например, можно вписывать исходное сообщение в прямоугольную таблицу, выбрав такой маршрут: по горизонтали, начиная с левого верхнего угла поочередно слева направо и справа налево. Выписывать же сообщение будем по другому маршруту: по вертикали, начиная с верхнего правого угла и двигаясь поочередно сверху вниз и снизу вверх. Зашифруем, например, указанным способом фразу: ПРИМЕРМАРШРУТНОЙПЕРЕСТАНОВКИ используя прямоугольник размера : П Р И М Е Р М Н Т У Р Ш Р А О Й П Е Р Е С И К В О Н А Т Зашифрованная фраза выглядит так: МАСТАЕРРЕШРНОЕРМИУПВКЙТРПНОИ Теоретически маршруты могут быть значительно более изощренными, однако запутанность маршрутов усложняет использование таких шифров. Ниже приводятся описания трех разновидностей шифров перестановки, встречавшихся в задачах олимпиад. Шифр ``Сцитала''. Одним из самых первых шифровальных приспособлений был жезл (``Сцитала''), применявшийся еще во времена войны Спарты против Афин в V веке до н. э. Это был цилиндр, на который виток к витку наматывалась узкая папирусная лента (без просветов и нахлестов), а затем на этой ленте вдоль его оси записывался необходимый для передачи текст. Лента сматывалась с цилиндра и отправлялась адресату, который, имея цилиндр точно такого же диаметра, наматывал ленту на него и прочитывал сообщение. Ясно, что такой способ шифрования осуществляет перестановку местами букв сообщения. Шифр ``Сцитала'', как видно из решения задачи 2.1, реализует не более перестановок ( , по прежнему, - длина сообщения). Действительно, этот шифр, как нетрудно видеть, эквивалентен следующему шифру маршрутной перестановки: в таблицу, состоящую из столбцов, построчно записывают сообщение, после чего выписывают буквы по столбцам. Число задействованных столбцов таблицы не может превосходить длины сообщения. Имеются еще и чисто физические ограничения, накладываемые реализацией шифра ``Сцитала''. Естественно предположить, что диаметр жезла не должен превосходить 10 сантиметров. При высоте строки в 1 сантиметр на одном витке такого жезла уместится не более 32 букв ( ). Таким образом, число перестановок, реализуемых ``Сциталой'', вряд ли превосходит 32. Шифр ``Поворотная решетка''. Для использования шифра, называемого поворотной решеткой, изготавливается трафарет из прямоугольного листа клетчатой бумаги размера клеток. В трафарете вырезано клеток так, что при наложении его на чистый лист бумаги того же размера четырьмя возможными способами его вырезы полностью покрывают всю площадь листа. Буквы сообщения последовательно вписываются в вырезы трафарета (по строкам, в каждой строке слева направо) при каждом из четырех его возможных положений в заранее установленном порядке. Поясним процесс шифрования на примере. Пусть в качестве ключа используется решетка , приведенная на рис. 6. Рис. 6. Зашифруем с ее помощью текст ШИФРРЕШЕТКАЯВЛЯЕТСЯЧАСТНЫМСЛУЧАЕМШИФРАМАРШРУТНОЙ ПЕРЕСТАНОВКИ Наложив решетку на лист бумаги, вписываем первые 15 (по числу вырезов) букв сообщения: ШИФРРЕШЕТКАЯВЛЯ.... Сняв решетку, мы увидим текст, представленный на рис. 7. Поворачиваем решетку на . В окошечках появятся новые, еще не заполненные клетки. Вписываем в них следующие 15 букв. Получится запись, приведенная на рис. 8. Затем переворачиваем решетку на другую сторону и зашифровываем остаток текста аналогичным образом (рис. 9, 10). Рис. 7. Рис. 8. Рис. 9. Рис. 10. Получатель сообщения, имеющий точно такую же решетку, без труда прочтет исходный текст, наложив решетку на шифртекст по порядку четырьмя способами. Можно доказать, что число возможных трафаретов, то есть количество ключей шифра ``решетка'', составляет (см. задачу 1.1). Этот шифр предназначен для сообщений длины . Число всех перестановок в тексте такой длины составит , что во много раз больше числа . Однако, уже при размере 4 миллиарда. трафарета число возможных решеток превосходит Широко распространена разновидность шифра маршрутной перестановки, называемая ``шифром вертикальной перестановки'' (ШВП). В нем снова используется прямоугольник, в который сообщение вписывается обычным способом (по строкам слева направо). Выписываются буквы по вертикали, а столбцы при этом берутся в порядке, определяемом ключом. Пусть, например, этот ключ таков: (5,4,1,7,2,6,3), и с его помощью надо зашифровать сообщение: ВОТПРИМЕРШИФРАВЕРТИКАЛЬНОЙПЕРЕСТАНОВКИ Впишем сообщение в прямоугольник, столбцы которого пронумерованы в соответствии с ключом: 5 1 4 7 2 6 3 В О Т П Р И М Е Р Ш И Ф Р А В Е Р Т И К А Л Ь Н О Й П Е Р Е С Т А Н О В К И - - - - Теперь, выбирая столбцы в порядке, заданном ключом, и выписывая последовательно буквы каждого из них сверху вниз, получаем такую криптограмму: ОРЕЬЕКРФИЙА-МААЕО-ТШРНСИВЕВЛРВИРКПН-ПИТОТ- Число ключей ШВП не более , где - число столбцов таблицы. Как правило, гораздо меньше, чем длина текста (сообщение укладывается в несколько строк по букв), а, значит, и много меньше . Пользуясь приведенной выше формулой Стирлинга при больших и , попытайтесь оценить, во сколько раз число возможных перестановок ШВП с столбцами меньше числа всех перестановок на тексте длины , кратном . В случае, когда ключ ШВП не рекомендуется записывать, его можно извлекать из какого-то легко запоминающегося слова или предложения. Для этого существует много способов. Наиболее распространенный состоит в том, чтобы приписывать буквам числа в соответствии с обычным алфавитным порядком букв. Например, пусть ключевым словом будет ПЕРЕСТАНОВКА. Присутствующая в нем буква А получает номер 1. Если какая-то буква входит несколько раз, то ее появления нумеруются последовательно слева направо. Поэтому второе вхождение буквы А получает номер 2. Поскольку буквы Б в этом слове нет, то буква В получает номер 3 и так далее. Процесс продолжается до тех пор, пока все буквы не получат номера. Таким образом, мы получаем следующий ключ: П Е Р Е С Т А Н О В К А 9 4 10 5 11 12 1 7 8 3 6 2 Перейдем к вопросу о методах вскрытия шифров перестановки. Проблема, возникающая при восстановлении сообщения, зашифрованного ШП, состоит не только в том, что число возможных ключей велико даже при небольших длинах текста. Если и удастся перебрать все допустимые варианты перестановок, не всегда ясно, какой из этих вариантов истинный. Например, пусть требуется восстановить исходный текст по криптограмме АОГР, и нам ничего не известно, кроме того, что применялся шифр перестановки. Какой вариант ``осмысленного'' исходного текста признать истинным: ГОРА или РОГА? А может быть АРГО? Приведем пример еще более запутанной ситуации. Пусть требуется восстановить сообщение по криптограмме ААНИНК-ТЕОМЛ,З.ЬЬЗИВТЛП-ЬЯО полученной шифром перестановки. Возможны, как минимум, два варианта исходного сообщения: КАЗНИТЬ,-НЕЛЬЗЯ-ПОМИЛОВАТЬ. и КАЗНИТЬ-НЕЛЬЗЯ,-ПОМИЛОВАТЬ. Эти варианты имеют прямо противоположный смысл и в имеющихся условиях у нас нет возможности определить, какой из вариантов истинный. Иногда, за счет особенностей реализации шифра, удается получить информацию об использованном преобразовании (перестановке). Рассмотрим шифр ``Сцитала'' из задачи 2.1. Выше уже рассматривался вопрос о количестве перестановок, реализуемых ``Сциталой''. Их оказалось не более 32. Это число невелико, поэтому можно осуществить перебор всех вариантов. При достаточной длине сообщения, мы, скорее всего, получим единственный читаемый вариант текста. Однако, используя информацию о расположении линий, оставленных шифровальщиком, удается определить диаметр стержня, а значит, и возникающую перестановку букв (см. задачу 2.1). В рассмотренном примере шифровальщик по неосторожности оставил на папирусе следы, позволяющие нам легко прочитать сообщение. Возможны и другие ситуации, когда не очень ``грамотное'' использование шифра облегчает вскрытие переписки. В задаче 5.2 содержится пример текста, зашифрованного ШВП. По условию пробелы между словами при записи текста в таблицу опускались. Поэтому заключаем, что все столбцы, содержащие пробел в последней строке, должны стоять в конце текста. Таким образом, возникает разбиение столбцов на две группы (содержащие 6 букв, и содержащие 5 букв). Для завершения восстановления исходного текста достаточно найти порядок следования столбцов в каждой из групп в отдельности, что гораздо проще. Аналогичная ситуация возникает и при ``неполном'' использовании шифра ``решетка'' (см. задачу 4.1). Пусть имеется решетка зашифрованное с ее помощью сообщение длины размера , и , не содержащее пробелов. Незаполненные мест в решетке при условии, что , соответствуют вырезам в четвертом положении решетки. На основе такой информации, происходит резкое уменьшение числа допустимых решеток (их будет ). Читателю предлагается самостоятельно подсчитать число допустимых решеток при . На примере решения задачи 5.2 продемонстрируем еще один подход к вскрытию шифров вертикальной перестановки - лингвистический. Он основан на том, что в естественных языках некоторые комбинации букв встречаются очень часто, другие - гораздо реже, а многие вообще не встречаются (например ``ыьъ''). Будем подбирать порядок следования столбцов друг за другом так, чтобы во всех строках этих столбцов получались ``читаемые'' отрезки текста. В приведенном решении задачи восстановление текста начинается с подбора цепочки из трех столбцов первой группы, содержащей в последней строке сочетание ТЧК, так как естественно предположить, что сообщение заканчивается точкой. Далее подбираются столбцы, продолжающие участки текста в других строках, и т.д. Сочетание лингвистического метода с учетом дополнительной информации довольно быстро может привести к вскрытию сообщения. В заключение рассказа о шифрах перестановки приведем историю с зашифрованным автографом А. С. Пушкина, описанную в романе В. Каверина ``Исполнение желаний''. Главный герой романа - студент-историк Н. Трубачевский, - занимавшийся работой в архиве своего учителя - академика Бауэра С. И., - нашел в одном из секретных ящиков пушкинского бюро фрагмент недописанной Х главы ``Евгения Онегина''. Это был перегнутый вдвое полулист плотной голубоватой бумаги с водяным знаком 1829 года. На листе было написано следующее. 1. Властитель слабый и лукавый 1. Нечаянно пригретый славой 2. Его мы очень смирным знали 2. Орла двуглавого щипали 3. Гроза двенадцатого года 3. Остервенение народа 4. Но Бог помог - стал ропот ниже 4. Мы очутилися в Париже 5. И чем жирнее, тем тяжеле 5. Скажи, зачем ты в самом деле 6. Авось, о Шиболет народный 6. Но стихоплет великородный 7. Авось, аренды забывая 7. Авось по манью Николая 8. Сей муж судьбы, сей странник бранный 8. Сей всадник, папою венчанный 9. Тряслися грозно Пиринеи 9. Безрукий князь друзьям Мореи 10. Я всех уйму с моим народом 10. А про себя и в ус не дует 11. Потешный полк Петра Титана 11. Предавших некогда тирана 12. Россия присмирела снова 12. Но искра пламени иного 13. У них свои бывали сходки 13. Они за рюмкой русской водки 14. Витийством резким знамениты 14. У беспокойного Никиты 15. Друг Марса, Вакха и Венеры 15. Свои решительные меры 16. Так было над Невою льдистой 16. Блестит над каменкой тенистой 17. Плешивый щеголь, враг труда 17. Над нами царствовал тогда 18. Когда не наши повара 18. У Бонапартова шатра 19. Настала - кто тут нам помог? 19. Барклай, зима иль русский бог? 20. И скоро силою вещей 20. А русский царь главой царей 21. О русский глупый наш народ 21. ... 22. Тебе б я оду посвятил 22. Меня уже предупредил 23. Ханжа запрется в монастырь 23. Семействам возвратит Сибирь 24. Пред кем унизились цари 24. Исчезнувший как тень зари 25. Волкан Неаполя пылал 25. Из Кишинева уж мигал 26. Наш царь в конгрессе говорил 26. Ты александровский холоп (?) 27. Дружина старых усачей 27. Свирепой шайке палачей 28. И пуще царь пошел кутить 28. Уже издавна, может быть 29. Они за чашею вина 29. ... 30. Сбирались члены сей семьи 30. У осторожного Ильи 31. Тут Лунин дерзко предлагал 31. И вдохновенно бормотал 32. Но там, где ранее весна 32. И над холмами Тульчина Без особых усилий Трубачевский прочитал рукопись, и ничего не понял. Он переписал ее, получилась бессвязная чепуха, в которой одна строка, едва начавшая мысль, перебивается другой, а та - третьей, еще более бессмысленной и бессвязной. Он попробовал разбить рукопись на строфы, - опять не получилось. Стал искать рифмы, - как будто и рифм не было, хотя на белый стих все это мало похоже. Просчитал строку - четырехстопный ямб, размер, которым написан ``Евгений Онегин''. Трубачевский с азартом взялся за рукопись, пытался читать ее, пропуская по одной строке, потом по две, по три, надеясь случайно угадать тайную последовательность, в которой были записаны строки. У него ничего не получалось. Тогда он стал читать третью строку вслед за первой, пятую за третьей, восьмую за пятой, предположив, что пропуски должны увеличиваться в арифметической прогрессии. Все то же! Отчаявшись, он бросил эту затею. Однако, она не давала ему покоя ни на лекции, ни в трамвае... Как шахматист, играющий в уме, он не только знал наизусть каждую строчку, он видел ее в десяти комбинациях сразу. Прошло время. Однажды, когда он смотрел на светлые пятна окон подходящего к перрону поезда, каким-то внутренним зрением он увидел перед собой всю рукопись - и с такой необыкновенной отчетливостью, как это бывает только во сне. Сможете ли вы прочитать эти стихи? Ответ вы найдете в романе В. Каверина.