Регистр сдвига с линейной обратной связью c. Теоретические основы работы. Для чего нужны последовательности, генерируемые регистрами сдвига

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

Регистр сдвига с обратной связью (далее РгСсОС) состоит из двух частей: регистра сдвига и функции обратной связи. Регистр сдвига представляет собой последовательность битов. Количество битов определяется длиной сдвигового регистра , если длина равна n битам, то регистр называется n-битовым сдвиговым регистром . Всякий раз, когда нужно извлечь бит, все биты сдвигового регистра сдвигаются вправо на 1 позицию. Новый крайний левый бит является функцией всех остальных битов регистра. На выходе сдвигового регистра оказывается один, обычно младший значащий, бит. Периодом сдвигового регистра называется длина получаемой последовательности до начала ее повторения.

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

Регистры сдвига очень быстро нашли применение в потоковых шифрах, так как они легко реализовывались с помощью цифровой аппаратуры. В 1965 году Эрнст Селмер (Ernst Selmer), главный криптограф норвежского правительства, разработал теорию последовательности регистров сдвига . Соломон Голомб (Solomon Golomb), математик NSA, написал книгу, излагающие некоторые свои результаты и результаты Селмера . Простейшим видом регистра сдвига с обратной связью является регистр сдвига с линейной обратной связью (linear feedback shift register, далее LFSR или РгСсЛОС). Обратная связь таких регистров представляет собой просто XOR (сложение по модулю два) некоторых битов регистра, перечень этих битов называется отводной последовательностью (tap sequence). Иногда такой регистр называется конфигурацией Фиббоначи. Из-за простоты последовательности обратной связи для анализа РгСсЛОС можно использовать довольно развитую математическую теорию. Проанализировав получаемые выходные последовательности, можно убедиться в том, что эти последовательности достаточно случайны, чтобы быть безопасными. РгСсЛОС чаще других сдвиговых регистров используются в криптографии.

Рисунок 2. РгСсЛОС Фиббоначи

В общем случае n-битовый РгСсЛОС может находиться в одном из N=2 n -1 внутренних состояний. Это означает, что теоретически такой регистр может генерировать псевдослучайную последовательность с периодом Т=2 n -1 битов. (Число внутренних состояний и период равны N=T max =2 n -1, потому что заполнение РгСсЛОС нулями, приведет к тому, что сдвиговый регистр будет выдавать бесконечную последовательность нулей, что абсолютно бесполезно). Только при определенных отводных последовательностях РгСсЛОС циклически пройдет через все 2 n -1 внутренних состояний, такие РгСсЛОС являются РгСсЛОС с максимальным периодом . Получившийся результат называется М-последовательностью .

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

Номер такта сдвига (внутреннего состояния)	Состояние регистров	Выходной бит
Инициальное значение
15 (возврат в инициальное состояние)
16 (повтор состояний)

Выходной последовательностью будет строка младших значащих битов: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 с периодом Т=15, общее число возможных внутренних состояний (кроме нулевого), N=2 4 -1=16-1=15=T max , следовательно, выходная последовательность - M-последовательность.

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

a n x n +a n-1 x n-1 + … +a 1 x 1 +a 0 x 0 =a n x n +a n-1 x n-1 + … +a 1 x+a 0 , где а i ={0,1} для i=1…n, a x i - указывает разряд.

Степень многочлена является длиной сдвигового регистра. Примитивный многочлен степени n - это неприводимый многочлен, который является делителем x 2n?1 +1, но не является делителем x d +1 для всех d, являющихся делителями 2 n -1. Соответствующую математическую теорию можно найти в .

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

Некоторые, но, конечно же, не все, многочлены различных степеней, примитивные по модулю 2, приведены далее. Например, запись

(32, 7, 5, 3, 2, 1, 0) означает, что следующий многочлен примитивен по модулю 2: x 32 + x 7 +x 5 + x 3 + x 2 + x + 1.

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

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

Рисунок 4. 32-битовый РгСсЛОС с максимальной длиной

Рассмотрим программный код РгСсЛОС, у которого отводная последовательность характеризуется многочленом (32, 7, 5, 3, 2, 1, 0). На языке C выглядит следующим образом :

static unsigned long ShiftRegister = 1;

/* Все, кроме 0. */

ShiftRegister = ((((ShiftRegister >> 31)

^(ShiftRegister >> 6)

^(ShiftRegister >> 4)

^(ShiftRegister >> 2)

^(ShiftRegister >> 1)

^ShiftRegister))

| (ShiftRegister >> 1);

return ShiftRegister & 0x00000001;}

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

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

Если p(x) примитивен, то примитивен и x n p (1/x), поэтому каждый элемент таблицы на самом деле определяет два примитивных многочлена. Например, если (a, b, 0) примитивен, то примитивен и (a, a-b, 0). Если примитивен (a, b, c, d, 0), то примитивен и (a, a-d, a-c, a-b, 0). Математически:

если примитивен 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. Быстрее всего программно реализуются примитивные трехчлены, так как для генерации нового бита нужно выполнять XOR только двух битов сдвигового регистра (нулевой член не учитывается, т.е. х 0 =1, см. пример выше). Действительно, все многочлены обратной связи, приведенные в таблице, являются разреженными, то есть, у них немного коэффициентов. Разреженность всегда представляет собой источник слабости, которой иногда достаточно для вскрытия алгоритма. Для криптографических алгоритмов гораздо лучше использовать плотные примитивные многочлены, те, у которых много коэффициентов. Применяя плотные многочлены, особенно в качестве части ключа, можно использовать значительно более короткие РгСсЛОС.

Генерировать плотные примитивные многочлены по модулю 2 нелегко. В общем случае для генерации примитивных многочленов степени k нужно знать разложение на множители числа 2 k -1.

Сами по себе РгСсЛОС являются хорошими генераторами псевдослучайных последовательностей, но они обладают некоторыми нежелательными неслучайными (детерминированными) свойствами. Последовательные биты линейны, что делает их бесполезными для шифрования. Для РгСсЛОС длины n внутреннее состояние представляет собой предыдущие n выходных битов генератора. Даже если схема обратной связи хранится в секрете, она может быть определена по 2n выходным битам генератора с помощью высоко эффективного алгоритма Berlekamp-Massey .

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

Простейшим видом функции обратной связи является линейная функция, например, сумма по модулю 2 содержимого определенных разрядов. Такой регистр называется сдвиговым регистром с линейной обратной связью (Linear Feedback Shift Register, сокращенно LFSR). В общем случае линейная функция обратной связи задается формулой . Здесь c k = 1, если k -й разряд используется в функции обратной связи, и c k = 0 в противном случае. Символ Å обозначает сложение по модулю 2 (исключающее ИЛИ).

Для примера рассмотрим LFSR с функцией обратной связи (см. рисунок).

Если начальным состоянием регистра является 1111, то в последующих тактах он будет принимать следующий ряд состояний: 1111, 0111, 1011, 0101, 1010, 1101, 0110, 0011, 1001, 0100, 0010, 0001, 1000, 1100, 1110, 1111, …

Выходная последовательность формируется из младшего (крайнего правого) разряда регистра. Она будет выглядеть следующим образом: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1. Видно, что генерируемая битовая последовательность целиком определяется начальным состоянием регистра и функцией обратной связи. Поскольку число всевозможных состояний регистра конечно (оно равно 2 L ), то, рано или поздно, ключевая последовательность начнёт повторяться. Максимальная длина неповторяющейся части ключевой последовательности называется ее периодом T . Период зависит от функции обратной связи. Максимально возможный период равен T max = 2 L -1 (регистр принимает все возможные состояния, кроме 0000...0). Выходная последовательность LFSR, обладающего максимальным периодом, называется М-последовательностью .

Чтобы выяснить условия, при которых LFSR будет обладать максимальным периодом, функции обратной связи ставят в соответствие характеристический полином . Так, регистру, приведенному выше в качестве примера, соответствует полином . Теоретический анализ показывает, что LFSR будет обладать максимальным периодом тогда и только тогда, когда полином P (x ) является примитивным . Ниже приведены некоторые примитивные полиномы, рекомендованные к применению на практике. В таблице указаны степени переменной x в записи полинома. Например, запись (31, 3) соответствует полиному .

№	P (x )	№	P (x )	№	P (x )
	(39, 16, 23, 35)		(38, 5, 6, 27)		(32, 2, 7, 16)
	(30, 6, 4, 1)		(31, 6)		(31, 7)
	(31, 13)		(31, 25, 23, 8)		(33, 13)
	(35, 2)		(47, 5)		(48, 9, 7, 4)
	(47, 11, 24, 32)		(46, 18, 31, 40)		(53, 6, 2, 1)
	(55, 24)		(57, 7)		(58, 19)
	(59, 7, 4, 2)		(41, 27, 31, 32)		(61, 5, 2, 1)
	(42, 30, 31, 34)		(51, 15, 24, 46)		(50, 17, 31, 34)

Изначально LFSR были разработаны для аппаратной реализации в виде набора цифровых схем. Программные реализации LFSR обычно проигрывают по скорости аппаратным. Для увеличения быстродействия состояние регистра выгодно хранить в виде целого L -разрядного числа, отдельные биты которого соответствуют двоичным разрядам регистра. Тогда для доступа к отдельным битам используются поразрядные операции (сдвиг, маскирование и т.д.).

Сдвиговый регистр с обратной связью ( FSR ) состоит из двух частей: сдвигового регистра и функции обратной связи .

Сдвиговый регистр (Error: Reference source not found) представляет собой последовательность битов. Когда нужно извлечь бит, все биты сдвигового регистра сдвигаются вправо на 1 позицию. Новый крайний левый бит является значением функции обратной связи от остальных битов регистра. Периодом сдвигового регистра называется длина получаемой последовательности до начала её повторения.

Простейшим видом сдвигового регистра с обратной связью является линейный сдвиговый регистр с обратной связью (LFSR – Left Feedback Shift Register ) (Error: Reference source not found). Обратная связь представляет собой простоXORнекоторых битов регистра, перечень этих битов называетсяотводной последовательностью .

n -битовыйLFSRможет находиться в одном из2 n -1 внутренних состояний. Это означает, что теоретически такой регистр может генерировать псевдослучайную последовательность с периодом2 n -1 битов. Число внутренних состояний и период равны, потому что заполнение регистра нулями приведет к тому, что он будет выдавать бесконечную последовательность нулей, что абсолютно бесполезно. Только при определенных отводных последовательностяхLFSRциклически пройдет через все2 n -1 внутренних состояний. ТакиеLFSRназываютсяLFSR с максимальным периодом .

Для того чтобы конкретный LFSRимел максимальный период, многочлен, образованный из отводной последовательности и константы1 должен быть примитивным по модулю2 .

Вычисление примитивности многочлена – достаточно сложная математическая задача. Поэтому существуют готовые таблицы, в которых приведены номера отводных последовательностей, обеспечивающих максимальный период генератора. Например, для 32-х битового сдвигового регистра можно найти такую запись: (32,7,5,3,2,1,0) . Это означает, что для генерации нового бита необходимо с помощью функцииXORпросуммировать тридцать второй, седьмой, пятый, третий, второй, и первый биты.

Код для такого LFSRна языке С++ будет таким:

// Любое значение кроме нуля

ShiftRegister = ((((ShiftRegister >> 31)

^ (ShiftRegister >> 6)

^ (ShiftRegister >> 4)

^ (ShiftRegister >> 2)

^ (ShiftRegister >> 1)

^ ShiftRegister)

& 0x00000001) <<31)

| (ShiftRegister >> 1);

return ShiftRegister & 0x00000001;

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

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

Эту модификацию называют конфигурацией Галуа . На языке С это выглядит следующим образом:

static unsigned long ShiftRegister = 1;

void seed_LFSR (unsigned long seed)

ShiftRegister = seed;

int Galua_LFSR (void)

if (ShiftRegister & 0x00000001) {

ShiftRegister = (ShiftRegister ^ mask >> 1) | 0x8000000;

ShiftRegister >>= 1;

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

Сами по себе LFSRявляются хорошими генераторами псевдослучайных последовательностей, но они обладают некоторыми нежелательными неслучайными свойствами. Последовательные биты линейны, что делает их бесполезными для шифрования. ДляLFSRдлиныn внутреннее состояние представляет собой предыдущиеn выходных битов генератора. Даже если схема обратной связи хранится в секрете, то она может быть определена по2 n выходным битам генератора при помощи специальных алгоритмов. Кроме того, большие случайные числа, генерируемые с использованием идущих подряд битов этой последовательности, сильно коррелированны и для некоторых типов приложений не являются случайными. Несмотря на это,LFSRчасто используются для создания алгоритмов шифрования. Для этого используются несколькоLFSR, обычно с различными длинами и номерами отводных последовательностей. Ключ является начальным состоянием регистров. Каждый раз, когда необходим новый бит, все регистры сдвигаются. Эта операция называетсятактированием . Бит выхода представляет собой функцию, желательно нелинейную, некоторых битовLFSR. Эта функция называетсякомбинирующей , а генератор в целом –комбинирующим генератором . Многие из таких генераторов безопасны до сих пор.

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

Описание

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

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

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

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

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

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

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

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

Рассмотрим 32-битовый сдвиговый регистр. Для него имеется отводная последовательность (32 , 31 , 30 , 28 , 26 , 1) {\displaystyle \left(32,\;31,\;30,\;28,\;26,\;1\right)} . Это означает, что для генерации нового бита необходимо с помощью операции 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 посредством распараллеливания можно выполнить за одно действие, а не последовательно одна за другой, как в конфигурации Фибоначчи. Данная схема также даст выигрыш при аппаратной реализации.

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

int LFSR_Galois (void ) { 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).

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

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

Пусть РСЛОС задаётся характеристическим многочленом 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 , 0 , 1 ] {\displaystyle \left}	1
1		0
2		0
3		1
4		1
5		1
6		0
7	[ 0 , 0 , 1 ] {\displaystyle \left}	1

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

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

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

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

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

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

Биты, n {\displaystyle n}	Примитивный многочлен	Период, 2 n − 1 {\displaystyle 2^{n}-1}	Число примитивных многочленов
2	x 2 + x + 1 {\displaystyle x^{2}+x+1}	3	1
3	x 3 + x 2 + 1 {\displaystyle x^{3}+x^{2}+1}	7	2
4	x 4 + x 3 + 1 {\displaystyle x^{4}+x^{3}+1}	15	2
5	x 5 + x 3 + 1 {\displaystyle x^{5}+x^{3}+1}	31	6
6	x 6 + x 5 + 1 {\displaystyle x^{6}+x^{5}+1}	63	6
7	x 7 + x 6 + 1 {\displaystyle x^{7}+x^{6}+1}	127	18
8	x 8 + x 6 + x 5 + x 4 + 1 {\displaystyle x^{8}+x^{6}+x^{5}+x^{4}+1}	255	16
9	x 9 + x 5 + 1 {\displaystyle x^{9}+x^{5}+1}	511	48
10	x 10 + x 7 + 1 {\displaystyle x^{10}+x^{7}+1}	1023	60
11	x 11 + x 9 + 1 {\displaystyle x^{11}+x^{9}+1}	2047	176
12	x 12 + x 11 + x 10 + x 4 + 1 {\displaystyle x^{12}+x^{11}+x^{10}+x^{4}+1}	4095	144
13	x 13 + x 12 + x 11 + x 8 + 1 {\displaystyle x^{13}+x^{12}+x^{11}+x^{8}+1}	8191	630
14	x 14 + x 13 + x 12 + x 2 + 1 {\displaystyle x^{14}+x^{13}+x^{12}+x^{2}+1}	16383	756
15	x 15 + x 14 + 1 {\displaystyle x^{15}+x^{14}+1}	32767	1800
16	x 16 + x 14 + x 13 + x 11 + 1 {\displaystyle x^{16}+x^{14}+x^{13}+x^{11}+1}	65535	2048
17	x 17 + x 14 + 1 {\displaystyle x^{17}+x^{14}+1}	131071	7710
18	x 18 + x 11 + 1 {\displaystyle x^{18}+x^{11}+1}	262143	7776
19	x 19 + x 18 + x 17 + x 14 + 1 {\displaystyle x^{19}+x^{18}+x^{17}+x^{14}+1}	524287	27594
20 - 168
2 - 786, 1024, 2048, 4096

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

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

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

Недостатки

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

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

Генератор такого типа состоит из нескольких регистров сдвига с линейной обратной связью, которые генерируют биты 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 меняет своё состояние в некоторый момент времени , только если выход РСЛОС-1 в момент времени был равен единице. Данная схема не устояла перед корреляционным вскрытием .

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

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

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

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

Данный генератор использует два регистра сдвига РСЛОС-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 ), когда

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

Сдвиговый регистр с обратной связью состоит из двух частей: сдвигового регистра и функции обратной связи (рисунок 1.2.1). Сдвиговый регистр представляет собой последовательность битов. (Количество битов определяется длиной сдвигового регистра. Если длина равна n битам, то регистр называется n-битовым сдвиговым регистром.) Всякий раз, когда нужно извлечь бит, все биты сдвигового регистра сдвигаются вправо на 1 позицию. Новый крайний левый бит является функцией всех остальных битов регистра. На выходе сдвигового регистра оказывается один, обычно младший значащий, бит. Периодом сдвигового регистра называется длина получаемой последовательности до начала ее повторения.

Рис. 1.2.1.

Криптографам нравились потоковые шифры на базе сдвиговых регистров: они легко реализовывались с помощью цифровой аппаратуры. Я лишь слегка затрону математическую теорию. В 1965 году Эрнст Селмер (Ernst Selmer), главный криптограф норвежского правительства, разработал теорию последовательности сдвиговых регистров. Соломон Голомб (Solomon Golomb), математик NSA, написал книгу, излагающие некоторые свои результаты и результаты Селмера.

Простейшим видом сдвигового регистра с обратной связью является линейный сдвиговый регистр с обратной связью (linear feedback shift register, или LFSR) (рисунок 1.2.2). Обратная связь представляет собой просто XOR некоторых битов регистра, перечень этих битов называется отводной последовательностью (tap sequence). Иногда такой регистр называется конфигурацией Фиббоначи. Из-за простоты последовательности обратной связи для анализа LFSR можно использовать довольно развитую математическую теорию. Криптографы любят анализировать последовательности, убеждая себя, что эти последовательности достаточно случайны, чтобы быть безопасными. LFSR чаще других сдвиговых регистров используются в криптографии.

Рис. 1.2.2.

На Рис. 1.2.3 показан 4-битовый LFSR с отводом от первого и четвертого битов. Если его проинициализировать значением 1111, то до повторения регистр будет принимать следующие внутренние состояния:

Рис. 1.2.3. 4

Выходной последовательностью будет строка младших значащих битов:

1 1 1 1 0 1 0 1 1 0 0 1 0 0 0....

n-битовый LFSR может находиться в одном из 2n-1 внутренних состояний. Это означает, что теоретически такой регистр может генерировать псевдослучайную последовательность с периодом 2n-1 битов. (Число внутренних состояний и период равны 2n-1, потому что заполнение LFSR нулями, приведет к тому, что сдвиговый регистр будет выдавать бесконечную последовательность нулей, что абсолютно бесполезно.) Только при определенных отводных последовательностях LFSR циклически пройдет через все 2n-1 внутренних состояний, такие LFSR являются LFSR с максимальным периодом. Получившийся результат называется М-последовательностью.

Для того, чтобы конкретный LFSR имел максимальный период, многочлен, образованный из отводной последовательности и константы 1, должен быть примитивным по модулю 2. Степень многочлена является длиной сдвигового регистра. Примитивный многочлен степени n - это неприводимый многочлен, который является делителем, но не является делителем xd+1 для всех d, являющихся делителями 2n-1.

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

Некоторые, но, конечно же, не все, многочлены различных степеней, примитивные по модулю 2. Например, запись (32, 7, 5, 3, 2, 1, 0) означает, что следующий многочлен примитивен по модулю 2:

x32 + x7 +x5 + x3 + x2 + x + 1

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

Продолжая пример, запись (32, 7, 5, 3, 2, 1, 0) означает, что для взятого 32-битового сдвигового регистра новый бит новый бит генерируется с помощью XOR тридцать второго, седьмого, пятого, третьего, второго и первого битов получающийся LFSR будет иметь максимальную длину, циклически проходя до повторения через 232-1 значений.