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

Описание

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

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

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

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

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

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

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

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

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

S L = ( c 1 ∗ S L − 1 ) ⊕ ( c 2 ∗ S L − 2 ) ⊕ ⋯ ⊕ ( c L ∗ S 0 ) {displaystyle 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 ) ⊕ ( c 2 ∗ S L − 1 ) ⊕ ⋯ ⊕ ( c L ∗ S 1 ) {displaystyle S_{L+1}=(c_{1}*S_{L})oplus (c_{2}*S_{L-1})oplus dots oplus (c_{L}*S_{1})} . . . {displaystyle ...} S L + j − 1 = ( c 1 ∗ S L + j − 2 ) ⊕ ( c 2 ∗ S L + j − 3 ) ⊕ ⋯ ⊕ ( c L ∗ S j − 1 ) {displaystyle 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 {displaystyle L} имеет 2 L {displaystyle 2^{L}} начальных состояний, задающих значения бит в ячейках. Из них 2 L − 1 {displaystyle 2^{L}-1} состояний - ненулевые, так что генерируемая последовательность имеет период T ≤ 2 L − 1 {displaystyle Tleq 2^{L}-1} . Период генерируемой последовательности максимален и равен 2 L − 1 {displaystyle 2^{L}-1} , если многочлен обратной связи (или характеристический многочлен) C ( x ) = c L x L + c L − 1 x L − 1 + ⋯ + c 1 x + 1 {displaystyle C(x)=c_{L}x^{L}+c_{L-1}x^{L-1}+dots +c_{1}x+1} над полем G F ( 2 ) {displaystyle mathrm {GF} (2)} является примитивным. Для этого необходимо (но не достаточно) выполнение следующих 2-х условий:

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

Число всех возможных примитивных многочленов равно ϕ ( 2 L − 1 ) L {displaystyle { frac {phi (2^{L}-1)}{L}}} , где ϕ {displaystyle phi } - функция Эйлера. Регистр, заданный таким многочленом, называется регистром сдвига максимального периода (или генератором псевдослучайной последовательности), а генерируемые последовательности - последовательностями максимального периода (или М-последовательностями).

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

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

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

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

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

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

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

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

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

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

Рассмотрим 32-битовый сдвиговый регистр. Для него имеется отводная последовательность ( 32 , 31 , 30 , 28 , 26 , 1 ) {displaystyle left(32,;31,;30,;28,;26,;1 ight)} . Это означает, что для генерации нового бита необходимо с помощью операции XOR просуммировать 31-й, 30-й, 29-й, 27-й, 25-й и 0-й биты. Полученный РСЛОС имеет максимальный период 2 32 − 1 {displaystyle 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 {displaystyle L-1} -й бит, а выходным — 0 {displaystyle 0} -й. Результат сложения записывается в следующую ячейку, а новый выходной бит записывается в L − 1 {displaystyle L-1} -ю. Таким образом, если генерируемый бит равен нулю, то все биты в ячейках сдвигаются вправо без изменений, если генерируемый бит равен единице, то биты отвода меняют своё значение на противоположное, и все биты сдвигаются вправо. И конфигурация Фибоначчи, и конфигурация Галуа одной и той же длины генерируют одинаковые, но смещённые по времени одна от другой последовательности (при этом внутренние состояния регистров могут отличаться).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Недостатки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Применение

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

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

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

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

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

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

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

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

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

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

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

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

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

  • ATSC;
  • DAB;
  • DVB-T;
  • NICAM;
  • CDMA;
  • 100BASE-T2 Fast Ethernet;
  • 1000BASE-T Gigabit Ethernet;
  • PCI Express 3.0;
  • SATA;
  • Serial Attached SCSI;
  • USB 3.0;
  • IEEE 802.11a;
  • Bluetooth LE.

Имя:*
E-Mail:
Комментарий: