Регистр сдвига с линейной обратной связью (Jyinvmj v;fnig v lnuywukw kQjgmukw vfx[,Z)

Регистр сдвига с линейной обратной связью (РСЛОС, англ. linear feedback shift register, LFSR) — сдвиговый^[англ.] регистр битовых слов, у которого значение входного (вдвигаемого) бита равно линейной булевой функции от значений остальных битов регистра до сдвига. Может быть организован как программными, так и аппаратными средствами. Применяется для генерации псевдослучайных последовательностей битов, что находит применение, в частности, в криптографии^[1]. По похожему принципу работают регистр сдвига с обратной связью по переносу и регистр сдвига с обобщённой обратной связью.

Описание

Четырёхразрядный генератор случайных чисел из одного элемента "исключающее или" и четырёх регистров. Обратите внимание на отсутствие состояния "0000"

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

В регистре сдвига с линейной обратной связью (РСЛОС) выделяют две части (модуля):

собственно регистр сдвига;
схему (или подпрограмму) обратной связи, вычисляющую значение вдвигаемого бита.

Регистр состоит из функциональных ячеек памяти (битов одного или нескольких машинных слов), в каждой из которых хранится текущее состояние (значение) одного бита. Количество ячеек $L$ , называют длиной регистра. Биты (ячейки) обычно нумеруются числами $i=0,\;1,\;\dots ,\;L-1$ , содержимое $i$ -й ячейки обозначается через $S_{(L-1)-i}$ . Значение нового бита $S_{L}$ определяется до сдвига битов в регистре и только после сдвига записывается в ячейку $0$ , а из ячейки $L-1$ извлекается очередной сгенерированный бит.

Функцией обратной связи для РСЛОС является линейная булева функция от значений всех или некоторых битов регистра. Функция выполняет умножение битов регистра на коэффициенты $c_{i}$ , где $i=1,\;2,\;\dots ,\;L$ . Количество коэффициентов совпадает с количеством битов регистра $L$ . Коэффициенты $c_{i}$ принимают значения $\{0,\;1\}$ , причём последний коэффициент $c_{L}$ равен $c_{L}=1$ , так как РСЛОС задаётся характеристическим многочленом степени $L$ . Сложение по модулю 2 (операция «XOR», обозначаемая в формулах символом « $\oplus$ ») или её логическая инверсия «XNOR» являются линейными булевыми функциями и наиболее часто применяются в таких регистрах^[2]. При этом биты, являющиеся переменными функции обратной связи, называются отводами, а сам регистр называется конфигурацией Фибоначчи^[3].

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

Принцип работы

В течение каждого такта сдвигового регистра с линейной обратной связью выполняет следующие операции:

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

Если функция обратной связи выполняет логическую операцию «XOR» (исключающее ИЛИ), значения бит (ячеек) могут быть вычислены по следующим формулам^[4]:

$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})$ $...$ $S_{L+j-1}=(c_{1}*S_{L+j-2})\oplus (c_{2}*S_{L+j-3})\oplus \dots \oplus (c_{L}*S_{j-1})$

Свойства

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

Периодом регистра сдвига называется минимальная длина получаемой последовательности до начала её повторения. РСЛОС длины $L$ имеет $2^{L}$ начальных состояний, задающих значения бит в ячейках. Из них $2^{L}-1$ состояний - ненулевые, так что генерируемая последовательность имеет период $T\leq 2^{L}-1$ . Период генерируемой последовательности максимален и равен $2^{L}-1$ , если многочлен обратной связи (или характеристический многочлен) $C(x)=c_{L}x^{L}+c_{L-1}x^{L-1}+\dots +c_{1}x+1$ над полем $\mathrm {GF} (2)$ является примитивным. Для этого необходимо (но не достаточно) выполнение следующих 2-х условий:

чётное число отводов;
номера отводов, взятые все вместе, а не попарно, взаимно просты.

Число всех возможных примитивных многочленов равно ${\tfrac {\phi (2^{L}-1)}{L}}$ , где $\phi$ - функция Эйлера^[5]. Регистр, заданный таким многочленом, называется регистром сдвига максимального периода (или генератором псевдослучайной последовательности), а генерируемые последовательности - последовательностями максимального периода (или М-последовательностями)^[4]^[6].

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

Линейной сложностью бесконечной двоичной последовательности $S=(S_{0},\;S_{1},\;S_{2},\;\dots )$ называется число $L(S)$ , которое определяется следующим образом:

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

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

Линейная сложность регистра сдвига с линейной обратной связью показывает, насколько близка генерируемая последовательность к случайной. Эффективным алгоритмом определения линейной сложности конечной бинарной последовательности является алгоритм Берлекэмпа-Мэсси.

Корреляционная независимость

Пытаясь получить высокую линейную сложность генерируемой последовательности, криптографы нелинейно объединяют выходы нескольких регистров сдвига. При этом одна или несколько выходных последовательностей (или даже выходы отдельных РСЛОС) могут быть связаны общим потоком и вскрыты криптоаналитиком. Взлом на основе такой уязвимости называют корреляционным вскрытием. Основная идея такого взлома заключается в обнаружении некоторой корреляции между выводом генератора и выводами его составных частей. Затем, наблюдая выходную последовательность, можно получить информацию об этих промежуточных выводах, и, таким образом, взломать генератор. Томас Сигенталер показал, что можно точно определить корреляционную независимость, и что существует компромисс между корреляционной независимостью и линейной сложностью^[7].

Программная реализация

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

Конфигурация Фибоначчи

Рассмотрим 32-битовый сдвиговый регистр. Для него имеется отводная последовательность $\left(32,\;31,\;30,\;28,\;26,\;1\right)$ . Это означает, что для генерации нового бита необходимо с помощью операции XOR просуммировать 31-й, 30-й, 29-й, 27-й, 25-й и 0-й биты. Полученный РСЛОС имеет максимальный период $2^{32}-1$ . Код для такого регистра на языке Си следующий:

int LFSR_Fibonacci (void)
{
  static unsigned long S = 0x00000001;
  S = ((((S >> 31) ^ (S >> 30) ^ (S >> 29) ^ (S >> 27) ^ (S >> 25) ^ S ) & 0x00000001 ) << 31 ) | (S >> 1);
  return S & 0x00000001;
}

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

Как и в конфигурации Фибоначчи, схема обратной связи представляет собой набор операций XOR отводных битов с выходом генератора, но порядок битов в регистре обратный: входным является $L-1$ -й бит, а выходным — $0$ -й. Результат сложения записывается в следующую ячейку, а новый выходной бит записывается в $L-1$ -ю. Таким образом, если генерируемый бит равен нулю, то все биты в ячейках сдвигаются вправо без изменений, если генерируемый бит равен единице, то биты отвода меняют своё значение на противоположное, и все биты сдвигаются вправо. И конфигурация Фибоначчи, и конфигурация Галуа одной и той же длины генерируют одинаковые, но смещённые по времени одна от другой последовательности (при этом внутренние состояния регистров могут отличаться)^[8].

Данный генератор не обладает большей криптостойкостью, но он даёт выигрыш в производительности: все операции XOR посредством распараллеливания можно выполнить за одно действие, а не последовательно одна за другой, как в конфигурации Фибоначчи. Данная схема также даст выигрыш при аппаратной реализации.

Код для регистра сдвига длины 32 бит на языке Си следующий:

int LFSR_Galois (void)
{
    // for polynomial 0x80000057, reversed 0xea000001
    static unsigned long S = 0x00000001;
    if (S & 0x00000001) {
        S = ((S ^ 0x80000057) >> 1) | 0x80000000;
        return 1;}
    else {
        S >>= 1;
        return 0;}
}

Стоит отметить, что цикл из фиксированного числа вызовов функции LFSR_Galois в конфигурации Галуа выполняется примерно в 2 раза быстрее, чем функция LFSR_Fibonacci в конфигурации Фибоначчи (компилятор MS VS 2010 на Intel Core i5).

Пример генерируемой последовательности

Конфигурация Фибоначчи

Пусть РСЛОС задаётся характеристическим многочленом $x^{3}+x+1$ . Это значит, что битами отвода будут 2-й и 0-й, а единица в формуле многочлена означает, что 0-й бит - входной. Функция обратной связи имеет вид $S_{j}=S_{j-1}\oplus S_{j-3}$ . Допустим, изначальным состоянием регистра сдвига была последовательность $\left[0,\;0,\;1\right]$ . Дальнейшие состояния регистра приведены в таблице ниже:

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

Поскольку внутреннее состояние на седьмом шаге вернулось к исходному, то, начиная со следующего шага, будет идти повтор битов. То есть генерируемая последовательность такова: $\left[1,\;0,\;0,\;1,\;1,\;1,\;0,\;1\;...\right]$ (порядок бит в последовательности соответствует порядку их генерации РСЛОС). Таким образом, период последовательности равен 7, то есть максимально возможному значению, что произошло в силу примитивности заданного многочлена.

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

Возьмём тот же характеристический многочлен, то есть $c_{3}=c_{1}=1$ , $c_{2}=0$ . С выходным битом складывается только 1-й бит. Начальное состояние то же самое. Дальнейшие состояния регистра:

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

Внутреннее состояние регистра на седьмом шаге вернулось к исходному, следовательно, его период также равен 7.

Пример реализации на логических элементах

На картинке справа можно увидеть пример реализации РСЛОС с конфигурацией Галуа вида (7, 10).

В верхней части схемы расположены выходные контакты, на которых можно увидеть последовательность генерируемых регистром битов. Ниже идут D-триггеры, которые соединены друг с другом и образуют собственно регистр. Самый правый триггер (номер 1) является выходным и, согласно реализуемой конфигурации, влияет на передачу бита из 10-го и 7-го триггеров (берётся XOR передаваемого и выходного бита). Остальные биты передаются без изменений.

Начальная конфигурация регистра задаётся при помощи мультиплексоров перед каждым триггером. Чтобы сбросить конфигурацию регистра до начальной (или той, которая нужна, её можно выбрать на контактах перед мультиплексорами), нужно всего лишь подать 1 на контакт Init, после чего подать сигнал синхронизации. После зануления синхронизации регистр примет нужную конфигурацию. Чтобы дальше он начал работать корректно, сигнал Init нужно вновь занулить.

Матричное представление LFSR

раздел английской статьи

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

Вычисление примитивного многочлена над полем $\mathrm {GF} (2)$ — достаточно сложная математическая задача: для генерации примитивного многочлена степени $k$ нужно знать множители числа $2^{k}-1$ . Проще случайным образом выбрать многочлен и проверить его на примитивность^[3]. Ещё один метод заключается в использовании готовых таблиц, в которых приведены номера отводных последовательностей, обеспечивающих максимальный период генератора. Ниже приведена таблица примитивных многочленов над полем $\mathrm {GF} (2)$ для регистров сдвига максимального периода длиной до 19 бит^[5]. Стоит учесть, что у генератора любой заданной длины может быть более одного примитивного многочлена согласно их свойствам. Полный список для регистров длиной от 4 до 32 бит можно найти здесь.

Биты, $n$	Примитивный многочлен	Период, $2^{n}-1$	Число примитивных многочленов
2	$x^{2}+x+1$	3	1
3	$x^{3}+x^{2}+1$	7	2
4	$x^{4}+x^{3}+1$	15	2
5	$x^{5}+x^{3}+1$	31	6
6	$x^{6}+x^{5}+1$	63	6
7	$x^{7}+x^{6}+1$	127	18
8	$x^{8}+x^{6}+x^{5}+x^{4}+1$	255	16
9	$x^{9}+x^{5}+1$	511	48
10	$x^{10}+x^{7}+1$	1023	60
11	$x^{11}+x^{9}+1$	2047	176
12	$x^{12}+x^{11}+x^{10}+x^{4}+1$	4095	144
13	$x^{13}+x^{12}+x^{11}+x^{8}+1$	8191	630
14	$x^{14}+x^{13}+x^{12}+x^{2}+1$	16383	756
15	$x^{15}+x^{14}+1$	32767	1800
16	$x^{16}+x^{14}+x^{13}+x^{11}+1$	65535	2048
17	$x^{17}+x^{14}+1$	131071	7710
18	$x^{18}+x^{11}+1$	262143	7776
19	$x^{19}+x^{18}+x^{17}+x^{14}+1$	524287	27594
20 - 168	[1]
2 - 786, 1024, 2048, 4096	[2]

Преимущества и недостатки

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

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

Недостатки

Одна из главных проблем РСЛОС в том, что их программная реализация крайне неэффективна: приходится избегать разреженных многочленов обратной связи, так как они приводят к облегчению взлома корреляционным вскрытием, а плотные многочлены очень медленно просчитываются. Поэтому программная реализация такого генератора работает не быстрее, чем реализация DES.
Линейность последовательности на выходе регистра позволяет однозначно определить многочлен обратной связи $C(x)$ по $2L$ последовательным битам с помощью алгоритма Берлекэмпа — Мэсси или алгоритма Евклида^[3]^[4].
Относительная лёгкость анализа алгебраическими методами не только облегчает разработку, но и увеличивает шансы на взлом генератора на базе РСЛОС.

Способы улучшения криптостойкости генерируемых последовательностей

Генераторы с несколькими регистрами сдвига

Генератор такого типа состоит из нескольких регистров сдвига с линейной обратной связью, которые генерируют биты $x_{1,i},\;x_{2,i},\;\dots ,\;x_{M,i}$ соответственно. Далее, генерируемые биты преобразуются некоторой булевой функцией $f(x_{1,i},\;x_{2,i},\;\dots ,\;x_{M,i})$ . Необходимо отметить, что у генераторов такого типа длины регистров $L_{i}$ , $i=1,\;2,\;\dots ,\;M$ , взаимно просты между собой.

Период данного генератора равен $T=(2^{L_{1}}-1)\cdot (2^{L_{2}}-1)\cdots (2^{L_{M}}-1)\lesssim 2^{L}$ , где $L=\sum \limits _{i=1}^{M}L_{i}$ — общее число ячеек. Следовательно, использование нескольких РСЛОС увеличивает период генерируемой последовательности по сравнению с одним регистром, что увеличивает криптостойкость генератора. Также увеличивается линейная сложность или длина кратчайшего регистра, соответствующего данному генератору. Такой регистр находится с помощью алгоритма Берлекэмпа — Мэсси по генерируемой последовательности. В лучшем случае его длина соизмерима с периодом генерируемой последовательности^[4].

Генераторы с нелинейными преобразованиями

Структурная схема такого генератора ничем не отличается от схемы предыдущего генератора. Главное отличие заключается в том, что устройство преобразования задано нелинейной булевой функцией $f(x_{1},x_{2},\dots ,x_{M})$ . В качестве такой функции берётся, например, полином Жегалкина (согласно теореме Жегалкина, всякая булева функция единственным образом может быть представлена полиномом Жегалкина).

Нелинейный генератор может быть также реализован на регистре сдвига с нелинейной обратной связью^[англ.]. Он может дать $2^{2^{L-1}-L}$ вариантов последовательностей максимального периода, что больше, чем у РСЛОС^[5].

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

Данный метод используется, например, в генераторе Геффа и обобщённом генераторе Геффа, однако такие генераторы могут быть взломаны корреляционным вскрытием^[7].

Генераторы с различным тактированием регистров сдвига

Генератор «стоп-пошёл»

Генератор «стоп-пошёл» (англ. Stop-and-Go, Both-Piper) использует вывод РСЛОС-1 для управления тактовой частотой РСЛОС-2, так что РСЛОС-2 меняет своё состояние в некоторый момент времени $t_{i}$ , только если выход РСЛОС-1 в момент времени $t_{i-1}$ был равен единице. Данная схема не устояла перед корреляционным вскрытием^[3].

В целях увеличения криптостойкости был предложен чередующийся генератор «стоп-пошёл». В нём используются три регистра сдвига различной длины. Здесь РСЛОС-1 управляет тактовой частотой 2-го и 3-го регистров, то есть РСЛОС-2 меняет своё состояние, когда выход РСЛОС-1 равен единице, а РСЛОС-3 - когда выход РСЛОС-1 равен нулю. Выходом генератора является операция сложения по модулю два выходов РСЛОС-2 и РСЛОС-3. У данного генератора большой период и большая линейная сложность. Существует способ корреляционного вскрытия РСЛОС-1, но это не сильно ослабляет криптографические свойства генератора.

Усложнённая схема тактирования использована в двустороннем генераторе «стоп-пошёл», в котором используются 2 регистра сдвига одинаковой длины. Если выход РСЛОС-1 в некоторый момент времени $t_{i-1}$ равен нулю, а в момент времени $t_{i-2}$ - единице, то РСЛОС-2 не тактируется в момент времени $t_{i}$ . Если выход РСЛОС-2 в момент времени $t_{i-1}$ равен нулю, а в момент времени $t_{i-2}$ - единице, и если этот регистр тактируется в момент времени $t_{i}$ , то в этот же момент РСЛОС-1 не тактируется. Линейная сложность данной схемы примерно равна периоду генерируемой последовательности.

Самопрореживающий генератор

Самопрореживающие (англ. self-decimated) генераторы управляют собственной частотой. Существует два типа таких генераторов. Первый был предложен Рэйнером Рюппелом. Он состоит из регистра сдвига и схемы с линейной обратной связью, которая тактирует этот регистр в зависимости от того, какими получаются выходные значения регистра сдвига. Если выход РСЛОС равен единице, то регистр тактируется с одной частотой, а если выход равен нулю - то с другой. Второй тип был предложен Биллом Чамберсом и Дитером Коллманом. В схему обратной связи поступает не сам выходной сигнал, а результат операции XOR определённых битов РСЛОС.

Существуют также прореживаемый (англ. shrinking) и самопрореживаемый (англ. self-shrinking) генераторы. Они достаточно новые, и не все их свойства хорошо изучены. Первый использует два РСЛОС. Если на генератор подать тактовый импульс, и выходом РСЛОС-1 является единица, то выходом генератора будет выход РСЛОС-2. В противном случае, при подаче тактового импульса оба бита сбрасываются, тактирование начинается заново. Во втором генераторе вместо проверки выходов двух регистров на 0 или 1 проверяются 2 бита одного регистра.

Прореживаемый генератор может быть взломан, если многочлены обратной связи прорежены. Кроме того, его скорость генерации не постоянна. Для самопрореживаемого генератора нужно примерно в 2 раза меньше памяти, чем первому, но при этом он работает в 2 раза медленнее^[7].

Многоскоростной генератор с внутренним произведением

Данный генератор использует два регистра сдвига РСЛОС-1 и РСЛОС-2. Тактовая частота РСЛОС-2 в $d$ раз больше, чем у РСЛОС-1. Определённые биты этих регистров перемножаются друг с другом операцией AND. Результаты умножений суммируются операцией XOR, и получается выходная последовательность. Этот генератор имеет высокую линейную сложность и обладает хорошими статистическими свойствами. Однако его состояние может быть определено по выходной последовательности длиной $L_{1}+L_{2}+\log _{2}{d}$ , где $L_{1}$ и $L_{2}$ — длины РСЛОС-1 и РСЛОС-2 соответственно, а $d$ — отношение их тактовых частот.

Каскад Голлманна

Данная схема представляет собой улучшенную версию генератора «стоп-пошёл». Он состоит из последовательности РСЛОС, тактирование каждого из которых управляется предыдущим РСЛОС. Если выходом РСЛОС-1 в момент времени $t_{i}$ является 1,то тактируется РСЛОС-2. Если выходом РСЛОС-2 в момент времени $t_{i}$ является 1, то тактируется РСЛОС-3, и так далее. Выход последнего РСЛОС является выходом генератора. Если длина всех РСЛОС одинакова и равна $L$ , то период системы из $M$ РСЛОС равен $(2^{L}-1)^{M}$ , а линейная сложность - $L(S)=L(2^{L}-1)^{M-1}$ ^[7].

Эта идея проста и может быть использована для генерации последовательностей с огромными периодами, большими линейными сложностями и хорошими статистическими свойствами. Но, к сожалению, они чувствительны к вскрытию, называемому запиранием (англ. lock-in), когда криптоаналитик, восстанавливая сначала входную последовательность последнего регистра в каскаде, взламывает весь каскад, регистр за регистром. С ростом числа регистров $M$ генерируемая последовательность приближается к случайной, так что лучше использовать больше РСЛОС небольшой длины, чем меньше длинных РСЛОС.

Мажоритарные генераторы

Мажоритарный (или пороговый) генератор состоит из большого числа регистров сдвига, выводы которых поступают на устройство, заданное функцией мажорирования, например, мажоритарный элемент. Особенность данного генератора заключается в том, что каждый из регистров сдвига имеет свой тактовый бит $a_{i}$ , $i=1,\;2,\;\dots ,\;M$ , которые и являются переменными мажоритарной функции. Например, для трёх регистров такая функция имеет вид $b(t)=(a_{1}\land a_{2})\oplus (a_{1}\land a_{3})\oplus (a_{2}\land a_{3})$ . Сдвигаются только те регистры, чьи тактовые биты равны значению $b(t)$ , то есть сдвиг регистров происходит по большинству значений таких битов: 0 или 1.

Таким образом, мы получаем генератор с переменным числом РСЛОС. Его линейная сложность $L(S)=\sum \limits _{i,j=1}^{M}L_{i}L_{j}$ , где $L_{i}$ — длина $i$ -го регистра^[7]. Недостатками такого генератора являются возможность прямого перебора и корреляционного вскрытия (каждый выходной бит дает некоторую информацию о состоянии сдвигового регистра, а точнее - 0.189 бита).

Подобные генераторы используются в алгоритмах шифрования A5 (A5/1, A5/2).

Применение

Регистры сдвига с линейной обратной связью могут быть реализованы аппаратными средствами, что позволяет их использовать для быстрой генерации псевдослучайной последовательности, например при расширении спектра методом прямой последовательности или для генерации шумового сигнала^[9].

Использование в криптографии

Регистры сдвига с линейной обратной связью издавна применяются в качестве генераторов псевдослучайной последовательности для потоковых шифров (особенно в военной криптографии). Однако РСЛОС представляет собой линейную схему и в некоторых случаях может быть легко взломан. Например, криптоаналитик может перехватить часть зашифрованного текста и по нему с помощью вышеупомянутого алгоритма Берлекэмпа — Мэсси восстановить РСЛОС минимального размера, который имитирует оригинальный РСЛОС. Затем, перехваченный текст может быть подан на полученный регистр и расшифрован. Методы увеличения криптостойкости потоковых шифров, основанных на РСЛОС, приведены выше.

На регистре сдвига с линейно обратной связью основаны такие потоковые шифры, как A5/1 и A5/2, используемые в стандарте GSM, и шифр E0^[англ.], используемый в Bluetooth. Шифр A5/2 был взломан, а шифры A5/1 и E0 имеют серьёзные недостатки^[10]^[11].

Регистр сдвига с линейной обратной связью тесно связан с линейным конгруэнтным генератором^[12].

Использование в качестве счётчиков

Периодичность генерируемой последовательности РСЛОС позволяет использовать его в качестве делителя тактовой частоты или счётчика^[13]. Счётчик на основе такого генератора имеет упрощенную схему обратной связи, в отличие от обычных двоичных счётчиков или счётчиков кода Грея, и, следовательно, может работать на высоких тактовых частотах. Однако необходимо убедиться, чтобы такой счётчик никогда не входил в нулевое состояние.

Тестирование цифровых устройств

В отличие от обычного счётчика, РСЛОС переходит из одного состояния в другое не в порядке двоичного счёта, что позволяет его использовать для генерации тестового сигнала при обнаружении ошибок в логических схемах^[6].

Также регистры сдвига с линейной обратной связью применяются во встроенных системах самоконтроля^[англ.] (англ. built-in self-test, BIST) для сигнатурного анализа (выявления ошибочных битов) в логических схемах. Подобные системы применяют ввиду ограниченности числа выводов микросхем (не все промежуточные значения битов можно подать на выход). Система BIST представляет собой 3 блока: генератор тестовой последовательности и сигнатурный анализатор, которые и строятся на основе РСЛОС, и контроллер тестов. Регистр сдвига в анализаторе «сжимает» результат схемы на тестовую последовательность в сигнатуру и продолжает работать до тех пор, пока всего его биты, кроме 0-го, не станут равными нулю, то есть до состояния $\left[1,\;0,\;0,\;...,\;0\right]$ . Наряду с РСЛОС работает двоичный счётчик, подсчитывающий количество тактов с момента окончания сжатия тестовой реакции. Если изначальное состояние регистра соответствовало эталонной сигнатуре (сигнатуре безошибочной схемы), то показание счётчика соответствует номеру ошибочного бита^[14]^[15].

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

Скремблирование

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

См. также

Примечания

↑ Б. Скляр, 2007.
↑ Linear Feedback Shift Registers in Virtex Devices (неопр.). Дата обращения: 19 ноября 2014. Архивировано 2 ноября 2013 года.
↑ ¹ ² ³ ⁴ ⁵ Б. Шнайер, 2013.
↑ ¹ ² ³ ⁴ Габидулин, Кшевецкий, Колыбельников, 2011.
↑ ¹ ² ³ Ю.Б. Кобзарев, 2013.
↑ ¹ ² Ларин, 2008.
↑ ¹ ² ³ ⁴ ⁵ Фомичёв, 2003.
↑ Beker, Piper, 1982.
↑ А. Сизоненко, 2012.
↑ E. Barklan, E. Biham, N. Keller, 2008.
↑ Y. Lu, W. Meier, S. Vaudenay, 2005.
↑ D. Eastlake, J. Schiller, S. Crocker, 2005.
↑ Efficient Shift Registers, LFSR Counters and Long Pseudo-Random Sequence Generators (неопр.). Дата обращения: 18 ноября 2014. Архивировано 25 января 2021 года.
↑ B. Harrington, 2008.
↑ О. Дяченко.
↑ В. Варгаузин, 1999.

Литература

Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. — Триумф, 2013. — 816 с. — ISBN 978-5-89392-527-2.
Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации: учебное пособие — М.: МФТИ, 2011. — 225 с. — ISBN 978-5-7417-0377-9
Ларин А. Л. Основы цифровой электроники — М.: МФТИ, 2008. — 314 с. — ISBN 978-5-7417-0228-4
Скляр Б. Цифровая связь. Теоретические основы и практическое применение. — Вильямс, 2007. — 1104 с. — ISBN 978-5-8459-0497-3.
Кобзарев Ю. Б. Современная радиолокация. — Рипол Классик, 2013. — 708 с. — ISBN 978-5-4584-7357-6.
Фомичёв В. М. Дискретная математика и криптология: Курс лекций / под ред. Н. Д. Подуфалов — М.: Диалог-МИФИ, 2013. — 397 с. — ISBN 978-5-86404-185-7
Beker H., Piper F. Cipher systems: the protection of communications (англ.) — London: Northwood Books, 1982. — 427 p. — ISBN 978-0-7198-2611-5
Сизоненко А. Б. Многоканальный цифровой источник шума на основе рекуррентного регистра сдвига. — Журнал «Спецтехника и связь» №3, 2012. Архивная копия от 29 ноября 2014 на Wayback Machine
Barklan E., Biham E., Keller N. Instant ciphertext-only cryptanalysis of GSM encrypted communication. — Journal of cryptology №21-3, 2008.
Lu Y., Meier W., Vaudenay S. Instant ciphertext-only Cryptanalysis of GSM encrypted communication. — Crypto №3621, 2005. (недоступная ссылка)
Eastlake D., Schiller J., Crocker S. Randomness requirements for security. — 2005.
Harrington B. Get your boost from BIST. — 2008. (недоступная ссылка)
Дяченко О. Н. Компактный анализ над полем GF(3).
Варгаузин В. Принципы цифрового телевидения стандарта ATSC. — Журнал Теле-Спутник №9(47), 1999.

Ссылки

LFSR reference (англ.). Теория и реализация LFSR, последовательности максимальной длины и полные таблицы отводных последовательностей для длин от 7 до 16 миллионов (от 3 до 24 битов), а также частичные таблицы для длин до 4 миллиардов (от 25 до 32 битов) (недоступная ссылка) Архивировано 1 октября 2018.
International telecommunications union recommendation O.151 (англ.). Август 1992
Pseudo-random number generation routine Архивная копия от 25 декабря 2008 на Wayback Machine (англ.)
[3] (англ.)
Simple explanation of LFSRs for engineers (англ.)
Feedback terms (англ.)
An implementation of a cryptographically secure shrinking pseudorandom number generator (англ.)
Методы и задачи криптографической защиты информации (недоступная ссылка)

[_884bb731adfcf1a4-1] Б. Скляр, 2007.

[2] Linear Feedback Shift Registers in Virtex Devices (неопр.). Дата обращения: 19 ноября 2014. Архивировано 2 ноября 2013 года.

[_97c38d0090b94b50-3] ¹ ² ³ ⁴ ⁵ Б. Шнайер, 2013.

[_e98c0fc999e22496-4] ¹ ² ³ ⁴ Габидулин, Кшевецкий, Колыбельников, 2011.

[_e45da462888d0612-5] ¹ ² ³ Ю.Б. Кобзарев, 2013.

[_58cbe161b14dd848-6] ¹ ² Ларин, 2008.

[_73a3c0e3e43d81d6-7] ¹ ² ³ ⁴ ⁵ Фомичёв, 2003.

[_358d977e8a5ca770-8] Beker, Piper, 1982.

[_3229f1d045579e8b-9] А. Сизоненко, 2012.

[_418b5d45bba5a6a6-10] E. Barklan, E. Biham, N. Keller, 2008.

[_8a90d56207508cdf-11] Y. Lu, W. Meier, S. Vaudenay, 2005.

[_8a8c5ecfc44bdf7e-12] D. Eastlake, J. Schiller, S. Crocker, 2005.

[13] Efficient Shift Registers, LFSR Counters and Long Pseudo-Random Sequence Generators (неопр.). Дата обращения: 18 ноября 2014. Архивировано 25 января 2021 года.

[_024587bf89713b83-14] B. Harrington, 2008.

[_7352782730a45699-15] О. Дяченко.

[_07cd4a48066a7751-16] В. Варгаузин, 1999.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]