Русская Википедия:Kupyna

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Карточка хеш-функции Kupyna (Шаблон:Lang-uk) — итеративная криптографическая хеш-функция. Принята в качестве национального стандарта Украины ДСТУ 7564:2014[1] в качестве замены устаревшей хеш-функции ГОСТ 34.311-95. Сжимающая функция Kupyna состоит из двух фиксированных 2n-битных перестановок T⊕ и T+, структура которых заимствована у шифра Kalyna. В частности, используется четыре таких же S-блока. Результат работы хеш-функции может иметь длину от 8 до 512 бит. Вариант, возвращающий n бит, называется «Kupyna-n»[2].

Происхождение названия

Купена аптечная — растение семейства Шаблон:Bt-ruslat, произрастающие на территории всей Украины в хвойных и смешанных лесах, занесена в Красную книгу Украины.[3]

Алгоритм

Сначала сообщение <math>M</math> дополняется до длины, кратной размеру блока. Для этого к сообщению добавляется 1 бит <math>1</math>, затем <math>d</math> нулевых битов, где <math>d=(-N-97)\ mod\ l</math> и 96 бит, содержащих длину сообщения в битах. Таким образом, максимальная длина сообщения <math>2^{96}-1</math> бит.

После этого сообщение разбивается на <math>t </math> блоков <math>m_1, m_2, ..., m_t</math> по <math>l</math> бит каждый. Для вариантов функции, возвращающих до 256 бит, <math>l</math> = 512. Для вариантов, возвращающих большие значения, <math>l</math> = 1024.

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

<math>h_0 = IV</math>

<math>h_\nu = T_l^\oplus</math><math>(</math><math>h_{\nu-1}\oplus</math><math>m_\nu)\oplus</math><math>T_l^+(m_\nu){\oplus}h_{\nu-1}</math>

<math>H(IV,M) = R_{l,n}(T_l^\oplus(h_k){\oplus}h_k)</math>

где

<math>\nu = 1, 2, ..., k</math>

<math>IV = 1 << 510</math>, если l = 512, или <math>1 << 1023</math>, если l = 1024

<math>R_{l,n}(X)</math> - функция, возвращающая <math>n</math> наиболее значимых битов блока размером <math>l</math>

Перестановки T⊕ и T+

Эти преобразования управляют состоянием, которое представляется матрицей G, содержащей в каждой ячейке 1 байт информации. Матрица имеет размер 8Х8 (при <math>l = 512</math>) или 8Х16 (при <math>l = 1024</math>).

Сначала матрица G заполняется последовательностью байт. Например для последовательности 00 01 02 … 3f матрица G выглядит следующим образом.

<math>

\begin{bmatrix} 

 00 & 08 & 10 & 18 & 20 & 28 & 30 & 38 \\
 01 & 09 & 11 & 19 & 21 & 29 & 31 & 39 \\
 02 & 0a & 12 & 1a & 22 & 2a & 32 & 3a \\
 03 & 0b & 13 & 1b & 23 & 2b & 33 & 3b \\
 04 & 0c & 14 & 1c & 24 & 2c & 34 & 3c \\
 05 & 0d & 15 & 1d & 25 & 2d & 35 & 3d \\
 06 & 0e & 16 & 1e & 26 & 2e & 36 & 3e \\
 07 & 0f & 17 & 1f & 27 & 2f & 37 & 3f

\end{bmatrix}

</math>

Аналогичным образом заполняется матрица 8 X 16.

Перестановки <math>T_l^\oplus</math> и <math>T_l^+</math> определены как:

<math>T_l^\oplus</math> <math>=</math> <math>\prod_{\nu=0}^{t-1}(\psi\circ\tau^{(l)}\circ\pi'\circ\kappa_\nu^{(l)})</math>

<math>T_l^+</math> <math>=</math> <math>\prod_{\nu=0}^{t-1}(\psi\circ\tau^{(l)}\circ\pi'\circ\eta_\nu^{(l)})</math>

Функция <math>\kappa_\nu^{(l)}</math> прибавляет по модулю 2 вектор

<math>\omega_j^{(\nu)} = ((j<<4)\oplus\nu,0,0,0,0,0,0,0)^T</math>

к каждому столбцу матрицы состояния (<math>\nu</math> - номер раунда).

Функция <math>\eta_\nu^{(l)}</math> прибавляет по модулю 64 вектор

<math>\varsigma_j^{(\nu)} = (0xF3, 0xF0, 0xF0, 0xF0, 0xF0, 0xF0, 0xF0 (c-1-j)<<4)^T</math>

к каждому столбцу матрицы состояния (<math>\nu</math> - номер раунда).

Функция <math>\pi'</math> заменяет элементы матрицы состояния <math>g_{i,j}</math> подстановкой из одного из четырёх S-блоков (номер S-блока определяется как <math>i\ mod\ 4</math>).

Функция <math>\tau_l</math> производит циклический сдвиг вправо элементов матрицы состояния. Строки с номерами <math>i = 0,1,2,3,4,5,6</math> сдвигаются на <math>i</math> элементов, а строка 7 сдвигается на 7 элементов при <math>l=512</math> или на 11 элементов при <math>l=1024</math>.

Для выполнения функции <math>\psi</math> каждый элемент матрицы состояния представляется как элемент конечного поля <math>GF(2^8)</math>, сформированного неприводимым полиномом <math>x^8+x^4+x^3+x^2+1</math>. Каждый элемент результирующей матрицы состояния <math>u_{i,j}</math> вычисляется по формуле:

<math>u_{i,j} = (v >>> i)\bigotimes G_j</math>

где <math>v</math> - вектор (0x01, 0x01, 0x05, 0x01, 0x08, 0x06, 0x07, 0x04), а <math>j</math> - номер столбца матрицы состояния <math>G</math>.

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

Создатели уверяют, что дифференциальные атаки и rebound атаки неэффективны уже после 4 итераций функций перестановок. В таблице приведены заявленные создателями показатели криптостойкости.

Вид атаки Kupyna-256 Kupyna-512
Коллизия 2128 2256
Прообраз 2256 2512
Второй прообраз 2256 2512
Фиксированные точки 2256 2512

В результате независимого криптоанализа удалось провести атаку только на первые 5 раундов; сложность нахождения коллизии для сокращённой до 5 раундов функции Kupyna-256 составляет 2120.[4][5]

S-блоки

Подстановка π0

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

Подстановка π1

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

Подстановка π2

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

Подстановка π3

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


Примеры хешей Kupyna

Значения разных вариантов хеша от пустой строки. 

Kupyna-256("")
0x cd5101d1ccdf0d1d1f4ada56e888cd724ca1a0838a3521e7131d4fb78d0f5eb6
Kupyna-512("")
0x 656b2f4cd71462388b64a37043ea55dbe445d452aecd46c3298343314ef04019
   bcfa3f04265a9857f91be91fce197096187ceda78c9c1c021c294a0689198538

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

Kupyna-256("The quick brown fox jumps over the lazy dog")
0x 996899f2d7422ceaf552475036b2dc120607eff538abf2b8dff471a98a4740c6
Kupyna-256("The quick brown fox jumps over the lazy dog.")
0x 88ea8ce988fe67eb83968cdc0f6f3ca693baa502612086c0dcec761a98e2fb1f


Примечания

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

Шаблон:Хеш-алгоритмы

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ http://csm.kiev.ua/index.php?view=article&id=3022 Шаблон:Wayback В Украине внедряются новые стандарты криптографической защиты информации
  2. ↑ http://eprint.iacr.org/2015/885.pdf Шаблон:Wayback A New Standard of Ukraine: The Kupyna Hash Function
  3. ↑ http://www.slideshare.net/oliynykov/kupyna Шаблон:Wayback Main properties of the new Ukrainian national standard on cryptographic hash function
  4. ↑ Шаблон:Cite web
  5. ↑ Шаблон:Cite web
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Kupyna&oldid=8703119