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

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


Содержание раздела