Материал: Методы криптографической защиты данных

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

Следует выделить следующие преимущества криптографии с симметричными ключами:

·        относительно высокая производительность алгоритмов;

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

К недостаткам криптографии с симметричными ключами следует отнести:

·        технологические трудности обеспечения неотказуемости.

2.3.1 МЕТОДЫ ЗАМЕНЫ

Сущность методов замены (подстановки) заключается в замене символов исходной информации, записанных в одном алфавите, символами из другого алфавита по определенному правилу. Самым простым является метод прямой замены. Символам s_0i исходного алфавита A₀, с помощью которых записывается исходная информация, однозначно ставятся в соответствие символы s_1i шифрующего алфавита А₁. В простейшем случае оба алфавита могут состоять из одного и того же набора символов. Например, оба алфавита могут содержать буквы русского алфавита.

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

Шаг 1. Формирование числового кортежа L_0h путем замены каждого символа , представленного в исходном алфавите A₀ размера [1xK], на число h_0i(s_0i), соответствующее порядковому номеру символа s_0i в алфавите A₀.

Шаг 2. Формирование числового кортежа L_1h путем замены каждого числа кортежа L_0h на соответствующее число h_1i кортежа L_1h, вычисляемое по формуле:

h_li=k₁*h_0i(s_0i)+k₂)(mod R),

где k₁ - десятичный коэффициент; k₂ - коэффициент сдвига. Выбранные коэффициенты k₁, k₂ должны обеспечивать однозначное соответствие чисел h_0i и h_1i, а при получении h_1i=0 выполнить замену h_1i=R.

Шаг 3. Получение шифртекста Т₁ путем замены каждого числа h_li(s_li) кортежа L_1h соответствующим символом  алфавита шифрования A₁размера [1xR].

Шаг 4. Полученный шифртекст разбивается на блоки фиксированной длины b. Если последний блок оказывается неполным, то в конец блока помещаются специальные символы-заполнители (например, символ *).

Пример. Исходными данными для шифрования являются:₀=<М Е Т О Д _ Ш И Ф Р О В А Н И Я>;₀=<А Б В Г Д Е Ж З И К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я _>;₁=<О Р Щ Ь Я Т Э _ Ж М Ч Х А В Д Ы Ф К С Е З П И Ц Г Н Л Ъ Ш Б У Ю>;=32; k₁=3; k₂=15; b=4.

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

Шаг 1. L_0h=<12, 6, 18, 14, 5, 32, 24, 9, 20, 16, 14, 3, 1, 13, 9, 31>.

Шаг 2. L_1h=<19, 1, 5, 25, 30, 15, 23, 10, 11, 31, 25, 24, 18, 22, 10, 12>.

Шаг 3. T₁=<С О Я Г Б Д И М Ч У Г Ц К П М Х>.

Шаг 4. T₂=<С О Я Г Б Д И М Ч У Г Ц К П М Х>.

При расшифровании сначала устраняется разбиение на блоки. Получается непрерывный шифртекст T₁ длиной K символов. Расшифрование осуществляется путем решения целочисленного уравнения:

k₁h₀₁+k₂=nR+h_1i,

При известных целых величинах k₁, k₂, h_1i и R величина h_0i вычисляется методом перебора n.

Последовательное применение этой процедуры ко всем символам шифртекста приводит к его расшифрованию.

По условиям приведенного примера может быть построена таблица замены, в которой взаимозаменяемые символы располагаются в одном столбце (табл. 2.3.1.1).

Использование таблицы замены значительно упрощает процесс шифрования. При шифровании символ исходного текста сравнивается с символами строки s_0i таблицы. Если произошло совпадение в i-м столбце, то символ исходного текста заменяется символом из строки s_1i, находящегося в том же столбце i таблицы. Расшифрование осуществляется аналогичным образом, но вход в таблицу производится по строке s_1i.

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

Существенно более стойкими являются методы полиалфавитной замены. Такие методы основаны на использовании нескольких алфавитов для замены символов исходного текста. Формально полиалфавитную замену можно представить следующим образом. При N - алфавитной замене символ s₀₁ из исходного алфавита A₀ заменяется символом s₁₁ из алфавита A₁, s₀₂ заменяется символом s₂₂ из алфавита А₂ и так далее. После замены s_0Nсимволом s_NN из А_N символ s_0(N+1) замещается символом s_1(N+1) из алфавита A₁ и так далее.

Наибольшее распространение получил алгоритм полиалфавитной замены с использованием таблицы (матрицы) Вижинера T_B, которая представляет собой квадратную матрицу [RxR], где R - количество символов в используемом алфавите. В первой строке располагаются символы в алфавитном порядке. Начиная со второй строки, символы записываются со сдвигом влево на одну позицию. Выталкиваемые символы заполняют освобождающиеся позиции справа (циклический сдвиг). Если используется русский алфавит, то матрица Вижинера имеет размерность [32 x 32] (рис. 2.3.1.2).

Рис.2.3.1.2. Матрица Вижинера

Шифрование осуществляется с помощью ключа, состоящего из М неповторяющихся символов. Из полной матрицы Вижинера выделяется матрица шифрования Т_ш, размерностью [(М+1), R]. Она включает первую строку и строки, первые элементы которых совпадают с символами ключа. Если в качестве ключа выбрано слово <ЗОНД>, то матрица шифрования содержит пять строк (рис. 2.3.1.3).

Рис. 2.3.1.3. Матрица шифрования для ключа <ЗОНД>

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

Шаг 1. Выбор ключа К длиной М символов.

Шаг 2. Построение матрицы шифрования Т_ш=(b_ij) размерностью [(М+1), R] для выбранного ключа К.

Шаг 3. Под каждым символом s_0r исходного текста длиной I символов размещается символ ключа k_m (рис. 2.3.1.3). Ключ повторяется необходимое число раз.

Шаг 4. Символы исходного текста последовательно замещаются символами, выбираемыми из Т_ш по следующему правилу:

1. определяется символ km ключа К, соответствующий замещаемому символу sor;

2.      находится строка i в Тш, для которой выполняется условие km=bi1;

.        определяется столбец j, для которого выполняется условие: sor=b1j;

.        символ sor замещается символом bij.

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

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

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

Шаг 2. Последовательно выбираются символы s_1r из шифртекста и соответствующие символы ключа K_m. В матрице Т_ш определяется строка i, для которой выполняется условие K_m = b_i1. В строке 1 определяется элемент b_ij = s_1r. В расшифрованный текст на позицию r помещается символ b_1j.

Шаг 3. Расшифрованный текст записывается без разделения на блоки. Убираются служебные символы.

2.3.2 МЕТОДЫ ПЕРЕСТАНОВКИ

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

Перестановки получаются за счет разницы путей записи исходной информации и путей считывания зашифрованной информации в пределах геометрической фигуры. Примером простейшей перестановки является запись блока исходной информации в матрицу по строкам, а считывание - по столбцам. Последовательность заполнения строк матрицы и считывания зашифрованной информации по столбцам может задаваться ключом. Криптостойкость метода зависит от длины блока (размерности матрицы). Так для блока длиной 64 символа (размерность матрицы 8 x 8) возможны 1,6 х 10⁹ комбинаций ключа. Для блока длиной 256 символов (матрица размерностью 16 x 16) число возможных ключей достигает 1,4 x 10²⁶. Решение задачи перебора ключей в последнем случае даже для современных ЭВМ представляет существенную сложность. Перестановки используются также в методе, основанном на применении маршрутов Гамильтона. Этот метод реализуется путем выполнения следующих шагов.

Шаг 1. Исходная информация разбивается на блоки. Если длина шифруемой информации не кратна длине блока, то на свободные места последнего блока помещаются специальные служебные символы-заполнители (например *).

Шаг 2. Символами блока заполняется таблица, в которой для каждого порядкового номера символа в блоке отводится вполне определенное место (рис. 2.3.2.1).

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

Шаг 4. Зашифрованная последовательность символов разбивается на блоки фиксированной длины L. Величина L может отличаться от длины блоков, на которые разбивается исходная информация на шаге 1.

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

Рис. 2.3.2.1. Вариант 8-элементной таблицы и маршрутов Гамильтона

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

Пусть требуется зашифровать исходный текст Т0 = <МЕТОДЫ_ПЕРЕСТАНОВКИ>. Ключ и длина зашифрованных блоков соответственно равны: К = <2, 1, 1>, L = 4. Для шифрования используются таблица и два маршрута, представленные на рис. 19. Для заданных условий маршруты с заполненными матрицами имеют вид, показанный на рис. 2.3.2.2.

Рис. 2.3.2.2. Пример шифрования с помощью маршрутов Гамильтона

Шаг 1. Исходный текст разбивается на три блока:

Б1 = <МЕТОДЫ_П>;

Б2 = <ЕРЕСТАНО>;

Б3 = <ВКИ*****>.

Шаг 2. Заполняются три матрицы с маршрутами 2, 1, 1 (рис. 2.3.2.2).

Шаг 3. Получение шифртекста путем расстановки символов в соответствии с маршрутами.

Т1 = <ОП_ТМЕЫДЕСРЕТАОНИ*КВ****>.

Шаг 4. Разбиение на блоки шифртекста

Т1 = <ОП_Т МЕЫД ЕСРЕ ТАОН И*КВ ****>.

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

Рис. 2.3.2.3. Схема перестановок

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

2.3.3 АНАЛИТИЧЕСКИЕ МЕТОДЫ ШИФРОВАНИЯ

Для шифрования информации могут использоваться аналитические преобразования. Наибольшее распространение получили методы шифрования, основанные на использовании матричной алгебры. Зашифрование k-го блока исходной информации, представленного в виде вектора B_k = ||b_j||, осуществляется путем перемножения матрицы-ключа А = ||a_ij|| и вектора B_k. В результате перемножения получается блок шифртекста в виде вектора C_k = ||c_i|| , где элементы вектора C_k определяются по формуле:

Расшифрование информации осуществляется путем последовательного перемножения векторов C_k и матрицы A^-1, обратной матрице A.

Пример шифрования информации с использованием алгебры матриц.

Пусть необходимо зашифровать и расшифровать слово

Т0 = < ЗАБАВА> с помощью матрицы-ключа А:

Для зашифрования исходного слова необходимо выполнить следующие шаги. Шаг 1. Определяется числовой эквивалент исходного слова как последовательность соответствующих порядковых номеров букв слов Т_э:_э = <8, 1, 2, 1, 3, 1>

Шаг 2. Умножение матрицы А на векторы В₁ = {8, 1, 2} и В₂ = {1, 3, 1}:

;

.

Шаг 3. Зашифрованное слово записывается в виде последовательности чисел Т1 = <28, 35, 67, 21, 26, 38>.

Расшифрование слова осуществляется следующим образом.

Шаг 1. Вычисляется определитель |А| = -115.

Шаг 2. Определяется присоединенная матрица А*, каждый элемент которой является алгебраическим дополнением элемента матрицы А

.

Шаг 3. Получается транспонированная матрица А^T

.

Шаг 4. Вычисляется обратная матрица А^-1 по формуле:

А^-1 = А^Т/|А|.

В результате вычислений обратная матрица имеет вид:

.

Шаг 5. Определяются векторы B₁ и B₂:

B₁ = A^-1*C₁; B₂ = A^-1*C₂.

,

.

Шаг 6. Числовой эквивалент расшифрованного слова

Т_э = <8, 1, 2, 1, 3, 1> заменяется символами, в результате чего получается исходное слово Т₀ = <ЗАБАВА>.

2.3.4 АДДИТИВНЫЕ МЕТОДЫ ШИФРОВАНИЯ

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

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