Общие сведения о регистрах сдвига с линейной обратной связью

Введение

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

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

Общие сведения о регистрах сдвига с линейной обратной связью

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

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

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

Регистры сдвига очень быстро нашли применение в потоковых шифрах, так как они легко реализовывались с помощью цифровой аппаратуры. В 1965 году Эрнст Селмер (ErnstSelmer), главный криптограф норвежского правительства, разработал теорию последовательности регистров сдвига [3]. Соломон Голомб (SolomonGolomb), математик NSA, написал книгу, излагающие некоторые свои результаты и результаты Селмера [7]. Простейшим видом регистра сдвига с обратной связью является регистр сдвига с линейной обратной связью (linearfeedbackshiftregister, далее LFSR или РгСсЛОС). Обратная связь таких регистров представляет собой просто XOR (сложение по модулю два) некоторых битов регистра, перечень этих битов называется отводной последовательностью (tapsequence). Иногда такой регистр называется конфигурацией Фиббоначи. Из-за простоты последовательности обратной связи для анализа РгСсЛОС можно использовать довольно развитую математическую теорию. Проанализировав получаемые выходные последовательности, можно убедиться в том, что эти последовательности достаточно случайны, чтобы быть безопасными. РгСсЛОСчащедругихсдвиговыхрегистровиспользуются в криптографии.

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

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

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

Таблица1

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

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

a_nxⁿ+a_n-1x^n-1+…+a₁x¹+a₀x⁰=a_nxⁿ+a_n-1x^n-1+…+a₁x+a₀, гдеа_i={0,1} дляi=1…n, a xⁱ – указываетразряд.

2. Архитектура ПЛИС.