ki

					f
											ui
					…

Рис. 2.23. Фильтрующий генератор Ключом соответствующего поточного шифра является начальное заполнение регистра,

реже – начальное заполнение и функция обратных связей.

Результат работы фильтрующего генератора можно представить в виде ki f ui1 ,ui2 , ,uin ,

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

uij – состояние j-ой ячейки LFSR.

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

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

Фильтрующий генератор можно рассматривать как частный случай комбинирующего генератора, у которого все LFSR одинаковы, а начальное состояние LFSR-i совпадает с состоянием LFSR-1 на i-ом такте работы. Но, поскольку криптоанализ этих схем несколько различается, принято рассматривать эти схемы как два различных типа генераторов ключевого потока.

Примерами комбинирующего генератора являются: генератор Геффе и генератор Дженнингса. Примером фильтрующего генератора является алгоритм N),ключи).Вanoteq.

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

Как уже говорилось выше, регистр сдвига с обратной связью состоит из двух частей: регистра сдвига и функции обратной связи. В качестве функции обратной связи выступает

174

любая булева функция f от n переменных. В случае, когда функция обратной связи f линейна, регистр сдвига называется регистром сдвига с линейной обратной связью (LFSR), в противном случае – регистром сдвига с нелинейной обратной связью (non-linear feedback shift register, N),ключи).ВLFSR).

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

Регистр сдвига с обратной связью по переносу (feedback with carry shift register, FCSR) напоминает LFSR [4]. В обоих используется регистр сдвига и функция обратной связи, но в FCSR дополнительно предусмотрен еще и регистр переноса (рисунок 8).

m div 2	mod 2 bn–1	bn–2	…	b1	b0
	c1	c2		cn–1	cn

Рисунок 2.24. Регистр сдвига FCSR

На рисунке 2.24 знак означает целочисленное сложение. Содержимое регистра сдвига состоит из n бит, обозначенных bn–1, bn–2, …, b1, b0.

Работа FCSR описывается следующим образом [6]:

n

1. Вычисляется сумма n ck bn k m .

k 1

2.Содержимое регистра сдвигается на одну позицию вправо. Содержимое крайней правой ячейки FCSR b0 поступает на выход.

3.Рассчитывается новое содержимое крайней левой ячейки bn–1 = n (mod

2).

			m	n an	n
	4.	В регистр переноса записывается новое значение					.
				2		2

Регистром переноса служит число, а не бит. Размер регистра переноса должен быть не менее log2t, где t – количество отводов. Например, если отвода два, то регистр переноса однобитовый, а если отводов четыре, то регистр переноса должен состоять из 2 бит.

Максимальный период последовательности, генерируемой FCSR, равен (c – 1), где c – число обратной связи (connection integer) FCSR. Число c определяется отводами обратной связи:

175