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

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

, (2.6)

, (2.7)

, (2.8)

, (2.9)

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

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

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

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

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

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

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

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

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

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

Перейти на страницу: 1 2 3 4 5 6

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

Моделирование радиомаячной системы посадки метрового диапазона с помощью программы Micro-Cap
Функциональные возможности использования авиации во многом определяются качеством решения задач навигации, в частности, уровнем развития устройств и систем радионавигации. Под термино ...

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

Обучающая подсистема для лабораторного исследования характеристик замкнутых САУ в среде интернет
В последние десятилетия в зарубежных системах образования произошли существенные изменения, обусловленные бурным развитием научно-технического прогресса и его воздейст ...

Основные разделы

Все права защищены! (с)2020 - www.generallytech.ru