Каждый элемент таблицы 2.1 определяет два примитивных полинома, поскольку если примитивен ,то примитивен и
Например, если
примитивен, то примитивен и
, или если
примитивен, то примитивен и
. Математически, если примитивен
, (2.6)
, (2.7)
, (2.8)
, (2.9)
Следует отметить, что все полиномы обратной связи, приведенные в таблице 2.1, являются прореженными, то есть имеют лишь несколько ненулевых коэффициентов. Прореженность - это всегда источник слабости, облегчающей вскрытие такого алгоритма генерации. Для криптографических алгоритмов лучше использовать плотные примитивные многочлены. Генерировать плотные примитивные многочлены по модулю 2 нелегко. В общем случае для генерации примитивных многочленов степени нужно знать разложение на множители числа
.
Регистры Галуа
Схему обратной связи LFSR можно модифицировать. Получающийся генератор не будет криптографически более надежным, но он все еще будет обладать максимальным периодом, и его легче реализовать программно.
Вместо использования для генерации нового крайнего левого бита битов отводной последовательности выполняется XOR каждого бита отводной последовательности с выходом генератора и замена его результатом действия, затем результат генератора становится новым крайним левым битом.
Рисунок 2.6 - Регистр Галуа
Таким образом, в отличие от регистра Фибоначчи, где обратная связь является функцией от всех ячеек в регистре, а результат помещается в самую левую ячейку, обратная связь в регистре Галуа потенциально применима к каждой ячейке регистра, хотя является функцией только от самой правой ячейки. Выигрыш здесь в том, что все операции XOR можно выполнять как одну операцию.
Эту схему также можно распараллелить, а отдельные многочлены обратной связи могут быть различны. Кроме того, конфигурация Галуа может работать быстрее и при аппаратной реализации, особенно при использовании заказных VLSI-чипов.
Подводя общий итог, можно сказать, что если используется элементная база с быстрой реализацией сдвигов, то следует обратиться к регистрам Фибоначчи; если же есть возможность применить распараллеливание, то лучший выбор - регистр Галуа.
Но, несмотря на то, как бы хорошо не был подобран полином обратной связи, регистр сдвига с обратной связью (LFSR) остается линейным устройством. А такие устройства обычно легко поддаются криптоанализу независимо от того, насколько много параметров сохраняется в тайне. В современной криптографической литературе регистры сдвига с линейной обратной связью, как и линейные конгруэнтные генераторы, сами по себе не рекомендуются в качестве генераторов псевдослучайных шифрующих последовательностей.
В то же время, подавляющее большинство реальных конструкций для поточного шифрования (гаммирования) строится на основе LFSR. На заре радиоэлектроники их было легко производить, так как регистр сдвига - это просто массив бит памяти, а последовательность обратной связи - ряд XOR-вентилей. И даже на современной элементной базе VLSI-чипов поточный шифр на основе LFSR может давать весьма серьезную криптостойкость при помощи всего нескольких логических вентилей.
Читайте также
Оптоэлектронные технологии
Оптоэлектроника
- бурно развивающаяся область науки и техники. Многие ее достижения вошли в
быт: индикаторы, дисплеи, лазерные видеопроигрыватели. Разрабатывается
твердоте ...
Проект организации широкополосного доступа в коттеджном микрорайоне Чистопрудный г. Ижевска
Возможность в любое время в любом месте при любых условиях
иметь доступ к неограниченным информационным ресурсам становится для
современного человека одним из самых важных аспектов жизни ...
Проектирование РЭА
При конструкторском проектировании РЭА (радиоэлектронной
аппаратуры) решаются задачи, связанные с поиском наилучшего варианта
конструкции, удовлетворяющего требованиям технического задан ...