03.09.2023 09:18
sci_nov 0 1300 Источник

Введение

Ранее, Full-stack шифрование на обобщенных регистрах с линейной обратной связью / Хабр (habr.com), рассматривались недвоичные регистры сдвига с линейной обратной связью (LFSR), обеспечивающие периоды T_q = {p}^{m-q} - 1, где q=0,1,....

Для увеличения периода комбинировались два регистра с периодами T_0 и T_1, что в итоге давало период

T = {{T_0 T_1} \over {p-1}}.

Видно, что присутствует уменьшение периода в p-1 раз. Хотелось бы избавиться от этого недостатка (это актуально для недвоичных регистров, т.е. при p>2). По этой причине было введено управление (модуляция) пилообразным кодом.

Описание модулированного LFSR генератора

Под пилообразным кодом понимается выход генератора типа

i \leftarrow (i + 1) \mod q.

Здесь переменная i есть целое число, увеличивающееся на единицу и не превосходящее q. Операция по модулю q обеспечивает цикличность процесса (модулирующий период). Начальное состояние задается числом i_0. Итого, пилообразный генератор характеризуется вектором параметров (i_0, q).

Выход генератора пилообразного кода подается на вход LFSR генератора, который рассматривался ранее. Численно показано, что для заданного начального состояния \vec s LFSR генератора, который имеет свободный период T_0, можно последовательно подобрать начальное состояние i_0 генератора пилообразного кода и его период q<pтакие, что общий период T всей системы будет в пределах

T_0 < T < q {T}_{0}.

Таким образом видим, что за счет модуляции LFSR генератора можно преодолеть коэффициент редукции p-1, и, более того, получить небольшой выигрыш (коэффициент усиления, gain). При этом заранее неизвестен итоговый период T, что дополнительно повышает случайность генерируемого процесса.

Работа LFSR генератора со скалярным входом a и вектором-генератором \vec g может быть выражена в виде рабочего цикла

\vec s = \left( v \vec g + D[\vec s, a, 1] \right) \mod p,v = {s}_{m-1}.

Здесь оператор D[\vec v, a, 1] означает преобразование одного вектора в другой вектор типа задержки со вставкой числа: (v_0, v_1, v_2, ...) \rightarrow (a, v_0, v_1, v_2, ...). Вектор \vec s является вектором состояния генератора, состоящий из m элементов, в которых хранятся числа по модулю p. Вместо скаляра a подставляем выход генератора пилообразного кода. В итоге, генератор пилообразного кода и LFSR генератор образуют некоторый общий генератор, который работает по единым тактам (тактовым импульсам). Общий период генератора определяется по равенству состояний не только LFSR генератора, но и генератора пилообразного кода!

Численно показано, что для фиксированного модуля p можно подбирать несколько модулированных LFSR генераторов с разными начальными состояниями, так, что общий период будет равен произведению периодов без всякой редукции, то есть возможно достичь единичного наибольшего общего делителя (НОД) периодов всех генераторов. Однако, имеется возможность установить допуск на максимальный НОД, что ускорит процесс поиска начальных состояний i_0и периодов qпилообразных модуляторов.

Численно показано (по уровню авто-корреляции), что после комбинирования типа XOR всех генераторов выгодно в плане повышения случайности генерируемого процесса выполнить операцию приведения по модулю p.

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

В терминах англоязычной аудитории примененный принцип усиления периода LFSR генераторов гласит как "Sawtooth boosted LFSR generators".

Комментарии (0)