3.1. Стохастическое преобразование информации

В качестве одного из алгоритмов нелинейного преобразования элементов x_i n-разрядной информационной последовательности

x = x₁ x₂ x₃ … x_i … x_m

длиной m под управлением ключевой n-разрядной последовательности

γ = γ₁ γ₂ γ₃ … γ_i … γ_m

такой же длины и качественного генератора псевдослучайных последовательностей (ПСП) с числом состояний 2ⁿ можно предложить следующий (рис. 3.1) . Для каждого элемента x_i повторяем нижеприведенную последовательность действий:

• очередной элемент x_i входной последовательности загружаем в память генератора ПСП;

• выполняем γ_i тактов работы генератора;

• состояние генератора после γ_i тактов работы при начальном состоянии x_i объявляем результатом y_i преобразования элемента x_i.

После преобразования всех элементов исходной последовательности будет получена результирующая последовательность

y = y₁ y₂ y₃ … y_i … y_m

длиной m, для каждого элемента которой справедливо

y_i = R(x_i, γ_i).

Данное преобразование может эффективно использоваться для решения различных задач, связанных с защитой информации. Впервые оно было предложено С. А. Осмоловским для реализации стохастического кодирования информации [2, 3]. В данной главе рассматривается его применение для построения генераторов ПСП.

Рис. 3.1. Стохастическое преобразование информационной последовательности {x_i}

3.2. R-блок

Схема одного из возможных вариантов построения блока R стохастического преобразования (Random) и его условное графическое обозначение показаны соответственно на рис. 3.2 и 3.3.

Ключевая информация R-блока – характер заполнения таблицы

,

размерности n × 2ⁿ, содержащей элементы GF(2ⁿ), перемешанные случайным образом, т. е. H(m) ∈ GF(2ⁿ). Результат R_H(A, B) преобразования входного n-разрядного двоичного набора А зависит от заполнения таблицы H и параметра преобразования В, задающего смещение в таблице относительно ячейки, содержащей значение А, следующим образом:

R_H(A,B) = H((m_A+B) mod 2ⁿ),

где m_A – адрес ячейки таблицы H, содержащей код А, т. е. H(m_A) = A. Другими словами, результат работы R-блока суть считывание содержимого ячейки таблицы H, циклически смещенной на В позиций в сторону старших адресов относительно ячейки, содержащей код А.

Для ускорения преобразования в состав R-блока вводится вспомогательный адресный массив

Addr = {Addr(j)}

размерности n × 2ⁿ, причем

Иными словами, ячейка с адресом j в массиве ADDR хранит адрес ячейки массива H, содержащей код j.

Заслуживают внимания следующие факты:

• при Addr = {0, 1, 2, ..., (2ⁿ – 1)}, т. е. при записи в каждую ячейку массива Addr ее собственного адреса, и n = 4 результат преобразования в точности совпадает с результатами работы двух тактов (сложение с 4 битами ключа и замена в соответствующем узле замены) одной секции раундовой функции российского стандарта криптографической защиты, ГОСТ 28147-89;

• в частном случае при Addr = {0, 1, 2, ..., (2ⁿ – 1)} и В = 0 получаем классический S-блок (блок замены) с таблицей замен Н;

• при записи в каждую ячейку массивов H и Addr ее собственного адреса получаем классический сумматор по модулю 2ⁿ, а значит, с полным на то основанием R-блок может быть назван стохастическим сумматором;

• по такому же принципу (заменой сумматора по модулю 256 на операцию поразрядного XOR) может быть построен стохастический сумматор в поле GF(2⁸) (стохастический XOR), а также другие элементы (AND, OR, mod p и т. п.) ;

• требует дополнительного исследования схема стохастического преобразования, показанная на рис. 3.4, где функция F – сумматор по модулю 2⁸ или поразрядный XOR (а возможно и другие операции AND, OR, mod p и т. п.).

Рис. 3.2. Логика работы R-блока

Рис. 3.3. Условное графическое обозначение R-блока

Рис. 3.4. Вариант схемы блока стохастического преобразования (RF‑блок)

Ключевая информация, необходимая для работы R-блока, – содержимое таблицы H стохастического преобразования. Алгоритм замены ключевой информации, т. е. «перемешивания» или «взбивания» таблиц H, показан на рис. 3.5. Каждая очередная пара байтов

BYTE_i, BYTE_i+1

инициализирующей последовательности меняет местами два соответствующих элемента массива Н, т. е. выполняется операция

H(BYTE_i) ↔ H(BYTE_i+1), i = 0, 2, 4, ...,

где H(j) – элемент массива Н, расположенный в ячейке с адресом j. Алгоритм формирования вспомогательного массива Addr показан на рис. 3.6.

Рис. 3.5. Схема алгоритма «перемешивания» таблицы стохастического преобразования с использованием инициализирующей ПСП BYTE₀, BYTE₁, BYTE₂, ..., BYTE_i, BYTE_{i + 1}, ...

Рис. 3.6. Схема алгоритма формирования адресного массива Addr по известному массиву H

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

Учитывая, что циклически сдвинутые таблицы стохастического преобразования эквивалентны, существует 255! различных вариантов заполнения таблицы H.

Рис. 3.7. Схема алгоритма формирования таблицы стохастического преобразования с использованием инициализирующей ПСП
BYTE₀, BYTE₁, BYTE₂, ..., BYTE_i,...

Возможен вариант использования R-блока, когда содержимое массива Н (а значит, и содержимое массива Addr) зафиксировано, а ключевая информация подается на вход В параметра преобразования. В этой ситуации для обеспечения возможности вычисления результата преобразования «на лету» (без использования таблиц) в качестве содержимого массива Н выбираются последовательные состояния генератора ПСП, который допускает эффективную программную реализацию.

3.3. Стохастические генераторы многоразрядных ПСП на регистрах сдвига – RFSR

Для построения стохастического генератора ПСП (Random Feedback Shift Register – RFSR) предлагается в схемах аддитивного генератора вместо блоков сложения использовать R-блоки (рис. 3.8) [1]. Ключевая информация – заполнение таблиц Н, определяющих логику работы R-блоков.

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

Рассмотрим вариант схемы генератора с одним R-блоком, который может быть представлен в одном из двух идентичных вариантов (рис. 3.9, а – RFSR1 или 3.9, б – RFSR2). При соответствующем выборе таблицы стохастического преобразования выходная ПСП по сути – это нелинейная М-последовательность, т. е. последовательность максимальной длины, по своим статистическим свойствам превосходящая классическую М-последова­тельность с выхода LFSR той же разрядности (рис. 3.10 – 3.11).

На рис. 3.10 и 3.11 показаны примеры генераторов стохастической М-последовательности длиной соответственно 15 и 63.

На рис. 3.12 приведен пример преобразования стохастического генератора, диаграмма состояний которого состоит из трех циклов длиной 22, 25, 16 и одного тривиального цикла, состоящего из состояния 000, переходящего самого в себя, в генератор последовательности длиной 64. Преобразование потребовало включения в состав устройства сумматора и элемента ИЛИ-НЕ, выход которого соединен со входом переноса сумматора. Переходы исходного генератора на рис. 3.12 показаны пунктирной линией.

Рис. 3.8. Общие схемы стохастических генераторов n-разрядной ПСП (режим OFB) с управляющим входом. Q_i – состояние i-го регистра генератора

Рис. 3.9. Варианты схемы стохастического генератора RFSR с одним R‑блоком (режим OFB)

а
б
Рис. 3.10. Стохастический генератор при N = 2: схема генератора – а; возможные таблицы преобразования и соответствующие им диаграммы переключений – б

а
б
Рис. 3.11. Стохастический генератор при N = 3:
схема генератора и таблица стохастического преобразования – а;
диаграмма его переключений – б

а
б
Рис. 3.12. Стохастический генератор ПСП длиной 64:
схема генератора и таблица стохастического преобразования – а;
диаграмма его переключений – б

На рис. 3.13 приведена схема генератора ПСП с непрерывно изменяющейся таблицей стохастического преобразования. В каж­дом такте работы такого RFSR слово (BYTE_i+1, BYTE_i) с выхода управляющего генератора меняет местами содержимое двух ячеек таблиц Н:

Н(BYTE_i+1)(Н(BYTE_i).

Рис. 3.13. Cхема генератора ПСП с непрерывно изменяющейся таблицей стохастического преобразования

3.4. Криптоанализ RFSR

Рассмотрим процедуру определения таблицы H стохастического преобразования RFSR с одним R-блоком по перехваченному фрагменту длиной m выходной последовательности на примере криптоанализа четырехразрядного стохастического генерато­ра, соответствующего Ф(х) = х⁴ + х³ + 1 (рис. 3.14). Таблица H стохастического преобразования имеет размерность 4 × 16 и содержит все 4-разрядные двоичные коды, перемешанные случайным образом, а число N регистров RFSR равно 4. Уравнение формирования очередного элемента γ(t) выходной последовательности γ имеет вид:

γ(t) = R(γ(t – 3), γ(t – 4)).

Предположим, был перехвачен фрагмент длиной m = 35:

9 2 3 14 14 10 11 10 3 13 0 4 14 4 4 9 9 12 1 13 11 9 10 14 5 2 12 13 3 3 0 0 5 3 0.

Шаг 1. «Перемещая» уравнение v(t) = R(γ(t – 3), γ(t – 4)) вдоль перехваченного фрагмента (, получим список А из 31-го равенства вида R(a, b) = c (рис. 3.15, а), где a, b и c – элементы фрагмента (. Равенство R(a, b) = c означает, что в искомой таблице Н элемент с циклически смещен в сторону старших адресов относительно элемента а на b позиций. В общем случае число этих равенств равно m – N.

Шаг 2. Проанализируем список А и исключим из него повторяющиеся строки, а также равенства вида R(a, 0) = a, не содержащие никакой полезной информации. Исключив из списка А равенства R(4, 0) = 4 и R(0, 0) = 0, получим новый список А, содержащий 29 равенств (рис. 3.15, б).

Шаг 3. Организуем еще три списка: В, С и D. Список В определяет последовательность анализа равенств из списка А (рис. 3.15, в). Равенствам R(a, b) = c, которые будут анализироваться первым, вторым, третьим, … в списке В будут соответствовать номера 1, 2, 3, … . Список С определяет последовательность заполнения таблицы Н (рис. 3.15, г). Ячейкам таблицы Н, которые будут заполнены первой, второй, третьей, … , в списке С будут соответствовать номера 1, 2, 3, … . Список D последовательно заполняется анализируемыми элементами таблицы Н (рис. 3.15, е).

Шаг 4. Начнем анализ первого равенства R(2, 9) = 14 в списке А. Запишем в верхнюю ячейку таблицы Н и в список D анализируемых элементов значение а = 2. Присвоим верхней ячейке таблицы Н номер 1 в списке С.

Шаг 5. Начнем анализ элемента 2 из списка D. Просмотрим список А на предмет наличия в нем равенств, в которых значение а = 2. Этому условию удовлетворяют равенства R(2, 9) = 14 и R(2, 5) = 3. Присвоим им номера соответственно 1 и 2 в списке В. Просмотрим список А на предмет наличия в нем равенств, в которых значение с = 2. Этому условию удовлетворяет равенство R(10, 9) = 2. Присвоим ему номер 3 в списке В.

Равенство R(2, 9) = 14 означает, что элемент 14 в таблице Н циклически смещен относительно элемента 2 на 9 позиций. Найдем соответствующую ячейку таблицы Н и запишем в нее значение с = 14. Присвоим этой ячейке номер 2 в списке С. Равенство R(2, 5) = 3 означает, что элемент 3 в таблице Н циклически смещен относительно элемента 2 на 5 позиций. Найдем соответствующую ячейку таблицы Н и запишем в нее значение с = 3. Присвоим этой ячейке номер 3 в списке С. Равенство R(10, 9) = 2 означает, что элемент 2 в таблице Н циклически смещен относительно элемента 10 на 9 позиций. Найдем соответствующую ячейку таблицы Н и запишем в нее значение а = 10. Присвоим этой ячейке номер 4 в списке С.

Анализ элемента 2 и соответствующих ему равенств в списке А закончен. Внесем под номером 2 в список D элемент, записанный в таблицу Н вторым, т. е. элемент 14.

Шаг 6. Возьмем следующий элемент из списка D, имеющий номер 2, т. е. 14. Приступим к его анализу. Просмотрим список А на предмет наличия в нем равенств, в которых значение а = 14. Этому условию удовлетворяют 4 равенства R(14, 3) = 11, R(14, 14) = 10, R(14, 4) = 9 и R(14, 10) = 12. Присвоим им номера соответственно 4, 5, 6 и 7 в списке В. Просмотрим список А на предмет наличия в нем равенств, в которых значение с = 14. Этому условию удовлетворяют 2 равенства R(13, 3) = 14 и R(11, 13) = 14. Присвоим им номера соответственно 8 и 9 в списке В.

Равенство R(14, 3) = 11 означает, что элемент 11 в таблице Н циклически смещен относительно элемента 14 на 3 позиции. Найдем соответствующую ячейку таблицы Н и запишем в нее значение с = 11. Присвоим этой ячейке номер 5 в списке С. Равенство R(14, 14) = 10 означает, что элемент 10 в таблице Н циклически смещен относительно элемента 14 на 14 позиций. Этот факт уже отражен в таблице, т. е. равенство никакой полезной информации не дает. Равенство R(14, 4) = 9 означает, что элемент 9 в таблице Н циклически смещен относительно элемента 14 на 4 позиции. Найдем соответствующую ячейку таблицы Н и запишем в нее значение с = 9. Присвоим этой ячейке номер 6 в списке С. Равенство R(14, 10) = 12 означает, что элемент 12 в таблице Н циклически смещен относительно элемента 14 на 10 позиций. Найдем соответствующую ячейку таблицы Н и запишем в нее значение с = 12. Присвоим этой ячейке номер 7 в списке С.

Равенство R(13, 3) = 14 означает, что элемент 14 в таблице Н циклически смещен относительно элемента 13 на 3 позиции. Найдем соответствующую ячейку таблицы Н и запишем в нее значение a = 13. Присвоим этой ячейке номер 8 в списке С. Равенство R(11, 13) = 14 означает, что элемент 14 в таблице Н циклически смещен относительно элемента 11 на 13 позиций. Этот факт уже отражен в таблице, т. е. равенство никакой полезной информации не дает.

На рис. 3.15 отражена ситуация на этот момент, при этом знаком «+» помечены те элементы списков В и D, анализ которых дал результат, а знаком «–» – те элементы списков В и D, анализ которых оказался безрезультатным.

Анализ элемента 14 и соответствующих ему равенств в списке А закончен. Внесем под номером 3 в список D элемент, записанный в таблицу Н третьим, т. е. элемент 3.

Шаг 7. Возьмем следующий элемент из списка D, имеющий номер 3, т. е. 3. Приступим к его анализу. Просмотрим список А на предмет наличия в нем равенств, в которых значение а = 3. Этому условию удовлетворяют 4 равенства R(3, 2) = 10, R(3, 10) = 4, R(3, 13) = 0, R(3, 3) = 5. Присвоим им номера соответственно 10, 11, 12 и 13 в списке В. Просмотрим список А на предмет наличия в нем равенств, в которых значение с = 3. Этому условию удовлетворяют 3 равенства R(10, 14) = 3, R(12, 2) = 3 и R(0, 3) = 3. Присвоим им номера соответственно 14, 15 и 16 в списке В.

Равенство R(3, 2) = 10 означает, что элемент 10 в таблице Н циклически смещен относительно элемента 3 на 2 позиции. Этот факт уже отражен в таблице, т. е. равенство никакой полезной информации не дает. Равенство R(3, 10) = 4 означает, что элемент 4 в таблице Н циклически смещен относительно элемента 3 на 10 позиций. Найдем соответствующую ячейку таблицы Н и запишем в нее значение с = 4. Присвоим этой ячейке номер 9 в списке С. Равенство R(3, 13) = 0 означает, что элемент 0 в таблице Н циклически смещен относительно элемента 3 на 13 позиций. Найдем соответствующую ячейку таблицы Н и запишем в нее значение с = 0. Присвоим этой ячейке номер 10 в списке С. Равенство R(3, 3) = 5 означает, что элемент 5 в таблице Н циклически смещен относительно элемента 3 на 3 позиции. Найдем соответствующую ячейку таблицы Н и запишем в нее значение с = 5. Присвоим этой ячейке номер 11 в списке С.

Равенство R(10, 14) = 3 означает, что элемент 3 в таблице Н циклически смещен относительно элемента 10 на 14 позиций. Равенство R(12, 2) = 3 означает, что элемент 3 в таблице Н циклически смещен относительно элемента 12 на 2 позиции. Равенство R(0, 3) = 3 означает, что элемент 3 в таблице Н циклически смещен относительно элемента 0 на 3 позиции. Все эти факты уже отражены в таблице, т. е. равенства никакой полезной информации не дают.

Анализ элемента 3 и соответствующих ему равенств в списке А закончен. Внесем под номером 4 в список D элемент, записанный в таблицу Н четвертым, т. е. элемент 10.

Шаг 8. Возьмем следующий элемент из списка D, имеющий номер 4, т. е. 10. Приступим к его анализу. Просмотрим список А на предмет наличия в нем равенств, в которых значение а = 10. Этому условию удовлетворяет равенство R(10, 11) = 0. Присвоим ему номер 17 в списке В. Просмотрим список А на предмет наличия в нем равенств, в которых значение с = 10. Этому условию удовлетворяет равенство R(13, 1) = 10. Присвоим ему номер 18 в списке В. Анализ этих равенств никакой полезной информации не дает.

Внесем под номером 5 в список D элемент, записанный в таблицу Н пятым, т. е. элемент 11.

Шаг 9. Возьмем следующий элемент из списка D, имеющий номер 5, т. е. 11. Приступим к его анализу. Просмотрим список А на предмет наличия в нем равенств, в которых значение а или с равно 11. Этому условию удовлетворяют два равенства R(11, 10) = 13 и R(12, 9) = 11. Присвоим им номера соответственно 19 и 20 в списке В. Анализ этих равенств никакой полезной информации не дает.

Внесем под номером 6 в список D элемент, записанный в таблицу Н шестым, т. е. элемент 9.

Шаг 10. Возьмем следующий элемент из списка D, имеющий номер 6, т. е. 9. Приступим к его анализу. Просмотрим список А на предмет наличия в нем равенств, в которых значение а или с равно 9. Этому условию удовлетворяют пять равенства R(9, 4) = 1, R(9, 9) = 13, R(9, 11) = 5, R(4, 14) = 9 и R(1, 12) = 9. Присвоим им номера соответственно 21, 22, 23, 24 и 25 в списке В.

Равенство R(9, 4) = 1 означает, что элемент 1 в таблице Н циклически смещен относительно элемента 9 на 4 позиции. Найдем соответствующую ячейку таблицы Н и запишем в нее значение с = 1. Присвоим этой ячейке номер 12 в списке С. Анализ остальных равенств никакой полезной информации не дает.

На рис. 3.16 отражена ситуация на этот момент.

Внесем под номером 7 в список D элемент, записанный в таблицу Н седьмым, т. е. элемент 12.

Шаг 11. Возьмем следующий элемент из списка D, имеющий номер 7, т. е. 12. Приступим к его анализу. Просмотрим список А на предмет наличия в нем равенств, в которых значение а или с равно 12. Этому условию удовлетворяет равенство R(4, 4) = 12. Присвоим ему номер 26 в списке В. Анализ этого равенства никакой полезной информации не дает.

Внесем под номером 8 в список D элемент, записанный в таблицу Н восьмым, т. е. элемент 13.

Шаг 12. Возьмем следующий элемент из списка D, имеющий номер 8, т. е. 13. Приступим к его анализу. Просмотрим список А на предмет наличия в нем равенств, в которых значение а или с равно 13. Этому условию удовлетворяют два равенства R(13, 12) = 0 и R(5, 14) = 13. Присвоим им номера соответственно 27 и 28 в списке В. Анализ первого из них никакой полезной информации не дает. Равенство R(5, 14) = 13 означает, что элемент 13 в таблице Н циклически смещен относительно элемента 5 на 14 позиций. Найдем соответствующую ячейку таблицы Н и запишем в нее значение а = 5. Присвоим этой ячейке номер 13 в списке С.

Внесем под номером 9 в список D элемент, записанный в таблицу Н девятым, т. е. элемент 4.

Шаг 13. Возьмем следующий элемент из списка D, имеющий номер 8, т. е. 4. Приступим к его анализу. Просмотрим список А на предмет наличия в нем равенств, в которых значение а или с равно 4. Этому условию удовлетворяет равенство R(0, 13) = 4. Присвоим ему номер 29 в списке В. Анализ этого равенства никакой полезной информации не дает.

Рис. 3.14. Пример четырехразрядного RFSR, соответствующего Ф(х) = х⁴ + х³ + 1, и фрагмент его выходной последовательности

Рис. 3.15. Результат 6 шагов процедуры криптоанализа;
Исходный список A равенств вида R(a, b) = c – a; модифицированный список A – б; список B, т. е. последовательность анализа равенств из списка A – в; список C, т. е. последовательность заполнения таблицы H – г; таблица H – д; список D, т. е. последовательность анализируемых элементов таблицы H – е

Рис. 3.16. Результат 10 шагов процедуры криптоанализа

Список А исчерпан, т. е. процедура анализа закончена (рис. 3.17). В таблице Н остались три незаполненные ячейки, а значит, перехваченный фрагмент выходной последовательности мог быть получен с выхода одного из 6 генераторов, таблицы стохастического преобразования которых показаны на рис. 3.18.

Рис. 3.17. Результат 13 шагов процедуры криптоанализа

Рис. 3.18. Варианты заполнения таблицы стохастического преобразования анализируемого RFSR

Для определения заполнения таблицы Н восьмиразрядного RFSR в самом благоприятном случае необходим фрагмент выходной последовательности длиной не менее 2⁸ + N байт, где N – число регистров генератора.

Можно выделить следующие направления в попытках решения проблемы стойкости стохастических генераторов ПСП:

• реализация функции обратной связи генератора на основе нескольких R-блоков;

• использование для формирования элементов выходной последовательности нелинейной функции выхода (в том числе реализованной с использованием R-блоков и блоков пространственного сжатия);

• использование приемов, аналогичных тем, которые применяются при построении генераторов на LFSR; например, использование нескольких RFSR, выходы которых обрабатываются функцией усложнения; работа по принципу stop-and-go и пр.;

• использование многоступенчатой структуры, при которой элементы выходных последовательностей RFSR первой ступени никогда не проходят на выход.

3.5. Двухступенчатые стохастические генераторы многоразрядных ПСП

Генераторы ПСП, схемы которых приведены на рис. 3.9, функционируют в режиме OFB. На рис. 3.19 показаны схемы двух вариантов формирования ПСП в режиме Counter. В состав устройства на рис. 3.19, а входят два генератора, байтовые ПСП с выхода которых поступают на входы R-блока.

Рис. 3.19. Варианты схемы стохастического генератора ПСП: выходная последовательность γ суть результат стохастического преобразования последовательности x₁ под управлением последовательности x₂ – а; выходная последовательность γ суть результат перемешивания двух ПСП под управлением третьей – б (режим Counter)

Первая ступень устройства на рис. 3.19, б – генератор ПСП, формирующий три пары n*-разрядных последовательностей, каждая из которых поступает на входы соответствующего R-блока. Последовательности, формируемые на выходах первого и второго R-блоков, перемешиваются под управлением последовательности с выхода третьего R-блока. Перемешивание обеспечивают n одноразрядных мультиплексоров 2 → 1. Включение в состав устройства блоков пространственного сжатия (БПС) информации n* → n позволяет исключить появление на выходе генератора двоичных наборов с выходов R-блоков.

Рассмотрим случай, когда n* = n. Для получения n-разрядной выходной последовательности

γ = γ₁γ₂γ₃...γ_t...

используется три n-разрядных R-блока, каждому из которых соответствует своя таблица H_i, i = 1, 2, 3, причем

.

Пусть

n-разрядный двоичный набор на выходе i-го R-блока в момент времени t, r_ij(t) ∈ {0, 1}, i = 1, 2, 3, Тогда уравнения работы генератора имеют вид

или

где Q_l(t) – n-разрядный код на l-м выходе ГПК в момент времени t, 0 < l < 5.

3.6. Стохастические генераторы ПСП с многораундовой функцией обратной связи

Одной из типовых структур, использующихся для построения многораундовых функций обратной связи генераторов ПСП, является квадрат (см. главу 1). Рассмотрим вариант схемы с подобной структурой на основе R-блоков. Входной блок разрядностью 128 бит и все промежуточные результаты его преобразования представляются двумерным массивом байтов размерностью 4 × 4, вид этого массива показан на рис. 3.20, а, где a_ij – элемент массива (байт), находящийся на пересечении i-й строки и j-го столбца, . Преобразование (рис. 3.20, б) суть многократное повторение одного и того же раунда, состоящего из трех операций:

• перемешивание строк;

• перемешивание столбцов;

• стохастическое преобразование байтов блока с использованием элементов (байтов) раундового ключа.

На рис. 3.21 показана схема операции стохастического преобразования байтов a_ij с использованием блоков стохастического R₁ преобразования, параметрами преобразования являются соответствующие байты k_ij раундового ключа, ,, i – номер строки, j – номер столбца, a(_ij – преобразованный байт, т. е. a(_ij = R₁(a_ij, k_ij).

На рис. 3.22 показаны варианты 4-тактного перемешивания строк

a_i3 a_i2 a_i1 a_i0, ,

с использованием блоков R₂ – R₅. На рис. 3.23 – варианты 4‑тактного перемешивания столбцов

a_3j a_2j a_1j a_0j, ,

с использованием блоков R₆ – R₉. Начальное состояние Q₃ Q₂ Q₁Q₀ регистров при преобразовании строк (столбцов) равно байтам строки (столбца) или соответствующим байтам ключа. Байты ключа в первом случае или байты строк (столбцов) во втором случае поступают на вход схем последовательно: в первом такте 3-й байт, во втором – 2-й, в третьем – 1-й и в четвертом 0-й.

Рис. 3.20. Принцип построения функции обратной связи генератора ПСП. Структура блока данных – а; процедура преобразования блока данных – б

Рис. 3.21. Раундовая операция стохастического преобразования байтов

Рис. 3.22. Варианты раундовой операции стохастического преобразования строк

Рис. 3.23. Варианты раундовой операции стохастического преобразования столбцов

На рис. 3.24, а показана схема формирования раундовых ключей из исходного 128-разрядного ключа, где k_i – 32-разрядные элементы ключа (столбцы); начальное заполнение генератора раундовых ключей равно k₃ k₂ k₁ k₀, т. е. исходному ключу. Функция F обратной связи зависит от индекса i: при i = 4n – 1, где n – натуральное, схема преобразования F показана на рис. 3.24, б, где con_3r con_2r con_1r con_0r – байты 32-разрядной константы (r – номер 128-разрядного ключевого элемента), в противном случае блок F осуществляет простую передачу 32-разрядного входного набора на выход без изменения. В качестве r-й константы можно использовать, например, состояние 32-разрядного LFSR в r-м такте его работы.

Рис. 3.24. Формирование раундовых ключей:
схема формирования – а; схема 4-тактного преобразования F – б

Можно предложить следующие варианты заполнения таблиц Н 1 – Н 9:

• фиксированные таблицы стохастического преобразования;

• таблицы, перемешанные с использованием исходной ключевой информации одним из указанных в разделе 3.2 способов.

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

3.7. Выводы

1. Рассмотренная схема 8-разрядного стохастического преобразования (R-блок) может эффективно использоваться для генерации ПСП.

2. Основным достоинством блоков стохастического преобразования и генераторов ПСП на их основе является эффективная программная и аппаратная реализация при приемлемой для большинства приложений криптостойкости.

3. Ключевая информация, необходимая для работы 8-разрядного блока стохастического преобразования, суть характер заполнения массива размерности 8×256. Всего существует 255! вариантов заполнения этого массива.

Литература к главе 3

1) Жуков И. Ю., Иванов М. А., Осмоловский С. А. Принципы построения криптостойких генераторов псевдослучайных кодов // Проблемы информационной безопасности. Компьютерные системы. 2001. № 1. С. 55–65.

2) Осмоловский С. А. Стохастические методы передачи данных. М.: Радио и связь, 1991.

3) Стохастическая защита информации кодами Осмоловского. http://stocos.ru