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