Введение

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

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

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

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

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

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

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

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

Численно показано, что для некоторого начального состояния пары, которая имеет свободный период , можно подобрать начальное состояние генератора пилообразного кода и его период, меньший , так, что периоды управляемых генераторов пары будут в пределах

$T_0 < T < p {T}_{0}.$

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

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

Работа LFSR генератора со скалярным входом и вектором-генератором $\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$ является вектором состояния генератора, состоящий из элементов, в которых хранятся числа по модулю . Вместо скаляра подставляем выход подобранного генератора пилообразного кода. В итоге, генератор пилообразного кода и LFSR генератор образуют некоторый общий генератор, который работает по единым тактам (тактовым импульсам). Общий период генератора определяется по равенству состояний LFSR генератора: начального и текущего. При достижении периода некоторого LFSR генератора пары, генератор пилообразного кода сбрасывается в начальное состояние, чтобы гарантировать достигнутый период.

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

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

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

Пример реализации рассмотренного генератора в качестве датчика случайных чисел приведен на платформе github:

nawww83/lfsr: LFSR and its cryptographic applications (github.com)

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