Поточный шифр F-FCSR-H

F-FCSR-H – аддитивный поточный шифр [5].

Для генерации ключевого потока из ключа длиной 80 бит и вектора инициализации длиной от 32 до 80 бит используется фильтрующий автомат FCSR.

Генерация ключевого потока

Воснове шифра F-FCSR-H лежит регистр сдвига с обратной связью по переносу (FCSR)

–автомат, который вычисляет двоичное разложение 2-адического числа p/q, где p и q – некоторые целые числа, с q нечетное. Допустим, что q < 0 < p < |q|. Размер FCSR n такой, что n + 1 является длиной q в битах.

Вданном шифре p зависит от секретного ключа (и IV), а q – открытый параметр. Выбор q порождает много свойств ключевого потока. Самое важное – то, что это полностью определяет длину периода ключевого потока. Условия для оптимального выбора:

q – (отрицательное) простое число размером (n + 1) бит.

(|q| − 1) – порядок 2 по модулю q.

T = (q – 1)/2 также является простым числом.

d = (1 + |q|)/2. W(d) – вес Хемминга двоичного разложения, W(d) > n/2. Автомат FCSR содержит два регистра (наборы ячеек): основной регистр M и регистр

переноса C. Основной регистр M содержит n ячеек. Обозначим mi (0 i n − 1) двоичные

n 1

знаки (n−1), содержащиеся в этих ячейках, и назовем числами m mi 2i содержимое (или

i 0

состояние) регистра M.

n 1

Пусть d – положительное целое число d = (1 − q)/2, а d di 2i его двоичное

i 0

разложение. Регистр переносов содержит l ячеек, где (l + 1) – количество чисел di отличных от нуля. Более строго, регистр переносов содержит одну ячейку для каждого ненулевого di, для 0 i (n − 2). Обозначим ci – двоичный знак, содержащийся в этой ячейке. Мы также

n 2

устанавливаем ci = 0 когда di = 0 или когда i = (n − 1). Назовем числом c ci 2i

i 0

содержимое (или состояние) регистра C. Вес Хемминга двоичного разложения c не больше, чем l. Функция перехода может быть описана выражениями

m(t + 1) = (m(t) >> 1) c(t) m0(t)d,

c(t + 1) = (m(t) >> 1) c(t) c(t) m0(t)d m0(t)d (m(t) >> 1).

190

Отметим, что m0(t) – самый младший бит в m(t). Числа m(t), c(t) и d – целые числа размером в n бит (или меньше).

Для извлечения псевдослучайных бит ключевого потока из основного регистра автомата FCSR используется фильтр. Этот фильтр описывает, какие ячейки выбраны для производства псевдослучайных битов. Чтобы получить мультиразрядный выход, используются восемь или шестнадцать одноразрядных фильтров, чтобы извлечь 8- или 16-битовые выходные слова после каждого перехода автомата.

n 1

Фильтр F – это битовая строка (f0, …, fn−1) длиной n (что эквивалентно числу fi 2i ).

i 0

Выходной бит z получается вычислением веса parity поразрядного И состояния M основного регистра и фильтра F:

n 1

z fi mi .

i 0

Это эквивалентно следующему:

S = M F, z = parity(S).

Аналогичным способом, предлагается метод извлечения s-битового слова из состояния FCSR. Значение s будет равно 8 для F-FCSR-H, и 16 для F-FCSR-16.

Фильтр F также является битовой строкой (f0, …, fn−1) длиной n (которая является кратной числу s). Он разбивает на s подфильтров F0, …, Fs−1 каждый определяется как

n s 1

Fj fsi j 2i . i 0

Каждый подфильтр Fj выбирает несколько ячеек mi в основном регистре среди тех, что удовлетворяют выражению i j mod s. Parity полученного двоичного слова дает j-й псевдослучайный бит:

ns 1

z j fsi j msi j . i 0

Так как есть s подфильтров, то мы получаем s битов при каждом переходе автомата.

Эта процедура может быть описана эквивалентно следующим образом. Фильтр F и состояние M комбинируются функцией И. Результат разбивается на n/s слова. Псевдослучайное слово получается операцией XOR этих n/s слов:

S = M F

n s 1

Определим Si с помощью выражения S Si 2si , для 0 Si 28 – 1.

i 0

191

Выходное слово z будет равно:

n s 1

zSi .

i 0

Отметим, что целое слово извлекается быстрее, чем отдельный бит.

Шифр F-FCSR-H использует ключи длиной 80 бит и IV размером от 32 до 80 бит. Если IV не используется, то по умолчанию можно использовать значение 0.

Длина FCSR (размер основного регистра) – n = 160. Регистр переносов содержит l = 82 ячейки. Обратное простое число

q = – 1993524591318275015328041611344215036460140087963

таким образом сложение полей и ячеек переносов присутствуют в позициях, соответствующих тем (кроме ведущего) в следующей строке 160 битов (которая имеет вес Хемминга 83),

d = (1 + |q|)/2 = (AE985DFF 26619FC5 8623DC8A AF46D590 3DD4254E)16. Фильтрация Чтобы извлечь один псевдослучайный байт, мы используем статический фильтр

F = d = (AE985DFF 26619FC5 8623DC8A AF46D590 3DD4254E)16

Фильтр F разбит на 8 подфильтров (подфильтр j получен выбором бита j в каждом байте

F),

F0 = (0011 0111 0100 1010 1010)2,

F1 = (1001 1010 1101 1100 0001)2,

F2 = (1011 1011 1010 1110 1111)2,

F3 = (1111 0010 0011 1000 1001)2,

F4 = (0111 0010 0010 0011 1100)2,

F5 = (1001 1100 0100 1000 1010)2,

F6 = (0011 0101 0010 0110 0101)2,

F7 = (1101 0011 1011 1011 0100)2.

Повторный вызов бита bi (0 ≤ i ≤ 7) каждого извлеченного байта выражается

19	fi	19
bi		j m8 j i , где Fi fi	j 2 j
		j 0
j 0

где mk – биты, содержащиеся в основном регистре.

Инициализация

Инициализация шифра F-FCSR-H производится в следующем порядке: v ≤ 80)

192