Эта статья выставлена на рецензию

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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Содержание

Описание[править | править вики-текст]

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

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

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

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

Принцип работы[править | править вики-текст]

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

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

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

  • на 1-м шаге: S_L=(c_1*S_{L-1})\oplus(c_2*S_{L-2})\oplus\dots\oplus(c_L*S_{0});
  • на 2-м шаге: S_{L+1}=(c_1*S_{L})\oplus(c_2*S_{L-1})\oplus\dots\oplus(c_L*S_{1});
  • ... ;
  • на j-м шаге: 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})[4].

Свойства[править | править вики-текст]

Периодичность[править | править вики-текст]

Периодом регистра сдвига называется минимальная длина получаемой последовательности до начала её повторения. РСЛОС длины L имеет 2^{L} начальных состояний, задающих значения бит в ячейках. Из них 2^{L}-1 состояний - ненулевые, так что генерируемая последовательность имеет период T\leq2^{L}-1. Период генерируемой последовательности максимален и равен 2^{L}-1, если многочлен обратной связи (или характеристический многочлен) ~C(x)=c_Lx^{L}+c_{L-1}x^{L-1}+\dots+c_1x+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)
{
    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 \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

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

Конфигурация Галуа[править | править вики-текст]

Пример РСЛОС конфигурации Галуа

Возьмём тот же характеристический многочлен, то есть c_3=c_1=c_0=1, c_2=0. С выходным битом складывается только 1-й бит. Начальное состояние то же самое. Дальнейшие состояния регистра:

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

Внутреннее состояние регистра на седьмом шаге вернулось к исходному, следовательно, его период также равен 7. В отличие от конфигурации Фибоначчи, внутренние состояния регистра получились другие, но генерируемая последовательность та же, только сдвинута на 4 такта: ~\left[1,\;1,\;1,\;0,\;1,\;0,\;0,\;1,\;1,\;1,\;...\right] (порядок бит в последовательности соответствует порядку их генерации РСЛОС).

Генерация примитивных многочленов[править | править вики-текст]

Вычисление примитивного многочлена над полем \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)\lesssim2^L, где L=\sum\limits_{i=1}^M L_i - общее число ячеек. Следовательно, использование нескольких РСЛОС увеличивает период генерируемой последовательности по сравнению с одним регистром, что увеличивает криптостойкость генератора.

Также криптографические свойства генератора могут быть улучшены увеличением длины регистра, эквивалентного данному генератору. Такой эквивалентный регистр находится с помощью алгоритма Берлекэмпа — Мэсси по генерируемой последовательности. В лучшем случае длина эквивалентного регистра соизмерима с периодом генерируемой последовательности[4].

Генераторы с нелинейными преобразованиями[править | править вики-текст]

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

Нелинейный генератор может быть также реализован на регистре сдвига с нелинейной обратной связью[en]. Он может дать 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 генерируемая последовательность приближается к случайной, так что лучше использовать больше РСЛОС небольшой длины, чем меньше длинных РСЛОС.

Мажоритарные генераторы[править | править вики-текст]

Система регистров сдвига в алгоритме шифрования А5/1

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

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

Подобные генераторы используются в алгоритме шифрования A5.

Применение[править | править вики-текст]

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

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

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

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

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

Использование в качестве счётчиков[править | править вики-текст]

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

Тестирование цифровых устройств[править | править вики-текст]

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

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

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

Скремблирование[править | править вики-текст]

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]