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

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

Рис. 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⁵).