Регистр сдвига с линейной обратной связью

Регистр сдвига с линейной обратной связью (РСЛОС, англ. Linear feedback shift register, LFSR) — один из методов генерации псевдослучайных чисел.

Определение

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

Для РСЛОС функция обратной связи представляет собой сумму по модулю 2 (xor) некоторых битов регистра, называемых отводами.

Регистр сдвига с линейной обратной связью длины $~L$ состоит из $~L$ ячеек, пронумерованных $~0,1,2,\dots ,L-1$, каждая из которых способна хранить $~1$ бит и имеет один вход и один выход, а также синхросигнал, который контролирует смещение данных. В течение каждой единицы времени выполняются следующие операции:

• содержимое ячейки $~L-1$ формирует часть выходной последовательности;
• содержимое $~i$-й ячейки перемещается в ячейку $~i+1$ для любого $~i,0<~i<~L-1$
• новое содержимое ячейки $~0$ определяется битом обратной связи, который вычисляется сложением по модулю $~2$ с определёнными коэффициентами битов ячеек $~0,1,2,\dots ,L-1$.

Регистр сдвига с линейной обратной связью

Таким образом, в качестве функции обратной связи берётся логическая операция XOR (исключающее ИЛИ), то есть:

• на первом шаге: $S_{L}=(c_{1}*S_{L-1})\oplus (c_{2}*S_{L-2})\oplus \dots \oplus (c_{L}*S_{0})$
• на втором шаге: $S_{L+1}=(c_{1}*S_{L})\oplus (c_{2}*S_{L-1})\oplus \dots \oplus (c_{L}*S_{1})$
• …
• на $j-L-1$-м шаге: $S_{j}=(c_{1}*S_{j-1})\oplus (c_{2}*S_{j-2})\oplus \dots \oplus (c_{L}*S_{j-L})$

Свойства

Свойства выдаваемой РСЛОС последовательности тесно связаны со свойствами ассоциированного многочлена $C(x)=1+c_{1}x+c_{2}x^{2}+\dots +c_{L}x^{L}$ над полем $\mathbb {F} _{2}$. Его ненулевые коэффициенты называются отводами, как и соответствующие ячейки регистра, поставляющие значения аргументов функции обратной связи.

Периодичность

Так как существует $2^{L}-1$ разных ненулевых состояний регистра, то период последовательности, генерируемой РСЛОС при любом ненулевом начальном состоянии, не превышает $2^{L}-1$. При этом период зависит от ассоциированного многочлена:

• если старший коэффициент ассоциированного многочлена $C_{L}$ равен нулю, то периодичная часть генерируемой последовательности может проявляться не сразу;
• если $C_{L}=1$, то соответствующая последовательность называется неособой. Такая последовательность начинается со своей периодичной части. Наиболее интересны неособые последовательности, соответствующие многочленам со следующими дополнительными свойствами:
  • если $C(x)$ неприводим, то при любом ненулевом начальном состоянии регистра период генерируемой последовательности равен наименьшему числу $N$, при котором многочлен $C(x)$ делит $1+x^{N}$. Как следствие, период последовательности будет делить число $2^{L}-1$;
  • если $C(x)$ примитивен (то есть, является делителем $x^{2^{L}-1}+1$, но не является делителем $x^{d}+1$ для всех d, делящих $2^{L}-1$), то любое ненулевое начальное состояние регистра дает последовательность с максимально возможным периодом $2^{L}-1$. Например, РСЛОС с отводной последовательностью, состоящей из первого и четвёртого битов имеет максимальный период тогда и только тогда, когда ассоциированный многочлен $x^{4}+x+1$ является примитивным.

Линейная сложность

Линейная сложность бинарной последовательности — одна из самых важных характеристик работы РСЛОС. Введём следующие обозначения:

• $S=(s_{1},\;s_{2},\;s_{3},\;\dots )$ — бесконечная последовательность;
• $S_{n}=(s_{1},\;s_{2},\;\dots ,\;s_{n})$ — подпоследовательность длины $n$ последовательности $S$;
• говорят, что РСЛОС генерирует последовательность $S$, если существует некоторое исходное состояние, при котором выходная последовательность РСЛОС совпадает $S$;
• говорят, что РСЛОС генерирует конечную последовательность $S_{n}$, если существует некоторое начальное состояние, для которого выходная последовательность РСЛОС имеет в качестве первых $n$ членов члены последовательности $S_{n}$.

Определение

Линейной сложностью бесконечной двоичной последовательности $S$ называется число $L(S)$, которое определяется следующим образом:

• если $S=(0,\;0,\;0,\dots )$ — нулевая последовательность, то $L(S)=0$;
• если не существует РСЛОС, который генерирует $S$, то $L(S)=\infty$;
• иначе $L(S)$ равна длине самого короткого РСЛОС, который генерирует $S$.

Линейной сложностью конечной двоичной последовательности $S_{n}$ называется число $L(S_{n})$, которое равно длине самого короткого РСЛОС, который генерирует последовательность, имеющую в качестве первых $n$ членов $L(S_{n})$.

Свойства линейной сложности

Пусть $S$ и $K$ — двоичные последовательности. Тогда:

1. для любого $n>0$ линейная сложность подпоследовательности $L(S_{n})$ удовлетворяет неравенствам $0\leq L(S_{n})\leq n$;
2. $L(S_{n})=0$ тогда и только тогда, когда $S_{n}$ — нулевая последовательность длины $n$;
3. $L(S_{n})=n$ тогда и только тогда, когда $S_{n}=(0,\;0,\;\dots ,\;0,\;1)$;
4. если $S$ периодическая с периодом $T$, то $L(S_{n})\leq T$;
5. $L(S\oplus K)\leq L(S)+L(K)$.

Пример

Для РСЛОС с ассоциированным многочленом $~x^{3}+x+1$ генерируемая последовательность имеет вид $~S_{j}=S_{j-1}\oplus S_{j-3}$. Допустим, перед началом процесса в регистре записана последовательность $~\left[0,~0,~1\right]$, тогда период генерируемого потока битов будет равен 7 со следующей последовательностью:

Номер шага	Состояние	Генерируемый бит
0	$~\left[0,~0,~1\right]$	-
1	$~\left[1,~0,~0\right]$	1
2	$~\left[1,~1,~0\right]$	0
3	$~\left[1,~1,~1\right]$	0
4	$~\left[0,~1,~1\right]$	1
5	$~\left[1,~0,~1\right]$	1
6	$~\left[0,~1,~0\right]$	1
7	$~\left[0,~0,~1\right]$	0

Поскольку внутреннее состояние на седьмом шаге вернулось к исходному, то, начиная со следующего шага, будет идти повтор. Иными словами, период последовательности оказался равен 7, что произошло ввиду примитивности многочлена $~x^{3}+x+1$.

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

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

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

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;
}

Программные реализации РСЛОС генераторов достаточно медленны и быстрее работают, если они написаны на ассемблере, а не на языке Си. Одним из решений является использование параллельно 16-ти РСЛОС (или 32, в зависимости от длины слова в архитектуре конкретного компьютера). В такой схеме используется массив слов, размер которого равен длине РСЛОС, а каждый бит слова массива относится к своему РСЛОС. При условии, что используются одинаковые номера отводных последовательностей, то это может дать заметный выигрыш в производительности.^{[нужен пример кода]} (См.: bitslice).

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

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

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

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

Преимущества

• высокое быстродействие криптографических алгоритмов, создаваемых на основе РСЛОС, например таких как потоковые шифры;
• применение только простейших битовых операций сложения и умножения, аппаратно реализованных практически во всех вычислительных устройствах;
• хорошие криптографические свойства (РСЛОС могут генерировать последовательности большого периода с хорошими статистическими свойствами);
• благодаря своей структуре ЛРС легко анализируются с использованием алгебраических методов.

См. также

• Регистр сдвига с обратной связью по переносу (FCSR)

Ссылки

• LFSR Reference Теория и реализация LFSR, последовательности максимальной длины и полные таблицы отводных последовательностей для длин от 7 до 16 777 215 (от 3 до 24 битов), а также частичные таблицы для длин до 4 294 967 295 (от 25 до 32 битов)
• International Telecommunications Union Recommendation O.151 август 1992
• Maximal Length LFSR table with length from 1 to 786, also 1024 and 2048.
• Pseudo-Random Number Generation Routine
• http://www.ee.ualberta.ca/~elliott/ee552/studentAppNotes/1999f/Drivers_Ed/lfsr.html
• http://www.quadibloc.com/crypto/co040801.htm
• Simple explanation of LFSRs for Engineers
• Feedback terms
• General LFSR Theory
• Shift register code generator
• An implementation of a cryptographically secure shrinking pseudorandom number generator
• Методы и задачи криптографической защиты информации
• РСЛОС