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

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

Алгоритм инициализируется загрузкой 80-битового ключа и 80-битового IV в 288-

битовое начальное состояние и устанавливает все оставшиеся биты в 0, за исключением s286, s287, и s288. Затем состояние изменяется за 4 полных цикла (без генерации бит ключевого потока). В итоге это можно представить в виде псевдокода, приведенного ниже:

(s1, s2, …, s93) (K1, …, K80, 0, …, 0) (s94, s95, …, s177) (IV1, …, IV80, 0, …, 0) (s178, s279, …, s288) (0, …, 0, 1, 1, 1) for i = 0 to 4 288 do

{

(s178, s279, …, s288) (t2, s178, …, s287)

}

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

Предложенная конструкция содержит 288-битовое внутреннее состояние, обозначенное

(s1, …, s288). Генерация ключевого потока состоит из итерационного процесса, который извлекает значения 15 определенных битов состояния и использует их для обновления 3

битов состояния и вычисления 1 бита ключевого потока zi. Затем биты состояния циклически сдвигаются и процесс повторяет, пока не будут сгенерированы требуемые N бит ключевого потока. Полное описание дается следующим простым псевдокодом:

for i = 1 to N do

{

t1 s66 s93 t2 s162 s177

t3 s243 s288

zi t1 t2 t3

t1 t1 s91 s92 s171 t2 t2 s175 s176 s264 t3 t3 s286 s287 s69

(s1, s2, …, s93) (t3, s1, …, s92) (s94, s95, …, s177) (t1, s94, …, s176)

(s178, s279, …, s288) (t2, s178, …, s287)

}

Графическое представление процесса генерации ключевого потока приведено на рис.

2.30.

181

Рис. 2.30. Поточный шифр Trivium

Блочные шифры в поточных режимах

Российский блочный шифр ГОСТ 28147-89 в поточном режиме

В России в качестве стандарта шифрования принят алгоритм криптографического преобразования ГОСТ 28147-89. Этот алгоритм предназначен для аппаратной и программной реализации, удовлетворяет необходимым криптографическим требованиям и не накладывает ограничений на степень секретности защищаемой информации.

Для шифрования используются 256 битовый ключ, который разбивается на 8 32-

битовых подключа: K0, K1, …, K7, и таблица блока подстановки H. Заполнение таблиц блока подстановки H является долговременным ключевым элементом.

Алгоритм криптографического преобразования ГОСТ 28147-89 опирается на цикл шифрования (рисунок 2.31). Цикл шифрования построен по принципу сети Фейстеля.

182

m = 0, …, 7

Rm = Km(L)

R <<< 11

Рис. 2.31. Цикл шифрования

Один цикл шифрования преобразует 64-битовый блок данных, используя один 32-

битовый элемент ключа Kj и блок подстановки H.

Преобразуемый 64-битовый блок данных (N) разбивается на две части: старшую (N2) и

младшую (N1). Значение N1 суммируется по модулю 232 с одним из 32-битовых элементов ключа Kj, j = 0, …, 7. Результат суммирования преобразуется в блоке подстановки H. Блок подстановки H состоит из 8 узлов замены H1, …, H8 размером 64 бита каждый.

Поступающий на блок подстановки 32-разрядный блок разбивается на восемь последовательно идущих 4-разрядных блоков, каждый из которых преобразуется в 4-

разрядный блок соответствующим узлом замены, представляющим собой таблицу из шестнадцати строк, содержащих по четыре бита заполнения в строке. Входной блок определяет адрес строки в таблице, заполнение данной строки является выходным блоком. Затем 4-разрядные выходные блоки последовательно объединяются в 32-

разрядный блок. Полученное значение R циклически сдвигается на 11 шагов в сторону старших разрядов. Результат сдвига суммируется поразрядно по модулю 2 со значением

N2. Полученный результат N2 записывается в N1, при этом старое значение N1

переписывается в N2.

Многократное повторение цикла шифрования, при использовании различных элементов ключа, позволяет построить циклы зашифрования (32-З) и расшифрования (32-

Р). В цикле зашифрования 32-З отдельный цикл шифрования повторяется 32 раза,

183

используя 32-битовые элементы ключа в следующем порядке: K0, …, K7, K0, …, K7, K0, …,

K7, K7, …, K0. Цикл расшифрования 32-Р отличается от цикла порядком использования 32-

битовых элементов ключа. В цикле 32-Р этот порядок следующий: K0, …, K7, K7, …, K0,

K7, …, K0, K7, …, K0.

Ниже приведено описание двух поточных режимов работы криптографического алгоритма ГОСТ 28147-89, а именно: гаммирование и гаммирование с обратной связью.

Гаммирование

Криптосхема, реализующая алгоритм зашифрования в режиме гаммирования, имеет вид,

указанный на рисунке 7.32а.

Рис. 2.32. Схема алгоритма зашифрования (а) и расшифрования (б) в режиме гаммирования

Открытые данные, разбитые на 64-разрядные блоки Тоi, зашифровываются в режиме гаммирования путем поразрядного суммирования по модулю 2 с гаммой шифра Гш, которая вырабатывается блоками по 64 бита Гшi, i = 1, …, m. m определяется объемом шифруемых данных. Число двоичных разрядов в блоке Тоm может быть меньше 64, при этом неиспользованная для зашифрования часть гаммы шифра из блока Гшm отбрасывается.

Для инициализации процесса генерации гаммы используется 64-разрядная двоичная последовательность (синхропосылка) S. К синхропосылке применяется цикл зашифрования

32-З. Результат шифрования N разбивается на две части: старшую (N2) и младшую (N1).

Значение N2 суммируется по модулю (232 – 1) с 32-разрядной константой C1 = 0101010416.

Значение N1 суммируется по модулю 232 с 32-разрядной константой C2 = 0101010116. К

полученному значению N применяется цикл зашифрования 32-З. Полученное в результате зашифрования значение N образует первый 64-разрядный блок гаммы шифра Гш1, который

184

суммируется поразрядно по модулю 2 с первым 64-разрядным блоком открытых данных То1.

В результате суммирования получается 64-разрядный блок зашифрованных данных Тш1. Для получения следующего 64-разрядного блока гаммы шифра Гш2 старшая часть N2 значения N

суммируется по модулю (232 – 1) с константой C1, а младшая часть N1 суммируется по модулю 232 с константой C2. К полученному значению применяется цикл зашифрования 32-З.

Полученное в результате зашифрования значение N образует второй 64-разрядный блок гаммы шифра Гш2, который суммируется поразрядно по модулю 2 со вторым блоком открытых данных То2. Аналогично вырабатываются блоки гаммы шифра Гш3, Гш4, …, Гшm и

зашифровываются блоки открытых данных То3, То4, …, Тоm. Если длина последнего m-го блока открытых данных Тоm меньше 64 бит, то из последнего m-го блока гаммы шифра Гшm

для зашифрования используется только соответствующее число разрядов гаммы шифра,

остальные разряды отбрасываются.

Аналогичным образом производится расшифрование в режиме гаммирования (рисунок

2.32б).

Гаммирование с обратной связью

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

Открытые данные, разбитые на 64-разрядные блоки Тоi, зашифровываются в режиме гаммирования с обратной связью путем поразрядного суммирования по модулю 2 с гаммой шифра Гш, которая вырабатывается блоками по 64 бита Гшi, i = 1, …, m. m определяется объемом шифруемых данных. Число двоичных разрядов в блоке Тоm может быть меньше 64.

Рис. 2.33. Схема алгоритма зашифрования (а) и расшифрования (б) в режиме гаммирования с обратной связью

Исходное значение – синхропосылка S зашифровывается с помощью цикла зашифрования 32-З. Полученное в результате зашифрования значение N образует первый 64-

разрядный блок гаммы шифра Гш1, который суммируется поразрядно по модулю 2 с первым

185

64-разрядным блоком открытых данных То1. В результате получается 64-разрядный блок зашифрованных данных Тш1.

Блок зашифрованных данных Тш1 одновременно является также исходным состоянием N

для выработки второго блока гаммы шифра Гш2 и по обратной связи передается на вход.

Новое значение N зашифровывается с помощью цикла зашифрования 32-З. Полученное в результате зашифрования значение N образует второй 64-разрядный блок гаммы шифра Гш2,

который суммируется поразрядно по модулю 2 со вторым блоком открытых данных То2.

Выработка последующих блоков данных шифра Гшi и зашифрование соответствующих блоков открытых данных Тоi (i = 3, …, m) производится аналогично. Если длина последнего m-го блока открытых данных Тоm меньше 64 бит, то из последнего m-го блока гаммы шифра

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

Аналогичным образом производится расшифрование в режиме гаммирования с обратной связью (рисунок 2.33б).

Блочный шифр AES в поточном режиме

В основе стандарта шифрования AES лежит алгоритм Rijndael. Rijndael – это

итерационный блочный шифр, имеющий архитектуру “Квадрат”. Шифр имеет переменную длину блоков и различные длины ключей. Длина ключа и длина блока могут быть равны независимо друг от друга 128, 192 или 256 битам. В стандарте AES-128 определена длина блока данных, равная 128 битам.

Операции алгоритма AES выполнены на основе двумерного массива байтов,

называемого состоянием (state). Состояние состоит из четырех строк, каждая из которых содержит Nb байт, где Nb – длина блока в битах, деленная на 32. В массиве состояния,

обозначенном символом s, каждый байт имеет два индекса: номер строки r, 0 ≤ r < 4, и

номер столбца c, 0 ≤ c < Nb. Это позволяет обращаться к отдельному байту состояния как src.

Для AES-128 Nb = 4, т.е. 0 ≤ c < 4.

Перед применением операции зашифрования или расшифрования, входной блок данных,

представленный в виде массива байтов in0, …, in15, копируется в массив состояния (рисунок

2.34):

src = inr+4c, 0 ≤ r < 4, 0 ≤ c < Nb,

ав конце операций зашифрования или расшифрования, данные из состояния копируются

ввыходной массив (рисунок 2.34):

outr+4c = src, 0 ≤ r < 4, 0 ≤ c < Nb.

186

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

строками (рисунок 2). Число столбцов Nk этого массива равно длине ключа в битах, деленной на 32. В стандарте определены ключи всех трех размеров – 128 бит, 192 бита и 256 бит, то есть соответственно 4, 6 и 8 32-разрядных слова (или столбца – в табличной форме представления). В некоторых случаях ключ шифрования рассматривается как линейный массив 4-байтовых слов. Слова состоят из 4 байтов, которые находятся в одном столбце (при представлении в виде прямоугольного массива).

Рис. 2.35. Формат представления ключа шифрования

Для алгоритма AES длина входного и выходного блоков, а также блока состояния – 128

битов, т.е. Nb = 4. Длина ключа шифрования равна 128, 192 или 256 битов, т.е. Nk = 4, 6 или 8.

Количество раундов, которые будут выполнены в течение выполнения алгоритма, зависит от размера ключа. Число раундов обозначается Nr, где Nr = 10 при Nk = 4, Nr = 12 при Nk = 6 и Nr

=14 при Nk = 8.

Идля шифрования, и для расшифрования, алгоритм AES использует раундовую функцию, которая составлена из четырех различных преобразований над байтами: 1) замена байта, используя таблицу замены (S-блок), 2) сдвиг строк массива состояния на различные смещениями, 3) смешивание данных в пределах каждого столбца массива состояния, и 4)

добавление раундового ключа к состоянию. Эти преобразования (и их инверсии) описаны

ниже.

187

Функция зашифрования

Перед зашифрованием входные данные копируются в массив состояния. После начального добавления раундового ключа, массив состояния преобразуется с помощью раундовой функции 10, 12 или 14 раз (в зависимости от длины ключа). Заключительный раунд немного отличается от первых Nr – 1 раундов. Затем полученное состояние копируется в выходной массив.

Раундовая функция состоит из 4 различных преобразований: SubBytes, ShiftRows,

MixColumns и AddRoundKey. Все Nr раундов идентичны за исключением последнего,

который не включает преобразование MixColumns (рисунок 2.36).

Входной блок

AddRoundKey round = 1 .. 9

SubBytes

ShiftRows

MixColumns

AddRoundKey

SubBytes

ShiftRows

AddRoundKey

Выходной блок

Рис. 2.36. Схема функции зашифрования (Nb = 4, Nk = 4)

Преобразование SubBytes – нелинейная замена байта, которая работает независимо на каждом байте состояния, используя таблицу замены (S-блок). Эта таблица замен создается с использованием двух преобразований:

1. получение обратного элемента относительно умножения в поле

GF(28), нулевой элемент переходит сам в себя;

2. применение преобразования над GF(2), определенного сле-

дующим образом:

b'i = bi b(i+4)mod8 b(i+5)mod8 b(i+6)mod8 b(i+7)mod8 ci,

где c0 = c1 = c5 = c6 = 1, c2 = c3 = c4 = c7 = 0, bi и b'i – соответственно исходное и преобразованное значение i-го бита, i = 0, …, 7.

В преобразовании ShiftRows байты в последних трех строках состояния циклически сдвигаются влево на различное число байт. Первая строка (r = 0) не сдвигается. Вторая

188

строка (r = 1) сдвигается на 1 байт, третья строка (r = 2) – на 2 байта, четвертая строка (r = 3)

– на 3 байта.

Преобразование MixColumns работает с состоянием столбец за столбцом, обрабатывая каждый столбец как 4-элементный полином. Столбцы рассматриваются как полиномы над

GF(28) и умножаются по модулю x4 + 1 на фиксированный полином a(x), приведенный ниже a(x) = {03}x3 + {01}x2 + {01}x + {02}.

Это может быть представлено в матричном виде:

Врезультате этого умножения байты столбца заменяются следующими: s'0c = ({02} • s0c) ({03} • s1c) s2c s3c,

s'1c = s0c ({02} • s1c) ({03} • s2c) s3c, s'2c = s0c s1c ({02} • s2c) ({03} • s3c), s'3c = ({03} • s0c) s1c s2c ({02} • s3c).

Впреобразовании AddRoundKey раундовый ключ добавляется к состоянию простой

поразрядной операцией XOR. Каждый раундовый ключ состоит из Nb 4-байтовых слов развернутого ключа. Сложение раундового ключа и состояния производится следующим образом:

[s'0c, s'1c, s'2c, s'3c] = [s0c, s1c, s2c, s3c] [wround Nb+c], 0 ≤ с < Nb,

где [wi] – слова развернутого ключа, описанного ниже, round – номер раунда, 0 ≤ round ≤ Nr. При зашифровании, перед первым применением раундовой функции, происходит начальное добавление раундового ключа (round = 0). Применение преобразования

AddRoundKey в Nr раундах зашифрования происходит при 1 ≤ round ≤ Nr.

Расширение ключа

В алгоритме AES для получения раундовых ключей используется алгоритм расширения ключа. Расширенный ключ представляет собой линейный массив w[i] из Nb(Nr + 1) 4-

байтовых слов, i = 0, …, Nb(Nr + 1). Алгоритм выработки ключей зависит от величины Nk.

Первые Nk слов расширенного ключа заполняются ключом шифрования. Каждое последующее слово w[i] получается посредством XOR предыдущего слова w[i–1] и слова на Nk позиций ранее w[i – Nk]

w[i] = w[i – 1] w[i – Nk].

189

Для слов, позиция которых кратна Nk, перед применением операции XOR слово w[i–l]

подвергается воздействию двух дополнительных функций: RotWord, осуществляющей побайтовый сдвиг 32-разрядного слова по формуле {a0 a1 a2 a3} {a1 a2 a3 a0}, и SubWord,

осуществляющей побайтовую замену с использованием S-блока функции SubBytes. Затем к полученному значению прибавляется раундовая константа Rcon[j] = 2j–1. В итоге значение w[i] равно

w[i] = SubWord(RotWord(w[i – 1])) Rcon[i/Nk] w[i – Nk].

i-ый раундовый ключ получается из слов массива раундового ключа от w[Nbi] и до w[Nb(i+1)].

Функция расшифрования

Если преобразования, используемые в функции зашифрования, инвертировать и затем применить в обратном порядке, то можно произвести обратное расшифрование. При расшифровании используются следующие преобразования: InvShiftRows, InvSubBytes,

InvMixColumns и AddRoundKey (рисунок 4а).

InvShiftRows – инверсия преобразования ShiftRows. Байты в последних трех строках состояния циклически сдвигаются вправо на различное число байт. Первая строка (r = 0) не сдвигается. Вторая строка (r = 1) сдвигается на 1 байт, третья строка (r = 2) – на 2 байта,

четвертая строка (r = 3) – на 3 байта.

InvSubBytes – инверсия преобразования замены байта, в котором к каждому байту состояния применяется обратный S-блок.

InvMixColumns – инверсия преобразования MixColumns. InvMixColumns оперирует состоянием столбец за столбцом, обрабатывая каждый столбец как 4-элементный полином,

как описано в ранее. Столбцы рассматривают как полиномы над GF(28) и умножаются по модулю x4 + 1 на фиксированный полином a–1(x)

a–1(x) = {0b}x3 + {0d}x2 + {09}x + {0e}.

Это может быть представлено в матричном виде:

В результате на выходе получаются следующие байты: s'0c = ({0e} • s0c) ({0b} • s1c) ({0d} • s2c) ({09} • s3c), s'1c = ({09} • s0c) ({0e} • s1c) ({0b} • s2c) ({0d} • s3c), s'2c = ({0d} • s0c) ({09} • s1c) ({0e} • s2c) ({0b} • s3c),

190