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

ГОСТ Р 34.12-2015 (Кузнечик)
Размер ключа:	256 бит
Размер блока:	128 бит
Число раундов:	10
Тип:	Подстановочно-перестановочная сеть

Блочный шифр «Кузнечик» — симметричный алгоритм блочного шифрования с размером блока 128 бит и длиной ключа 256 бит и использующий для генерации раундовых ключей сеть Фейстеля.

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

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

Обозначения

<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>

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

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

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

<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> </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>, i=1,2,…32. Задается общий ключ <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}]H^{-1}N^{-1}Add_2[K_2]</math>…<math>H^{-1}N^{-1}Add_2[K_9]H^{-1}N^{-1}Add_2[K_{10}](a).</math>

Пример

Строка «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-преобразования

<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>

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

Открытый текст <math>a=1122334455667700ffeeddccbbaa9988,</math>

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

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

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

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

Ссылки

• [habrahabr.ru/post/266359/ В ГОСТе сидел «Кузнечик»]^{[неавторитетный источник? 3033 дня]}

Литература

• [www.tc26.ru/download/kuznechik_description_cor.pdf Kuznechik description] / ТЕХНИЧЕСКИЙ КОМИТЕТ ПО СТАНДАРТИЗАЦИИ «КРИПТОГРАФИЧЕСКАЯ ЗАЩИТА ИНФОРМАЦИИ» (TK 26)

Отрывок, характеризующий Кузнечик (шифр)

– Народ все еще надеется увидать ваше величество.
Обед уже кончился, государь встал и, доедая бисквит, вышел на балкон. Народ, с Петей в середине, бросился к балкону.
– Ангел, отец! Ура, батюшка!.. – кричали народ и Петя, и опять бабы и некоторые мужчины послабее, в том числе и Петя, заплакали от счастия. Довольно большой обломок бисквита, который держал в руке государь, отломившись, упал на перилы балкона, с перил на землю. Ближе всех стоявший кучер в поддевке бросился к этому кусочку бисквита и схватил его. Некоторые из толпы бросились к кучеру. Заметив это, государь велел подать себе тарелку бисквитов и стал кидать бисквиты с балкона. Глаза Пети налились кровью, опасность быть задавленным еще более возбуждала его, он бросился на бисквиты. Он не знал зачем, но нужно было взять один бисквит из рук царя, и нужно было не поддаться. Он бросился и сбил с ног старушку, ловившую бисквит. Но старушка не считала себя побежденною, хотя и лежала на земле (старушка ловила бисквиты и не попадала руками). Петя коленкой отбил ее руку, схватил бисквит и, как будто боясь опоздать, опять закричал «ура!», уже охриплым голосом.
Государь ушел, и после этого большая часть народа стала расходиться.
– Вот я говорил, что еще подождать – так и вышло, – с разных сторон радостно говорили в народе.
Как ни счастлив был Петя, но ему все таки грустно было идти домой и знать, что все наслаждение этого дня кончилось. Из Кремля Петя пошел не домой, а к своему товарищу Оболенскому, которому было пятнадцать лет и который тоже поступал в полк. Вернувшись домой, он решительно и твердо объявил, что ежели его не пустят, то он убежит. И на другой день, хотя и не совсем еще сдавшись, но граф Илья Андреич поехал узнавать, как бы пристроить Петю куда нибудь побезопаснее.


15 го числа утром, на третий день после этого, у Слободского дворца стояло бесчисленное количество экипажей.
Залы были полны. В первой были дворяне в мундирах, во второй купцы с медалями, в бородах и синих кафтанах. По зале Дворянского собрания шел гул и движение. У одного большого стола, под портретом государя, сидели на стульях с высокими спинками важнейшие вельможи; но большинство дворян ходило по зале.
Все дворяне, те самые, которых каждый день видал Пьер то в клубе, то в их домах, – все были в мундирах, кто в екатерининских, кто в павловских, кто в новых александровских, кто в общем дворянском, и этот общий характер мундира придавал что то странное и фантастическое этим старым и молодым, самым разнообразным и знакомым лицам. Особенно поразительны были старики, подслеповатые, беззубые, плешивые, оплывшие желтым жиром или сморщенные, худые. Они большей частью сидели на местах и молчали, и ежели ходили и говорили, то пристроивались к кому нибудь помоложе. Так же как на лицах толпы, которую на площади видел Петя, на всех этих лицах была поразительна черта противоположности: общего ожидания чего то торжественного и обыкновенного, вчерашнего – бостонной партии, Петрушки повара, здоровья Зинаиды Дмитриевны и т. п.
Пьер, с раннего утра стянутый в неловком, сделавшемся ему узким дворянском мундире, был в залах. Он был в волнении: необыкновенное собрание не только дворянства, но и купечества – сословий, etats generaux – вызвало в нем целый ряд давно оставленных, но глубоко врезавшихся в его душе мыслей о Contrat social [Общественный договор] и французской революции. Замеченные им в воззвании слова, что государь прибудет в столицу для совещания с своим народом, утверждали его в этом взгляде. И он, полагая, что в этом смысле приближается что то важное, то, чего он ждал давно, ходил, присматривался, прислушивался к говору, но нигде не находил выражения тех мыслей, которые занимали его.
Был прочтен манифест государя, вызвавший восторг, и потом все разбрелись, разговаривая. Кроме обычных интересов, Пьер слышал толки о том, где стоять предводителям в то время, как войдет государь, когда дать бал государю, разделиться ли по уездам или всей губернией… и т. д.; но как скоро дело касалось войны и того, для чего было собрано дворянство, толки были нерешительны и неопределенны. Все больше желали слушать, чем говорить.
Один мужчина средних лет, мужественный, красивый, в отставном морском мундире, говорил в одной из зал, и около него столпились. Пьер подошел к образовавшемуся кружку около говоруна и стал прислушиваться. Граф Илья Андреич в своем екатерининском, воеводском кафтане, ходивший с приятной улыбкой между толпой, со всеми знакомый, подошел тоже к этой группе и стал слушать с своей доброй улыбкой, как он всегда слушал, в знак согласия с говорившим одобрительно кивая головой. Отставной моряк говорил очень смело; это видно было по выражению лиц, его слушавших, и по тому, что известные Пьеру за самых покорных и тихих людей неодобрительно отходили от него или противоречили. Пьер протолкался в середину кружка, прислушался и убедился, что говоривший действительно был либерал, но совсем в другом смысле, чем думал Пьер. Моряк говорил тем особенно звучным, певучим, дворянским баритоном, с приятным грассированием и сокращением согласных, тем голосом, которым покрикивают: «Чеаек, трубку!», и тому подобное. Он говорил с привычкой разгула и власти в голосе.
– Что ж, что смоляне предложили ополченцев госуаю. Разве нам смоляне указ? Ежели буародное дворянство Московской губернии найдет нужным, оно может выказать свою преданность государю импературу другими средствами. Разве мы забыли ополченье в седьмом году! Только что нажились кутейники да воры грабители…
Граф Илья Андреич, сладко улыбаясь, одобрительно кивал головой.
– И что же, разве наши ополченцы составили пользу для государства? Никакой! только разорили наши хозяйства. Лучше еще набор… а то вернется к вам ни солдат, ни мужик, и только один разврат. Дворяне не жалеют своего живота, мы сами поголовно пойдем, возьмем еще рекрут, и всем нам только клич кликни гусай (он так выговаривал государь), мы все умрем за него, – прибавил оратор одушевляясь.
Илья Андреич проглатывал слюни от удовольствия и толкал Пьера, но Пьеру захотелось также говорить. Он выдвинулся вперед, чувствуя себя одушевленным, сам не зная еще чем и сам не зная еще, что он скажет. Он только что открыл рот, чтобы говорить, как один сенатор, совершенно без зубов, с умным и сердитым лицом, стоявший близко от оратора, перебил Пьера. С видимой привычкой вести прения и держать вопросы, он заговорил тихо, но слышно:
– Я полагаю, милостивый государь, – шамкая беззубым ртом, сказал сенатор, – что мы призваны сюда не для того, чтобы обсуждать, что удобнее для государства в настоящую минуту – набор или ополчение. Мы призваны для того, чтобы отвечать на то воззвание, которым нас удостоил государь император. А судить о том, что удобнее – набор или ополчение, мы предоставим судить высшей власти…
Пьер вдруг нашел исход своему одушевлению. Он ожесточился против сенатора, вносящего эту правильность и узкость воззрений в предстоящие занятия дворянства. Пьер выступил вперед и остановил его. Он сам не знал, что он будет говорить, но начал оживленно, изредка прорываясь французскими словами и книжно выражаясь по русски.
– Извините меня, ваше превосходительство, – начал он (Пьер был хорошо знаком с этим сенатором, но считал здесь необходимым обращаться к нему официально), – хотя я не согласен с господином… (Пьер запнулся. Ему хотелось сказать mon tres honorable preopinant), [мой многоуважаемый оппонент,] – с господином… que je n'ai pas L'honneur de connaitre; [которого я не имею чести знать] но я полагаю, что сословие дворянства, кроме выражения своего сочувствия и восторга, призвано также для того, чтобы и обсудить те меры, которыми мы можем помочь отечеству. Я полагаю, – говорил он, воодушевляясь, – что государь был бы сам недоволен, ежели бы он нашел в нас только владельцев мужиков, которых мы отдаем ему, и… chair a canon [мясо для пушек], которую мы из себя делаем, но не нашел бы в нас со… со… совета.