Блочные алгоритмы симметричного шифрования

У Г А Т У
Содержание лекции
Уфимский государственный авиационный технический университет
Семейство DES
DES: Операция зашифровывания-расшифровывания
DES: Операция расширения ключа
3DES
Алгоритм AES
Семейство RC

У Г А Т У
Семейство DES
Уфимский государственный авиационный технический университет
1971-73 Исследовательский проект Lucifer
Первая версия – SP-сеть, дальнейшие – сбалансированная сеть Фейстеля
1977 Алгоритм DES
Размер блока – 64 бита, размер ключа – 56 бит
К середине 1990-х такая длина ключа утратила криптостойкость
1978 3DES
Алгоритм использует операции за/расшифровывания DES
Длина ключа – 112 или 168 бит
Алгоритм имеет некоторое применение в настоящее время, однако чрезвычайно тяжеловесен в программной реализации

У Г А Т У
Алгоритм DES
Уфимский государственный авиационный технический университет
Операция зашифровывания
Этап 1. Начальная перестановка Т=IP(T)
Этап 2. 16 раундов сети Фейстеля
Этап 3. Конечная перестановка T=FP(T)
Конечная перестановка обратна начальной FP( IP(T) ) = T
Таблица начальной перестановки DES
Таблица конечной перестановки DES.

У Г А Т У
Алгоритм DES
Уфимский государственный авиационный технический университет
Функция F
Аргументы: полублок 32 бита, раундовый ключ 48 бит
шаг 1. Перестановка-расширение полублока до 48 бит
шаг 2. XOR расширенного полублока c раундовым ключом
шаг 3. Подстановка-сжатие обратно до 32 бит
шаг 4. Перестановка
Таблица перестановки-расширения
Таблица перестановки

У Г А Т У
Алгоритм DES
Уфимский государственный авиационный технический университет
Функция F
шаг 3. Подстановка-сжатие обратно до 32 бит
48-битный расширенный полублок разбивается на 6-битные слова
Каждое 6-битное слово заменяется на 4-битное по своей таблице замен (S1..S8)
В таблице номер строки определяется первым и последним битом слова, номер столбца – 4-мя средними

У Г А Т У
Алгоритм DES
Уфимский государственный авиационный технический университет
Расширение ключа
шаг 1. Вычисляются С[0] и D[0] как результат перестановки исходного ключа
шаг 2. Для i от 1 до 16 вычисляется C[i] и D[i] как циклический сдвиг C[i-1] и D[i-1] влево
на 1 бит, если i=1,2,9,16
на 2 бита для остальных раундов
шаг 3. i-й раундовый ключ берется как перестановка-сжатие вектора С[i]||D[i]
Таблица перестановки для расчета C[0] и D[0]
Таблица перестановки-сжатия для получения раундового ключа
Процедура расширения состоит только из перестановок (включая сжатия и расширения). В расширенном ключе используются только биты исходного ключа, поэтому если исходный ключ состоит лишь из нулей, то и расширенный будет состоять лишь из нулей

У Г А Т У
Алгоритм 3DES
Уфимский государственный авиационный технический университет
3DES-EEE3
ключ 168 бит разбивается на 3 подключа по 56 бит
текст последовательно зашифровывается по DES на каждом подключе
3DES-EDE3 (Более популярный вариант)
То же самое, но при шифровании вторым подключом применяется операция расшифровывания
3DES-EEE2 и 3DES-EDE2
Длина ключа 112 бит, третий подключ равен первому

У Г А Т У
Семейство DES
Уфимский государственный авиационный технический университет
Проблемы
Семейство заточено под аппаратную реализацию, при программной работает медленно
Размер блока ограничен 64 битами
Существуют слабые ключи
Если ключ состоит из одних нулей, то и раундовые подключи будут из одних нулей
Если ключ состоит из одних единиц, то и раундовые подключи будут из одних единиц
Надежные ключи должны выглядеть как случайные данные
Если перед зашифровыванием инвертировать открытый текст и ключ, в результате получится инверсия шифротекста:
Ш ( не(ОТ), не(К) ) = не ( Ш(ОТ,К) )

У Г А Т У
Содержание лекции
Уфимский государственный авиационный технический университет
Семейство DES
Алгоритм AES
Операция зашифровывания
Операция расширения ключа
Семейство RC

У Г А Т У
Алгоритм AES
Уфимский государственный авиационный технический университет
Rijndael: длина блока и длина ключа 128, 160, 192, 234 или 256 бит
AES: длина блока 128 бит, длина ключа 128, 192 или 256
В остальном алгоритмы идентичны
Число раундов 6+k/32, где k – длина ключа; также есть нулевой раунд
Классическая SP-сеть

У Г А Т У
Алгоритм AES
Уфимский государственный авиационный технический университет
Операция зашифровывания
Байты блока записываются в матрицу State 4 на 4
(первые 4 байта в первый столбец, следующие во второй и т. д.)
На каждом раунде выполняются 4 операции
SubBytes – подстановка
ShiftRows - перестановка
MixColumns - перестановка
AddRoundKey – XOR с раундовым ключом
На нулевом раунде выполняется только AddRoundKey
На финальном раунде не выполняется операция MixColumns
При расшифровке выполняются операции InvSubBytes, InvShiftRows, InvMixColumns

У Г А Т У
Алгоритм AES
Уфимский государственный авиационный технический университет
Операция зашифровывания
SubBytes – подстановка для каждого байта по общей таблице замен
ShiftRows – перестановка
Первая строка State неизменна
Вторая << на 1 байт
Третья << на 2 байта
Четвертая << на 3 байта
MixColumns - на каждый столбец в поле Галуа умножается фиксированная матрица
AddRoundKey – XOR с раундовым ключом
Таблица замен SubBytes

У Г А Т У
Алгоритм AES
Уфимский государственный авиационный технический университет
Операция расширения ключа
Для AES-128 (в других версиях – другая процедура)
Расширенный ключ состоит из 32-битных слов
Первые 4 слова заполняются исходным ключом, затем, каждое j-e слово вычисляется на основе предыдущих:
ЕСЛИ (j mod 4 = 1) ТО
W_J=SubWord(W[j-1]) \\ аналогично SubBytes
W_J=RotWord(W_J) \\ циклический сдвиг влево на 1 байт
W_J = XOR(W_J, RCon]) \\ RСon зависит от номера раунда
W[j] = XOR(W_J, W[j-4]) 2
ИНАЧЕ
W[j]=XOR(W[j-1], W[j-4])
Ключ i-го раунда K[i] равен словам W[j-3] || W[j-2] || W[j-1] || W[j] где j=(i+1)*4
Можно либо посчитать расширенный ключ целиком, либо поочередно рассчитывать раундовые ключи для каждого раунда (например, параллельно с зашифровыванием)
Ключ нулевого раунда идентичен исходному

У Г А Т У
Содержание лекции
Уфимский государственный авиационный технический университет
Семейство DES
Алгоритм AES
Семейство RC
RC2
RC5
RC6

У Г А Т У
Семейство RC
Уфимский государственный авиационный технический университет
Алгоритмы, разработанные Роном Райвестом
(RC – Ron’s Code, Rivest Cipher)
RC1 – «не вышел за пределы записной книжки»
RC2 -1987
RC3 – взломан в процессе разработки
RC4 – 1987, потоковый
RC5 - 1994
RC6 – 1998, переделка RC5 под конкурс AES

У Г А Т У
Алгоритм RC2
Уфимский государственный авиационный технический университет
Разработан как альтернатива DES
Не был запрещен к экспорту из США
Быстрее в программной реализации и проще в аппаратной (т.к. подстановка не используется при шифровании, а только при расширении ключа)
Размер блока – 64 бита
Размер ключа – от 9 до 1024 бит
на практике обычно – 56 бит в эпоху DES и 128/256 теперь
Длина расширенного ключа – 1024 бита или 128 байт
Несбалансированная сеть Фейстеля
Блок разбивается не на 2 полублока, а на 4 16-битных слова R[0]R[1]R[2]R[3]

У Г А Т У
Алгоритм RC2
Уфимский государственный авиационный технический университет
Процедура зашифровывания

У Г А Т У
Алгоритм RC2
Уфимский государственный авиационный технический университет
Процедура зашифровывания
R0
R1
R2
R3
&
&
Σ
KR

У Г А Т У
Алгоритм RC2
Уфимский государственный авиационный технический университет
Процедура расширения ключа
Расширенный ключ записывается в байтовый массив L[0]…L[127]
Число байт в исходном ключе обозначается как t (округляется вверх)
Создается байт TM, заполненный нулями
Если число байт нецелое, ключ дополняется единицами и то же число единиц записывается в те же разряды ТМ
Используется таблица замен на основе 16-чного представления π
Таблица замен

У Г А Т У
Алгоритм RC2
Уфимский государственный авиационный технический университет
Процедура расширения ключа
ДЛЯ i ОТ t ДО 127
L[i] = L[i-1]+L[i-t]
L[i] = S(L[i]) \\ подстановка по таблице замен
КОНЕЦ
L[128-t] = L[128-t] & TM \\ обнуляются биты, на которые в байте t не приходится дополнение
L[128-t] = S(L[128-t])
ДЛЯ i ОТ 127-t ДО 0
L[i] = XOR (L[i+1],L[i+t])
L[i] = S(L[i])
КОНЕЦ

У Г А Т У
Алгоритм RC2
Уфимский государственный авиационный технический университет
Выбор раундового ключа
Выбор раундового ключа
L[0]…L[127] разбивается на 64 раундовых подключа
В смешивающих раундах подключи используются последовательно (по 4 на раунд)
В объединяющем раунде для зашифровки текущего слова берется подключ с номером, равным численному выражению младших 6 бит слова, расположенного слева от текущего

У Г А Т У
Алгоритм RC5
Уфимский государственный авиационный технический университет
Версия алгоритма обозначается по типу RC5-32/12/16
32 – длина обрабатываемого слова-полублока (м. б. также 16 и 64); длина блока вдвое больше
12 – число раундов (от 1 до 255)
16 - длина ключа в байтах (от 1 до 255, т. е. от 8 до 2048 бит с шагом 8)
RC5 условно считается разновидностью сети Фейстеля
Расшифровывание выполняется в виде операций, обратных зашифровыванию в обратном порядке

У Г А Т У
Алгоритм RC5
Уфимский государственный авиационный технический университет
Процедура зашифровывания

У Г А Т У
Алгоритм RC5
Уфимский государственный авиационный технический университет
Процедура расширения ключа (версия с 32-битным полублоком)
Расширенный ключ – массив 32-битных слов S[0]…S[2r+1]
r – число раундов
Раундовый ключ K[i]=S[2i]||S[2i+1]
Исходный ключ записывается в массив 32-битных слов L[0]…L[c-1]
Слово L[n] при необходимости дополняется нулями
Массив S изначально заполняется с помощью конгруэнтного генератора ПСП заданного в 16-чной системе:
S[0]=B7E15163
S[i]=(S[i-1] + 9E3779B9) mod FFFFFFFF
A = 0; B = 0; i = 0; j = 0;
n = max(c, 2r+2)
ДЛЯ k ОТ 1 ДО n
S[i] = (S[i]+A+B) <<< 3
A = S[i]
L[i] = (L[i]+A+B) <<< (A+B)
B = L[i]
i = (i+1) mod (2r+2)
j = (j+1) mod c
КОНЕЦ

У Г А Т У
Алгоритм RC6
Уфимский государственный авиационный технический университет
Адаптация RC5 под условия конкурса AES
Параметры варьируются как в RC5
Конкурсные версии - RC6-32/20/16, RC6-32/20/24 и RC6-32/30/32
Уступил Rijndael из-за медленного выполнения арифметического умножения на ряде платформ
Является несбалансированной сетью Фейстеля
Отличия от RC5:
Блок делится не на 2 слова, а на 4 A,B,C,D
После каждого раунда блок сдвигается на 1 слово влево
Преобразование раунда имеет следующий вид:
t1 = ( B * (2B+1) ) <<< 5;
t2 = ( D * (2D+1) ) <<< 5;
A = xor(A,t1) <<< t2
C = xor(C,t2) <<< t1