Интернет магазин китайских планшетных компьютеров

Компьютеры - Регистр сдвига с линейной обратной связью - Пример

Для РСЛОС с ассоциированным многочленом генерируемая последовательность имеет вид . Допустим, перед началом процесса в регистре записана последовательность , тогда период генерируемого потока битов будет равен 7 со следующей последовательностью:

Номер шага	Состояние	Генерируемый бит
0		-
1		1
2		0
3		0
4		1
5		1
6		1
7		0

Поскольку внутреннее состояние на седьмом шаге вернулось к исходному, то, начиная со следующего шага, будет идти повтор. Иными словами, период последовательности оказался равен 7, что произошло ввиду примитивности многочлена .

Алгоритмы генерации примитивных многочленов

Готовые таблицы

Вычисление примитивности многочлена — достаточно сложная математическая задача. Поэтому существуют готовые таблицы, в которых приведены номера отводных последовательностей, обеспечивающих максимальный период генератора. Например, для 32-битового сдвигового регистра имеется последовательность . Это означает, что для генерации нового бита необходимо с помощью функции XOR просуммировать 32-й, 7-й, 5-й, 3-й, 2-й и 1-й биты. Код для такого РСЛОС на языке Си следующий:

int LFSR {
  static unsigned long ShiftRegister = 1;
  ShiftRegister = 
    ^ 
    ^ 
    ^ 
    ^ 
    ^ ShiftRegister) & 0x00000001) << 31)
    | ;
  return ShiftRegister & 0x00000001;
}

Программные реализации РСЛОС генераторов достаточно медленны и быстрее работают, если они написаны на ассемблере, а не на языке Си. Одним из решений является использование параллельно 16-ти РСЛОС. В такой схеме используется массив слов, размер которого равен длине РСЛОС, а каждый бит слова массива относится к своему РСЛОС. При условии, что используются одинаковые номера отводных последовательностей, то это может дать заметный выигрыш в производительности..

Конфигурация Галуа

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

static unsigned long ShiftRegister = 1;
static unsigned long mask = 0x80000057;
void seed_LFSR {
  if 
    seed = 1;
  ShiftRegister = seed;
}
 
int Galua_LFSR {
  if  {
    ShiftRegister =  | 0x80000000;
    return 1;
  } else {
    ShiftRegister >>= 1;
    return 0;
  } 
}

Выигрыш состоит том, что все XOR выполняются за одну операцию.