Просмотр кода страницы Кузнечик (шифр)

{{другие значения}}
{{Карточка блочного шифра
| изображение = 
| ширина = 
| название = Кузнечик
| создатель = [[ФСБ России]],<br>[[ИнфоТеКС|АО «ИнфоТеКС»]]
| опубликован = [[2015]]
| стандарты = [[ГОСТ 34.12-2018]], [[ГОСТ Р 34.12-2015]], RFC 7801
| размер ключа = 256 бит
| размер блока = 128 бит
| число раундов = 10
| тип = [[SP-сеть|Подстановочно-перестановочная сеть]]
}}
'''«Кузнечик»''' ({{lang-en|Kuznyechik}}<ref>Согласно [[ГОСТ Р 34.12-2015]] и RFC 7801 шифр может именоваться на английском как {{lang-en2|Kuznyechik}}</ref> или {{lang-en|Kuznechik}}<ref>Согласно [[ГОСТ 34.12-2018]] шифр может именоваться на английском как {{lang-en2|Kuznechik}}.</ref><ref>Некоторые программные реализации шифра с [[Открытое программное обеспечение|открытым исходным кодом]] используют наименование {{lang-en2|Grasshopper}}</ref>) — симметричный алгоритм [[Блочный шифр|блочного шифрования]] с размером блока 128 бит и длиной ключа 256 бит, использующий для генерации раундовых ключей [[SP-сеть]].

== Общие сведения ==
Данный шифр утверждён (наряду с [[Магма (шифр)|блочным шифром «Магма»]]) в качестве стандарта в [[ГОСТ Р 34.12-2015]] «Информационная технология. Криптографическая защита информации. Блочные шифры» приказом от 19 июня 2015 года № 749-ст<ref>{{Cite web |url=http://www.tc26.ru/standard/gost/GOST_R_3412-2015.pdf |title=«ГОСТ Р 34.12-2015» |accessdate=2015-09-04 |archiveurl=https://web.archive.org/web/20150924113434/http://www.tc26.ru/standard/gost/GOST_R_3412-2015.pdf |archivedate=2015-09-24 |deadlink=yes }}</ref>. Стандарт вступил в действие с 1 января 2016 года<ref>{{Cite web |url=http://infotecs.ru/press/news/15/14508/ |title=«О введении новых криптографических стандартов» |access-date=2015-09-04 |archive-date=2016-09-27 |archive-url=https://web.archive.org/web/20160927151009/http://www.infotecs.ru/press/news/15/14508 |deadlink=no }}</ref>. Шифр разработан Центром защиты информации и специальной связи [[Федеральная служба безопасности Российской Федерации|ФСБ России]] с участием АО «Информационные технологии и коммуникационные системы» ([[ИнфоТеКС|АО «ИнфоТеКС»]]). Внесён Техническим комитетом по стандартизации ТК 26 «Криптографическая защита информации»<ref>{{Cite web |url=http://www.tc26.ru/ |title=«www.tc26.ru» |access-date=2014-12-14 |archive-date=2014-12-18 |archive-url=https://web.archive.org/web/20141218075053/http://tc26.ru/ |deadlink=no }}</ref><ref>{{Cite web |url=http://tc26.ru/standard/draft/PR_GOSTR-bch_v4.zip |title=Архивированная копия |accessdate=2016-04-13 |archiveurl=https://web.archive.org/web/20160424051147/http://tc26.ru/standard/draft/PR_GOSTR-bch_v4.zip |archivedate=2016-04-24 |deadlink=yes }}</ref>.

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

== Обозначения ==
'''<math>\mathbb F</math>''' — [[Конечное поле|поле Галуа]] <math>GF(2^8)</math> по модулю неприводимого многочлена <math>x^8 + x^7 + x^6 + x + 1</math>.

'''<math>Bin_8 : \Z_p \rightarrow V_8</math>''' — биективное отображение, ставящее в соответствие элементу кольца <math>\Z_p</math> (<math>p=2^8</math>) его двоичное представление.

'''<math>{Bin_8}^{-1}: V_8 \rightarrow \Z_p</math>''' — отображение, обратное к <math>Bin_8</math>.

'''<math>\delta: V_8 \rightarrow \mathbb F</math>''' — биективное отображение, ставящее в соответствие двоичной строке элемент поля <math>\mathbb F</math>.

'''<math>\delta^{-1}: \mathbb F \rightarrow V_8</math>''' — отображение, обратное к '''<math>\delta</math>

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

<math>Add_2[k](a)=k\oplus a</math>, где <math>k</math>, <math>a</math> — двоичные строки вида <math>a=a_{15}||</math>…<math>||a_{0}</math> (<math>||</math> — символ [[Конкатенация|конкатенации]] строк).

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

<math>G(a)=\gamma(a_{15},</math>…<math>,a_0)||a_{15}||</math>…<math>||a_{1}.</math>

<math>G^{-1}(a)</math> — обратное к <math>G(a)</math> преобразование, причём <math>G^{-1}(a)=a_{14}||a_{13}||</math>…<math>||a_{0}||\gamma(a_{14},a_{13},</math>…<math>,a_0,a_{15}).</math>

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

<math>F[k](a_1,a_0)=(HNAdd_2[k](a_1)\oplus a_0, a_1).</math>

=== Нелинейное преобразование ===
Нелинейное преобразование задается подстановкой <big>S = Bin<sub>8</sub> S' Bin<sub>8</sub><sup>−1</sup>.</big>

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

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

=== Линейное преобразование ===
Задаётся отображением <math>\gamma</math>:

<math>\gamma(a_{15}, </math>…<math>, a_0) = \delta^{-1}~(148 * \delta(a_{15}) + 32 * \delta(a_{14}) + 133 * \delta(a_{13}) + 16 * \delta(a_{12}) +</math>
<math>194 * \delta(a_{11}) + 192 * \delta(a_{10}) + 1 * \delta(a_9) + 251 * \delta(a_8) + 1 * \delta(a_7) + 192 * \delta(a_6) +</math>
<math>194 * \delta(a_5) + 16 * \delta(a_4) + 133 * \delta(a_3) + 32 * \delta(a_2) + 148 * \delta(a_1) + 1 * \delta(a_0)),</math>

где операции сложения и умножения осуществляются в поле <math>\mathbb F</math>.

=== Генерация ключа ===
Алгоритм генерации ключа использует итерационные константы <math>C_i=H(Bin_{128}(i))</math><big>, i=1,2,…32.</big>
Задается общий ключ <math>K=k_{255}||</math>…<math>||k_0</math>.

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

<math>K_1=k_{255}||</math>…<math>||k_{128}</math>

<math>K_2=k_{127}||</math>…<math>||k_{0}</math>

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

=== Алгоритм зашифрования ===
<math>E(a)=Add_2[K_{10}]HNAdd_2[K_9]</math>…<math>HNAdd_2[K_2]HNAdd_2[K_1](a),</math> где a — строка размером 128 бит.

=== Алгоритм расшифрования ===
<math>D(a)=Add_2[K_{1}]N^{-1}H^{-1}Add_2[K_2]</math>…<math>N^{-1}H^{-1}Add_2[K_9]N^{-1}H^{-1}Add_2[K_{10}](a).</math>

== Пример<ref>http://www.tc26.ru/standard/draft/GOSTR-bsh.pdf {{Wayback|url=http://www.tc26.ru/standard/draft/GOSTR-bsh.pdf |date=20141226234140 }} см. Контрольные примеры</ref> ==

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

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

{| class="wikitable" style="text-align:center"
 |-
 |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-преобразования ===
<math>N(00112233445566778899aabbccddeeff)=fc7765aeeaoc9a7ee8d7387d88d86cb6</math>

=== Пример G-преобразования ===
<math>G(00000000000000000000000000000100)=94000000000000000000000000000001</math>

<math>G(94000000000000000000000000000001) = a5940000000000000000000000000000</math>

<math>G(a5940000000000000000000000000000) = 64a59400000000000000000000000000</math>

<math>G(64a59400000000000000000000000000) = 0d64a594000000000000000000000000</math>

=== Пример H-преобразования ===
<math>H(64a59400000000000000000000000000) = d456584dd0e3e84cc3166e4b7fa2890d</math>

=== Пример генерации ключа ===
<math>K=8899aabbccddeeff0011223344556677fedcba98765432100123456789abcdef.</math>

<math>K_1=8899aabbccddeeff0011223344556677,</math>

<math>K_2=fedcba98765432100123456789abcdef.</math>

<math>C_1=6ea276726c487ab85d27bd10dd849401,</math>

<math>Add_2[C_1](K_1)=e63bdcc9a09594475d369f2399d1f276,</math>

<math>NAdd_2[C_1[(K_1)=0998ca37a7947aabb78f4a5ae81b748a,</math>

<math>HNAdd_2[C_1](K_1)=3d0940999db75d6a9257071d5e6144a6,</math>

<math>F[C_1](K_1,K_2)=(HNAdd_2[C_1](K_1)\oplus K_2, K_1)=(c3d5fa01ebe36f7a9374427ad7ca8949, 8899aabbccddeeff0011223344556677).</math>


<math>C_2=dc87ece4d890f4b3ba4eb92079cbeb02,</math>

<math>F[C_2]F[C_1](K_1,K_2)=(37777748e56453377d5e262d90903f87, c3d5fa01ebe36f7a9374427ad7ca8949).</math>


<math>C_3=b2259a96b4d88e0be7690430a44f7f03,</math>

<math>F[C_3]F[C_2]F[C_1](K_1,K_2)=(f9eae5f29b2815e31f11ac5d9c29fb01, 37777748e56453377d5e262d90903f87).</math>


<math>C_4=7bcd1b0b73e32ba5b79cb140f2551504,</math>

<math>F[C_4]F[C_3]F[C_2]F[C_1](K_1,K_2)=(e980089683d00d4be37dd3434699b98f, f9eae5f29b2815e31f11ac5d9c29fb01).</math>


<math>C_5=156f6d791fab511deabb0c502fd18105,</math>

<math>F[C_5]F[C_4]F[C_3]F[C_2]F[C_1](K_1,K_2)=(b7bd70acea4460714f4ebe13835cf004, e980089683d00d4be37dd3434699b98f).</math>


<math>C_6=a74af7efab73df160dd208608b9efe06,</math>

<math>F[C_6]F[C_5]F[C_4]F[C_3]F[C_2]F[C_1](K_1,K_2)=(1a46ea1cf6ccd236467287df93fdf974, b7bd70acea4460714f4ebe13835cf004).</math>


<math>C_7=c9e8819dc73ba5ae50f5b570561a6a07,</math>

<math>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)=(3d4553d8e9cfec6815ebadc40a9ffd04, 1a46ea1cf6ccd236467287df93fdf974).</math>


<math>C_8=f6593616e6055689adfba18027aa2a08,</math>

<math>(K_3,K_4)=F[C_8]F[C_7]</math>…<math>F[C_2]F[C_1](K_1,K_2)=(db31485315694343228d6aef8cc78c44, 3d4553d8e9cfec6815ebadc40a9ffd04).</math>


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

<math>K_1=8899aabbccddeeff0011223344556677,</math>

<math>K_2=fedcba98765432100123456789abcdef,</math>

<math>K_3=db31485315694343228d6aef8cc78c44,</math>

<math>K_4=3d4553d8e9cfec6815ebadc40a9ffd04,</math>

<math>K_5=57646468c44a5e28d3e59246f429f1ac,</math>

<math>K_6=bd079435165c6432b532e82834da581b,</math>

<math>K_7=51e640757e8745de705727265a0098b1,</math>

<math>K_8=5a7925017b9fdd3ed72a91a22286f984,</math>

<math>K_9=bb44e25378c73123a5f32f73cdb6e517,</math>

<math>K_{10}=72e9dd7416bcf45b755dbaa88e4a4043.</math>

=== Пример алгоритма зашифрования ===
{{Дополнить раздел|дата=2018-01-08}}
Открытый текст <math>a=1122334455667700ffeeddccbbaa9988,</math>

== Криптостойкость ==
Ожидается, что новый блочный шифр «Кузнечик» будет [[Криптографическая стойкость|устойчив]] ко всем видам [[Атака на блочный шифр|атак на блочные шифры]].

На конференции «CRYPTO 2015» Алекс Бирюков, Лео Перрин и Алексей Удовенко представили доклад, в котором говорится о том, что несмотря на утверждения разработчиков, значения S-блока шифра Кузнечик и [[ГОСТ Р 34.11-2012|хеш-функции Стрибог]] не являются (псевдо)случайными числами, а сгенерированы на основе скрытого алгоритма, который им удалось восстановить методами [[Обратная разработка|обратного проектирования]]<ref>{{cite web|url=https://tosc.iacr.org/index.php/ToSC/article/view/567/509|title=Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1 (Full Version)|author=Alex Biryukov, Léo Perrin, Aleksei Udovenko|date=2016-05-08|access-date=2021-05-21|archive-date=2021-03-04|archive-url=https://web.archive.org/web/20210304115943/https://tosc.iacr.org/index.php/ToSC/article/view/567/509|deadlink=no}}</ref>. Позднее Лео Перрин и Алексей Удовенко опубликовали два альтернативных алгоритма генерации S-блока и доказали его связь с S-блоком белорусского шифра [[BelT]]<ref>{{cite web
| author=Léo Perrin, Aleksei Udovenko
| title=Exponential S-Boxes: a Link Between the S-Boxes of BelT and Kuznyechik/Streebog
| date=2017-02-03
| url=https://tosc.iacr.org/index.php/ToSC/article/download/567/509/567-1538-1-SM.pdf
| access-date=2017-09-14
| archive-date=2021-04-17
| archive-url=https://web.archive.org/web/20210417213022/https://tosc.iacr.org/index.php/ToSC/article/download/567/509/567-1538-1-SM.pdf
| deadlink=no
}}</ref>. В этом исследовании авторы также утверждают, что, хотя причины использования такой структуры остаются неясны, использование скрытых алгоритмов для генерации [[S-блок (информатика)|S-блоков]] противоречит принципу [[:en:Nothing up my sleeve number|отсутствия козыря в рукаве]], который мог бы служить доказательством отсутствия специально заложенных уязвимостей в дизайне алгоритма.

Riham AlTawy и Amr M. Youssef описали атаку «[[Метод встречи посередине|встречи посередине]]» на 5 раундов шифра Кузнечик, имеющую вычислительную сложность 2<sup>140</sup> и требующую 2<sup>153</sup> памяти и 2<sup>113</sup> данных<ref name="mitm">{{cite web |author=Riham AlTawy and Amr M. Youssef |date=2015-04-17 |title=A Meet in the Middle Attack on Reduced Round Kuznyechik |url=https://eprint.iacr.org/2015/096.pdf |access-date=2016-06-08 |archive-date=2017-07-16 |archive-url=https://web.archive.org/web/20170716222946/https://eprint.iacr.org/2015/096.pdf |deadlink=no }}</ref>.

== Примечания ==
{{примечания}}

== Ссылки ==
* {{ГОСТ|Р 34.12-2015}}
* {{ГОСТ|34.12-2018}}
* [http://habrahabr.ru/post/266359/ В ГОСТе сидел «Кузнечик»]{{неавторитетный источник|05|01|2016}}

{{Симметричные криптосистемы}}

{{rq|check}}

[[Категория:Блочные шифры]]
[[Категория:SP-сеть]]
[[Категория:Стандарты криптографии]]
[[Категория:ГОСТ]]