Линейные рекуррентные генераторы

Каждый элемент таблицы 2.1 определяет два примитивных полинома, поскольку если примитивен ,то примитивен и Например, если примитивен, то примитивен и , или если примитивен, то примитивен и . Математически, если примитивен

, (2.6)

, (2.7)

, (2.8)

, (2.9)

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

Регистры Галуа

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

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

Рисунок 2.6 - Регистр Галуа

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

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

Подводя общий итог, можно сказать, что если используется элементная база с быстрой реализацией сдвигов, то следует обратиться к регистрам Фибоначчи; если же есть возможность применить распараллеливание, то лучший выбор - регистр Галуа.

Но, несмотря на то, как бы хорошо не был подобран полином обратной связи, регистр сдвига с обратной связью (LFSR) остается линейным устройством. А такие устройства обычно легко поддаются криптоанализу независимо от того, насколько много параметров сохраняется в тайне. В современной криптографической литературе регистры сдвига с линейной обратной связью, как и линейные конгруэнтные генераторы, сами по себе не рекомендуются в качестве генераторов псевдослучайных шифрующих последовательностей.

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

Читайте также

Проектирование устройства автоматической компенсации доплеровской частоты для СДЦ РЛС 5Н84А
Широкое применение радиолокационной техники в военных целях (воздушная и наземная разведки, навигация, вывод на траекторию ракет различного назначения) вызвало в последние годы бурное р ...

Поверка электронного вольтметра В7-26 по напряжению постоянного тока
Считается, что первый вольтметр изобрел М. Фарадей, причем в 1830 году, ещё за год до того, как он же открыл явление электромагнитной индукции, на котором основано действие целого класса ...

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