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

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

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

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

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

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

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

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

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

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

Пример РСЛОС конфигурации Фибоначчи

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На регистре сдвига с линейно обратной связью основаны такие потоковые шифры, как 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-го, не станут равными нулю, то есть до состояния ${\displaystyle \left[1,\;0,\;0,\;...,\;0\right]}$. Наряду с РСЛОС работает двоичный счётчик, подсчитывающий количество тактов с момента окончания сжатия тестовой реакции. Если изначальное состояние регистра соответствовало эталонной сигнатуре (сигнатуре безошибочной схемы), то показание счётчика соответствует номеру ошибочного бита[14][15].

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

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

• ATSC[16];
• 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.