9.3.1. методы замены

9.3.1. методы замены

Сущность методов замены (подстановки) заключается в замене символов исходной информации, записанных в одном алфавите, символами из другого алфавита по определенному правилу [56]. Самым простым является метод прямой замены. Символам s0i исходного алфавита A0, с помощью которых записывается исходная информация, однозначно ставятся в соответствие символы sli шифрующего алфавита A1. В простейшем случае оба алфавита могут состоять из одного и того же набора символов. Например, оба алфавита могут содержать буквы русского алфавита.

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

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

Шаг 1. Формирование числового кортежа L0h путем замены каждого символа s0i ä Т0 (1=1,К), представленного в исходном алфавите A0 размера [1xR], на число h0i(s0i), соответствующее порядковому номеру символа s0i в алфавите A0.

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

hli = (k1 x h0i(s0i) + k2)(mod R),

где k1 десятичный коэффициент; k2 коэффициент сдвига. Выбранные коэффициенты k1 k2 должны обеспечивать однозначное соответствие чисел h0i и hli, а при получении hli = 0 выполнить замену hli = R.

Шаг 3. Получение шифртекста T1 путем замены каждого числа hli(sli)кортежа L1h соответствующим символом sli ä T1 (i=1,K) алфавита шифрования A1 размера [1XR].

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

Рис. 15. Классификация методов шифрования

Пример. Исходными данными для шифрования являются:

T0 = <МЕТОД_ШИФРОВАНИЯ>;

A0 = <АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ_>;

А1 = <ОРЩЬЯТЭ_ЖМЧХАВДЫФКСЕЗПИЦГН

ЛЪШБУЮ>;

R=32; k1=3; k2=15, b=4.

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

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

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

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

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

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

k1 h0i +k2=nR+ hli,

При известных целых величинах k1 k2, hli и R величина h0i вычисляется методом перебора n.

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

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

Таблица 1

Таблица замены

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

Расшифрование осуществляется аналогичным образом, но вход в таблицу производится по строке sli.

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

Существенно более стойкими являются методы полиалфавитной замены. Такие методы основаны на использовании нескольких алфавитов для замены символов исходного текста. Формально полиалфавитную замену можно представить следующим образом. При N алфавитной замене символ s01 из исходного алфавита A0 заменяется символом s11 из алфавита А1, s02 заменяется символом s22 из алфавита А2 и так далее. После замены s0N символом sNN из AN символ s0(N+1) замещается символом s1(N+1) из алфавита А1 и так далее.

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

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

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

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

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

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

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

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

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

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

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

3) определяется столбец j, для которого выполняется условие: s0r= bij;

4) символ s0r замещается символом bij.

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

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

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

Шаг 2. Последовательно выбираются символы s1r из шифртекста и соответствующие символы ключа km, В матрице Тш определяется строка i, для которой выполняется условие km= bil. В строке i определяется элемент bij = s1r. В расшифрованный текст на позицию r помещается символ blj.

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

Пример.

Требуется с помощью ключа К = <ЗОНД> зашифровать исходный текст Т = <БЕЗОБЛАЧНОЕ_НЕБО>. Механизмы зашифрования и расшифрования представлены на рис. 18.

Рис. 18. Пример шифрования с помощью матрицы Вижинера

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

Для повышения криптостойкости может использоваться модифицированная матрица шифрования. Она представляет собой матрицу размерности [11,R], где R число символов алфавита. В первой строке располагаются символы в алфавитном порядке. Остальные 10 строк нумеруются от 0 до 9. В этих строках символы располагаются случайным образом.

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