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

Определение

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

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

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

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

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

• на первом шаге:
• на втором шаге:
• …
• на -м шаге:

Свойства

Свойства выдаваемой РСЛОС последовательности тесно связаны со свойствами ассоциированного многочлена над полем . Его ненулевые коэффициенты называются отводами, как и соответствующие ячейки регистра, поставляющие значения аргументов функции обратной связи.

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

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

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

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

• если примитивный многочлен степени , то примитивен и ;
• если примитивет многочлен , то примитивен и ;
• если примитивен многочлен , то примитивен и .

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

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

•  — бесконечная последовательность;
•  — подпоследовательность длины последовательности ;
• говорят, что РСЛОС генерирует последовательность , если существует некоторое исходное состояние, при котором выходная последовательность РСЛОС совпадает ;
• говорят, что РСЛОС генерирует конечную последовательность , если существует некоторое начальное состояние, для которого выходная последовательность РСЛОС имеет в качестве первых членов члены последовательности .

Определение

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

• если — нулевая последовательность, то ;
• если не существует РСЛОС, который генерирует , то ;
• иначе равна длине самого короткого РСЛОС, который генерирует .

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

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

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

1. для любого линейная сложность подпоследовательности удовлетворяет неравенствам ;
2. тогда и только тогда, когда  — нулевая последовательность длины ;
3. тогда и только тогда, когда ;
4. если периодическая с периодом , то ;
5. .

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

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

Примечание

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

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

Пример

Для РСЛОС с ассоциированным многочленом генерируемая последовательность имеет вид . Допустим, перед началом процесса в регистре записана последовательность , тогда период генерируемого потока битов будет равен 7 со следующей последовательностью:

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

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

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

Вычисление примитивности многочлена — достаточно сложная математическая задача. Поэтому существуют готовые таблицы, в которых приведены номера отводных последовательностей, обеспечивающих максимальный период генератора. Например, для 32-битового сдвигового регистра имеется последовательность . Это означает, что для генерации нового бита необходимо с помощью функции 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, то тактируется РСЛОС-2, и так далее. Выход последнего РСЛОС является выходом генератора. Если длина всех РСЛОС одинакова и равна n, то линейная сложность системы из k РСЛОС равна

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

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

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

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

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

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

где , , – длины первого, второго и третьего регистров сдвига.

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

Другие виды генераторов

Опишем их кратко

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

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

Многоскоростной генератор с внутренним произведением (inner-product)

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

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

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

Недостатки

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

См. также

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

Ссылки

• LFSR Reference Теория и реализация LFSR, последовательности максимальной длины и полные таблицы отводных последовательностей для длин от 7 до 16 777 215 (от 3 до 24 битов), а также частичные таблицы для длин до 4 294 967 295 (от 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
• Методы и задачи криптографической защиты информации
• РСЛОС