Симметричные блочные криптоалгоритмы

 

Наиболее распространенным классом компьютерных симметричных криптосистем стали алгоритмы шифрования, построенные по принципу сети Фейстела [5, 6]. Входной блок делится на несколько равной длины подблоков, называемых ветвями, как правило, по 32 бита каждая[†]. Каждая ветвь обрабатывается независимо от другой, после чего осуществляется циклический сдвиг всех ветвей влево. Такое преобразование выполняется несколькими циклами или раундами.  

Другим подходом к построению блочных шифров является использование обратимых зависящих от ключа преобразований. В этом случае на каждой итерации изменяется весь блок и, соответственно, общее количество итераций может быть сокращено. Каждая итерация представляет собой последовательность преобразований (так называемых «слоев»), каждое из которых выполняет свою функцию. K недостаткам данного подхода можно отнести то, что для процедур шифрования и дешифрования в общем случае нельзя использовать одни и те же блоки, как при использовании сетей Фейстела, что увеличивает аппаратные и/или программные затраты на реализацию.

Характеристики наиболее используемых симметричных блочных алгоритмов приведены в таблице 3.1.

 

Таблица 3.1 – Характеристики основных симметричных блочных алгоритмов [5]

Название	Длина ключа, битов	Размер обрабатываемых блоков, битов	Число раундов
AES(Rijndael)	128, 192, 256	128, 192, 256	10, 12, 14
Blowfish	32–448	64	16
CAST-128	128	64	16
CAST-256	256	128	16
DES	56	64	16
IDEA	128	64	8
NewDES	120	64	17
RC2	До 1024	64	16
RC5	До 2048	32, 64, 128	0…255
ГОСТ 28147-89	256	64	16, 32

 

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

Американский алгоритм шифрования DES (Data Encryption Standard) [5, 6], являвшийся официальным стандартом шифрования США с 1978-го по 2000 г., осуществляет шифрование 64-битовых блоков данных с помощью 56-битового ключа. Дешифрование в DES является операцией,  обратной шифрованию, и выполняется путем повторения операций шифрования в обратной последовательности. Структура алгоритма DES приведена на рисунке 3.1.

 

Рисунок 3.1 – Структура алгоритма шифрования DES

 

Процесс шифрования заключается в начальной перестановке бит  64-битового блока, 16 циклах шифрования и, наконец, в обратной перестановке битов. Необходимо отметить, что все таблицы, приведенные ниже, являются стандартными (IP, IP^-1, блоки перестановок S-boxes). Все перестановки и коды в таблицах подобраны разработчиками таким образом, чтобы максимально затруднить процесс дешифрования путем подбора ключа.

Пусть из файла считан очередной 8-байтовый блок T, который преобразуется с помощью матрицы начальной перестановки IP (таблица 3.2) следующим образом: бит 58 блока T становится битом 1, бит 50 – битом 2 и т.д., что даст в результате: T(0) = IP(T).

Полученная последовательность битов T(0) разделяется на две последовательности по 32 бита каждая: L(0) – левые, или старшие, биты; R(0) – правые, или младшие, биты. Затем выполняется шифрование, состоящее из 16 итераций. Результат i-й итерации описывается следующими формулами:

 

L(i) = R(i−1), i = 1, 2,…,16 R(i) = L(i−1) Å F(R(i−1), K(i)), i = 1,2,…, 16,

(3.1)

 

где Å – операция XOR, сложение по модулю 2.

 

Функция F называется функцией шифрования. Ее аргументы – это
32-битовая последовательность R(i−1), полученная на (i−1)-й итерации, и
48-битовый ключ K(i), который является результатом преобразования
64-битового ключа K. Подробно функция шифрования и алгоритм получения ключей К(i) описаны ниже.

На 16-й итерации получают последовательности R(16) и L(16) (без перестановки), которые конкатенируют в 64-битовую последовательность R(16)L(16). Затем позиции битов этой последовательности переставляют в соответствии с матрицей IP⁻¹ (таблица 3.3).

 

Таблица 3.2 – Матрица начальной перестановки IP 58 50 42 34 26 18 10 02 60 52 44 36 28 20 12 04 62 54 46 38 30 22 14 06 64 56 48 40 32 24 16 08 57 49 41 33 25 17 09 01 59 51 43 35 27 19 11 03 61 53 45 37 29 21 13 05 63 55 47 39 31 23 15 07

Таблица 3.3 – Матрица обратной перестановки IP−1 40 08 48 16 56 24 64 32 39 07 47 15 55 23 63 31 38 06 46 14 54 22 62 30 37 05 45 13 53 21 61 29 36 04 44 12 52 20 60 28 35 03 43 11 51 19 59 27 34 02 42 10 50 18 58 26 33 01 41 09 49 17 57 25

Матрицы IP⁻¹ и IP соотносятся следующим образом: значение первого элемента матрицы IP^-1 равно 40, а значение 40-го элемента матрицы IP равно 1; значение второго элемента матрицы IP⁻¹ равно 8, а значение 8-го элемента матрицы IP равно 2 и т.д.

Процесс дешифрования данных является инверсным по отношению к процессу шифрования. Итеративный процесс дешифрования может быть описан следующими формулами:

 

R(i−1) = L(i), i = 1, 2,…,16; L(i−1) = R(i) Å F(L(i), K(i)), i = 1,2,…, 16.

(3.2)

 

Рассмотрим функцию шифрования F(R(i−1), K(i)), схематически показанную на рисунке 3.2.

 

 

Рисунок 3.2 – Вычисление функции F(R(i−1), K(i))

 

Для вычисления значения функции F используются следующие функции-матрицы:

– Е – расширение 32-битовой последовательности до 48-битовой;

– S1, S2,..., S8 – преобразование шестибитового блока в четырехбитовый;

– Р – перестановка битов в 32-битовой последовательности.

Функция расширения Е определяется таблицей 3.4: первые три бита Е(R(i−1)) – это биты 32, 1 и 2, а последние – 31, 32 и 1.

Таблица 3.4 – Функция расширения E 32 01 02 03 04 05 04 05 06 07 08 09 08 09 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 01

Результатом функции Е(R(i−1)) является 48-битовая последовательность, которая складывается по модулю 2 (операция Å) с
48-битовым ключом К(i). Получается
48-битовая последовательность, которая разбивается на восемь шестибитовых блоков B(1)B(2)B(3)B(4)B(5)B(6)B(7)B(8), а именно:

 

E(R(i−1)) Å K(i) = B(1)B(2)...B(8).                        (3.3)

 

Функции S1, S2,..., S8 определяются таблицей 3.5. Пусть на вход функции-матрицы Sj поступает шестибитовый блок B(j) = b1b2b3b4b5b6, тогда двухбитовое число b1b6 указывает номер строки матрицы, а b2b3b4b5 – номер столбца. Результатом Sj(B(j)) будет четырехбитовый элемент, расположенный на пересечении указанных строки и столбца. Например, В(1) = 011011. Тогда S1(В(1)) расположен на пересечении строки 1 и столбца 13. В столбце 13 строки 1 задано значение 5. Значит, S1(011011) = 0101. Применив операцию выбора к каждому из   шестибитовых блоков B(1), B(2),..., B(8),     получаем

32-битовую последовательность S1(B(1))S2(B(2))S3(B(3))...S8(B(8)).

Для получения результата функции шифрования надо переставить биты этой последовательности. Для этого применяется функция перестановки P (таблица 3.6). Во входной последовательности биты перестанавливаются так, чтобы бит 16 стал битом 1, а бит 7 – битом 2 и т.д. Таким образом:

 

F(R(i−1), K(i)) = P(S1(B(1)),...S8(B(8))).                (3.4)

 

Чтобы завершить описание алгоритма шифрования данных, проведем алгоритм получения 48-битовых ключей К(i), i = 1,..., 16. На каждой итерации используется новое значение ключа K(i),  которое вычисляется из начального ключа K. K представляет собой 64-битовый блок с восемью битами контроля по четности, расположенными в позициях 8, 16, 24, 32, 40, 48, 56, 64.

Для удаления контрольных битов и перестановки остальных используется функция G первоначальной подготовки ключа (таблица 3.7). Результат преобразования G(K) разбивается на два 28-битовых блока C(0) и D(0), причем C(0) будет состоять из битов 57, 49,..., 44, 36 ключа K, а D(0) – из битов 63, 55,..., 12, 4 ключа K. После определения C(0) и D(0) рекурсивно определяются C(i) и D(i), i = 1,..., 16. Для этого применяют циклический сдвиг влево на один или два бита в зависимости от номера итерации (таблица 3.8). Полученное значение вновь «перемешивается» в соответствии с матрицей H (таблица 3.9).

Ключ K(i) будет состоять из битов 14, 17,..., 29, 32 последовательности C(i)D(i). Таким образом:

 

K(i) = H(C(i)D(i)).                         (3.5)

 

Блок-схема алгоритма вычисления ключа приведена на рисунке 3.3.

Таблица 3.5 – Функции преобразования S

Функции S   0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 2 4 1 4 8 13 6 2 11 15 12 9 7 3 10 5 0 3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 0 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10 1 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5 2 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15 3 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9 0 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8 1 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1 2 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7 3 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12 0 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15 1 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9 2 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4 3 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14

Функции S   0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9 1 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6 2 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14 3 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3 0 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11 1 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8 2 9 14 15 5 2 8 12 3 7 0 4 10 1 13 1 6 3 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13 0 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1 1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 2 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2 3 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12 0 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7 1 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2 2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8 3 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11

Потоковое шифрование

 

Суть потокового шифрования заключается в преобразовании исходного текста в шифрованный по биту, а не блоками. Часто потоковое шифрование называют гаммированием в соответствии с одним из способов потокового криптопреобразования – сложением по модулю 2 битов открытого текста с битами псевдослучайной последовательности (ПСП) [5].

Потоковые шифры по сравнению с блочными обладают рядом достоинств: более высокая скорость шифрования, относительная простота реализации и отсутствие размножение ошибок. Недостаток заключается в необходимости передачи информации синхронизации перед заголовком сообщения, которая должна быть принята до дешифрования сообщения [5].

Для дешифрования на приемной стороне ключевая принятая последовательность складывается по модулю 2 с ключевой последовательностью для получения исходного текста:

– шифрование:

 

C_i = P_i Å T_i;                                      (3.6)

 

где C_i – зашифрованный текст; P_i – исходный текст; T_i – ключевая последовательность; Å – операция сложения по модулю 2;

 

– дешифрование:

 

P_i= C_iÅ T_i = P_i Å T_i Å T_i.                          (3.7)

 

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

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

В настоящее время наиболее доступными и эффективными являются конгруэнтные генераторы ПСП. Одним из хороших конгруэнтных генераторов является линейный конгруэнтный датчик ПСП. Он вырабатывает последовательности псевдослучайных чисел T(i), описываемые соотношением:

 

T_i+1 = (A·T_i + C) mod m,                           (3.8)

 

где А и С – константы, от которых зависит период генерируемой псевдослучайной последовательности;

Т₀ – исходная величина, выбранная в качестве порождающего числа.

m = 2^s (обычно), где s – длина слова в битах.

 

Как показано Д. Кнутом, линейный конгруэнтный датчик ПСЧ имеет максимальную длину m тогда, когда С – нечетное и А mod 4 = 1.