Шифрование текстовых файлов на основе линейных

Сдвиговых регистров с обратной связью.

Цель работы: Изучить принципы работы линейного сдвигового регистра с обратной связью (ЛРОС) и организацию шифрования на их основе

Задание на лабораторную работу:

1. Изучить теоретический материал по принципам построения и работы ОРОС,
2. Разработать программу на языке VBA в Excel, моделирующую работу ЛРОС,
3. Выполнить шифрование/ расшифровку произвольного файла с использованием этой программы. Для шифрования выбрать неприводимый многочлен степени не ниже 16. Шифрование выполнять побитно над словами длины 2 байта.
4. Ответить на контрольные вопросы в конце задания.

ТЕОРЕТИЧЕСКИЙ МАТЕРИАЛ.

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

Сдвиговый регистр с обратной связью состоит из двух частей: сдвигового регистра и функции обратной связи. Сдвиговый регистр представляет собой последовательность битов фиксированной длины. Число битов называется длиной сдвигового регистра. Функция обратной связи является булевой функцией из множества L-мерных векторов с координатами из множества {0, 1} в множество {0, 1}, L – длина сдвигового регистра. В начальный момент работы сдвиговый регистр заполняется некоторым начальным значением. На каждом последующем шаге вычисляется значение , где x_i – значение ячейки с номером s_i, содержимое регистра сдвигается вправо, а в освободившееся место помещается значение y.

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

Простейшим видом сдвигового регистра с обратной связью является линейный сдвиговый регистр с обратной связью (linear feedback shift register LFSR). Функция обратной связи является в этом случае просто суммой по модулю 2 нескольких фиксированных разрядов .

Пример. Рассмотрим линейный сдвиговый регистр R длины L=4 и функцией обратной связи (отвод от первого и четвертого вывода).

Пусть исходное значение регистра равно <1,1,1,1>, тогда этот регистр будет порождать следующую последовательность

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

Последовательность максимальной длины называется M-последовательностью. Не всякий регистр LFSR может обладать такой последовательностью. Проблема определения по заданному регистру LFSR, будет ли он обладать M-последовательностью, является нетривиальной. Для ее решения сопоставим произвольному регистру LFSR длины L следующий многочлен (*), где коэффициент принимает значение 1 или 0 в зависимости от того, присутствует ли соответствующее слагаемое в функции обратной связи. Например, регистру LFSR в рассмотренном выше примере соответствует многочлен .

Теорема. Произвольный LFSR регистр обладает M-последовательностью тогда и только тогда, когда соответствующий многочлен является неприводимым (неразложимым) над полем F₂={0, 1}.

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

В общем случае, нет простого способа генерировать многочлены заданной степени по модулю 2, однако можно легко проверить, является ли заданный многочлен приводимым или нет над заданным конечным полем. Для этого используется алгоритм Берлекампа (Berlekamp) (см. Лидл, Нидеррайтер[7], т.1, гл.3.). В следующем разделе мы рассмотрим упрощенную ыерсию алгоритма Берленкамфа.