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

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

     Пример (шифра Плейфера):

     Пусть шифр использует прямоугольник размером 5 × 6 , в который записан систематически перемешанный русский 30-буквенный алфавит на основе ключевого слова командир:

 

     Зашифруем фразу «автором метода является Уитстон». В качестве «пустышки» будем использовать редкую букву ф. Представим фразу в виде последовательности биграмм:

     АВ  ТО РО МФ ME ТО ДА ЯВ ЛЯ ЕТ ТЯ УИ ТС ТО НФ

     (Нам  пришлось дважды вставить "пустышку".)

     В соответствии со сформулированными  правилами получаем шифртекст:

     ВП  ЗД ЗР ОХ ДБ ЗД КН ЭЕ ТЫ ТШ ШД ЩЖ ЖТ ЗД ОЧ

или без пробелов

впздзрохдбздкнэетытшшдщжжтздоч

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

     Шифрвеличинами  для другого широко известного блочного шифра – шифра Хилла (названного по имени Лестора Хилла) – являются n-граммы открытого текста (n ≥ 2), представленного некоторым числовым кодом (так что алфавитом открытого текста служит кольцо вычетов по модулю мощности алфавита Z_m).

     Правило зашифрования представляет собой линейное преобразование кольца Z_m: если х = (х₁,...,х_n) – n-грамма открытого текста, k = (k_ij) – некоторая обратимая матрица над Z_m (ключ) и y = (y₁,…,y_n) – n-грамма шифртекста, то y^↓= E_k(x) = k · x^↓. Соответственно   x^↓ = D_k(y) = k^-1 · y^↓, где k^-1 – матрица, обратная к матрице для k.

     Замечание. Из соображений удобства в применении получили широкое распространение шифры, для которых правила зашифрования и расшифрования идентичны. Такие шифры называются обратимыми. Шифр Хилла является обратимым в том и только том случае, когда k^-1 = k , или иначе: k² = Е, где Е – единичная матрица. Матрица, удовлетворяющая этому свойству, называется инволютивной.

     Заметим, что правило зашифрования Е_M (с матрицей М_n×n) в шифрсистеме Хилла является обратимым линейным преобразованием n-мерного модуля . Такая функция является лишь одним из примеров простого задания обратимого преобразования → , являющегося, очевидно, биекцией на . Любая же такая биекция потенциально может рассматриваться как правило зашифрования блочного шифра простой замены (если n – размер блока), выбираемого некоторым ключом.

      1.1.10. Многоалфавитные шифры замены

     Напомним, что правило зашифрования многоалфавитного шифра однозначной замены определяется следующим образом. Пусть x = (x₁,…,x_l) – открытый текст, представленный последовательностью шифрвеличин , i = , и k – произвольный ключ. Тогда

     E_k(x) = (π₁(x₁),…,π_l(x_l)),

где π_i, i = – некоторые подстановки на множестве всех шифрвеличин, однозначно определяемые данным ключом. При этом здесь и далее мы ограничимся рассмотрением случая, когда множества шифрвеличин и шифробозначений совпадают друг с другом (U = V ).

     Заметим, что в рассматриваемых условиях любой многоалфавитный шифр представляет собой совокупность шифров простой замены, каждая из которых используется для зашифрования очередной шифрвеличины в соответствии с вспомогательной последовательностью ψ(k,l) (распределителем), определяемой выбранными ключом и открытым текстом по формуле ψ(k, l) = , N_r, j = . Принципиально один многоалфавитный шифр отличается от другого лишь способом образования распределителя.

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

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

      1.2.1. Шифры обхода

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

     Пример:

     Пусть требуется зашифровать сообщение  «ВОРОНА СЕЛА НА ВОРОТА». Пусть дано ключевое слово «ДОМ». Тогда шифрование выглядит следующим образом:

     Д О М

     1 3 2

     В О Р

     О Н А

     С Е Л

     А Н А

     В О Р

     О Т А

получаем  криптотекст: ВОСАВОРАЛАРАОНЕНОТ.

      1.2.2. Шифр Кардано

     В качестве еще одного примера шифра  перестановки приведем довольно известный в популярной математике шифр Кардано. Это блоковый шифр с периодом l = к², где к четное число. Ключом является вырезанный из бумаги в клетку квадрат размером к на к, что дает к² клеток, четвертая часть которых, то есть к²/4, прорезают.

     

     Пусть требуется зашифровать блок сообщения, в котором к² букв. Криптотекст записывают на клетчатую бумагу в квадраты к на к. Процедура займет четыре шага. На первом шаге на лист, на котором будет писаться криптотекст, накладывают ключ и вписывают первую к²/4 букву сообщения в прорезанной клетке, начиная с верхнего ряда. На втором шаге ключ поворачивают на 90 градусов по часовой стрелке относительно центра квадрата и в прорезанные клетки вписывают следующие к²/4 буквы сообщения. Подобным образом выполняют третий и четвертый шаги – каждый раз ключ поворачивают на 90 градусов и в новой позиции прорезанных клеток вписывают очередные к²/4 буквы сообщения. Ключ должен быть изготовлен таким образом, чтобы при повороте прорезанные в ключе клетки попали на свободные клетки листа, и ни в коем случае не накладывались на клетки уже заполненные на предыдущих шагах. В результате после четвертого шага все к² буквы блока сообщения оказываются размещенными в некотором порядке в квадрате к на к. Считывая их рядами, получаем криптотекст.

     Пример:

     Пусть требуется зашифровать сообщение  «МАМА МЫЛА РАМУ РАНО». Воспользуемся шифром Кардано. Тогда шифрование выглядит следующим образом:

     

 

     В результате получили криптотекст: РМРМЫАААММЛНУАОА

     Шифр  Кардано – это шифр перестановки специального вида, в котором правило перестановки букв в блоки удобно для реализации на бумаге с помощью ножниц и карандаша.

      1.2.3.Общая схема шифра перестановки

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

 

     которая показывает, что первая буква блока открытого текста занимает позицию i₁ в соответствующем блоке криптотекста. Вторая буква перемещается на позицию i₂ и т.д. Например, при l = 4 шифр перестановки с ключом

 

преобразует открытый текст МАМАМЫЛАРАМУРАНО в криптотекст АМАМАЛЫМУМАРОНАР. Шифр Кардано с представленным ключом описывается перестановкой 

 

    Теорема. Шифр перестановки с периодом l имеет l! различных ключей. 

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