Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


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




Большинство реальных поточных шифров основано на регистрах сдвига с обратной связью. Регистр сдвига применяют для генерации ключевой последовательности. Регистр сдвига с обратной связью состоит из двух частей: регистра сдвига и функции обратной связи (рис. 4).

Рис.4. Общая схема

 

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

Простейшим видом регистра сдвига с обратной связью является регистр сдвига с линейной обратной связью, РСЛОС (Linear Feedback Shift Register, LFSR). Обратная связь представляет собой XOR некоторых битов регистра; эти биты называются отводной последовательностью.

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

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

В качестве примера метода, рассмотрим 4-х битовый LFSR с отводом от первого и четвёртого битов:

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

№ такта Состояние регистров Выходной бит
-

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

 


Поделиться:

Дата добавления: 2015-01-19; просмотров: 104; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.005 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты