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

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

Определение

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

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

Для РСЛОС функция обратной связи является линейной булевой функцией от состояний всех или некоторых битов регистра. Например, сумма по модулю два или её логическая инверсия является линейной булевой функцией (операция XOR, в формулах обозначают как $\oplus$) и наиболее часто применяется в таких регистрах.

При этом те биты, которые являются переменными функции обратной связи, принято называть отводами.

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

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

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

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

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

• на первом шаге: $S_L = (c_1*S_{L-1}) \oplus (c_2*S_{L-2}) \oplus \dots \oplus (c_L*S_{0})$
• на втором шаге: $S_{L+1} = (c_1*S_{L}) \oplus (c_2*S_{L-1}) \oplus \dots \oplus (c_L*S_{1})$
• …
• на $j-(L-1)$-м шаге: $S_{j} = (c_1*S_{j-1}) \oplus (c_2*S_{j-2}) \oplus \dots \oplus (c_L*S_{j-L})$, причём некоторые коэффициенты (но не все, иначе вырожденный случай) $~c_i$ равны 0.

Свойства примитивных многочленов

• если $P(X)$ примитивный многочлен степени $N$, то примитивен и $X^N P(1/X)$;
• если примитивен многочлен $X^A + X^B + 1$, то примитивен и $X^A + X^{A-B} + 1$;
• если примитивен многочлен $X^A + X^B + X^C + X^D + 1$, то примитивен и $X^A + X^{A-D} + X^{A-C} + X^{A-B} + 1$.

Свойства

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

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

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

• $S=(s_1,\;s_2,\;s_3,\;\dots)$ — бесконечная последовательность;
• $S_n=(s_1,\;s_2,\;\dots,\;s_n)$ — подпоследовательность длины $n$ последовательности $S$;
• говорят, что РСЛОС генерирует последовательность $S$, если существует некоторое исходное состояние, при котором выходная последовательность РСЛОС совпадает $S$;
• говорят, что РСЛОС генерирует конечную последовательность $S_n$, если существует некоторое начальное состояние, для которого выходная последовательность РСЛОС имеет в качестве первых $n$ членов члены последовательности $S_n$.

Определение

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

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

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

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

Конфигурация Галуа регистра сдвига с линейной обратной связью

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

int LFSR (void)
{
    static unsigned long Q = 1;
    Q = (Q>>1) ^ ( Q&1 ? 0x80000057 : 0 );
    return Q & 1;
}

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

• можно доказать, что приведенная первой конфигурация Фибоначчи и приведенная здесь конфигурация Галуа дают одинаковые последовательности (длиной 2³²−1), но смещённые по фазе одна от другой
• цикл из фиксированного числа вызовов функции LFSR в конфигурации Галуа выполняется примерно в два раза быстрее, чем в конфигурации Фибоначчи (компилятор MS VS 2010 на Intel Core i5)
• обратите внимание, что в конфигурации Галуа порядок бит в слове, определяющем обратную связь, обратный по сравнению с конфигурацией Фибоначчи

Примеры генераторов

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

Чередующийся генератор «стоп-пошёл»

Этот генератор использует вывод одного РСЛОС для управления тактовой частотой другого РСЛОС. Тактовый выход РСЛОС-2 управляется выходом РСЛОС-1, так что РСЛОС-2 может менять своё состояние в момент времени t, только если выход РСДОС-1 в момент времени t-1 был равен единице. Но эта схема не устояла перед корреляционным вскрытием.

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

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

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

Каскад Голлманна представляет собой усиленную версию генератора «стоп-пошёл». Он состоит из последовательности РСЛОС, тактирование каждого из которых управляется предыдущим РСЛОС. Если выходом РСЛОС-1 в момент времени t является 1,то тактируется РСЛОС-2. Если выходом РСЛОС-2 в момент времени t является 1, то тактируется РСЛОС-3, и так далее. Выход последнего РСЛОС является выходом генератора. Если длина всех РСЛОС одинакова и равна n, то линейная сложность системы из k РСЛОС равна $n(2^n - 1)^((k-1))$.

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

Пороговый генератор

Пороговый генератор

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

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

Для случая трёх регистров сдвига генератор можно представить как:

$b = (a_1 \and a_2)\oplus(a_1 \and a_3)\oplus(a_2 \and a_3)$

Этот генератор похож на генератор Геффа за исключением того, что пороговый генератор обладает большей линейной сложностью. Его линейная сложность равна:

$n_1 n_2 + n_1 n_3 + n_2 n_3$

где $n_1$, $n_2$, $n_3$ — длины первого, второго и третьего регистров сдвига.

Его недостатком является то, что каждый выходной бит дает некоторую информацию о состоянии сдвигового регистра. А точнее 0.189 бита. Поэтому данный генератор может не устоять перед корреляционным вскрытием.

Другие виды

Самопрореживающие

Самопрореживающими называются генераторы, которые управляют собственной частотой. Было предложено два типа таких генераторов. Первый состоит из регистра сдвига с обратной линейной связью и некоторой схемы, которая тактирует этот регистр, в зависимости от того какими получаются выходные значения регистра сдвига. Если выход РСЛОС равен единице, то регистр тактируется d раз. Если выход равен нулю, то регистр тактируется k раз. Второй имеет практически ту же конструкцию, но несколько модифицированную: в схеме тактирования на вход, в качестве проверки на 0 или 1, поступает не сам выходной сигнал, а XOR определённых битов регистра сдвига с линейной обратной связью. К сожалению, этот вид генератора не безопасен.

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

Этот генератор использует два регистра сдвига с линейной обратной связью с разными тактовыми частотами: РСЛОС-1 и РСЛОС-2. Тактовая частота РСЛОС-2 в d раз больше чем РСЛОС-1. Отдельные биты этих регистров объединяются операцией AND. Затем с выходами операции AND выполняется операция XOR. С этого блока XOR снимается выходная последовательность. Опять же и этот генератор не безупречен (Он не выстоял перед вскрытием линейной согласованности. Если $N_1$ — длина РСЛОС-1,$N_2$- длина РСЛОС-2, а d — отношение тактовых частот, то внутреннее состояние генератора может быть получено по выходной последовательности длиной $N_1 + N_2 + LOG_2{d}$), но он имеет высокую линейную сложность и обладает великолепными статистическими характеристиками.

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

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

Недостатки

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

См. также

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

Ссылки

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