Kupyna

Поделись знанием:
Перейти к: навигация, поиск
Криптографическая</br>хеш-функция
Название

Kupyna

Опубликован

2014

Размер хеша

переменный, 8-512 бит (рекомендуемые значения 256, 384, 512)

Число раундов

10 при длине хеша 8-256 бит; 14 при длине хеша 264-512 бит

Тип

хеш-функция

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





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

Купена аптечная — растение семейства Иглицевые (Ruscaceae), произрастающие на территории всей Украины в хвойных и смешанных лесах, занесена в Красную книгу Украины.[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)\oplus 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 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

Подстановка π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


Напишите отзыв о статье "Kupyna"

Примечания

  1. ↑ www.csm.kiev.ua/index.php?option=com_content&view=article&id=3022:2015-02-16-08-31-21&catid=1:latest-news&Itemid=120&lang=ru В Украине внедряются новые стандарты криптографической защиты информации
  2. ↑ eprint.iacr.org/2015/885.pdf A New Standard of Ukraine: The Kupyna Hash Function
  3. ↑ www.slideshare.net/oliynykov/kupyna Main properties of the new Ukrainian national standard on cryptographic hash function
  4. ↑ Christoph Dobraunig, Maria Eichlseder, and Florian Mendel. [eprint.iacr.org/2015/956.pdf Analysis of the Kupyna-256 Hash Function] (англ.) (2015). Проверено 1 октября 2015.
  5. ↑ Jian Zou, Le Dong. [eprint.iacr.org/2015/959.pdf Cryptanalysis of the Round-Reduced Kupyna Hash Function] (англ.) (2015). Проверено 2 октября 2015.
Общего назначения

Adler-32 • CRC • FNV • Murmur2 • PJW-32 • TTH • Jenkins hash

Криптографические

CubeHash • BLAKE • BMW • ECHO • FSB • Fugue • Grøstl • JH • Hamsi • HAVAL • Keccak (SHA-3) • Kupyna • LM-хеш • Luffa • MD2 • MD4 • MD5 • MD6 • N-Hash • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 • SHA-1 • SHA-2 • SHABAL • SHAvite-3 • SIMD • Skein • Snefru • SWIFFT • Tiger • Whirlpool • ГОСТ Р 34.11-94 • ГОСТ Р 34.11-2012

Функции формирования ключа

bcrypt • PBKDF2 • scrypt

Отрывок, характеризующий Kupyna


Вернувшись в полк и передав командиру, в каком положении находилось дело Денисова, Ростов с письмом к государю поехал в Тильзит.
13 го июня, французский и русский императоры съехались в Тильзите. Борис Друбецкой просил важное лицо, при котором он состоял, о том, чтобы быть причислену к свите, назначенной состоять в Тильзите.
– Je voudrais voir le grand homme, [Я желал бы видеть великого человека,] – сказал он, говоря про Наполеона, которого он до сих пор всегда, как и все, называл Буонапарте.
– Vous parlez de Buonaparte? [Вы говорите про Буонапарта?] – сказал ему улыбаясь генерал.
Борис вопросительно посмотрел на своего генерала и тотчас же понял, что это было шуточное испытание.
– Mon prince, je parle de l'empereur Napoleon, [Князь, я говорю об императоре Наполеоне,] – отвечал он. Генерал с улыбкой потрепал его по плечу.
– Ты далеко пойдешь, – сказал он ему и взял с собою.
Борис в числе немногих был на Немане в день свидания императоров; он видел плоты с вензелями, проезд Наполеона по тому берегу мимо французской гвардии, видел задумчивое лицо императора Александра, в то время как он молча сидел в корчме на берегу Немана, ожидая прибытия Наполеона; видел, как оба императора сели в лодки и как Наполеон, приставши прежде к плоту, быстрыми шагами пошел вперед и, встречая Александра, подал ему руку, и как оба скрылись в павильоне. Со времени своего вступления в высшие миры, Борис сделал себе привычку внимательно наблюдать то, что происходило вокруг него и записывать. Во время свидания в Тильзите он расспрашивал об именах тех лиц, которые приехали с Наполеоном, о мундирах, которые были на них надеты, и внимательно прислушивался к словам, которые были сказаны важными лицами. В то самое время, как императоры вошли в павильон, он посмотрел на часы и не забыл посмотреть опять в то время, когда Александр вышел из павильона. Свидание продолжалось час и пятьдесят три минуты: он так и записал это в тот вечер в числе других фактов, которые, он полагал, имели историческое значение. Так как свита императора была очень небольшая, то для человека, дорожащего успехом по службе, находиться в Тильзите во время свидания императоров было делом очень важным, и Борис, попав в Тильзит, чувствовал, что с этого времени положение его совершенно утвердилось. Его не только знали, но к нему пригляделись и привыкли. Два раза он исполнял поручения к самому государю, так что государь знал его в лицо, и все приближенные не только не дичились его, как прежде, считая за новое лицо, но удивились бы, ежели бы его не было.
Борис жил с другим адъютантом, польским графом Жилинским. Жилинский, воспитанный в Париже поляк, был богат, страстно любил французов, и почти каждый день во время пребывания в Тильзите, к Жилинскому и Борису собирались на обеды и завтраки французские офицеры из гвардии и главного французского штаба.
24 го июня вечером, граф Жилинский, сожитель Бориса, устроил для своих знакомых французов ужин. На ужине этом был почетный гость, один адъютант Наполеона, несколько офицеров французской гвардии и молодой мальчик старой аристократической французской фамилии, паж Наполеона. В этот самый день Ростов, пользуясь темнотой, чтобы не быть узнанным, в статском платье, приехал в Тильзит и вошел в квартиру Жилинского и Бориса.
В Ростове, также как и во всей армии, из которой он приехал, еще далеко не совершился в отношении Наполеона и французов, из врагов сделавшихся друзьями, тот переворот, который произошел в главной квартире и в Борисе. Все еще продолжали в армии испытывать прежнее смешанное чувство злобы, презрения и страха к Бонапарте и французам. Еще недавно Ростов, разговаривая с Платовским казачьим офицером, спорил о том, что ежели бы Наполеон был взят в плен, с ним обратились бы не как с государем, а как с преступником. Еще недавно на дороге, встретившись с французским раненым полковником, Ростов разгорячился, доказывая ему, что не может быть мира между законным государем и преступником Бонапарте. Поэтому Ростова странно поразил в квартире Бориса вид французских офицеров в тех самых мундирах, на которые он привык совсем иначе смотреть из фланкерской цепи. Как только он увидал высунувшегося из двери французского офицера, это чувство войны, враждебности, которое он всегда испытывал при виде неприятеля, вдруг обхватило его. Он остановился на пороге и по русски спросил, тут ли живет Друбецкой. Борис, заслышав чужой голос в передней, вышел к нему навстречу. Лицо его в первую минуту, когда он узнал Ростова, выразило досаду.
– Ах это ты, очень рад, очень рад тебя видеть, – сказал он однако, улыбаясь и подвигаясь к нему. Но Ростов заметил первое его движение.
– Я не во время кажется, – сказал он, – я бы не приехал, но мне дело есть, – сказал он холодно…
– Нет, я только удивляюсь, как ты из полка приехал. – «Dans un moment je suis a vous», [Сию минуту я к твоим услугам,] – обратился он на голос звавшего его.
– Я вижу, что я не во время, – повторил Ростов.
Выражение досады уже исчезло на лице Бориса; видимо обдумав и решив, что ему делать, он с особенным спокойствием взял его за обе руки и повел в соседнюю комнату. Глаза Бориса, спокойно и твердо глядевшие на Ростова, были как будто застланы чем то, как будто какая то заслонка – синие очки общежития – были надеты на них. Так казалось Ростову.
– Ах полно, пожалуйста, можешь ли ты быть не во время, – сказал Борис. – Борис ввел его в комнату, где был накрыт ужин, познакомил с гостями, назвав его и объяснив, что он был не статский, но гусарский офицер, его старый приятель. – Граф Жилинский, le comte N.N., le capitaine S.S., [граф Н.Н., капитан С.С.] – называл он гостей. Ростов нахмуренно глядел на французов, неохотно раскланивался и молчал.
Жилинский, видимо, не радостно принял это новое русское лицо в свой кружок и ничего не сказал Ростову. Борис, казалось, не замечал происшедшего стеснения от нового лица и с тем же приятным спокойствием и застланностью в глазах, с которыми он встретил Ростова, старался оживить разговор. Один из французов обратился с обыкновенной французской учтивостью к упорно молчавшему Ростову и сказал ему, что вероятно для того, чтобы увидать императора, он приехал в Тильзит.
– Нет, у меня есть дело, – коротко ответил Ростов.
Ростов сделался не в духе тотчас же после того, как он заметил неудовольствие на лице Бориса, и, как всегда бывает с людьми, которые не в духе, ему казалось, что все неприязненно смотрят на него и что всем он мешает. И действительно он мешал всем и один оставался вне вновь завязавшегося общего разговора. «И зачем он сидит тут?» говорили взгляды, которые бросали на него гости. Он встал и подошел к Борису.
– Однако я тебя стесняю, – сказал он ему тихо, – пойдем, поговорим о деле, и я уйду.
– Да нет, нисколько, сказал Борис. А ежели ты устал, пойдем в мою комнатку и ложись отдохни.
– И в самом деле…
Они вошли в маленькую комнатку, где спал Борис. Ростов, не садясь, тотчас же с раздраженьем – как будто Борис был в чем нибудь виноват перед ним – начал ему рассказывать дело Денисова, спрашивая, хочет ли и может ли он просить о Денисове через своего генерала у государя и через него передать письмо. Когда они остались вдвоем, Ростов в первый раз убедился, что ему неловко было смотреть в глаза Борису. Борис заложив ногу на ногу и поглаживая левой рукой тонкие пальцы правой руки, слушал Ростова, как слушает генерал доклад подчиненного, то глядя в сторону, то с тою же застланностию во взгляде прямо глядя в глаза Ростову. Ростову всякий раз при этом становилось неловко и он опускал глаза.


Источник — «http://wiki-org.ru/wiki/index.php?title=Kupyna&oldid=73737278»