9. Аддитивные потоковые шифры

Потоковое шифрование на основе генераторов псевдослучайных последовательностей (ГПСП) реализуется с помощью схемы, представленной на рис. 7, где ГПСП служит датчиком шифрующей гаммы .

Потоковые шифры имеют следующие преимущества перед блоковыми:

• проще аппаратная реализация,

• высокая скорость шифрования,

• отсутствует размножение ошибок, возникающих в каналах связи.

Эти преимущества привели к тому, что потоковые шифры получили наибольшее распространение при шифровании оцифрованных речевых сигналов и цифровых данных, требующих оперативной доставки информации потребителю. Наиболее типичном примером использования потоковых шифров является защита информации в сетях GSM.

Датчики гаммы весьма разнообразны. Во многих потоковых шифрах в качестве датчиков гаммы применяется хорошо известный из различных технических приложений рекуррентный метод формирования псевдослучайных последовательностей с помощью так называемого линейного рекуррентного регистра сдвига с обратными связями (ЛРР).

Схема аппаратной реализации линейного рекуррентного регистра сдвига с обратными связями через отводы показана на рис. 13.

Рис. 13. Линейный рекуррентный регистр сдвига с обратными связями

Индивидуальные свойства ЛРР определяет двоичная последовательность множителей h₀,h₁,..., h_n , гдеh₀=h_n = 1. Поскольку среди элементов последовательности некоторые имеют нулевые значения, отводы оказываются подключенными не ко всем сумматорам, а только к тем, которым соответствуютh_i= 1. Текущее состояние ЛРР определяется конкретным заполнением всех ячеек памяти a₀, a₁,..., a_n–1 .

Перед пуском производится заполнение ячеек ЛРР элементами начальной двоичной последовательности.

Под действием каждого поступающего тактового импульса вычисляется по модулю 2 сумма: a₀ + h₁a₁ + h₂a₂ +…+ h _n–1a _n–1 , и происходит сдвиг содержимого всех ячеек в сторону выхода. Шаг сдвига – одна ячейка. Освободившаяся ячейка с номером n –1 заполняется найденной суммой, а содержимое ячейки с нулевым номеромa₀покидает регистр и становится очередным символовb_jвыходной последовательности.По окончанию следующего такта на выходе появится содержимое предыдущей ячейкиa₁в качестве символаb_j+1и т.д.

Каждому ЛРР можно сопоставить полином обратной связи

h(x) =xⁿ+h_n–1 x^n–1+h_n–2 x^n–2+ ... +h₁ x+ 1

с двоичными коэффициентами h_i, где h₀=h_n = 1. Верно и обратное, по заданному степенному полиномуh(x) всегда можно построить ЛРР. Например, полиномуh(x) =x⁴+x+ 1 соответствует линейный рекуррентный регистр сдвига из четырех ячеек памяти (n = 4), приведенный на рис. 14.

10. 

    Рис. 14. ЛРР, соответствующий полиному h(x) = x⁴ + x +1

    Свойства линейных рекуррентных регистров

Линейный рекуррентный регистр сдвига длиною nимеет следующие основные свойства:

Период Tвыходной последовательности из символовb_j при любом начальном заполнении ячеек памяти ограничен неравенствомT2ⁿ– 1.

Период Tвыходной последовательности максимален, т.е. определяется равенствомT= 2ⁿ – 1, при любом начальном заполнении тогда и только тогда, когда полином обратной связиh(x) является примитивным полиномом.

Выходная последовательность линейного рекуррентного регистра сдвига, реализованного на примитивном полиноме, обладает свойствами «баланса» и «окна». Свойство «баланса» состоит в том, что число нулей на периоде T= 2ⁿ– 1 точно равно 2^n – 1– 1, тогда как число единиц равно 2^n – 1. Свойство «окна» гарантирует, что во всех 2^n – 1 «окнах» изnсимволов, последовательно расположенных на периоде, все возможные 2^n – 1 ненулевые двоичные последовательности появятся только по одному разу.

Определение. Полиномh(x) степениnc двоичными коэффициентами называется примитивным, если он

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

• делит полином без остатка, но не делит без остатка ни один полином видапри любом.

Пример примитивного полинома – полином x⁴+x+1. Полиномx²+1 примитивным не является.

Полином x⁴+x+1 делитx¹⁵+1, поскольку

x¹⁵+1 = (x⁴+x+1)(x¹¹+x⁸+x⁷+x⁵+x³+x²+x+1).

Из данных соотношений видно, что при больших значениях степени nчисло примитивных полиномов весьма велико. В настоящее время имеются подробные таблицы примитивных полиномов, в том числе и больших степеней. Имеются также алгоритмы, которые позволяют проверить, является ли случайно сгенерированный полином, даже весьма высокой степени, примитивным. Таким образом, не существует проблемы выбора примитивного полинома обратной связиh(x) для ЛРР достаточно большой длины n, т.е. такого полинома, который обеспечит достаточно большой период выходной последовательностиT= 2ⁿ – 1 при любом начальном заполнении. Отметим, что с целью сокращения числа отводов в конструкции ЛРР среди примитивных полиномов данной степени используют полиномы с наименьшим числом ненулевых коэффициентов

Перечисленные свойства ЛРР, а также некоторые другие, приводят к тому, что последовательность символов на выходе ЛРР может быть принята за чисто случайную. Она практически не отличается от последовательностей, получаемых при бросании симметричной монеты. Однако в действительности выходная последовательность ЛРР является строго детерминированной. Она однозначно задается начальным заполнением a_j{0,1},j= 0, 1,...,n – 1, и полиномом обратной связиh(x), в силу чего ее называютпсевдослучайной последовательностью(ПСП).