30 июня 2014

Облегченный алгоритм шифрования Curupira

С.П. Панасенко,
зам. директора Фирмы «АНКАД»
по науке и системной интеграции,
кандидат технических наук.

Алгоритм шифрования Curupira разработан в 2007 г. Авторы алгоритма: Пауло Баррето (Paulo S.L.M. Barreto) и Маркос Симплисио (Marcos A. Simplício Jr.) из Университета г. Сан-Паулу, Бразилия.

Пауло Баррето известен как один из соавторов целого ряда криптографических алгоритмов, в частности, алгоритмов шифрования Anubis [1] и Khazad [2], принимавших участие в европейском криптопроекте NESSIE [3], а также известного алгоритма хэширования Whirlpool [4]. Алгоритм Curupira унаследовал часть преобразований от данных алгоритмов.

Алгоритм Curupira позиционируется авторами как облегченный криптоалгоритм, т.е. предназначенный для устройств с ограниченными ресурсами, например, различных датчиков, беспроводных сенсоров, радиочастотных идентификаторов и т.п.

Необычно название алгоритма шифрования – как сказано в [5], «Curupira – это дух природы и защитник лесов. Он выглядит как рыжеволосый мальчик, ступни которого повернуты задом наперед, что сбивает охотников со следа».

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

Curupira шифрует данные 96-битными блоками с использованием ключа одного из следующих фиксированных размеров: 96, 144 и 192 бит. Блок данных представляется в виде байтового массива размером 3 X 4 (называемого состоянием алгоритма), над которым в каждом раунде выполняется следующая последовательность операций [6]:

Операция γ: табличная замена каждого байта обрабатываемого блока данных согласно следующей таблице S (см. рис. 1):

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

Рис. 1. Табличная замена

Здесь и далее символами a_i,j обозначены байты состояния до выполнения конкретной операции, b_i,j – после выполнения.

Аналогичная таблица замен используется в алгоритмах Anubis и Khazad (существуют варианты данных алгоритмов и с другой таблицей замен – см. [7]).

Данная таблица замен является суперпозицией двух других таблиц (замещающих 4-битные значения): P и Q. Схема вычисления таблицы S из P и Q приведена на рис. 2 [5]. Сами таблицы P и Q приведены далее.

Рис. 2. Структура таблицы S

Таблица P:

Таблица Q:

В зависимости от ресурсов шифратора, таблица S может быть реализована как с помощью приведенных таблиц P и Q, так и напрямую.

Операция π: байтовая перестановка в пределах строк таблицы по следующему правилу (см. рис 3):

b_i,j = a_i,i_ j, i = 0, 1, 2, j = 0…n,

где n – количество столбцов состояния алгоритма.

Рис. 3. Байтовая перестановка

Операция θ: рассеивающее линейное преобразование, выполняемое путем умножения в поле GF(256) матрицы D на состояние алгоритма (см. рис. 4).

Рис. 4. Рассеивающее преобразование

Матрица D определена следующим образом:

3	2	2
4	5	4
6	6	7

Операция σ(K_r): наложение ключа r-го раунда K_r (см. рис. 5):

b_i_,j = a_i_,j  k_i_,j, i = 0, 1, 2, j = 0…n,

где k_i_,_j – байты ключа раунда (процедура расширения ключа будет описана далее).

Рис. 5. Наложение ключа

Количество раундов алгоритма не является строго определенным; для каждого из фиксированных размеров ключа предусмотрено минимальное и максимальное количество раундов согласно следующей таблице:

Размер ключа в битах	Количество раундов
96	10–11
144	14–17
192	18–23

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

Последний раунд отличается от остальных тем, что в нем не выполняется операция θ.

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

Ключ шифрования, в зависимости от его размера, представляется в виде байтового массива размером 3 X 4, 3 X 6 или 3 X 8 (ключевого массива). Массив инициализируется байтами ключа последовательно по столбцам, а не по строкам.

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

Операция σ(q_r): наложение раундовой константы q_r, которое выполняется с помощью операции XOR аналогично описанной выше операции σ(K_r). Раундовые константы будут приведены далее.
Операция ξ: циклический сдвиг строк массива (см. на рис. 6 вариант для 96-битного ключа):
- первая строка не меняется;
- вторая строка сдвигается на 1 байт влево;
- третья строка сдвигается на 1 байт вправо.

Рис. 6. Циклический сдвиг строк

Символами K_ij на рис. 6 обозначены байты ключевого массива.

Операция μ: умножение в поле GF(2⁸) матрицы E на ключевой массив. Матрица E определена следующим образом:

1+c	c	c
c	1+c	c
c	c	1+c

где c(x) = x⁴ + x³ + x².

Раундовые константы q_r (для r = 1…N, где N – количество раундов алгоритма) представляют собой массивы, аналогичные по размерности ключевому массиву. Байты данных констант являются нулевыми, за исключением первой строки, байты которой (обозначим байты констант q_r как q_r[i, j]) вычисляются следующим образом (принцип вычисления раундовых констант также унаследован от алгоритма Anubis):

q_r[0,j] = S(2t * (r - 1) + j), j = 0…t,

где:

t – размер ключа в 48-битных фрагментах;

S() – описанная выше таблица замен.

Байты ключей раундов k_ij выбираются из ключевого массива по мере необходимости следующим образом:

k_0j = S(K_0j) для i = 0, j = 0…3;
k_ij = K_ij для i > 0, j = 0…3.

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

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

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

Литература

Barreto P. S. L. M., Rijmen V. The Anubis Block Cipher. // http://www.cosic.esat.kuleuven.be.
Barreto P. S. L. M., Rijmen V. The Khazad Legacy-Level Block Cipher. // http://www.cosic.esat.kuleuven.be.
Van Rompay B. NESSIE Public Report D02: Report on the NESSIE Call. // http://www.cosic.esat.kuleuven.be.
Barreto P. S. L. M., Rijmen V. The Whirlpool Hashing Function. // http://www.larc.usp.br – Revised on May 24, 2003.
Barreto P. S. L. M., Simplício M. A. Jr. CURUPIRA-1, a block cipher for constrained platforms – extended version. // http://www.larc.usp.br – Universidade de São Paulo, Brazil.
Barreto P. S. L. M., Simplício M. A. Jr. CURUPIRA, a block cipher for constrained platforms. // http://bibliotecadigital.sbc.org.br – SBRC 2007 – Universidade de São Paulo, Brazil.
Панасенко С. П. Алгоритмы шифрования. Специальный справочник. – СПб.: БХВ-Петрбург, 2009 – 576 с.

Просмотров: 1513

Мнения экспертов

Веретенников А.А.
-
кандидат технических наук

Автор в своей работе обращает внимание читателей на одного из представителей семейства, так называемых, «lightweight cryptography» - алгоритмов. Эта тема достаточна актуальна в связи с широкой распространенностью устройств с ограниченными ресурсами, с одной стороны, и необходимостью обеспечить защиту обрабатываемых такими устройствами данных – с другой. Принятие в 2012 г. семейства стандартов ISO/IEC 29192 – подтверждает такую тенденцию. Как и в других своих работах, Сергей Петрович полностью раскрывает тему, при этом использует в необходимом объеме поясняющие элементы и ссылки на источники информации. Считаю, что данная работа подлежит публикации на портале и будет интересна широкому кругу читателей.