Регистр сдвига с линейной обратной связью (РСЛОС, , ) — регистр битовых слов, у которого значение входного (вдвигаемого) бита равно линейной булевой функции от значений остальных битов регистра до сдвига. Может быть организован как программными, так и аппаратными средствами. Применяется для генерации псевдослучайных последовательностей битов, что находит применение, в частности, в криптографии. По похожему принципу работают регистр сдвига с обратной связью по переносу и регистр сдвига с обобщённой обратной связью.
Описание
В регистре сдвига с линейной обратной связью (РСЛОС) выделяют две части (модуля): собственно регистр сдвига; схему (или подпрограмму) обратной связи, вычисляющую значение вдвигаемого бита. Регистр состоит из функциональных ячеек памяти (битов одного или нескольких машинных слов), в каждой из которых хранится текущее состояние (значение) одного бита. Количество ячеек , называют длиной регистра. Биты (ячейки) обычно нумеруются числами , содержимое -й ячейки обозначается через . Значение нового бита определяется до сдвига битов в регистре и только после сдвига записывается в ячейку , а из ячейки извлекается очередной сгенерированный бит.
Функцией обратной связи для РСЛОС является линейная булева функция от значений всех или некоторых битов регистра. Функция выполняет умножение битов регистра на коэффициенты , где . Количество коэффициентов совпадает с количеством битов регистра . Коэффициенты принимают значения , причём последний коэффициент равен , так как РСЛОС задаётся характеристическим многочленом степени . Сложение по модулю 2 (операция «XOR», обозначаемая в формулах символом «») или её логическая инверсия «XNOR» являются линейными булевыми функциями и наиболее часто применяются в таких регистрах. При этом биты, являющиеся переменными функции обратной связи, называются отводами, а сам регистр называется конфигурацией Фибоначчи.
Управление регистром в аппаратных реализациях производится подачей сдвигающего импульса (иначе называемого тактовым или синхроимпульсом) на все ячейки. Управление регистром в программных реализациях производится выполнением цикла. На каждой итерации цикла вычисляется функция обратной связи и выполняется битовый сдвиг в слове.
Принцип работы В течение каждого такта сдвигового регистра с линейной обратной связью выполняет следующие операции: читается бит, расположенный в ячейке ; этот бит является очередным битом выходной последовательности; функции обратной связи вычисляет новое значение для ячейки , используя текущие значения ячеек; содержимое каждой -й ячейки перемещается в следующую ячейку , где ; в ячейку записывается бит, ранее вычисленный функцией обратной связи.
Если функция обратной связи выполняет логическую операцию «XOR» (исключающее ИЛИ), значения бит (ячеек) могут быть вычислены по следующим формулам:
Свойства
Периодичность Периодом регистра сдвига называется минимальная длина получаемой последовательности до начала её повторения. РСЛОС длины имеет начальных состояний, задающих значения бит в ячейках. Из них состояний — ненулевые, так что генерируемая последовательность имеет период . Период генерируемой последовательности максимален и равен , если многочлен обратной связи (или характеристический многочлен) над полем является примитивным. Для этого необходимо (но не достаточно) выполнение следующих 2-х условий: чётное число отводов; номера отводов, взятые все вместе, а не попарно, взаимно просты. Число всех возможных примитивных многочленов равно , где — функция Эйлера. Регистр, заданный таким многочленом, называется регистром сдвига максимального периода (или генератором псевдослучайной последовательности), а генерируемые последовательности — последовательностями максимального периода (или М-последовательностями).
Линейная сложность Линейной сложностью бесконечной двоичной последовательности называется число , которое определяется следующим образом: если — нулевая последовательность, то ; если не существует РСЛОС, который генерирует , то ; в противном случае равна длине самого короткого РСЛОС, который генерирует . Линейной сложностью конечной двоичной последовательности называется число , равное длине самого короткого РСЛОС, который генерирует эту последовательность.
Линейная сложность регистра сдвига с линейной обратной связью показывает, насколько близка генерируемая последовательность к случайной. Эффективным алгоритмом определения линейной сложности конечной бинарной последовательности является алгоритм Берлекэмпа-Мэсси.
Корреляционная независимость Пытаясь получить высокую линейную сложность генерируемой последовательности, криптографы нелинейно объединяют выходы нескольких регистров сдвига. При этом одна или несколько выходных последовательностей (или даже выходы отдельных РСЛОС) могут быть связаны общим потоком и вскрыты криптоаналитиком. Взлом на основе такой уязвимости называют корреляционным вскрытием. Основная идея такого взлома заключается в обнаружении некоторой корреляции между выводом генератора и выводами его составных частей. Затем, наблюдая выходную последовательность, можно получить информацию об этих промежуточных выводах, и, таким образом, взломать генератор. Томас Сигенталер показал, что можно точно определить корреляционную независимость, и что существует компромисс между корреляционной независимостью и линейной сложностью.
Программная реализация Программные реализации РСЛОС достаточно медленны и работают быстрее, если они написаны на ассемблере. Одно из решений — параллельное использование 16-ти РСЛОС (или 32-х, в зависимости от длины слова в архитектуре компьютера). В такой схеме используется массив слов, размер которого равен длине регистра сдвига, а каждый бит слова относится к своему РСЛОС. Так как используются одинаковые номера отводных последовательностей, то это может дать заметный выигрыш в производительности генератора.
Конфигурация Фибоначчи Рассмотрим 32-битовый сдвиговый регистр. Для него имеется отводная последовательность . Это означает, что для генерации нового бита необходимо с помощью операции XOR просуммировать 31-й, 30-й, 29-й, 27-й, 25-й и 0-й биты. Полученный РСЛОС имеет максимальный период . Код для такого регистра на языке Си следующий: 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 отводных битов с выходом генератора, но порядок битов в регистре обратный: входным является -й бит, а выходным — -й. Результат сложения записывается в следующую ячейку, а новый выходной бит записывается в -ю. Таким образом, если генерируемый бит равен нулю, то все биты в ячейках сдвигаются вправо без изменений, если генерируемый бит равен единице, то биты отвода меняют своё значение на противоположное, и все биты сдвигаются вправо. И конфигурация Фибоначчи, и конфигурация Галуа одной и той же длины генерируют одинаковые, но смещённые по времени одна от другой последовательности (при этом внутренние состояния регистров могут отличаться).
Данный генератор не обладает большей криптостойкостью, но он даёт выигрыш в производительности: все операции 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).
Пример генерируемой последовательности
Конфигурация Фибоначчи
Пусть РСЛОС задаётся характеристическим многочленом . Это значит, что битами отвода будут 2-й и 0-й, а единица в формуле многочлена означает, что 0-й бит — входной. Функция обратной связи имеет вид . Допустим, изначальным состоянием регистра сдвига была последовательность . Дальнейшие состояния регистра приведены в таблице ниже:
Номер шага Состояние Генерируемый бит 0 1 1 0 2 0 3 1 4 1 5 1 6 0 7 1
Поскольку внутреннее состояние на седьмом шаге вернулось к исходному, то, начиная со следующего шага, будет идти повтор битов. То есть генерируемая последовательность такова: (порядок бит в последовательности соответствует порядку их генерации РСЛОС). Таким образом, период последовательности равен 7, то есть максимально возможному значению, что произошло в силу примитивности заданного многочлена.
Конфигурация Галуа
Возьмём тот же характеристический многочлен, то есть , . С выходным битом складывается только 1-й бит. Начальное состояние то же самое. Дальнейшие состояния регистра: Номер шага Состояние Генерируемый бит 0 1 1 1 2 1 3 0 4 1 5 0 6 0 7 1 Внутреннее состояние регистра на седьмом шаге вернулось к исходному, следовательно, его период также равен 7.
Пример реализации на логических элементах
На картинке справа можно увидеть пример реализации РСЛОС с конфигурацией Галуа вида (7, 10).
В верхней части схемы расположены выходные контакты, на которых можно увидеть последовательность генерируемых регистром битов. Ниже идут D-триггеры, которые соединены друг с другом и образуют собственно регистр. Самый правый триггер (номер 1) является выходным и, согласно реализуемой конфигурации, влияет на передачу бита из 10-го и 7-го триггеров (берётся XOR передаваемого и выходного бита). Остальные биты передаются без изменений.
Начальная конфигурация регистра задаётся при помощи мультиплексоров перед каждым триггером. Чтобы сбросить конфигурацию регистра до начальной (или той, которая нужна, её можно выбрать на контактах перед мультиплексорами), нужно всего лишь подать 1 на контакт Init, после чего подать сигнал синхронизации. После зануления синхронизации регистр примет нужную конфигурацию. Чтобы дальше он начал работать корректно, сигнал Init нужно вновь занулить.
Матричное представление LFSR
раздел английской статьи
Генерация примитивных многочленов Вычисление примитивного многочлена над полем — достаточно сложная математическая задача: для генерации примитивного многочлена степени нужно знать множители числа . Проще случайным образом выбрать многочлен и проверить его на примитивность. Ещё один метод заключается в использовании готовых таблиц, в которых приведены номера отводных последовательностей, обеспечивающих максимальный период генератора. Ниже приведена таблица примитивных многочленов над полем для регистров сдвига максимального периода длиной до 19 бит. Стоит учесть, что у генератора любой заданной длины может быть более одного примитивного многочлена согласно их свойствам. Полный список для регистров длиной от 4 до 32 бит можно найти здесь. Биты, Примитивный многочлен Период, Число примитивных многочленов 2 3 1 3 7 2 4 15 2 5 31 6 6 63 6 7 127 18 8 255 16 9 511 48 10 1023 60 11 2047 176 12 4095 144 13 8191 630 14 16383 756 15 32767 1800 16 65535 2048 17 131071 7710 18 262143 7776 19 524287 2759420 — 168 2 — 786, 1024, 2048, 4096
Преимущества и недостатки
Преимущества высокое быстродействие криптографических алгоритмов, создаваемых на основе РСЛОС (например потоковых шифров); применение только простейших битовых операций сложения и умножения, аппаратно реализованных практически во всех вычислительных устройствах; хорошие криптографические свойства (РСЛОС могут генерировать последовательности большого периода с хорошими статистическими свойствами); благодаря своей структуре, РСЛОС легко анализируются с использованием алгебраических методов.
Недостатки