Кодирование и шифрование информации в радиоэлектронных системах передачи информации. Часть 2. Шифрование

Рис. 2.26. Выходное преобразование четырех последовательных раундов Sosemanuk

Шифр Sosemanuk объединяет FSM и LFSR для производства выходных значений zt.

Время t = 0 определяет внутреннее состояние после инициализации; первое выходное значение – z1. На рисунке 3 представлено описание шифра Sosemanuk.

171

Рис. 2.27. Описание шифра Sosemanuk

Вмоменты времени t 1 выполняются следующие операции:

обновляется FSM: из R1t−1, R2t−1, st+1, st+8 и st+9 вычисляются R1t, R2t и промежуточные значения ft.

обновляется LFSR: из st, st+3 и st+9 вычисляется st+10. Значение st

передается внутреннему буферу, LFSR сдвигается.

Каждые четыре шага, из накопленных значений ft, ft+1, ft+2, ft+3 и st, st+1, st+2, st+3 производятся четыре выходных значения zt, zt+1, zt+2, и zt+3. Таким образом, Sosemanuk

производит 32-битовые значения.

Соответственно первые четыре итерации Sosemanuk’а следующие:

Начальное состояние LFSR содержит значения s1, …, s10; значение s0 не определено. Начальное состояние FSM содержит R10 и R20.

В течение первого шага из R10, R20, s2, s9 и s10 вычисляются R11, R21 и f1.

Первый шаг производит промежуточные значения s1 и f1, сохраняемые в

буфере.

В течение первого шага, вычисляется слово обратной связи s11 из s10, s4 и

s1, обновляется внутреннее состояние LFSR, что приводит к новому состоянию, формируемое из s2, …, s11.

172

Первые четыре выходные значения – z1, z2, z3 и z4, вычисляются,

используя однократное применение Serpent1’а к (f4, f3, f2, f1), выход которого объединяется с (s4, s3, s2, s1) при помощи XOR.

Поточный шифр 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. Функция перехода может быть описана выражениями

173

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).

Отметим, что 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

zfi mi .

i0

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

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 каждый определяется как

ns 1

Fj fsi j 2i . i 0

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

псевдослучайный бит:

ns 1

z j f si j msi j . i 0

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

Эта процедура может быть описана эквивалентно следующим образом. Фильтр F и

состояние M комбинируются функцией И. Результат разбивается на n/s слова.

Псевдослучайное слово получается операцией XOR этих n/s слов:

S = M F

174

ns 1

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

i 0

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

n s 1

zSi .

i0

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

Шифр 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) каждого извлеченного байта выражается

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

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

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

175

v ≤ 80)

1. Основной регистр М инициализируется ключом и IV:

M:= K + 280 IV = (080–v||IV||K)

2.Регистр переносов инициализируется в 0:

C := 0 = (082)

3. FCSR тактируется 160 раз. (На этом шаге выход отбрасывается),

После фазы установки, псевдослучайный поток производится тактированием FCSR и

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

Поточный шифр Grain-128

Grain – двоичный аддитивный поточный шифр, ориентированный на аппаратную реализацию. Версия, которая обозначается Grain v.1 [6], предназначена для приложений,

которые имеют очень ограниченные аппаратные ресурсы. Grain v.1 поддерживает 80-

битовый размер ключа.

Версия нифра Grain-128 поддерживает размер ключа – 128 бит и размер вектора IV – 96

битов. Шифр Grain-128 также является очень компактным и легко осуществимым в аппаратных средствах. Кроме того, возможно достаточно просто увеличивать скорость за счет большего количества аппаратных средств. Это является отличительной особенность семейства поточных шифров Grain, и во многих других шифрах явно не обосновано. Grain-

128 использует линейный регистр сдвига с обратной связью, чтобы гарантировать хорошие статистические свойства и гарантировать нижнюю границу периода ключевой последовательности. Чтобы ввести нелинейность вместе с нелинейным фильтром используется нелинейный регистр сдвига с обратной связью (NFSR). Нелинейный фильтр берет в качестве входных данных значения от обоих сдвиговых регистров.

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

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

176

zi

Рис. 2.28. Краткий обзор шифра.

Шифр состоит из трех основных строительных блоков, а именно: LFSR, NFSR и

выходной функции. Содержимое LFSR обозначается si, si+1, …, si+127. Аналогичным образом содержание NFSR обозначается bi, bi+1, …, bi+127. Полином обратной связи LFSR,

обозначенный f(x), является примитивным полиномом степени 128. Он определен как

f(x) = 1 + x32 + x47 + x58 + x90 + x121 + x128.

Чтобы избежать любой возможной неопределенности, разработчики в [6] привели соответствующую функцию обновления LFSR:

si+128 = si + si+7 + si+38 + si+70 + si+81 + si+96.

Нелинейный полином обратной связи NFSR, g(x), является суммой одной линейной и одной нелинейной функций. Он определен как

g(x) = 1 + x32 + x37 + x72 + x102 + x128 + x44x60 + x61x125 + + x63x67 + x69x101 + x80x88 + x110x111 + x115x117.

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

приведенной ниже, бит si, опущенный в полиноме обратной связи, включен и замаскирован со входом NFSR.

bi+128 = si + bi + bi+26 + bi+56 + bi+91 + bi+96 + bi+3bi+67 + bi+11bi+13 +

+ bi+17bi+18 + bi+27bi+59 + bi+40bi+48 + bi+61bi+65 + bi+68bi+84.

256 элементов памяти в этих двух сдвиговых регистрах представляют состояние шифра.

Из этого состояния берется 9 переменных в качестве входа булевой функции h(x). Два входа h(x) берутся из NFSR, а семь – из LFSR. Эта функция имеет степень 3 и является очень простой. Она определяется как

177

h(x) = x0x1 + x2x3 + x4x5 + x6x7 + x0x4x8,

где переменные x0, x1, x2, x3, x4, x5, x6, x7 и x8 соответствуют позициям сигнала bi+12, si+8, si+13, si+20, bi+95, si+42, si+60, si+79 и si+95 соответственно. Выходная функция определяется как

zi bi j h x si 93 ,

j A

где A = {2,15,36,45,64,73,89}.

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

Перед генерацией ключевой последовательности шифр должен быть инициализирован с помощью ключа и вектора IV. Пусть биты ключа k будут обозначаться ki, 0 i 127, а биты вектора IV будут обозначаться IVi, 0 i 95. Тогда инициализация ключа и вектора IV

выполняется следующим образом. 128 элементов NFSR заполняются битами ключа, bi = ki, 0i 127, затем первые 96 элементов LFSR заполняются битами IV битами, si = IVi, 0 i 95.

Последние 32 бита LFSR заполняются единицами, si = 1, 96 i 127. После загрузки битов ключа и IV, шифр тактируется 256 раз, без производства ключевой последовательности.

Вместо выходной функции производится подача назад и сложение по модулю 2 (XOR’тся) со входом и LFSR и NFSR, см. рисунок 2.29

Рис. 2.29. Инициализация ключа

Поточный шифр MICKEY-128

MICKEY-128 – поточный шифр, ориентированный на аппаратную реализацию. для генерации ключевого потока MICKEY-128 использует 128 битовый ключ [6]. Этот шифр использует нерегулярно тактируемые регистры сдвига с новыми методиками,

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

178

периоде и псевдослучайностью и необходимостью избежать определенных

криптоаналитических атак.

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

MICKEY128 2.0 использует два входных параметра:

128-битовый секретный ключ K, биты которого обозначаются k0 … k127;

вектор инициализации IV (initialisation variable), длиной от 0 до 128

битов, биты которой обозначаются iv0 … ivIVLENGHT–1, где IVLENGHT – размер вектора инициализации в битах.

Генератор строится из двух регистров R и S. Каждый регистр длиной 160 разрядов. Биты в регистрах обозначаются r0 … r159 и s0 … s159 соответственно.

Разработчики заявляют, что R – это “линейный регистр”, а S – это “нелинейный регистр”.

Инициализация генератора начинается с обнуления всех разрядов регистров R и S. Затем производится загрузка вектора инициализации IV путем тактирования всего генератора

IVLENGHT раз с помощью операции clock_KG(R, S, Mixing = True, Input_bit = ivi),

описанной в п.1.3.8.2. Затем производится загрузка ключа: весь генератор тактируется 128

раз, так же с помощью операции clock_KG(R, S, Mixing = True, Input_bit = ki). Заканчивается процесс инициализации 160 кратным применением операции clock_KG(R, S, Mixing = True, Input_bit = 0) тактирования всего генератора.

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

После выполнения операции инициализации можно приступить к генерации битов ключевой последовательности z0 … zL–1:

For 0 i L–1:

zi = r0 s0,

clock_KG(R, S, Mixing = False, Input_bit = 0),

где clock_KG(R, S, Mixing, Input_bit)и – операция тактирования всего генератора, которая определяется в соответствии со следующим псевдокодом:

Control_bit_R = s54 r106

Control_bit_S = s106 r53

If Mixing = True,

o clock_R(R, Input_bit_R = Input_bit s80, Control_bit_R = Control_bit)

oclock_S(S, Input_bit_S = Input_bit, Control_bit_S = Control_bit)

If instead Mixing = False,

oclock_R(R, Input_bit_R = Input_bit, Control_bit_R = Control_bit)

o clock_S(S, Input_bit_S = Input_bit, Control_bit_S = Control_bit)

179

clock_R и clock_S – это операции тактирования регистров R и S соответственно.

Операция тактирования регистра R clock_R(R, Input_bit_R, Control_bit_R) определяется следующим псевдокодом:

Пусть r0 … r159 будет состоянием регистра R до тактирования, а r’0 …

r’159 будет состоянием регистра R после тактирования.

Feedback_bit = r159 Input_bit_R

For 1 i 159 {r’i = ri–1; r’0 = 0;}

For 0 i 159 {if i Rtaps, r’i = r’i Feedback_bit}

If Control_bit_R = 1

o For 0 i 159 {r’i = r’i ri}

Rtaps – это набор позиций отводов обратной связи для R:

Rtaps = {0, 4, 5, 8, 10, 11, 14, 16, 20, 25, 30, 32, 35, 36, 38, 42, 43, 46, 50, 51, 53, 54, 55, 56, 57, 60, 61, 62, 63, 65, 66, 69, 73, 74, 76, 79, 80, 81, 82, 85, 86, 90, 91, 92, 95, 97, 100, 101, 105, 106, 107, 108, 109, 111, 112, 113, 115, 116, 117, 127, 128, 129, 130, 131, 133, 135, 136, 137, 140, 142, 145, 148, 150, 152, 153, 154, 156, 157}.

Операция тактирования регистра S clock_S(S, Input_bit_S, Control_bit_S) определяется следующим псевдокодом:

Пусть s0 … s159 будет состоянием регистра S до тактирования, а s’0 …

переменные.

Feedback_bit = s159 Input_bit_R

If Control_bit_S = 0:

o For 0 i 159 {s’i = si (fb0i Feedback_bit)}

If instead Control_bit_S = 1

o For 0 i 159 {s’i = si (fb1i Feedback_bit)}

Значения comp0, comp1, fb0 и fb1, определенные разработчиками, приведены в [6].

Поточный шифр Trivium

Trivium – синхронный поточный шифр, использующий 80-битовый ключ и 80-

битовый вектор инициализации IV .

180