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

     Ключ: S .

     Шифрование. Сообщение разбивается на k-грамм. Каждая k-грамма X заменяется k-граммою Е(Х) = Х + S.

     Дешифрование. Каждая k-грамма криптотекста заменяется k-граммою D( ) = + , где = –S является расшифрующим ключом.

     Пример:

     Рассмотрим  случай k = 2, т.е. биграммный шифр сдвига. Пусть нужно зашифровать сообщение «ЗАВТРА». В ключе выбираем вектор S = над Z₃₃. Сообщение будем разбивать на биграммы. Первая биграмма «ЗА» отвечает вектору . Вторая ВТ = . Далее находим образ биграммы РА = . После разбиения сообщения на векторы – биграммы, получаем матрицу и прибавляем к каждому столбцу вектор S. Получаем новую матрицу: , т.е. получаем криптотекст «ИОГБСО».

     Дешифрование  происходит точно так же, только с использованием расшифрующего  ключа S^’ = - . При шифровании мы получилим криптотекст «ИОГБСО». Разобьем его на векторы-биграммы и сложим с S^’:

     

.

     В результате получаем сообщение «ЗАВТРА».

     Перед тем, как перейти к линейному  шифру напомним, что через M_k(Z_n) мы обозначили множество матриц размерностью k k с коэффициентами из кольца Z_n, а через GL_k(Z_n) – подмножество обратных матриц. Для А GL_k(Z_n) обратную к ней матрицу обозначим через А^-1. Произведением А∙Х матрицы А=(aij) из M_k(Z_n) на вектор-столбец Х = (х₁,…,х_k) из является вектор-столбец:

     

.

     Линейный  шифр k-го порядка

     Ключ: А GL_k(Z_n).

     Шифрование. Сообщение разбивается на k-граммы. Каждая k-грамма Х заменяется k-граммою Е(Х) = А∙Х.

     Дешифрование. Каждая k-грамма криптотекста заменяется k-граммою D( ) = , где - расшифрующий ключ.

     Линейный  шифр 1-го порядка обговаривался  ранее. Рассмотрим подробно случай k = 2, т.е. биграммный линейный шифр. В ключе выбирается матрица с коэффициентами a, b, c, d Z_n. Матрица А должна быть обратимой. Это значит, что НОД( , n) = 1 для = (ad – bc) – определитель матрицы. По этому условию, с помощью расширенного алгоритма Евклида мы можем найти в Z_n обратный элемент ^-1 и, по формуле обратной матрицы, вычисляется расшифрующий ключ

     

.

     Пример:

     Пусть нужно зашифровать сообщение  «ЗАВТРА». В ключе выбираем матрицу  с коэффициентами  1, 1, 32, 1 Z₃₃. Для этой матрицы над Z₃₃ имеем . Первая биграмма «ЗА» отвечает вектору . Умножение на матрицу А дает: . Далее находим образ биграммы «ВТ» = . Также умножаем ее на матрицу А и получаем: . Таким же образом находим образ биграммы «РА» = . Получаем . В результате появилась новая матрица: .

     Превратим столбцы полученной матрицы в  биграммы и получим криптотекст  «ЗШФРРП». Заметим, что умножение матрицы А на три вектора-биграммы эквивалентно умножению этой матрицы на матрицу размерностью : .

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

     

.

     Определим x и y из матричного равенства. Получим систему линейных уравнений: . Решаем полученную систему методом сложения, учитывая, что равенство задано в кольце : . Окончательно получаем : , , .

     Аналогично  определяем z и u : , , , , .

     В результате получаем матрицу  и вычисляем для нее определитель . Пусть мы имеем криптотекст «ЗШФРРП». Разбиваем его на биграммы и выполняем умножение на матрицу : .

     В результате получаем сообщение «ЗАВТРА».

     Аффинный  шифр k-го порядка

     Ключ: А GL_k(Z_n) и .

     Шифрование. Сообщение разбивается на k-грамму. Каждая k-грамма Х заменяется k-граммою E(X) = A∙X + S.

     Дешифрование. Каждая k-грамма криптотекста заменяется k-граммою , ГДЕ и – расшифрующий ключ.

     Пример 1.

     Необходимо  зашифровать сообщение «ЗАВТРА» при помощи ключа  и над . Часть работы уже выполнена нами в примерах на использование линейного шифра. После разбития сообщения на векторы-биграммы и умножения их на матрицу А  по модулю 33 мы бы получили . Прибавив к каждому столбцу вектор S, получим , т.е. получаем криптотекст «ИЖХЯСЮ».

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

.

     В результате получаем сообщение «ЗАВТРА».

      1.3.5. Криптоанализ аффинных шифров

      Атака с выбором открытого текста

     Несложно  заметить, что аффинный шифр неустойчивый к этому виду криптоанализа. Обозначим через Х_i,  , вектор с - той компонентой 1, в котором остальные компоненты равны 0, а через - нулевой вектор. Сопернику достаточно выяснить, в какие криптотексты переходят заменяющие векторы k - граммы. Действительно,  , а образ равен - тому столбцу матрицы А, что позволяет полностью определить ключ.

      Атака с известным открытым текстом

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

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

     Атака только по криптотексту

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

     Рассмотрим  линейный шифр k - го порядка над алфавитом . Посмотрим, чем отличается грубая атака. Иными словами, насколько реально провести полный перебор ключей. Очевидно, что количество ключей равняется количеству матриц в , для которого введем обозначение . Можно показать, что .

     С одной стороны, . С другой, из формулы Эйлера для функции получим

       В силу оценки  [2,6] имеем , при n>4. Значения возрастают по n как полином и по k как экспонента. Полученные результаты позволяют оценить размер пространства ключей для любых конкретных значений k и п. Попробуем найти количество всевозможных ключей при k = 5 и n = 32. Подставим в формулу значения k = 5 и n = 32:

     

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

     Расшифровка итерациями

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

     Шифрующее отображение  можно применять несколько раз. Отображение определим индуктивно, что и для i >1. будем называть i – кратной итерацией или i – той степенью отображения .

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

     _{1.4. Цифровые криптоалгоритмы}

     1.4.1. Шифр одноразового блокнота

       Представление текста в цифровой форме

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

      Здесь выгодна подача информации в цифровой форме. Идея совсем проста: каждый символ текста заменяют его номером в алфавите. Нумерацию мы договариваемся начинать с нуля.

      Например, слово БАНАН будет выглядеть как 0100150015. Каждая буква представлена своим номером, записана двумя цифрами, первая из которых может быть ноль. При необходимости в алфавит нужно включить, кроме букв, знаки пунктуации, пропуски и так далее.

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

      Таким образом, текст можно записывать в двоичной форме, используя всего лишь два символа 0 и 1. Эти два символа называют битами. Любую последовательность битов называют двоичным словом.

     Принцип шифрования с помощью  одноразового блокнота

      Данный  шифр был изобретён в 1977 году Гильбертом Вернамом. Он использует операцию добавления битов по модулю 2, которую мы, рассмотрели, перед тем как описать сам шифр. Операция обозначается и задается так: , , , .

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

000001000000010001000000010001

001101110101100010011000111010

001100110101110011011000101011

     Для двоичных слов X и Y одинаковой длины результат их побитового сложения обозначается математически как X Y. Легко проверить равенства: , , которые выполняются для любых двоичных слов X, Y и Z одинаковой длины. Для любого двоичного слова X, составленного из k нулей, справедливо равенство и .

      Подробное описание шифра одноразового блокнота изложено в главе 2 пункте «2.2.6. Шифр одноразового блокнота».

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