Методы и задачи криптографической защиты информации. Мартынов А.И. - 47 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

Простейшим видом сдвигового регистра с обратной связью является
линейный сдвиговый регистр с обратной связью (LFSR – Left Feedback Shift
Register)(Рисунок 2.10). Обратная связь представляет собой просто XOR
некоторых битов регистра, перечень этих битов называется отводной
последовательностью.
n-битовый LFSR может находиться в одном из 2
n
-1 внутренних
состояний. Это означает, что теоретически такой регистр может генерировать
псевдослучайную последовательность с периодом 2
n
-1 битов. Число
внутренних состояний и период равны, потому что заполнение регистра нулями
приведет к тому, что он будет выдавать бесконечную последовательность
нулей, что абсолютно бесполезно. Только при определенных отводных
последовательностях LFSR циклически пройдет через все 2
n
-1 внутренних
состояний. Такие LFSR называются LFSR с максимальным периодом.
Для того чтобы конкретный LFSR имел максимальный период,
многочлен, образованный из отводной последовательности и константы 1,
должен быть примитивным по модулю 2.
Вычисление примитивности многочлена – достаточно сложная
математическая задача. Поэтому существуют готовые таблицы, в которых
приведены номера отводных последовательностей, обеспечивающих
максимальный период генератора. Например, для 32-битового сдвигового
регистра можно найти такую запись: (32,7,5,3,2,1,0). Это означает, что для
генерации нового бита необходимо с помощью функции XOR просуммировать
тридцать второй, седьмой, пятый, третий, второй и первый биты.
Код для такого LFSR на языке С++ будет таким:
int LFSR (void)
{
static unsigned long ShiftRegister = 1;
//  ,  
ShiftRegister = ((((ShiftRegister >> 31)
^ (ShiftRegister >> 6)
^ (ShiftRegister >> 4)
^ (ShiftRegister >> 2)
^ (ShiftRegister >> 1)
^ ShiftRegister)& 0x00000001) <<31)
| (ShiftRegister >> 1);
return ShiftRegister & 0x00000001; }
Рисунок 2.10. Сдвиговый регистр с линейной обратной связью (LFSR)

Страницы