Перехват

Рис. 9.1. Прямые и обратные криптопреобразования информации

методом перестановки информационных символов

Известный алгоритм усложнённой перестановки использует перестановки по «маршрутам Гамильтона⁴» Y-элементной таблицы-схемы T_k и состоит в следующем:

Шаг 1. Последовательная запись исходного M_о в таблицу T_k перестановки согласно нумерации её элементов. Если длина шифруемого ИМ M_о не кратна числу элементов T_k, то при последнем заполнении в свободные элементы заносится произвольный символ (знак).

( Например, Y = 8 (рис. 9.2, табл. 9.4),

M_о = <АВТОМАТИЗАЦИЯ_УПРАВЛЕНИЯ>,

1-я запись m₁ = <ЯИНЕЛВАР>,

2-я запись m₂ = <ПУ_ЯИЦАЗ>,

3-я запись m₃ = <ИТАМОТВА>).

5 6

1 2

3 4

7 8

Рис. 9.2. Пример 8-элементной таблицы Гамильтона

(обозначен маршрут № 1)

Таблица 9.4

Маршруты в таблице Гамильтона

Номер	Последовательность вершин таблицы
1	1	3	4	2	6	8	7	5
2	1	2	6	5	7	8	4	3
3	1	5	7	3	4	2	6	8
4	1	2	4	3	7	5	6	8
5	1	2	4	8	6	5	7	3
6	1	2	6	5	7	3	4	8
7	1	2	6	8	4	3	7	5
8	1	3	4	2	6	5	7	8
9	1	3	7	8	4	2	6	5
10	1	5	7	8	6	2	4	3
11	1	5	6	2	4	3	7	8
12	1	5	6	8	7	3	4	2
13	1	3	7	5	6	2	4	8
14	1	3	4	8	7	5	6	2
15	1	3	7	5	6	8	4	2
16	1	5	6	2	4	8	7	3
17	1	5	7	3	4	8	6	2
18	1	2	4	3	7	8	6	5

Шаг 2. Формирование ПИМ M_f путём выборки из таблицы T_k (после каждого её заполнения) символов шифруемого ИМ M_о по своему маршруту, при этом очерёдность маршрутов задаётся тайным ключом K*.

(K* = <4, 3, 5, 6, 2, 7, 8, 1, 14, 13, 15, 9, 16, 11, 12, 18, 17, 10>,

1-я выборка m₁ = <ЯНЕИВРАЛ >,

2-я выборка m₂ = <ПУЦИАЗЯ_>,

3-я выборка m₃ = <ИОВАМТТА>,

M_f = <ИОВАМТТАПУЦИАЗЯ_ЯНЕИВРАЛ>).

Шаг 3. Формирование выходного ПИМ M_g, передаваемого по линиям связи, путём разделения ПИМ M_f на g-значные группы с добавлением произвольных (*) символов на незаполненных позициях последней группы.

( g = 5, M_g = <*ИОВА_МТТАП_УЦИАЗ_Я_ЯНЕ_ИВРАЛ>).

Достоинства алгоритмов перестановки в простоте и возможности программной реализации.

Недостатками являются:

- низкая стойкость (при большой длине исходного ИМ в ПИМ M_f проявляются статистические закономерности ключа, что позволяет его легко раскрыть);

- низкая защищённость от тестирования (если длина блока в исходном ИМ равна N символам, то для раскрытия ключа достаточно пропустить через матрицу перестановки (N – 1) блоков специального тестового ИМ, в которых все символы, кроме одного, одинаковы).

Методы замены (подстановки) основаны на том, что символы исходного ИМ (блока), записанные в одном алфавите, заменяются на символы другого алфавита в соответствии с принятым ключом K преобразования:

K : S_oi S_fi , i = 1,…,I ; S_оi  M_о(A_о), S_fi  M_f(A_f). (9.8)

Различают прямую (моноалфавитную, монофоническую и др.) и рассчитываемую аналитически (полиалфавитную, многоконтурную и др.) подстановки.

В моноалфавитных подстановках устанавливается взаимооднозначное соответствие между каждым символом (знаком) S_fi алфавита сообщений (кортежа замен) A_f и соответствующим символом (знаком) S_оi ИМ, представленным в исходном алфавите A_о (табл. 9.5).

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

Ш аг 1. Формирование числового кортежа M_oh, F: M_о M_oh путём замены каждого символа (знака) S_оi  M_о , i = 1,…,I , представленного в исходном алфавите A_о размера [1R_о], на соответствующее число h(S_оi).

( Например, R = 33,

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

M_o = <АВТОМАТИЗАЦИЯ_УПРАВЛЕНИЯ>,

M_oh = <1, 3, 19, 15, 13, 1, 19, 10, 7, 1, 23, 10, 32, 33, 20, 16, 17, 1, 3, 12, 6, 14, 10, 32 >).

Шаг 2. Формирование эквивалентного числового кортежа M_fh путём последовательной замены каждого числа h_oi кортежа M_oh на эквивалентное число h_fi, i = 1,…,I кортежа M_fh по уравнению:

h_fi = [ k₁ h_оi(S_оi) + k₂ ] mod R_o , (9.9)

где k₁ – десятичный коэффициент; k₂ – коэффициент сдвига; mod – оператор вычитания по правилу модуля (R_o).

(k₁ = 5, k₂ = 10,

M_fh = <15, 25, 6, 19, 9, 15, 6, 27, 22, 15, 26, 27, 5, 10, 11, 24, 29, 15, 25, 4, 7, 14, 27, 5>).

Таблица 9.5

Вариант сопоставления двух алфавитов (таблица замены)

Ао		Аf
А	1	15	О
Б	2	20	У
В	3	25	Ш
Г	4	30	Э
Д	5	2	Б
Е	6	7	Ё
Ё	7	12	Л
Ж	8	17	Р
З	9	22	Х
И	10	27	Ь
К	11	32	Я
Л	12	4	Г
М	13	9	З
Н	14	14	Н
О	15	19	Т
П	16	24	Ч
Р	17	29	Ъ
С	18	1	А
Т	19	6	Е
У	20	11	К
Ф	21	16	П
Х	22	21	Ф
Ц	23	26	Щ
Ч	24	31	Ю
Ш	25	3	В
Щ	26	8	Ж
Ь	27	13	М
Ы	28	18	С
Ъ	29	23	Ц
Э	30	28	Ы
Ю	31	33	(пробел)
Я	32	5	Д
(пробел)	33	10	И

Шаг 3. Формирование ПИМ M_f, путём замены каждого числа h_fi(S_fi) кортежа M_fh соответствующим символом S_fi  M_f, i = 1,…,I, алфавита сообщений (шифровального алфавита или кортежа замен) A_f размера [1R_f], R_f = R_o.

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

M_f = <ОЩЖТёОЖЬХОШЬДИКЧЪОЩГЗНЬД>).

Шаг 4. Формирование выходного ПИМ M_g путём разделения ПИМ M_f на g-значные группы с добавлением произвольных (*) символов S_fj A_f, j = 1,…,J на незаполненных позициях последней группы.

(g = 5,

M_g = <ОЩЖТЁ_ОЖЬХО_ШЬДИК_ЧЪОЩГ_ЗНЬД*>).

Таким образом, при преобразовании производится замена исходных символов ИМ M_о на их эквивалент из кортежа замен A_f, смещённый от начала исходного алфавита A_о на величину k = k(k₁, k₂ ). При k₁ = 1, k₂ = 3 и R = 27 (латинский алфавит с пробелом) уравнение (9.9) превращается в известное уравнение алгоритма моноалфавитной подстановки Юлия Цезаря («шифр Цезаря»).

При обратном преобразовании поиск производится в кортеже замен A_f, а эквивалент выбирается из A_o . Однако, ПИМ имеет сравнительно низкий уровень защиты, так как исходный и преобразованный ИМ имеют одинаковые статистические характеристики, что позволяет осуществить (с помощью ЭВМ) частотный анализ встречаемости букв и их сочетаний (пар букв и др.).

Большинство искусственных и все естественные языки имеют характерное частотное распределение букв и других знаков [4]. Например, для русского языка наиболее часто «встречаются» буквы (в порядке убывания) о, е(ё), а, и, н; наименее часто – ф, щ, э; для английского языка – е, t, o, a, n и z, q, j, соответственно.

ИМ, зашифрованные методами перестановки или одноалфавитной подстановки, сохраняют характерное частотное распределение, а это даёт криптоаналитику путь к раскрытию шифра, на основе использования так называемого коэффициента соответствия  в качестве оценки суммы (_i p_i², i = 1,…,R) квадратов вероятностей каждой буквы:

 = [1/N(N – 1)] _i f_i(f_i– 1), i = 1,…,R (9.10)

где f_i – общее число встречаемости i-й буквы в ПИМ; N – количество букв в ПИМ-криптограмме (шифрограмме).

Например, для английского языка теоретически ожидаемое значение  определяется следующим выражением [4]:

 = [1/l(N – 1)] [0,066(N – l) + 0,038(l – 1)N ], (9.11)

где l – число алфавитов.

Тогда с учётом (9.11) при перехвате ПИМ значительного объёма (N  R) уже по значению  можно предположить, что если:

-  > 0,066 – использовалась одноалфавитная подстановка;

- 0,052 <  < 0,066 – использовалась двухалфавитная подстановка (и т.д. до  = 1/26 = 0,038);

-  < 0,038 – использовалась полиалфавитная подстановка с l  10.

Простая полиалфавитная подстановка (на основе матрицы T_v Вижинера⁵) последовательно и циклически меняет используемые алфавиты. При N-алфавитной подстановке символ (знак) S_o1 из исходного алфавита A_о заменяется символом (знаком) S_f1 из алфавита A_f1 , S_o2 – соответствующим S_f2 из алфавита A_f2 ,..., S_oN – S_fN из A_fN , S_o(N+1) – снова S_f1 из алфавита A_f1 и т.д. При этом обеспечивается маскировка естественной частотной статистики исходного языка A_о, так как конкретный символ (знак) S_oi  A_o может быть преобразован в несколько различных символов (знаков) шифровальных алфавитов A_fj, j = 1,…,N .

С другой стороны, различные символы (знаки) исходного алфавита могут быть заменены одинаковыми символами (знаками) шифровальных алфавитов. Степень обеспечиваемой защиты теоретически пропорциональна длине периода (N) в последовательности используемых алфавитов.

Алгоритм N-алфавитной замены (подстановки) реализуется следующим образом:

Шаг 1. Формирование матрицы T_v Вижинера размера [RR] циклическим сдвигом строк на одну позицию влево, начиная со строки алфавита A_o.

(Например, R = 33,

A_o =<АБВГД ... ЭЮЯ_>,

A	Б	В	…	Ю	Я	_
Б	В	Г	…	Я	_	А
В	Г	Д	…	_	А	Б
…	…	…	…	…	…	…
…	…	…	…	…	…	…
…	…	…	…	…	…	…
_	A	Б	…	Э	Ю	Я

T_v[3333] =

Шаг 2. Формирование матрицы T_k = KT_v замены размера [(N+1)R], где K – индикаторная матрица-ключ размера [(N+1)R], соответствующая символьному (буквенному) ключу K = <S_rn>, r  R, n = 1,…,N и содержащая в каждой строке единицу на позиции с номером, равным номеру r-го символа ключа K в алфавите A_o, а также в дополнительной строке.

(K = <АСУ>, r =(1, 18, 20), N = 3, R =33,

1	0	…	0	0	0	…	0	0
0	0	…	1	0	0	…	0	0
0	0	…	0	0	1	…	0	0
0	0	…	0	0	0	…	0	1

K_[433] =

A	Б	В	…	Ю	Я	_
C	Т	У	…	О	П	Р
У	Ф	Ц	…	Р	С	Т
_	A	Б	…	Э	Ю	Я

T_k[433] = KT_v =

Шаг 3. Попарное последовательное объединение символов исходного M_o ИМ с символами, повторяющими ключ K требуемое число раз с последующим преобразованием: символы M_o заменяются по T_k символами, расположенными на пересечении линий, соединяющих символы дополнительной (у нас последней) строки матрицы T_k и символы ключа K, находящиеся над ним.

(M_o = <АВТОМАТИЗАЦИЯ_УПРАВЛЕНИЯ>,

операция преобразования – сложение по mod 33 (табл. 9.6),

M_f = <БУЖПЮФУЫЬБЕЭ_СЗРБФГЭЫОЫТ>).

Таблица 9.6

Преобразование информации путём простого дополнения

в алгоритме трёхалфавитной замены

ИМ Mо	Ключ K	Операция преобразования (сложение по mod33)	ПИМ Mf
А	А	1 + 1 mod33 = 2	Б
В	С	2 + 18 mod33 = 20	У
Т	У	19 + 20 mod33 = 6	Ж
О	А	15 + 1 mod33 = 16	П
М	С	13 + 18 mod33 = 31	Ю
А	У	1 + 20 mod33 = 21	Ф
Т	А	19 + 1 mod33 = 20	У
И	С	10 + 18 mod33 = 28	Ы
З	У	7 + 20 mod33 = 27	Ь
А	А	1 + 1 mod33 = 2	Б
Ц	С	23 + 18 mod33 = 8	Е
И	У	10 + 20 mod33 = 30	Э
Я	А	32 + 1 mod33 = 0	_
_	С	0 + 18 mod33 = 18	С
У	У	20 + 20 mod33 = 7	З
П	А	16 + 1 mod33 = 17	Р
Р	С	17 + 18 mod33 = 2	Б
А	У	1 + 20 mod33 = 21	Ф
В	А	3 + 1 mod33 = 4	Г
Л	С	12 + 18 mod33 = 30	Э
Е	У	8 + 20 mod33 = 28	Ы
Н	А	14 + 1 mod33 = 15	О
И	С	10 + 18 mod33 = 28	Ы
Я	У	32 + 20 mod33 = 19	Т

Шаг 4. Формирование выходного ПИМ M_g путём разделения ПИМ M_f на g-значные группы с добавлением произвольных (*) символов S_rj A_o , r  R, j = 1,...,J на незаполненных позициях последней группы.

(g = 5,

M_g = <БУЖПЮ_ФУЫЬБ_ЕЭ_СЗ_РБФГЭ_ЫОЫТ*>).

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

во всех (кроме последней) строках T_v символы (знаки) расположить в произвольном порядке;

выбрать десять (не считая последней) строк, пронумерованных от 0 до 9;

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

e = 2,7182818285...,  = 3,14159265... или др.).

Алгоритм многоконтурной полиалфавитной подстановки использует L наборов алфавитов, применяемых циклически с периодами N_l, l = 1,…,L. При этом преобразованный символ S_fj  M_f , j = 1,…,J формируется из уравнения:

S_fj = S_oj₁, _{j mod N1}₂, _{j mod N2}... _L, _{j mod N L}, j = 1,…,J (9.12)

где S_oj – символ (знак) исходного ИМ M_о;  – знак некоторой обратимой операции; _l, l = 1,…,L – набор алфавитов (ключ полиалфавитного преобразования).

Надёжность данного алгоритма значительно выше, чем алгоритма простой полиалфавитной подстановки.

Алгоритмы монофонической полиалфавитной замены позволяют уравнивать частоту появления преобразованных символов и знаков и таким образом защищать ПИМ от раскрытия с помощью частотного анализа. Для знаков, встречающихся часто требуется относительно большое количество преобразованных эквивалентов, а для нечасто используемых исходных знаков – один, два [4].

Методы аналитических преобразований. Часто в алгоритмах замены, обеспечивающих надёжное преобразования ИМ, используются аналитические преобразования информации по некоторой формуле (аналитическому правилу). Например, по правилу умножения матрицы {t_ij} на вектор {z_i}:

t ₁₁ t₁₂ t₁₃ z₁ t₁₁z₁ + t₁₂z₂ + t₁₃z₃ z_f1

t₂₁ t₂₂ t₂₃  z₂ = t₂₁z₁ + t₂₂z₂ + t₂₃z₃ = z_f2 (9.13)

t₃₁ t₃₂ t₃₃ z₃ t₃₁z₁ + t₃₂z₂ + t₃₃z₃ z_f3 .

Тогда матрицу {t_ij} можно использовать в качестве T_k, знаками z_i, i = 1,2,3 вектора могут быть символы и знаки S_oi , i = 1,...,I исходного ИМ M_о, а знаками z_fi, i = 1,2,3 вектора-результата – символы и знаки S_fj, j = 1,...,J ПИМ M_f. Для преобразования буквенных ИМ M_o вначале заменяют символы и знаки алфавита их числовыми эквивалентами (порядковыми номерами букв и др.)

Для «депреобразования» используются те же правила умножения матрицы на вектор, только в качестве T_k берётся обратная матрица T_k^–1 ={t_ij⁰}, а в качестве умножаемого вектора – соответствующее количество чисел ПИМ M_f. Цифрами вектора-результата будут цифровые эквиваленты (h_oi ) символов и знаков исходного ИМ M_о.

Кроме того, на практике широко используются криптоалгоритмы, реализующие плохообратимые показательные функции. Прямое преобразование ИМ при этом осуществляется путём несложного вычисления значений показательных функций в полях Галуа⁶ с Q простыми элементами, с 2 элементами или в кольцах по модулю простых чисел (в отличие от двухсоставных чисел в (9.26)) [5]. Обратное преобразование ИМ (при отсутствии дополнительной информации) можно выполнить лишь путём огромного количества вычислений логарифмов в соответствующем поле.

Например,

M_f = a^Mo modQ, 1 < M_o < Q – 1, (9.14)

M_o = log_a M_f modQ , 1 < M_f < Q – 1, (9.15)

где Q {0, 1,..., Q – 1} – простое число конечного Q-элементного поля GF(Q) Галуа; a – фиксированный примитивный элемент поля GF(Q), т.е. степени a дают все ненулевые элементы поля (например, при Q = 7 имеем a = 3, так как a¹ = 3; a²= 9 mod 7 = 2; a³ = 27 mod 7 = 6; a⁴ = 4; a⁵ = 5; a⁶ = 1).

При повторяющемся возведении в квадрат для прямого вычисления по (9.13) потребуется не более 2log Q операций умножения [5].

Например:

a³⁷ = a³²⁺⁴⁺¹ = ((((a²)²)²)²)²(a²)²a¹.

Извлечение же логарифмов по modQ из M_f по (9.14) с целью получения M_o (другого метода пока не известно) потребует [5] проведения только предварительных вычислений по объёму пропорциональных величине

V(Q) = exp (lnQlnlnQ)^–0,5.

Для пары <i, j> абонентов, взаимодействующих в ИРС, можно записать

M_fi = a^Moi mod Q , (9.16)

M_fj = a^Moj mod Q , (9.17)

где M_oi , M_oj {1, 2,..., Q – 1} – случайно выбранные числа i-го и j-го абонентов, соответственно.

Тогда выражение:

K_ij = a^{Moi Moj} mod Q (9.18)

можно использовать в качестве тайного ключа, известного только паре <i, j> абонентов сети, реализующих каждый свои преобразования:

i: K_ij = M_fj^Moi mod Q = (a^Moj)^Moi mod Q = a^{M Moj} mod Q, (9.19)

j: K_ij = M_fi^Moj mod Q = (a^Moi)^Moj mod Q = a^{Moj Moi} mod Q . (9.20)

Посторонние абоненты, не зная M_oi, M_oj, вынуждены вычислять K_ij только по перехваченным M_fi, M_fj.

Если Q имеет длину 1000 бит, то для вычисления M_oi из M_fi потребуется примерно 2000 операций умножения 1000-битовых чисел. Для решения обратной задачи (на основе вычисления логарифмов над полем GF(Q) Галуа) потребуется более 2¹⁰⁰ (или  10³⁰) операций.

Отсюда с учётом (9.1) уровень стойкости такого криптоалгоритма на месячном интервале времени равен:

E = 10 lg(10³⁰/10⁸2,59210⁶)  160 дБ .

Методы гаммирования реализуются сложением символов исходного ИМ и ключа по модулю, равному числу букв в алфавите A_о (например, если используется двоичный алфавит A_о⁽²⁾ = <0, 1>, то производится сложение по mod 2). В качестве ключа они используют некоторую последовательность символов (кодов) того же алфавита A_о и такой же длины, что и в исходном ИМ.

Соответствующий алгоритм аддитивного преобразования ИМ может состоять, в частности, в следующем:

Шаг 1. Кодирование символов S_оi  M_о, i = 1,…,I исходного ИМ M_о и символов k_j  K_Г , j = 1,…,J_k ключа-гаммы (некоторой последовательности кодов) двоичным кодом и расположение их один под другим.

Шаг 2. Формирование ПИМ M_f путём замены каждой пары двоичных знаков одним двоичным знаком z_fi  M_f , i = 1,…,I_M согласно принятому уравнению преобразования (например, с помощью логической операции «исключающего ИЛИ»).

Шаг 3. Формирование ПИМ M_g, передаваемого по линиям связи путём замены полученной последовательности знаков z_fi  M_f , i = 1,…,I_M символами S_оi, i = 1,…,I_M алфавита A_о в соответствии с выбранным кодом.

Если ключ K_Г преобразования выбирается случайным образом, например, с помощью датчика псевдослучайных чисел (ПСЧ), то раскрыть ПИМ теоретически и практически невозможно (в случае, когда периодичность ключа превышает длину всех перехваченных ПИМ и никакой исходный ИМ не был похищен).

Датчики ПСЧ гененируют последовательности ключей K_Гj, j = 1,2,..., в которых числа k_ij  K_Гj , i = 1,…,I «кажутся случайными» и произвольно распределены в интервале [1, J_K], где J_K – некоторое максимальное число. К наиболее приемлемым (с точки зрения периодичности и случайности) для шифрования датчикам ПСЧ относится линейно-конгруэнтный⁷, вырабатывающий последовательность ПСЧ:

₁, ₂, ₃,..., _JK, ₁, ₂,... ,

используя соотношения:

_i+1 = (k₁_i + k₂) mod J_K, J_K = 2^b , b  2, (9.21)

где k₁, k₂ – константы, определяющие период повторения ПСЧ (причём, если k₂ – нечётная и k₁ mod 4 = 1, то J_K = max); _о – порождающее (исходное) число (может определяться идентификатором или паролем абонента, именем файла, длиной ИМ и др. константами); J_K – длина ключа-гаммы; b – длина машинного слова в бит.

Полученный ключ изменяется случайным образом для каждой группы символов (слова) исходного ИМ M_о в отличие от периодически повторяющегося (см. табл. 9.6).

Применение длинного ключа, для которого I_M = J_K, ограничено объёмом памяти ЭВМ, а также резким (в 2 раза) увеличением объёма информационного массива <M_g ,K_Г>, передаваемого по линиям связи.

Указанные недостатки метода гаммирования снижают возможности использования его на практике. Поэтому в АИС он реализуется, как правило, в комбинированных алгоритмах (в комбинации с методами перестановки и замены по типу второго закрытия при защите особенно важных ИМ).

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