Кузнечик (шифр)

Шаблон:Другие значения Шаблон:Карточка блочного шифра «Кузнечик» (Шаблон:Lang-en^[1] или Шаблон:Lang-en^[2]^[3]) — симметричный алгоритм блочного шифрования с размером блока 128 бит и длиной ключа 256 бит, использующий для генерации раундовых ключей SP-сеть.

Общие сведения

Данный шифр утверждён (наряду с блочным шифром «Магма») в качестве стандарта в ГОСТ Р 34.12-2015 «Информационная технология. Криптографическая защита информации. Блочные шифры» приказом от 19 июня 2015 года № 749-ст^[4]. Стандарт вступил в действие с 1 января 2016 года^[5]. Шифр разработан Центром защиты информации и специальной связи ФСБ России с участием АО «Информационные технологии и коммуникационные системы» (АО «ИнфоТеКС»). Внесён Техническим комитетом по стандартизации ТК 26 «Криптографическая защита информации»^[6]^[7].

Протоколом № 54 от 29 ноября 2018 года, на основе ГОСТ Р 34.12-2015, Межгосударственным советом по метрологии, стандартизации и сертификации был принят межгосударственный стандарт ГОСТ 34.12-2018. Приказом Федерального агентства по техническому регулированию и метрологии от 4 декабря 2018 года № 1061-ст стандарт ГОСТ 34.12-2018 введен в действие в качестве национального стандарта Российской Федерации с 1 июня 2019 года.

Обозначения

$𝔽$ — поле Галуа $G F (2^{8})$ по модулю неприводимого многочлена $x^{8} + x^{7} + x^{6} + x + 1$ .

$B i n_{8} : ℤ_{p} \to V_{8}$ — биективное отображение, ставящее в соответствие элементу кольца $ℤ_{p}$ ( $p = 2^{8}$ ) его двоичное представление.

${B i n_{8}}^{- 1} : V_{8} \to ℤ_{p}$ — отображение, обратное к $B i n_{8}$ .

$δ : V_{8} \to 𝔽$ — биективное отображение, ставящее в соответствие двоичной строке элемент поля $𝔽$ .

$δ^{- 1} : 𝔽 \to V_{8}$ — отображение, обратное к $δ$

Описание алгоритма

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

$A d d_{2} [k] (a) = k \oplus a$ , где $k$ , $a$ — двоичные строки вида $a = a_{15} | |$ … $| | a_{0}$ ( $| |$ — символ конкатенации строк).

$N (a) = S (a_{15}) | |$ … $| | S (a_{0}) . N^{- 1} (a)$ — обратное к $N (a)$ преобразование.

$G (a) = γ (a_{15},$ … $, a_{0}) | | a_{15} | |$ … $| | a_{1} .$

$G^{- 1} (a)$ — обратное к $G (a)$ преобразование, причём $G^{- 1} (a) = a_{14} | | a_{13} | |$ … $| | a_{0} | | γ (a_{14}, a_{13},$ … $, a_{0}, a_{15}) .$

$H (a) = G^{16} (a)$ , где $G^{16}$ — композиция преобразований $G^{15}$ и $G$ и т. д.

$F [k] (a_{1}, a_{0}) = (H N A d d_{2} [k] (a_{1}) \oplus a_{0}, a_{1}) .$

Нелинейное преобразование

Нелинейное преобразование задается подстановкой S = Bin₈ S' Bin₈⁻¹.

Значения подстановки S' заданы в виде массива S' = (S'(0), S'(1), …, S'(255)):

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

Линейное преобразование

Задаётся отображением $γ$ :

$γ (a_{15},$ … $, a_{0}) = δ^{- 1} (148 * δ (a_{15}) + 32 * δ (a_{14}) + 133 * δ (a_{13}) + 16 * δ (a_{12}) +$ $194 * δ (a_{11}) + 192 * δ (a_{10}) + 1 * δ (a_{9}) + 251 * δ (a_{8}) + 1 * δ (a_{7}) + 192 * δ (a_{6}) +$ $194 * δ (a_{5}) + 16 * δ (a_{4}) + 133 * δ (a_{3}) + 32 * δ (a_{2}) + 148 * δ (a_{1}) + 1 * δ (a_{0})),$

где операции сложения и умножения осуществляются в поле $𝔽$ .

Генерация ключа

Алгоритм генерации ключа использует итерационные константы $C_{i} = H (B i n_{128} (i))$ , i=1,2,…32. Задается общий ключ $K = k_{255} | |$ … $| | k_{0}$ .

Вычисляются итерационные ключи

$K_{1} = k_{255} | |$ … $| | k_{128}$

$K_{2} = k_{127} | |$ … $| | k_{0}$

$(K_{2 i + 1}, K_{2 i + 2}) = F [C_{8 (i - 1) + 8}]$ … $F [C_{8 (i - 1) + 1}] (K_{2 i - 1}, K_{2 i}), i = 1, 2, 3, 4 .$

Алгоритм зашифрования

$E (a) = A d d_{2} [K_{10}] H N A d d_{2} [K_{9}]$ … $H N A d d_{2} [K_{2}] H N A d d_{2} [K_{1}] (a),$ где a — строка размером 128 бит.

Алгоритм расшифрования

$D (a) = A d d_{2} [K_{1}] N^{- 1} H^{- 1} A d d_{2} [K_{2}]$ … $N^{- 1} H^{- 1} A d d_{2} [K_{9}] N^{- 1} H^{- 1} A d d_{2} [K_{10}] (a) .$

Пример^[8]

Строка «a» задается в шестнадцатеричном виде и имеет размер 16 байт, причём каждый байт задается двумя шестнадцатеричными числами.

Таблица соответствия строк в двоичном и в шестнадцатеричном виде:

0000	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100	1101	1110	1111
0	1	2	3	4	5	6	7	8	9	a	b	c	d	e	f

Пример N-преобразования

$N (00112233445566778899 a a b b c c d d e e f f) = f c 7765 a e e a o c 9 a 7 e e 8 d 7387 d 88 d 86 c b 6$

Пример G-преобразования

$G (00000000000000000000000000000100) = 94000000000000000000000000000001$

$G (94000000000000000000000000000001) = a 5940000000000000000000000000000$

$G (a 5940000000000000000000000000000) = 64 a 59400000000000000000000000000$

$G (64 a 59400000000000000000000000000) = 0 d 64 a 594000000000000000000000000$

Пример H-преобразования

$H (64 a 59400000000000000000000000000) = d 456584 d d 0 e 3 e 84 c c 3166 e 4 b 7 f a 2890 d$

Пример генерации ключа

$K = 8899 a a b b c c d d e e f f 0011223344556677 f e d c b a 98765432100123456789 a b c d e f .$

$K_{1} = 8899 a a b b c c d d e e f f 0011223344556677,$

$K_{2} = f e d c b a 98765432100123456789 a b c d e f .$

$C_{1} = 6 e a 276726 c 487 a b 85 d 27 b d 10 d d 849401,$

$A d d_{2} [C_{1}] (K_{1}) = e 63 b d c c 9 a 09594475 d 369 f 2399 d 1 f 276,$

$N A d d_{2} [C_{1} [(K_{1}) = 0998 c a 37 a 7947 a a b b 78 f 4 a 5 a e 81 b 748 a,$

$H N A d d_{2} [C_{1}] (K_{1}) = 3 d 0940999 d b 75 d 6 a 9257071 d 5 e 6144 a 6,$

$F [C_{1}] (K_{1}, K_{2}) = (H N A d d_{2} [C_{1}] (K_{1}) \oplus K_{2}, K_{1}) = (c 3 d 5 f a 01 e b e 36 f 7 a 9374427 a d 7 c a 8949, 8899 a a b b c c d d e e f f 0011223344556677) .$

$C_{2} = d c 87 e c e 4 d 890 f 4 b 3 b a 4 e b 92079 c b e b 02,$

$F [C_{2}] F [C_{1}] (K_{1}, K_{2}) = (37777748 e 56453377 d 5 e 262 d 90903 f 87, c 3 d 5 f a 01 e b e 36 f 7 a 9374427 a d 7 c a 8949) .$

$C_{3} = b 2259 a 96 b 4 d 88 e 0 b e 7690430 a 44 f 7 f 03,$

$F [C_{3}] F [C_{2}] F [C_{1}] (K_{1}, K_{2}) = (f 9 e a e 5 f 29 b 2815 e 31 f 11 a c 5 d 9 c 29 f b 01, 37777748 e 56453377 d 5 e 262 d 90903 f 87) .$

$C_{4} = 7 b c d 1 b 0 b 73 e 32 b a 5 b 79 c b 140 f 2551504,$

$F [C_{4}] F [C_{3}] F [C_{2}] F [C_{1}] (K_{1}, K_{2}) = (e 980089683 d 00 d 4 b e 37 d d 3434699 b 98 f, f 9 e a e 5 f 29 b 2815 e 31 f 11 a c 5 d 9 c 29 f b 01) .$

$C_{5} = 156 f 6 d 791 f a b 511 d e a b b 0 c 502 f d 18105,$

$F [C_{5}] F [C_{4}] F [C_{3}] F [C_{2}] F [C_{1}] (K_{1}, K_{2}) = (b 7 b d 70 a c e a 4460714 f 4 e b e 13835 c f 004, e 980089683 d 00 d 4 b e 37 d d 3434699 b 98 f) .$

$C_{6} = a 74 a f 7 e f a b 73 d f 160 d d 208608 b 9 e f e 06,$

$F [C_{6}] F [C_{5}] F [C_{4}] F [C_{3}] F [C_{2}] F [C_{1}] (K_{1}, K_{2}) = (1 a 46 e a 1 c f 6 c c d 236467287 d f 93 f d f 974, b 7 b d 70 a c e a 4460714 f 4 e b e 13835 c f 004) .$

$C_{7} = c 9 e 8819 d c 73 b a 5 a e 50 f 5 b 570561 a 6 a 07,$

$F [C_{7}] F [C_{6}] F [C_{5}] F [C_{4}] F [C_{3}] F [C_{2}] F [C_{1}] (K_{1}, K_{2}) = (3 d 4553 d 8 e 9 c f e c 6815 e b a d c 40 a 9 f f d 04, 1 a 46 e a 1 c f 6 c c d 236467287 d f 93 f d f 974) .$

$C_{8} = f 6593616 e 6055689 a d f b a 18027 a a 2 a 08,$

$(K_{3}, K_{4}) = F [C_{8}] F [C_{7}]$ … $F [C_{2}] F [C_{1}] (K_{1}, K_{2}) = (d b 31485315694343228 d 6 a e f 8 c c 78 c 44, 3 d 4553 d 8 e 9 c f e c 6815 e b a d c 40 a 9 f f d 04) .$

В итоге получаем итерационные ключи:

$K_{1} = 8899 a a b b c c d d e e f f 0011223344556677,$

$K_{2} = f e d c b a 98765432100123456789 a b c d e f,$

$K_{3} = d b 31485315694343228 d 6 a e f 8 c c 78 c 44,$

$K_{4} = 3 d 4553 d 8 e 9 c f e c 6815 e b a d c 40 a 9 f f d 04,$

$K_{5} = 57646468 c 44 a 5 e 28 d 3 e 59246 f 429 f 1 a c,$

$K_{6} = b d 079435165 c 6432 b 532 e 82834 d a 581 b,$

$K_{7} = 51 e 640757 e 8745 d e 705727265 a 0098 b 1,$

$K_{8} = 5 a 7925017 b 9 f d d 3 e d 72 a 91 a 22286 f 984,$

$K_{9} = b b 44 e 25378 c 73123 a 5 f 32 f 73 c d b 6 e 517,$

$K_{10} = 72 e 9 d d 7416 b c f 45 b 755 d b a a 88 e 4 a 4043 .$

Пример алгоритма зашифрования

Шаблон:Дополнить раздел Открытый текст $a = 1122334455667700 f f e e d d c c b b a a 9988,$

Криптостойкость

Ожидается, что новый блочный шифр «Кузнечик» будет устойчив ко всем видам атак на блочные шифры.

На конференции «CRYPTO 2015» Алекс Бирюков, Лео Перрин и Алексей Удовенко представили доклад, в котором говорится о том, что несмотря на утверждения разработчиков, значения S-блока шифра Кузнечик и хеш-функции Стрибог не являются (псевдо)случайными числами, а сгенерированы на основе скрытого алгоритма, который им удалось восстановить методами обратного проектирования^[9]. Позднее Лео Перрин и Алексей Удовенко опубликовали два альтернативных алгоритма генерации S-блока и доказали его связь с S-блоком белорусского шифра BelT^[10]. В этом исследовании авторы также утверждают, что, хотя причины использования такой структуры остаются неясны, использование скрытых алгоритмов для генерации S-блоков противоречит принципу отсутствия козыря в рукаве, который мог бы служить доказательством отсутствия специально заложенных уязвимостей в дизайне алгоритма.

Riham AlTawy и Amr M. Youssef описали атаку «встречи посередине» на 5 раундов шифра Кузнечик, имеющую вычислительную сложность 2¹⁴⁰ и требующую 2¹⁵³ памяти и 2¹¹³ данных^[11].

Примечания

Шаблон:Примечания

Ссылки

Шаблон:Симметричные криптосистемы

Шаблон:Rq

↑ Согласно ГОСТ Р 34.12-2015 и RFC 7801 шифр может именоваться на английском как Шаблон:Lang-en2
↑ Согласно ГОСТ 34.12-2018 шифр может именоваться на английском как Шаблон:Lang-en2.
↑ Некоторые программные реализации шифра с открытым исходным кодом используют наименование Шаблон:Lang-en2
↑ Шаблон:Cite web
↑ Шаблон:Cite web
↑ Шаблон:Cite web
↑ Шаблон:Cite web
↑ http://www.tc26.ru/standard/draft/GOSTR-bsh.pdf Шаблон:Wayback см. Контрольные примеры
↑ Шаблон:Cite web
↑ Шаблон:Cite web
↑ Шаблон:Cite web

[1] Согласно ГОСТ Р 34.12-2015 и RFC 7801 шифр может именоваться на английском как Шаблон:Lang-en2

[2] Согласно ГОСТ 34.12-2018 шифр может именоваться на английском как Шаблон:Lang-en2.

[3] Некоторые программные реализации шифра с открытым исходным кодом используют наименование Шаблон:Lang-en2

[4] Шаблон:Cite web

[5] Шаблон:Cite web

[6] Шаблон:Cite web

[7] Шаблон:Cite web

[8] ttp://www.tc26.ru/standard/draft/GOSTR-bsh.pdf Шаблон:Wayback см. Контрольные примеры

[9] Шаблон:Cite web

[10] Шаблон:Cite web

[mitm-11] Шаблон:Cite web

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

Кузнечик (шифр)

Содержание

Общие сведения

Обозначения

Описание алгоритма

Нелинейное преобразование

Линейное преобразование

Генерация ключа

Алгоритм зашифрования

Алгоритм расшифрования

Пример^[8]

Пример N-преобразования

Пример G-преобразования

Пример H-преобразования

Пример генерации ключа

Пример алгоритма зашифрования

Криптостойкость

Примечания

Ссылки

Навигация

Кузнечик (шифр)

Общие сведения

Обозначения

Описание алгоритма

Нелинейное преобразование

Линейное преобразование

Генерация ключа

Алгоритм зашифрования

Алгоритм расшифрования

Пример[8]

Пример N-преобразования

Пример G-преобразования

Пример H-преобразования

Пример генерации ключа

Пример алгоритма зашифрования

Криптостойкость

Примечания

Ссылки

Навигация

Поиск

Пример^[8]