Перегляд вихідного коду сторінки Купина (геш-функція)

{{Otheruses|Купина}}
{{Стандарт
|зображення     = Vlad1Trezub.svg
|Позначення     = ДСТУ 7564:2014
|Повна назва     = Інформаційні технології. Криптографічний захист інформації. Функція хешування
|Офіційні мови = 
|Тип стандарту   = Державний стандарт України
|Розроблено      = 
|Розробники     = Приватне акціонерне товариство «Інститут інформаційних технологій»
|Внесено           = Мінекономрозвитку України
|Введено в дію = наказ від [[2 грудня]] [[2014]] р. № 1431
|На заміну         = 
|Чинний від      = [[1 квітня]] [[2015]] року
|Статус              = Чинний<ref>[http://csm.kiev.ua/nd/nd.php?z=ДСТУ+7564%3A2014&st=0&b=1 ДСТУ 7564:2014 в Каталозі НД України]</ref>
|Останні зміни  = ІПС №11-2015
|Доповнення     = 
|Перегляд          = 
|Ідентичний      = 
|Гармонізований = 
|Подібний          =
|Пов'язані стандарти= [[ДСТУ 7624:2014]], [[ДСТУ 4145-2002]], {{Нп|ГОСТ 34.311-95|ГОСТ 34.311-95|ru|ГОСТ 34.311-95}}
|Кількість сторінок = 40
|внизу              = [http://www.csm.kiev.ua/nd/nd.php База нормативних документів]
}}
«'''Купина'''» ({{lang-en|Kupyna}})&nbsp;— ітеративна [[Криптографічна геш-функція|криптографічна геш-функція]] описана у [[Національний стандарт|національному стандарті України]] '''ДСТУ 7564:2014''' «Інформаційні технології. Криптографічний захист інформації. Функція хешування». Стандарт набрав чинності з [[1 квітня]] [[2015]] року наказом [[Міністерство економічного розвитку і торгівлі України|Мінекономрозвитку]] від [[2 грудня]] [[2014]] року №&nbsp;1431<ref>[https://zakon.rada.gov.ua/rada/show/v1431731-14 Про прийняття національних стандартів України, гармонізованих з європейськими стандартами, міжнародних стандартів як національних стандартів України, затвердження національних стандартів України, скасування міждержавних стандартів в Україні та внесення зміни до наказу Державного комітету стандартизації, метрології та сертифікації України від 12.06.2002 №357]</ref>. Текст стандарту є у вільному доступі <ref>{{Cite web |url=http://uas.org.ua/ua/services/standartizatsiya/109-2/ |title=Текст стандарту ДСТУ 7564:2014 на сайті Державного підприємства «Український науково-дослідний і навчальний центр проблем стандартизації, сертифікації та якості» |accessdate=2019-05-05 |archive-date=2019-05-14 |archive-url=https://web.archive.org/web/20190514014155/http://uas.org.ua/ua/services/standartizatsiya/109-2/ }}</ref>.

Стандарт [[ДСТУ 7564:2014]] розроблено задля поступової заміни міждержавного стандарту {{Нп|ГОСТ 34.311-95|ГОСТ 34.311-95|ru|ГОСТ 34.311-95}}<ref>[http://www.dsszzi.gov.ua/dsszzi/control/uk/publish/article?art_id=120158&cat_id=119123 Держспецзв’язку впроваджує нові стандарти криптографічного захисту інформації]</ref> та згідно з чинним наказом [[Міністерство цифрової трансформації України|Мінцифри]] від [[30 вересня]] [[2020]] року №&nbsp;140/614<ref>{{Cite web|url=https://zakon.rada.gov.ua/laws/show/z1039-20|website=zakon.rada.gov.ua|accessdate=2021-01-04|title=Наказ № 140/614 від 30.09.2020  "Про встановлення вимог до технічних засобів, процесів їх створення, використання та функціонування у складі інформаційно-телекомунікаційних систем під час надання кваліфікованих електронних довірчих послуг"|last=|first=|date=2020-09-30|publisher=Міністерство цифрової трансформації України|language=uk}}</ref> може застосовуватися для створення [[Електронний цифровий підпис|кваліфікованого електронного підпису]] з [[0 січня|01 січня]] [[2021]] року, та обов'язковий для застосування після [[1 січня]] [[2022]] року замість [[Хеш-функція|функції гешування]] за {{Нп|ГОСТ 34.311-95|ГОСТ 34.311-95|ru|ГОСТ 34.311-95}}.

Функція стиснення Купини складається з двох фіксованих 2n-бітних [[Перестановка|перестановок]] T<sup>⊕</sup> і T<sup>+</sup>, структура яких запозичена у [[Шифр|шифра]] [[Калина (шифр)|Калина]]. Зокрема, використовуються чотири таких самих [[S-блок|S-блока]]. Результат роботи геш-функції може мати довжину від 8 до 512 біт. Варіант, який повертає n біт, позначається як ''Купина-n''.<ref name = "eprint-desc">https://eprint.iacr.org/2015/885.pdf Roman Oliynykov, Ivan Gorbenko, Oleksandr Kazymyrov, Victor Ruzhentsev, Oleksandr Kuznetsov, Yurii Gorbenko, Artem Boiko, Oleksandr Dyrda, Viktor Dolgov, Andrii Pushkaryov A New Standard of Ukraine: The Kupyna Hash Function</ref>

== Алгоритм ==

Спочатку повідомлення <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. Для варіантів, які повертають значення, довші 256 біт, <math>l</math> = 1024.

Далі, будується геш-функція, з використанням наступного ітеративного алгоритму<ref name = "eprint-desc"></ref>.

<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>&nbsp;— функція, яка повертає <math>n</math> найбільш значущих бітів блока розміром <math>l</math><ref name = "eprint-desc"></ref>

Кількість ітерацій для варіантів функції, які повертають до 256 біт включно&nbsp;— 10. Кількість ітерацій для варіантів функції, які повертають значення, довші 256 біт,&nbsp;— 14<ref name = "eprint-desc"></ref>.

=== Перестановки T<sup>⊕</sup> і T<sup>+</sup> ===

Ці перетворення керують станом, представленим [[Матриця (математика)|матрицею]] G, яка містить у кожній комірці 1 байт інформації<ref name = "eprint-desc"></ref>. Матриця має розмір 8Х8 (при <math>l = 512</math>) або 8Х16 (при <math>l = 1024</math>)<ref name = "eprint-desc"></ref>.

Спочатку матриця G заповнюється послідовністю байт<ref name = "eprint-desc"></ref>. Наприклад для послідовності 00 01 02 … 3f матриця G виглядає так<ref name = "eprint-desc"></ref>.


<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><ref name = "eprint-desc"></ref>

Аналогічно заповнюється матриця 8 X 16<ref name = "eprint-desc"></ref>.

Перестановки <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><ref name = "eprint-desc"></ref>

Функція <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>&nbsp;— номер раунду)<ref name = "eprint-desc"></ref>.

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

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

до кожного стовпця матриці стану (<math>\nu</math>&nbsp;— номер раунду)<ref name = "eprint-desc"></ref>.

Функція <math>\pi'</math> підміняє елементи матриці стану <math>g_{i,j}</math> підстановкою з одного з чотирьох [[S-блок]]ів (номер S-блока визначається як <math>i\ mod\ 4</math>)<ref name = "eprint-desc"></ref>.

Функція <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><ref name = "eprint-desc"></ref>.

Для виконання функції <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)\oplus G_j</math>

де <math>v</math>&nbsp;— вектор (0x01, 0x01, 0x05, 0x01, 0x08, 0x06, 0x07, 0x04), а <math>j</math>&nbsp;— номер стовпця матриці стану <math>G</math><ref name = "eprint-desc"></ref>.

== S-блоки ==

=== Підстановка π<sub>0</sub> ===

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

=== Підстановка π<sub>1</sub> ===

{| class="wikitable"
|-
|CE||BB||EB||92||EA||CB||13||C1||E9||3A||D6||B2||D2||90||17||F8
 |-
|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
 |}

=== Підстановка π<sub>2</sub> ===

{| class="wikitable"
|-
|93||D9||9A||B5||98||22||45||FC||BA||6A||DF||02||9F||DC||51||59
 |-
|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
 |}

=== Підстановка π<sub>3</sub> ===

{| class="wikitable"
|-
|68||8D||CA||4D||73||4B||4E||2A||D4||52||26||B3||54||1E||19||1F
 |-
|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
 |}

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

Автори запевняють, що [[Диференціальний криптоаналіз|диференціальні атаки]] і rebound-атаки неефективні вже після 4 ітерацій функцій перестановок. У таблиці наведені заявлені авторами показники криптостійкості.

{| class="wikitable"
|-
! Вид атаки !! Купина-256!! Купина-512
|-
| [[Колізійна атака|Колізія]] || 2<sup>128</sup> || 2<sup>256</sup>
|-
| [[Атака знаходження першовзору|Першовзір]] || 2<sup>256</sup> || 2<sup>512</sup>
|-
| Другий першовзір || 2<sup>256</sup> || 2<sup>512</sup>
|-
| Фіксовані точки || 2<sup>256</sup> || 2<sup>512</sup>
|}

У результаті незалежного [[Криптоаналіз|криптоаналізу]] вдалося провести [[колізійна атака|атаку]] тільки на перші 5 раундів; складність знаходження [[Колізія хеш-функції|колізії]] для скороченої до 5 раундів функції Купина-256 складає 2<sup>120</sup>.<ref>{{cite web
  | url = https://eprint.iacr.org/2015/956.pdf
  | title = Analysis of the Kupyna-256 Hash Function
  | year = 2015
  | author = Christoph Dobraunig, Maria Eichlseder, and Florian Mendel
  | accessdate = 1 жовтня 2015
  | lang = en
 }}</ref><ref>{{cite web
  | url = https://eprint.iacr.org/2015/959.pdf
  | title = Cryptanalysis of the Round-Reduced Kupyna Hash Function
  | year = 2015
  | author = Jian Zou, Le Dong
  | accessdate = 2 жовтня 2015
  | lang = en
 }}</ref>

== Використання ==

[https://github.com/Roman-Oliynykov/Kupyna-reference Kupyna-reference] — код референсної реалізаціі на C

[https://sourceforge.net/projects/cppcrypto cppcrypto] — Бібліотека з відкритим вихідним кодом на C++

[https://github.com/privat-it/cryptonite cryptonite] — бібліотека криптографічних перетворень від [[ПриватБанк|ПриватБанку]] з відкритим програмним кодом на C, [https://data.gov.ua/dataset/7b0d45fe-75eb-4d14-9792-59e440305678 має експертний висновок UA.14360570.00001-01 90 01-1 за результатами державної експертизи у галузі КЗІ]

== Примітки ==
{{reflist|2}}

== Див. також ==
* [[Калина (шифр)]]
* [[СТРУМОК (шифр)]]
* [[Стандарти криптографії]]


{{Геш-функції та коди аутентифікації повідомлення}}
{{ВП-портали|Програмування|}}

[[Категорія:Криптографія]]
[[Категорія:Геш-функції]]
[[Категорія:Криптографічні геш-функції]]
[[Категорія:Стандарти криптографії]]
[[Категорія:Стандарти ДСТУ]]