Создание электронного обучающего средства по криптографии

      1.2.4. Маршрутные перестановки

Широкое применение получили так называемые маршрутные перестановки, основанные на некоторой геометрической фигуре. Подробное описание маршрутных перестановок описано в главе 2 пункте «2.2.4. Маршрутные перестановки».

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

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

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

 

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

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

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

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

     В нашем примере 38 = 7 · 5 + 3, поэтому  в заполненной таблице имеется  3 длинных и 4 коротких столбца. Согласно числовому ключу, начальные буквы криптограммы берутся из второго (по счету слева) столбца, он – длинный (так как первые три столбца – длинные), поэтому первые шесть букв образуют пятый столбец (он – короткий). И так далее.

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

      1.2.5. Криптоанализ шифров перестановки

     Укажем  сначала основные идеи, используемые при вскрытии вертикальных перестановок.

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

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

     Если  приписываемые к друг другу буквы  разделены, скажем, только двумя буквами, то мы можем составить в соседних столбцах не более трех пар, и длина каждого столбца не превышает четырех. Кроме того, ограничением может послужить появление запретной биграммы (например, гласная – мягкий знак).

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

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

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

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

     1.3. Аффинные шифры

      1.3.1. Шифр сдвига

     Рассмотрим, как можно описать шифр простой замены с применением арифметического аппарата. Польза такого подхода понятна – вычислительную технику почти всегда проще научить оперировать с числовой информацией, чем с символьной. Основная договоренность, которую мы будем соблюдать, такова: n – символьный алфавит, отождествляем с кольцом . Обозначением количества букв в алфавите открытого текста и будет служить n. Каждая буква заменяется своим номером в алфавите, причем нумерация начинается с нуля. Например, латинская азбука отождествляется с , а русская с . Русская буква «а» шифруется как  «0», буква «б» как «1», «в» как «2» и так далее. Теперь для букв открытого текста мы можем свободно применять операцию сложения и умножения по соответствующему модулю.

     Допустим, во всех последующих примерах сообщения  записываются в русском алфавите без пропусков между словами и разделительных знаков, т.е. n = 33, и все вычисления будем производить в Z₃₃.

     Шифр  сдвига

     Ключ: s , такое, что .

     Шифрование: в сообщении каждая буква x заменяется буквой .

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

     Пример:

     Пусть требуется зашифровать слово «ЗАВТРА» и для шифровки используется ключ s = 5. В цифровой форме слово «ЗАВТРА» представляется последовательностью: 8, 0, 2, 19, 17, 0. Сложим эту последовательность с s по модулю 33. Получили новую последовательность: 13, 5, 7, 24, 22, 5, где ответом криптотекста является «ОЕЗЩЧЕ».

     Дешифрование  производится с использованием расшифровывающего  ключа: s^’ = 33 – 5 = 28. При шифровании мы получили криптотекст «ОЕЗЩЧЕ» = 13, 5, 7, 24, 22, 5. Сложим эту последовательность с s^’ по модулю 33. Получим новую последовательность 8, 0, 2, 19, 17, 0 = «ЗАВТРА» .

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

      1.3.2. Линейный шифр

     Ключ: a , такое, что   и .

     Шифрование: в сообщении каждая буква x заменяется буквой .

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

     Пример:

     Пусть для шифрования используется ключ . Рассмотрим процедуру шифрования сообщения «ЗАВТРА». В цифровой форме оно представляется последовательностью чисел  8, 0, 2, 19, 17, 0. Умножение на 2 по модулю 33 дает последовательность 16, 0, 4, 5, 1, 0, где ответом криптотекста является «ПАДЕБА».

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

     a^’ = a^-1(mod n) ↔ a ∙ a^’ ≡ 1(mod n).

     В нашем примере а = 2, следовательно, 2 ∙ a^’ ≡ 1(mod 33). По определению сравнения по модулю 2 ∙ a^’ = 1 + 33 ∙ n. Попробуем найти a^’ с помощью перебора n. Пусть n = 1, тогда

     2 ∙ a^’ = 1 + 33 ∙ 1 → 2 ∙ a^’ = 1 + 33 → 2 ∙ a^’ = 34 → a^’ = 17.

     Расшифрующий  ключ найден. При шифровании мы получили криптотекст «ПАДЕБА» = 16, 0, 4, 5, 1, 0. Умножение на 17 по модулю 33 приведет к   8, 0, 2, 19, 17, 0 = «ЗАВТРА».

     Обобщением  и шифра сдвига, и линейного  шифра является аффинный шифр.

      1.3.3. Аффинный шифр

     Ключ: а, такие, что  , и .

     Шифрование: в сообщении каждая буква x заменяется буквой .

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

     Пример:

     Пусть для шифровки используется ключ а = 2, s = 1. Чтобы зашифровать сообщение «ЗАВТРА», представим его в цифровой форме как последовательность 8, 0, 2, 19, 17, 0. Умножение на 2 по модулю 33 дает последовательность 16, 0, 4, 5, 1, 0. К результату добавляем единицу и получаем последовательность 17, 1, 5, 6, 2, 1, которая соответствует криптотексту «РБЕЁВБ».

     Дешифрование криптотекста  «РБЕЁВБ» = 17, 1, 5, 6, 2, 1 происходит с использованием ключа a^’ = 17, вычисленного в примере на использование линейного шифра, и s^’, вычисляемого по формуле: s^’ = (- 17 ∙1)(mod 33) = 16.

       Умножение каждого из чисел  по модулю 33 на 17 и прибавление  16 дает 8, 0, 2, 19, 17, 0 = «ЗАВТРА».

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

      1.3.4. Аффинные шифры высших порядков

     Подумаем, как можно расширить монограммные шифры так, чтобы они оперировали  с k-граммами для произвольного k > 1. Вначале введем операцию сложения в . Суммой векторов Х = (х₁,…,х_k) и S = (s₁,…,s_k) из является вектор X + S = ((x₁ + s₁)mod n,…,(x_k + s_k)mod n). с операцией сложения является группой. Вектор S = (n – s₁,…,n – s_k) является обратным к вектору S = (s₁,…,s_k).

     Шифр  сдвига k-го порядка (шифр Виженера с периодом k)