LFSR (Linear-Feedback Shift Register)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 14:01, 12 июня 2016.

Достоинства LFSR

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

Однородный LFSR

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

FSR 123.png

Тогда знак выходной последовательности вычисляется по формуле:

для всех

Соотношение можно записать в виде:

которое выполняется для всех , или, еще короче:

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

TemplateDifinitionIcon.svg Определение «Определение - Линейная рекуррента»
Бесконечная последовательность элементов поля удовлетворяющих соотношению для всех называется линейной однородной рекуррентной последовательностью степени над полем
TemplateDifinitionIcon.svg Определение «Определение - Линейная рекуррента»
Бесконечная последовательность элементов поля удовлетворяющих соотношению для всех называется линейной неоднородной рекуррентной последовательностью степени над полем

Неоднородный LFSR

Рассмотрим линейную неоднородную последовательность степени удовлетворяющую соотношению . Для неё

Тогда вычитая равенство из равенства , получаем:

или


Таким образом, мы видим, что в действительности эта последовательность является однородной линейной рекуррентной последовательностью степени с характеристическим многочленом :

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

Характеристический многочлен

TemplateDifinitionIcon.svg Определение «Определение - Характеристический многочлен»
Многочлен вида называется характеристическим многочленом линейной рекуррентной последовательности


В общем виде


Каждому LFSR сопоставим однозначно определенный многочлен вида

где коэффициенты из функции обратной связи

Многочлен называется характеристическим многочленом LFSR


TemplateDifinitionIcon.svg Определение «Определение - Формальный степенной ряд»
Пусть дана любая последовательность (конечная или бесконечная) элементов поля С этой последовательностью можно связать формальный степенной ряд, т.е. выражение вида


где - формальная переменная.

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

На множестве формальных степенных рядов можно задать операции сложения и умножения. Если:

то

где

где

Вычисление периода LFSR

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

,

где – квадратная матрица вида:

TemplateLemmaIcon.svg Лемма «Лемма»
Вектор внутреннего состояния LFSR выражается формулой , где – вектор начального состояния LFSR.


Доказательство. С очевидностью следует из соотношения (1).

TemplateTheoremIcon.svg Теорема Теорема
Последовательность внутренних состояний не сингулярного LFSR является чисто периодической последовательностью. Ее период совпадает с порядком матрицы вида (2) как элемента группы – группы невырожденных L×L матриц над полем . Выходная последовательность LFSR также является чисто периодической последовательностью. Ее период делит период последовательности внутренних состояний LFSR.
Доказательство

Так как , то , т.е. является элементом группы . Так как группа – конечна, то порядок матрицы конечен, более того, он делит порядок группы . Пусть порядок равен , т.е. и – минимальное натуральное число, для которого выполняется это равенство. Тогда в силу равенства (1), последовательность внутренних состояний является чисто периодической последовательностью: длялюбого

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


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

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

TemplateDifinitionIcon.svg Определение «Определение»
Ганкелевой - матрицей, связанной с последовательностью , назовем матрицу вида:

где .

Пусть . Ганкелевой - системой линейных уравнений, связанной с последовательностью , назовем систему линейных уравнений вида:

Заметим, что матрицей ганкелевой -системы является Ганкелева матрица , а ее расширенной матрицей – ганкелева матрица .

TemplateLemmaIcon.svg Лемма «Лемма 1»
Последовательность порождается LFSR длины , то- гда и только тогда, когда соответствующая ганкелева -система (2) является совместной.


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

Следствие. Если ганкелева - система, связанная с последовательностью , является несовместной, то длина кратчайшего LFSR, порождающего эту последовательность, строго больше, чем .

Рассмотрим последовательность , и соответствующую ей квадратную ганкелеву матрицу размера k × k.

TemplateLemmaIcon.svg Лемма «Лемма 2»
Если ранг матрицы не уменьшается при отбрасывании последнего столбца, то последовательность можно получить с помощью LFSR длины не более, чем . Обратно, если последовательность можно получить с помощью LFSR длины не более, чем , то при отбрасывании последнего столбца матрицы ее ранг не изменяется.


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

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

TemplateLemmaIcon.svg Лемма «Лемма 3»
Если ранг матрицы не уменьшается при отбрасывании последнего столбца, то ранг матрицы равен рангу матрицы :
.


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

Заметим, что матрицы определяют последовательные главные миноры матрицы .

TemplateLemmaIcon.svg Лемма «Лемма 4»
Если LFSR длины является кратчайшим LFSR для последовательности длины или больше, то этот кратчайший LFSR определен однозначно.


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

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

TemplateLemmaIcon.svg Лемма «Лемма 5»
Если LFSR длины является кратчайшим LFSR для последовательности длины , то этот же регистр является единственным кратчайшим для последовательности , при всех , где последовательность образована первыми знаками последовательности .


Доказательство. Аналогично доказательству предыдущей леммы, предположим, что для последовательности найдется другой кратчайший регистр. Сопоставим выходным последовательностям, порожденным этими регистрами, соответствующие степенные ряды: , .

Тогда , , при этом , и по крайней мере первые слагаемых в рядах и – совпадают. Так как , то аналогично лемме 4 получаем: , где – некоторый ненулевой ряд.

Соотношения между степенями многочленов и ряда приводят к такому же, как и в лемме 4 противоречию.

TemplateTheoremIcon.svg Теорема Теорема 1
Если LFSR длины является кратчайшим LFSR для последовательности длины , то ганкелева матрица является невырожденной.
Доказательство
LFSR длины полностью определяется своими коэффициентами обратной связи . По лемме 5 этот же регистр является единственным кратчайшим регистром для последовательности . Таким образом, коэффициенты являются решением ганкелевой -системы линейных уравнений, определяемых последовательностью . Матрица этой системы равна . Если бы матрица была вырожденной, ганкелева -система допускала бы несколько решений, что противоречит полученному в лемме 5 утверждению об однозначности кратчайшего регистра.


TemplateTheoremIcon.svg Теорема Теорема 2
Пусть дана конечная бинарная последовательность , и соответствующая ганкелева - система является совместной. Если – длина кратчайшего LFSR, порождающего данную последовательность, то . Более того, выполняются следующие соотношения для главных миноров матрицы :

.

Доказательство
Обозначим через длину кратчайшего LFSR, порождающего данную последовательность. Так как соответствующая ганкелева -система является совместной, по лемме 1 получаем, что . Тогда по теореме 1, учитывая, что , получаем:. Так как кратчайший LFSR длины порождает всю последовательность , получаем, что каждый столбец матрицы начиная с –го является линейной комбинацией предыдущих столбцов, откуда следуют указанные соотношения для миноров матрицы и ее ранга.


TemplateTheoremIcon.svg Теорема Теорема 3
Пусть дана конечная бинарная последовательность , и соответствующая ганкелева -система является совместной. Тогда
  • Если – длина кратчайшего LFSR, порождающего данную последовательность, и , то .
  • Если , то .
Доказательство
Доказательство. Если – длина кратчайшего LFSR, порождающего данную последовательность, и , то в матрице каждый столбец, начиная с –го, будет равен линейной комбинации стоящих перед ним столбцов. В то же время по теореме 1 матрица является невырожденной, откуда следует, что . Аналогичные рассуждения справедливы и для матрицы . Пусть кратчайший LFSR, порождающий последовательность , в качестве следующего знака вырабатывает знак . Тогда этот же LFSR будет кратчайшим LFSR для последовательности . По теореме 1 матрица будет невырожденной, т.е. , а тогда ранг матрицы будет на единицу меньше.