Стохастические генераторы псевдослучайных последовательностей

          

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


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

Стохастические генераторы псевдослучайных последовательностей


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

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

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

? = ?1?2?3...?t...

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

Стохастические генераторы псевдослучайных последовательностей
.

Пусть

Стохастические генераторы псевдослучайных последовательностей

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

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

Стохастические генераторы псевдослучайных последовательностей

или

Стохастические генераторы псевдослучайных последовательностей

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



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


Рассмотрим процедуру определения таблицы H стохастического преобразования RFSR с одним R-блоком по перехваченному фрагменту длиной m выходной последовательности на примере криптоанализа четырехразрядного стохастического генерато­ра, соответствующего Ф(х) = х4 + х3 + 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, соответствующего Ф(х) = х4 + х3 + 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 в самом благоприятном случае необходим фрагмент выходной последовательности длиной не менее 28 + N байт, где N – число регистров генератора.

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

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

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

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

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


R-блок


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

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

Стохастические генераторы псевдослучайных последовательностей
,

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

RH(A,B) = H((mA+B) mod 2n),

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

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

Addr = {Addr(j)}

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

Стохастические генераторы псевдослучайных последовательностей

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

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

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

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

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

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

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

Стохастические генераторы псевдослучайных последовательностей

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

Стохастические генераторы псевдослучайных последовательностей


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

Стохастические генераторы псевдослучайных последовательностей


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

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

BYTEi, BYTEi+1

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

H(BYTEi) - H(BYTEi+1), i = 0, 2, 4, ...,

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

Стохастические генераторы псевдослучайных последовательностей


Рис. 3.5. Схема алгоритма «перемешивания» таблицы стохастического преобразования с использованием инициализирующей ПСП BYTE0, BYTE1, BYTE2, ..., BYTEi, BYTEi + 1, ...

Стохастические генераторы псевдослучайных последовательностей


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

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

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

Стохастические генераторы псевдослучайных последовательностей

Рис. 3.7. Схема алгоритма формирования таблицы стохастического преобразования с использованием инициализирующей ПСП
BYTE0, BYTE1, BYTE2, ..., BYTEi,...


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


Стохастические генераторы многоразрядных ПСП на регистрах сдвига – 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) с управляющим входом. Qi – состояние i-го регистра генератора

Стохастические генераторы псевдослучайных последовательностей


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

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

Стохастические генераторы псевдослучайных последовательностей
а
Стохастические генераторы псевдослучайных последовательностей
б
Рис. 3.11. Стохастический генератор при N = 3:


схема генератора и таблица стохастического преобразования – а;
диаграмма его переключений – б


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


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

Н(BYTEi+1)(Н(BYTEi).

Стохастические генераторы псевдослучайных последовательностей


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


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


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

Стохастические генераторы псевдослучайных последовательностей
. Преобразование (рис. 3.20, б) суть многократное повторение одного и того же раунда, состоящего из трех операций:

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

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

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

На рис. 3.21 показана схема операции стохастического преобразования байтов aij с использованием блоков стохастического R1 преобразования, параметрами преобразования являются соответствующие байты kij раундового ключа,

Стохастические генераторы псевдослучайных последовательностей
,
Стохастические генераторы псевдослучайных последовательностей
, i – номер строки, j – номер столбца, a(ij – преобразованный байт, т. е. a(ij = R1(aij, kij).

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

ai3 ai2 ai1 ai0,

Стохастические генераторы псевдослучайных последовательностей
,

с использованием блоков R2 – R5. На рис. 3.23 – варианты 4?тактного перемешивания столбцов

a3j a2j a1j a0j,

Стохастические генераторы псевдослучайных последовательностей
,

с использованием блоков R6 – R9. Начальное состояние Q3 Q2 Q1Q0 регистров при преобразовании строк (столбцов) равно байтам строки (столбца) или соответствующим байтам ключа. Байты ключа в первом случае или байты строк (столбцов) во втором случае поступают на вход схем последовательно: в первом такте 3-й байт, во втором – 2-й, в третьем – 1-й и в четвертом 0-й.

Стохастические генераторы псевдослучайных последовательностей

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

Стохастические генераторы псевдослучайных последовательностей


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

Стохастические генераторы псевдослучайных последовательностей


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

Стохастические генераторы псевдослучайных последовательностей


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


На рис. 3.24, а показана схема формирования раундовых ключей из исходного 128-разрядного ключа, где ki – 32-разрядные элементы ключа (столбцы); начальное заполнение генератора раундовых ключей равно k3 k2 k1 k0, т. е. исходному ключу. Функция F обратной связи зависит от индекса i: при i = 4n – 1, где n – натуральное, схема преобразования F показана на рис. 3.24, б, где con3r con2r con1r con0r – байты 32-разрядной константы (r – номер 128-разрядного ключевого элемента), в противном случае блок F осуществляет простую передачу 32-разрядного входного набора на выход без изменения. В качестве r-й константы можно использовать, например, состояние 32-разрядного LFSR в r-м такте его работы.

Стохастические генераторы псевдослучайных последовательностей


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


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

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

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

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


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


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

x = x1 x2 x3 … xi … xm

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

? = ?1 ?2 ?3 … ?i … ?m

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

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

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

выполняем ?i тактов работы генератора;

состояние генератора после ?i тактов работы при начальном состоянии xi объявляем результатом yi преобразования элемента xi.

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

y = y1 y2 y3 … yi … ym

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

yi = R(xi, ?i).

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

Стохастические генераторы псевдослучайных последовательностей

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



может эффективно использоваться для генерации


1. Рассмотренная схема 8-разрядного стохастического преобразования (R-блок) может эффективно использоваться для генерации ПСП.
2. Основным достоинством блоков стохастического преобразования и генераторов ПСП на их основе является эффективная программная и аппаратная реализация при приемлемой для большинства приложений криптостойкости.
3. Ключевая информация, необходимая для работы 8-разрядного блока стохастического преобразования, суть характер заполнения массива размерности 8?256. Всего существует 255! вариантов заполнения этого массива.