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

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

Генераторы ПСП, схемы которых приведены на рис. 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! вариантов заполнения этого массива.



    Программирование: Языки - Технологии - Разработка

• Программирование
  
• Технологии программирования
  
• Разработка программ
  
• Работа с данными
  
• Методы программирования
  
  
• IDE интерфейс
  
• Графический интерфейс
  
• Программирование интерфейсов
  
• Отладка программ
  
• Тестирование программ
  
  
• Программирование на Delphi
  
• Программирование в ActionScript
  
• Assembler
  
• Basic
  
• Pascal
  
  
• Perl
  
• VBA
  
• VRML
  
• XML
  
• Ada
  
  
• Lisp
  
• Python
  
• UML
  
• Форт
  
• Языки программирования