поточный шифр, а в режиме гаммирования с обратной связью – как самосинхронизирующийся.

Строительные блоки поточных шифров

Рассмотрим основные блоки, используемые для построения поточных шифров.

Регистры сдвига с обратной связью

Большинство предложенных до настоящего времени алгоритмов поточного шифрования так или иначе основаны на использовании регистров сдвига с обратной связью.

Регистр сдвига с обратной связью (feedback shift register, FSR) состоит из двух частей: регистра сдвига и функции обратной связи (рисунок 3). Регистр сдвига представляет собой последовательность битов. Длина регистра сдвига выражается числом битов. Если длина регистра равна n битам, регистр называют n-битовым регистром сдвига. При каждом извлечении бита все биты регистра сдвига сдвигаются вправо на 1 позицию. Новый старший бит рассчитывается как функция от всех остальных битов регистра. На выходе регистра сдвига оказывается 1 бит [4, 6].

bn–1

bn–2

bn–3

…

b2

b1

b0

Функция обратной связи

Рис. 2.19. Регистр сдвига с обратной связью

Регистры сдвига с линейной обратной связью

К простейшему типу FSR относится регистр сдвига с линейной обратной связью (linear feedback shift register, LFSR) [4]. Подавляющее большинство предложенных до настоящего времени генераторов поточного шифрования так или иначе основано на LFSR.

На это существует несколько причин:

LFSR хорошо подходят для аппаратной реализации;

LFST могут производить последовательности большого периода;

LFSR могут производить последовательности с хорошими статистическими свойствами;

LFSR могут быть легко проанализированы с помощью алгебраических

техник.

LFSR длины n состоит из n элементов задержки (ячеек) bn–1, bn–2, …, b1, b0, каждый из которых может хранить один бит и имеет по одному входу и выходу.

170

Исходной информацией для построения LFSR является образующий многочлен. Степень этого многочлена определяет разрядность регистра сдвига, а ненулевые коэффициенты – характер обратных связей (номера отводов сигналов обратной связи). В общем случае двоичный образующий многочлен степени n имеет вид [6]:

n

c(x) = ci xi = 1 + c1x + c2x2 + … + cn–1xn–1 + cnxn,

i 0

где cn = c0 = 1, cj {0, 1} для j = 1, …, (n – 1).

В общем случае двоичному образующему многочлену c(x) соответствует две схемы: Фибоначчи (рисунок 4) и Галуа (рисунок 2.20).

bn–1	bn–2	bn–3	…	b2		b1	b0
c0	c1	c2			cn–2	cn–1	cn

…

Рис. 2.20. LFSR, схема Фибоначчи

На каждом такте работы схемы Фибоначчи содержимое регистра сдвигается вправо на один бит, так что bi = bi+1 для i = 0, …, (n – 2), а содержимое 0-ой ячейки b0 поступает на выход LFSR. Новое содержимое (n – 1)-ой ячейки bi–1 рассчитывается как сумма по модулю 2 предыдущих состояний определенных ячеек

n 1

bn 1 cn i bi . i 0

При ci = 1 умножение на ci равносильно наличию обратной связи, при ci = 0 – отсутствию.

Схема Галуа представлена на рисунке 2.21.

bn–1	bn–2	…	b1		b0
c0	c1			cn–1	cn

…

171

Рис. 2.21. LFSR, схема Галуа

На каждом такте работы схемы Галуа содержимое регистра сдвига сдвигается вправо на 1 бит так, что bi = bi+1 b0cn–i, а содержимое 0-ой ячейки b0 поступает на выход LFSR и в (n – 1) ячейку регистра, т.е. bn–1 = b0.

n-битовый LFSR может находиться в одном из (2n – 1) внутренних состояний. Это значит, что теоретически такой регистр может генерировать псевдослучайную последовательность с периодом (2n – 1) битов. (Это число равно (2n – 1), а не 2n, поскольку заполнение LFSR нулями влечет вывод регистром бесконечной последовательности нулей, что совершенно бесполезно.) Только при определенных последовательностях отводов LFSR циклически пройдет через все 2n – 1 внутренних состояний. Такие регистры называются регистрами LFSR с максимальным периодом. Получившийся выход называют m- последовательностью.

Для обеспечения максимального периода конкретного LFSR, соответствующий многочлен, образованный из последовательности отводов регистра, должен быть примитивным по модулю 2. Степень многочлена является длиной регистра сдвига [4, 6].

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

Регистры LFSR сами по себе являются хорошими генераторами псевдослучайных последовательностей, но они обладают некоторыми нежелательными неслучайными свойствами. Последовательные биты линейны, что делает их бесполезными для шифрования. Внутреннее состояние LFSR длины n определяет следующие n выходных битов генератора. Даже если схема обратной связи хранится в секрете, она может быть определена по 2n выходным битам генератора с помощью высокоэффективного алгоритма Берлекампа-Мэсси [4]. В то же время подавляющее большинство реальных конструкций для поточного шифрования строится на основе LFSR [6].

Генераторы на основе LFSR

Поточные шифры на основе LFSR подразделяют на [4]:

системы с генератором с равномерным движением регистров;

системы с генератором с неравномерным движением регистров.

Вгенераторе с равномерным движением регистров каждый раз для получения нового

172

бита следует однократно сдвинуть LFSR. Выходной бит представляет собой функцию некоторых битов LFSR. Генераторы с равномерным движением в свою очередь делятся на

[4, 5]:

комбинирующий генератор;

фильтрующий генератор.

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

LFSR-1

ui1

…

f

LFSR-2

ui2

ki

…

…

uin

…

LFSR-n

Рис. 2.22. Комбинирующий генератор Ключом соответствующего поточного шифра является начальное заполнение каждого

регистра, реже – начальное заполнение и функции обратных связей. Результат работы комбинирующего генератора можно представить в виде ki f ui1 ,ui2 , ,uin ,

где ki – i-ый бит ключевого потока, производимого генератором; n – количество LFSR;

uij – i-ый бит, генерируемый j-ым LFSR.

Фильтрующий генератор (рисунок 2.23) состоит из одного LFSR. Для генерации ключевого потока используется нелинейная функция f, на вход которой подаются значения некоторых ячеек LFSR. Функция f в этом случае называется фильтрующей функцией.

173