Войти

Приложения и утилиты

Алгоритмы шифрования – участники конкурса NESSIE. Часть 2

Вторая и третья части статьи посвящены 128-битным алгоритмам блочного шифрования, не вышедшим во второй раунд конкурса NESSIE. Начнем с алгоритма Anubis.

Алгоритм Anubis

Блочный шифр Anubis разработан специально для участия в конкурсе NESSIE интернациональным дуэтом авторов: бельгийцем Винсентом Риджменом (Vincent Rijmen) и бразильцем Пауло Баррето (Paulo S.L.M. Barreto).

Алгоритм назван в честь древнеегипетского бога Анубиса – бога бальзамирования (embalming) и погребения (entombment); к его ведению авторы алгоритма решили отнести и криптографию [1].

Anubis шифрует данные блоками по 128 бит с использованием ключа размером от 128 до 320 бит; размер ключа должен быть кратен 32 битам.

Данный алгоритм продолжает серию алгоритмов, соавтором которых является Винсент Риджмен: Square, Shark и Rijndael (подробное описание этих алгоритмов на русском языке можно найти, например, в статьях [17], [18] и [19], соответственно). Все эти алгоритмы объединяет их относительно редко встречающаяся (напротив, частая среди алгоритмов – участников конкурса NESSIE) структура типа «квадрат» (square) – см. статью «Назначение и структура алгоритмов шифрования» – и весьма схожий набор выполняемых преобразований.

Структура алгоритма

Алгоритм представляет блок шифруемых данных в виде 16-байтового массива, который для удобства описания представлен виде квадрата 4 * 4 байт. В каждом раунде алгоритма выполняются следующие действия [1]:

Табличная замена

, выполняемая, согласно следующей таблице S (см. рис. 1): Операция y алгоритма Anubis

Рис. 1. Операция

алгоритма Anubis

A7	D3	E6	71	D0	AC	4D	79
3A	C9	91	FC	1E	47	54	BD
8C	A5	7A	FB	63	B8	DD	D4
E5	B3	C5	BE	A9	88	0C	A2
39	DF	29	DA	2B	A8	CB	4C
4B	22	AA	24	41	70	A6	F9
5A	E2	B0	36	7D	E4	33	FF
60	20	08	8B	5E	AB	7F	78
7C	2C	57	D2	DC	6D	7E	0D
53	94	C3	28	27	06	5F	AD
67	5C	55	48	0E	52	EA	42
5B	5D	30	58	51	59	3C	4E
38	8A	72	14	E7	C6	DE	50
8E	92	D1	77	93	45	9A	CE
2D	03	62	B6	B9	BF	96	6B
3F	07	12	AE	40	34	46	3E
DB	CF	EC	CC	C1	A1	C0	D6
1D	F4	61	3B	10	D8	68	A0
B1	0A	69	6C	49	FA	76	C4
9E	9B	6E	99	C2	B7	98	BC
8F	85	1F	B4	F8	11	2E	00
25	1C	2A	3D	05	4F	7B	B2
32	90	AF	19	A3	F7	73	9D
15	74	EE	CA	9F	0F	1B	75
86	84	9C	4A	97	1A	65	F6
ED	09	BB	26	83	EB	6F	81
04	6A	43	01	17	E1	87	F5
8D	E3	23	80	44	16	66	21
FE	D5	31	D9	35	18	02	64
F2	F1	56	CD	82	C8	BA	F0
EF	E9	E8	FD	89	D7	C7	B5
A4	2F	95	13	0B	F3	E0	37

Значения таблицы выбраны псевдослучайным образом с учетом необходимости ее соответствия следующему соотношению:

S[S[x]] = x.

Операция – байтовая перестановка, простейшим образом преобразующая строку обрабатываемого блока ключевой информации в столбец (см. рис. 2):
Рис. 2. Операция алгоритма Anubis
b_i,j = a_j,i,

где a_i,j и b_i,j – байты массива данных до и после выполнения текущей операции, соответственно.
Операция , представляющая собой умножение массива на фиксированную матрицу H (см. рис. 3):
Рис. 3. Операция алгоритма Anubis

1 2 4 6
2 1 6 4
4 6 1 2
6 4 2 1
Умножение выполняется в конечном поле GF(2⁸).
Наложение ключа r-го раунда k[r] (процедура расширения ключа будет подробно описана далее); выполняется побитовой логической операцией «исключающее или» (XOR), применяемой к каждому биту массива данных и соответствующему биту k[r] (см. рис. 4):
Рис. 4. Операция алгоритма Anubis
b_i,j = a_i,j k[r]_i,j.

Данная операция обозначается как .

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

Стоит отметить, что все перечисленные операции являются обратными самим себе, соответственно, расшифрование выполняется с помощью тех же операций в том же порядке, что и при зашифровании. Меняется только порядок использования подключей на обратный.

Число раундов алгоритма R зависит от размера ключа шифрования и определяется следующим образом:

R = 8 + N,

где N – размер ключа в 32-битных фрагментах.

Некоторые криптоаналитики считают, что число раундов в алгоритме Anubis несколько завышено, видимо, с целью обеспечить более высокий запас криптостойкости [3].

Процедура расширения ключа

Процедура расширения ключа достаточно проста и основана, практически, на той же последовательности операций, которые применяются в раундах алгоритма. Расширение ключа выполняется следующим образом: сначала исходный ключ шифрования K представляется в виде байтового массива 4 * 4 (что обозначается как KI₀), после чего в цикле выполняются следующие операции:

Итеративно вычисляются остальные промежуточные ключи KI₁...KI_R:
KI_j = f(KI_j-1),

где f() – совокупность операций , , и ; в операции в качестве ключа раунда используется соответствующая из констант c[r], которые, в свою очередь, определяются следующим образом:
c[r]_0,j = S[4 * (r – 1) + j]

для j = 0...3 (см. описание операции ). Остальные байты c[r]_i,j являются нулевыми.
Операция – циклический сдвиг столбцов таблицы вниз по следующему простому правилу: j-й столбец сдвигается на j позиций (см. рис.5).
Рис. 5. Операция алгоритма Anubis
На основе предварительных ключей вычисляются подключи k₀...k_r:
k_r = g(KI_r),

где функция g() представляет собой последовательное выполнение следующих операций: .
Операции и были описаны выше, а представляет собой умножение блока на фиксированную матрицу V (аналогично операции – см. рис. 3), определенную следующим образом:

1 1 1 1
1 2 4 8
1 6 36 216
1 8 64 0
Стоит отметить, что при зашифровании данных процедура расширения ключа позволяет вычислять ключи «на лету», т.е. по мере необходимости. Однако, при расшифровании необходимо полностью выполнить расширение ключа до начала преобразований.
Достоинства и недостатки алгоритма
Прежде всего, стоит сказать, что на конкурсе NESSIE была рассмотрена нескоько модифицированная версия алгоритма Anubis, отличие которой от описанной здесь состояло лишь в операции . Модифицированная операция вместо одной табличной замены 8 * 8 бит выполняла 3 уровня табличных замен 4 * 4. Данная модификация произведена для упрощения аппаратной реализации алгоритма [12].
Anubis был признан одним из наиболее быстродействующих алгоритмов шифрования (из участников конкурса) [13]. Еще одно явное достоинство алгоритма – отсутствие проблем с криптостойкостью [14]. Однако, злую шутку с алгоритмом Anubis сыграло его сходство с алгоритмом Rijndael (который, как известно, является новым стандартом шифрования США под названием AES [7] – см. статью «Алгоритмы шифрования – финалисты конкурса AES»), который также рассматривался в рамках конкурса NESSIE. Эксперты конкурса посчитали, что при таком явном сходстве Anubis не может иметь настолько серьезных преимуществ перед алгоритмом Rijndael, которые позволили бы ему выиграть у Rijndael в финале конкурса NESSIE [13, 15]. Поэтому Anubis не выбран во второй этап конкурса.
Алгоритм Grand Cru
Алгоритм Grand Cru разработан специально для участия в конкурсе NESSIE. Автор алгоритма – Йохан Борст (Johan Borst) из Католического Университета г. Лювен, Бельгия.
Как и алгоритм Anubis, Grand Cru имеет структуру «квадрат». Данный алгоритм основан на алгоритме Rijndael, разработанном, как известно, Джоан Деймен (Joan Daemen) и упомянутым выше Винсентом Риджменом. Несомненно, тот факт, что Rijndael выиграл конкурс AES и в настоящее время является стандартом шифрования США AES, сподвигнул некоторых разработчиков алгоритмов шифрования на конструирование блочных шифров на его основе. Один из них – Anubis – был рассмотрен выше. Grand Cru – второй пример; фактически, он является глубокой модификацией алгоритма Rijndael.
Как известно, среди четырех преобразований данных в каждом раунде алгоритма Rijndael существует только одна операция (наложение подключа операцией XOR), выполняющая зависящие от ключа преобразования [7]. По мнению автора алгоритма Grand Cru, увеличение количества ключевых преобразований в раунде алгоритма усилит криптостойкость алгоритма при том же количестве раундов или позволит уменьшить количество раундов (чем увеличить скорость шифрования) при заданном уровне криптостойкости. Соответственно, раунд Grand Cru – это, фактически, раунд Rijndael с добавлением двух ключевых операций вместо одной бесключевой [4].
Алгоритм Grand Cru шифрует данные блоками по 128 бит с использованием только 128-битного ключа шифрования.
Структура алгоритма
Как было сказано выше, алгоритм имеет структуру «квадрат»: аналогично рассмотренному выше алгоритму Anubis, при шифровании данные представляются в виде таблицы 4 * 4 байт. Каждый раунд подразумевает выполнение следующих операций:
1. Наложение фрагмента ключа r-го раунда k[r, 0] (см. ниже), которое выполняется с помощью операции XOR полностью аналогично операции алгоритма Anubis – см. рис. 4 (однако, в спецификации алгоритма Grand Cru [4] используется обратная нумерация столбцов – справа налево – как на рис. 6). Данная операция в алгоритме Grand Cru также обозначается как .
Рис. 6. Первый этап перестановки алгоритма Grand Cru
Как было сказано выше, раунд алгоритма содержит 3 операции с участием фрагментов расширенного ключа. Обозначим эти фрагменты следующим образом:
- k[r, 0] – 128-битный фрагмент ключа раунда k[r] для наложения ключа,
- k[r, 1] – 40-битный фрагмент для описанной ниже операции ,
- k[r, 2] – 48-битный фрагмент для операции .

Табличная замена

, замещающая каждый байт массива согласно следующей таблице S:

99	124	119	123	242	107	111	197
48	1	103	43	254	215	171	118
202	130	201	125	250	89	71	240
173	212	162	175	156	164	114	192
183	253	147	38	54	63	247	204
52	165	229	241	113	216	49	21
4	199	35	195	24	150	5	154
7	18	128	226	235	39	178	117
9	131	44	26	27	110	90	160
82	59	214	179	41	227	47	132
83	209	0	237	32	252	177	91
106	203	190	57	74	76	88	207
208	239	170	251	67	77	51	133
69	249	2	127	80	60	159	168
81	163	64	143	146	157	56	245
188	182	218	33	16	255	243	210
205	12	19	236	95	151	68	23
196	167	126	61	100	93	25	115
96	129	79	220	34	42	144	136
70	238	184	20	222	94	11	219
224	50	58	10	73	6	36	92
194	211	172	98	145	149	228	121
231	200	55	109	141	213	78	169
108	86	244	234	101	122	174	8
186	120	37	46	28	166	180	198
232	221	116	31	75	189	139	138
112	62	181	102	72	3	246	14
97	53	87	185	134	193	29	158
225	248	152	17	105	217	142	148
155	30	135	233	206	85	40	223
140	161	137	13	191	230	66	104
65	153	45	15	176	84	187	22

Данная операция также аналогична (но с другой таблицей замен) операции алгоритма Anubis – см. рис. 1.

Зависящая от ключа перестановка . Использует 5-байтный фрагмент расширенного ключа k[r, 1], причем процедура расширения ключа гарантирует, что значение каждого байта k[r, 1] лежит в диапазоне от 1 до 24 включительно. Перестановка выполняется в 5 этапов:
- На первом этапе выполняется перестановка строк массива данных. Для этого по первому байту ключа k[r, 1] (обозначим его значение как x) из следующей таблицы выбирается константа t_x:
  
  x tx
  1 78
  2 36
  3 2D
  4 C9
  5 93
  6 72
  7 4B
  8 9C
  9 87
  10 63
  11 D2
  12 39
  13 8D
  14 1E
  15 E4
  16 B4
  17 6C
  18 D8
  19 E1
  20 C6
  21 27
  22 B1
  23 4E
  24 1B
  t_x представляется в виде четырех 2-битных значений t_x[0]...t_x[3]; подбор констант t_x гарантирует, что значения t_x[0]...t_x[3] представляют собой последовательность из неповторяющихся значений от 0 до 3 включительно, например, для x = 1:
  t_x[0] = 1,
  t_x[1] = 3,
  t_x[2] = 2,
  t_x[3] = 0.
  Перестановка строк состоит в том, что i-я строка массива данных заменяется строкой, номер которой определяется значением t_x[i] (см. пример для x = 1 на рис. 6).
- Со второго по пятый этапы выполняют перестановку байт одного из столбцов массива данных: i-й этап переставляет байты i-2-го столбца, руководствуясь значением t_x, выбираемым из приведенной выше таблицы согласно x – значению i-го байта ключа k[r, 1]. Перестановка байт выполняется абсолютно аналогично описанной выше перестановке строк – см. пример для этапа 2 и x = 2 на рис. 7.
  Рис. 7. Второй этап перестановки алгоритма Grand Cru
Операция – умножение обрабатываемой таблицы на фиксированную матрицу H – аналогично одноименной операции Anubis (см. рис. 3). Матрица H унаследована от алгоритма Rijndael, в котором она определена следующим образом [7]:

2 3 1 1
1 2 3 1
1 1 2 3
3 1 1 2

Зависящее от ключа вращение (операция

) каждого байта массива на переменное число бит, определяемое значениями соответствующих бит фрагмента ключа r-го раунда k[r, 2] (см. рис. 8):

Рис. 8. Операция

алгоритма Grand Cru

b_i,j = a_i,j <<< x_i,j,

где в качестве x_i,j используются значения трех последовательных бит фрагмента k[r, 2] в соответствии со следующей таблицей:

i	j	Используемые биты k[r, 2]
3	3	45, 46, 47
3	2	42, 43, 44
3	1	39, 40, 41
3	0	36, 37, 38
2	3	33, 34, 35
2	2	30, 31, 32
2	1	27, 28, 29
2	0	24, 25, 26
1	3	21, 22, 23
1	2	18, 19, 20
1	1	15, 16, 17
1	0	12, 13, 14
0	3	9, 10, 11
0	2	6, 7, 8
0	1	3, 4, 5
0	0	0, 1, 2

Таким образом, раунд алгоритма состоит из последовательно выполняемых операций: . Кроме того, перед первым по порядку (при зашифровании раунды нумеруются от 8 до 0) раундом выполняются операции и (составляющие предварительное преобразование), которые будут подробно описаны ниже. После последнего раунда выполняется заключительное преобразование – последовательность операций: , где ^-1 – операция, обратная к , также подробно описана ниже. Происхождение фрагментов расширенного ключа, используемых в ключевых операциях предварительного и заключительного преобразований, будет приведено в описании процедуры расширения ключа.

Операции , выполняемые перед первым и после последнего раунда алгоритма, представляют собой входное и выходное отбеливание данных соответственно. Данные операции накладывают на обрабатываемый блок данных соответствующие фрагменты ключа (обозначим их kwi и kwo) с помощью операции сложения по модулю 256 (см. рис. 9). Операция алгоритма Grand Cru

Рис. 9. Операция

алгоритма Grand Cru

Например, для входного отбеливания:

b_i,j = a_i,j + kwi_i,j mod 256.

представляет собой операцию бесключевого рассеивания данных и выполняется в два этапа:

В цикле по n от 0 до 15 выполняется следующее действие:
b_{n+1 mod 16} = a_{n+1 mod 16} S(a_n),
где a_x и b_x – значения x-го байта данных до и после выполнения текущего действия соответственно (в данном случае блок данных представляется не в виде таблицы, а в виде последовательности байт).
В цикле по n1 от 0 до 15 выполняется цикл по n2 от 0 до 15, в котором выполняется следующее действие:
b_n2 = a_n2 S(a_n1).
Данное действие не выполняется при n2 = n1.

Обратная к операция ^-1 определена так:

В цикле по n1 от 15 до 0 выполняется цикл по n2 от 15 до 0 (кроме шага, в котором n2 = n1), в котором выполняется следующее действие:
b_n2 = a_n2 S(a_n1).
В цикле по n от 0 до 15 выполняется следующее действие:
b_{n+1 mod 16} = a _{n+1 mod 16} S(a_n).

Расшифрование

Расшифрование выполняется применением обратных операций в обратной последовательности:

Обратное заключительное преобразование: , где – обратные операции к , , и соответственно и будут описаны ниже (обратная операция к эквивалентна самой операции ).
9 раундов (от 0-го до 8-го), в каждом из которых выполняется следующая последовательность действий: , где ^-1 – операция, обратная к .
Обратное предварительное преобразование, состоящее из двух операций: ^-1 и ^-1.

^-1 выполняет наложение фрагментов расширенного ключа kwo и kwi путем вычитания по модулю 256, например:

b_i,j = a_i,j - kwi_i,j mod 256.

^-1 выполняется аналогично операции , однако, вращение каждого байта блока данных выполняется не влево, а вправо:

b_i,j = a_i,j >>> x_i,j.

^-1 – обратная перестановка относительно операции – ее этапы выполняются в обратной последовательности; кроме того, в каждом этапе выполняется обратная перестановка.

^-1 аналогична прямой операции ^-1, но замена выполняется с помощью обратной таблицы S^-1.

^-1 представляет собой умножение блока данных на обратную к H матрицу H^-1, которая определена так:

E	B	D	9
9	E	B	D
D	9	E	B
B	D	9	E

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

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

Прежде всего, вычисляется последовательность промежуточных ключей K₀...K₃ следующим образом:

128-битный исходный ключ шифрования представляется в виде четырех столбцов, которые обозначаются K₀’...K₃’.
Формируется последовательность столбцов K₄’...K₁₅’ путем следующих действий:
K’_i = K’_i-4 G(R(K’_i-1) c_i/4),
если i кратно четырем, иначе:
K’_i = K’_i-4 K’_i-1.
Функция R() представляет собой побайтное вращение обрабатываемого столбца на 1 байт вверх.
Функция G() обрабатывает каждый байт столбца с помощью описанной выше таблицы замен S, т.е. x-й байт столбца a_x заменяется значением S(a_x).
Модифицирующие константы c_x взяты из алгоритма Rijndael, где они определены согласно следующей таблице:

x cx
1 1
2 2
3 4
В принципе, в алгоритме может использоваться ключ шифрования, больший 128 бит, но не превышающий 512 бит и кратный 32 битам. В этом случае последовательность K₀’...K₁₅’ заполняется аналогичным образом 32-битными фрагментами ключа шифрования, насколько это возможно, а недостающие столбцы рассчитываются согласно приведенным выше формулам.
Из столбцов, рассчитанных на предыдущем шаге, формируется последовательность промежуточных ключей K₀...K₃:
K_i = (K’_4i+3 | K’_4i+2 | K’_4i+1 | K’_4i).

Совокупность преобразований, используемых для получения промежуточного ключа K_i из исходного ключа шифрования (обозначим его KU) обозначим следующим образом:

K_i = F(KU, i).

В дальнейшем, с помощью аналогичных преобразований вычисляются необходимые подключи:

Для операции требуются 9 128-битных подключей k[0, 0]...k[8, 0] – по одному для каждого раунда алгоритма, а также 2 подключа (k[9, 0] и k[10, 0]), поочередно используемые в заключительном преобразовании (в обратном заключительном преобразовании эти два подключа используются в обратном порядке). Данные 11 подключей вычисляются на основе промежуточного ключа K₀ следующим образом:
k[i, 0] = F(K₀, i).
Операция использует два 128-битных подключа kwi и kwo, которые вычисляются так:
kwi = F(K₃, 0),
kwo = F(K₃, 1).
При расшифровании kwi и kwo применяются в обратном порядке.
Для операции требуются 48-битные подключи k[0, 2]...k[8, 2] – по одному для каждого раунда, а также k[9, 2] для заключительного преобразования. Эти подключи вычисляются следующим образом: для каждого i = 0...9 выполняются следующие действия:
- вычисляется еще один промежуточный ключ:
  K = F(K₂, i);
- вычисляется k[i, 2]:
  k[i, 2] = LSB₃(K₁₅) | LSB₃(K14) | ... | LSB₃(K₀),
  где K_x – x-й байт промежуточного ключа K,
  | – операция конкатенации,
  а LSB₃(X) – три младших бита значения X.
Для операции требуется 10 40-битных подключей: k[0, 1]...k[8, 1] для 9 раундов алгоритма и k[9, 1] для заключительного преобразования. Эти подключи для i = 0...9 вычисляются так:
- вычисляется промежуточный ключ:
  K = F(K₁, i);
- K представляется в виде байтового массива из 16 элементов: K₀...K₁₅.
- Из данного массива набираются первые 5 байт из тех, значения которых попадают в требуемый диапазон: от 1 до 24. Если в массиве таких байт меньше пяти, недостаточное количество набирается с начала массива, в качестве значения байта ключа берется остаток от деления значения используемого байта массива на 16 (вместо 0 используется значение 16).

Достоинства и недостатки алгоритма

Как видно из приведенного выше описания алгоритма Grand Cru, данный алгоритм является весьма сложным; причем, сложным и запутанным выглядит как шифрование, так и процедура расширения ключа. Из избыточной сложности алгоритма следует тот факт, что алгоритм Grand Cru оказался самым медленным (причем, с огромным отрывом от быстродействия большей части других алгоритмов) среди всех участников конкурса [14].

В процессе изучения алгоритма в рамках конкурса NESSIE в нем не было обнаружено каких-либо слабостей, и, соответственно, каких-либо атак на данный алгоритм [16]. Тем не менее, эксперты конкурса посчитали, что возможно высокая (но недоказанная) криптостойкость данного алгоритма не компенсирует ужасающе низкой скорости шифрования, поэтому Grand Cru не был выбран во второй раунд конкурса [13].

Алгоритм Noekeon

Алгоритм Noekeon разработан в 2000 г. коллективом разработчиков из Бельгии, авторы алгоритма:

Джоан Деймен, Михаэль Петерс (Michael Peeters) и Жиль Ван Аске (Gilles Van Assche) из компании Proton World,
Винсент Риджмен из Католического Университета г. Лювен.

И снова вспомним алгоритм Rijndael, поскольку среди автором алгоритма Noekeon присутствуют оба автора Rijndael – Джоан Деймен и Винсент Риджмен. Однако, Noekeon несравнимо меньше похож на Rijndael, чем рассмотренные ранее Anubis и Grand Cru.

Noekeon шифрует данные 128-битными блоками с использованием 128-битного ключа шифрования. Алгоритм существует в двух режимах: прямом (direct mode) и косвенном (indirect mode), разница между которыми существует лишь в процедуре расширения ключа; оба режима будут рассмотрены ниже.