2.4. Построение устройств генерации ключей

Псевдослучайная последовательность элементов может быть реа-лизована программными, аппаратными и программно – аппаратными сред-ствами. Аппаратная реализация основана на теории линейных переключательных схем [3,7], которые проектируются на регистрах сдвига с обратными связями.

В общем случае линейные переключательные схемы используются для умножения, деления и генерации различных цифровых последовательностей. На рис. 2.1 изображена схема умножения многочлена

на фиксированный многочлен

,

где a_j и q_i  {0,1,2,…, q – 1} элементы поля GF(q).

Рис. 2.1. Схема для умножения многочлена a(x)

на фиксированный многочлен на основе регистра типа LFSR1.

Схему на рис. 2.1 называют регистром сдвига с линейной обрат- ной связью LFSR1 (Linear Feedback Shift Register) [7].

Второй вариант схемы умножения на фиксированный многочлен приведён на рис. 2.2, сумматоры и умножители в которой подключены в соответствии с регистром типа LFSR2.

Выход a(x)q(x)

Рис. 2.2. Схема для умножения многочлена a(x) на фиксированный многочлен на основе регистра типа LFSR2.

Регистр в умножителях содержит m разрядов, каждый из которых состоит из узла задержки (ЗУ), хранящего один из q элементов поля GF(q). Цепи обратной или прямой связи замкнуты в соответствии с неприводимым полиномом q(х). В цепях связи происходит умножение коэффициентов многочлена a(x) на коэффициенты многочлена q(х). Суммирование элементов q осуществляется по обычным правилам. Если в многочлене, при какой либо переменной хⁱ коэффициент равен 0, то и в регистре отсутствует соответствующая связь.

Приведенные схемы можно преобразовать в генератор псевдослучайной последовательности, который вырабатывает последовательности элементов с периодом q^m-1. Для этого необходимо выбрать неприводимый многочлен, преобразовать его в нормированный многочлен путём деления всех его коэффициентов q_i на старший коэффициент q_m. В схемах необходимо исключить входы, а в регистр занести любую последовательность элементов q. Две разновидности генератора псевдослучайной последовательности приведены на рис.2.3 и рис.2.4.

Рисунок 2.3. – Генератор псевдослучайной последовательности на основе регистра типа LFSR1.

Рисунок 2.4. – Генератор псевдослучайной последовательности на основе регистра типа LFSR2.

Состояния регистра в последовательные моменты времени t и t+1 можно описать уравнением

Q(t+1) = M  Q(t+1),

где М – сопровождающая матрица. Для генераторов на рис. 2.3 и рис. 2.4 она имеет соответственно вид:

В случае если q=2 умножение в цепи обратной связи соответствует наличию (при q_i=1) или отсутствию (при q_i=0) обратной связи на соответствующий сумматор по модулю 2. Пример генератора псевдослучайной последовательности с числом элементов 2⁵-1, построенного на основе полинома p(x)=x⁵+x²+1 и реализованного с помощью Д – триггеров и сумматоров по модулю 2 M2, показан на рисунке 2.5.

Рисунок 2.5– Генератор псевдослучайной последовательности.

Для генерации последовательности в регистр предварительно записывается любое значение элемента поля GF(2⁵).

31