Меню Главная Случайная статья Настройки Hamsi Материал из https://ru.wikipedia.org Hamsi — криптографическая хеш-функция, в основу которой положены алгоритмы Grindahl[1] и Serpent[2]. Эта хеш-функция не запатентована и является общественным достоянием. Существуют две разновидности алгоритма: Hamsi-256 и Hamsi-512. В основе алгоритма лежат функция разложения и циклическая трансформация. Циклическая трансформация работает с четырьмя строками матрицы состояний. Число столбцов этой матрицы равно 4 для Hamsi-256, 8 для Hamsi-512. Элементами матрицы являются слова размером 32 бита. Содержание 1 История 2 Описание 2.1 Общая структура 2.2 Начальные значения 2.3 Дополнение сообщения 2.4 Расширение сообщения 2.5 Конкатенация 2.6 Нелинейная перестановка P 2.6.1 1) Прибавление констант и счетчика 2.6.2 2) Этап подстановки 2.6.3 3) Этап преобразования 2.7 Округление 2.8 Нелинейная перестановка Pf 2.9 Количество циклов 3 Примечания 4 Литература История Hamsi была одним из участников в открытом конкурсе[3] SHA-3 Национального института стандартов и технологий[4] по разработке новых криптографических хеш-функций, которые преобразуют сообщения переменной длины в сжатые текстовые строки фиксированной длины, что может быть использовано для электронно-цифровых подписей, аутентификации сообщений и других применений. В первом раунде соревнования приняли участие 51 кандидат. 14 из них (включая Hamsi) прошли во второй тур[5]. Однако Hamsi не попала в число 5 кандидатов последнего тура, объявленных 10 декабря 2010 года[6]. Описание Общая структура Hamsi использует такие преобразования, как конкатенация (англ. Concatenation), перестановка (англ. Permutation) и округление (англ. Truncation), которые также используются в других алгоритмах хеширования, например Snefru[7] и Grindahl. В алгоритме также применяется функции расширения текста сообщения (англ. Message expansion) и распространения связывающего значения (англ. Chaining value) на каждой итерации. Для нелинейных перестановок (англ. Non-linear Permitations) используются линейные преобразования и один S-box из блочного шифрования Serpent. Общую структуру Hamsi можно представить в виде: 1 Message Expansion E : {0, 1}${\displaystyle ^{m}}$ {0, 1}${\displaystyle ^{n}}$ 2 Concatenation C : {0, 1}${\displaystyle ^{n}}$ x {0, 1}${\displaystyle ^{n}}$ {0, 1}${\displaystyle ^{s}}$ 3 Non-linear Permutations P,P${\displaystyle _{f}}$ : {0, 1}${\displaystyle ^{s}}$ {0, 1}${\displaystyle ^{s}}$ 4 Truncation T : {0, 1}${\displaystyle ^{s}}$ {0, 1}${\displaystyle ^{n}}$ Обозначения: F${\displaystyle _{n}}$ Конечное поле из n элементов <<< Циклический сдвиг влево ${\displaystyle \oplus }$ Исключающее ИЛИ (XOR) << Битовый сдвиг влево [n, m, d] Код длины n, размерностью m и минимальным расстоянием d Значения m, n и s для различных вариантов Hamsi представлены в следующей таблице: m n s Hamsi-256 32 256 512 Hamsi-512 64 512 1024 Пусть (M1||M2||M3|| . . . ||M${\displaystyle _{\ell }}$||) уже дополненное сообщение, тогда разновидности Hamsi могут быть описаны следующим образом: Hamsi-256: h${\displaystyle _{i}}$ = (T P C(E(M${\displaystyle _{i}}$), h${\displaystyle _{i}}$1)) h${\displaystyle _{i}}$1, h${\displaystyle _{0}}$ = ${\displaystyle i}$v256, 0 < ${\displaystyle i}$ < ${\displaystyle \ell }$ h = (T P${\displaystyle _{f}}$ C(E(M${\displaystyle _{\ell }}$), h${\displaystyle _{\ell }}$1)) h${\displaystyle _{\ell }}$1 Hamsi-512: h${\displaystyle _{i}}$ = (T P C(E(M${\displaystyle _{i}}$), h${\displaystyle _{i}}$1)) h${\displaystyle _{i}}$1, h${\displaystyle _{0}}$ = ${\displaystyle i}$v512, 0 < ${\displaystyle i}$ < ${\displaystyle \ell }$ h = (T P${\displaystyle _{f}}$ C(E(M${\displaystyle _{\ell }}$), h${\displaystyle _{\ell }}$1)) h${\displaystyle _{\ell }}$1 Начальные значения Начальным значением для алгоритма является начальное значение связывающего значения h${\displaystyle _{0}}$. Оно получено с помощью кодировки UTF-8 следующего сообщения: «Ozgul Kucuk, Katholieke Universiteit Leuven, Departement Elektrotechniek, Computer Security and Industrial Cryptography, Kasteelpark Arenberg 10, bus 2446, B-3001 Leuven-Heverlee, Belgium.» Начальные значения для различных разновидностей алгоритма представлены в следующей таблице: ${\displaystyle i}$v256 0x76657273, 0x69746569, 0x74204c65, 0x7576656e 0x2c204b61, 0x74686f6c, 0x69656b65, 0x20556e69 ${\displaystyle i}$v512 0x73746565, 0x6c706172, 0x6b204172, 0x656e6265 0x72672031, 0x302c2062, 0x75732032, 0x3434362c 0x20422d33, 0x30303120, 0x4c657576, 0x656e2d48 0x65766572, 0x6c65652c, 0x2042656c, 0x6769756d Дополнение сообщения Hamsi оперирует с блоками сообщений длиной 32 и 64 бита для алгоритмов Hamsi-256 и Hamsi-512 соответственно. Если длина блока меньше чем необходимо, тогда происходит дополнение сообщения (англ. Message padding). Дополнение происходит следующим образом. К сообщению справа добавляется один бит значением '1', а затем добавляются биты со значениями равными '0' до тех пор пока длина сообщения не станет равной 32 или 64. Пример: Есть сообщение длиной 24 бита 1010 0110 1110 1111 1111 0000 После дополнения до 32-х битного оно будет выглядеть так 1010 0110 1110 1111 1111 0000 1000 0000 Расширение сообщения Hamsi использует линейные коды[8] для расширения сообщений. Для Hamsi-256 расширение сообщения длиной 32 бита в сообщение длиной 256 бит производится с помощью кода [128, 16, 70] над полем F${\displaystyle _{4}}$[9]. Для Hamsi-512 расширение сообщения длиной 64 бита в сообщение длиной 512 бит производится с помощью кода [256, 32, 131] над полем F${\displaystyle _{4}}$. Конкатенация К словам расширенного сообщения (m${\displaystyle _{0}}$,m${\displaystyle _{1}}$, . . . ,m${\displaystyle _{i}}$) приписывается связывающее значение (c${\displaystyle _{0}}$, c${\displaystyle _{1}}$, . . . , c${\displaystyle _{j}}$). Значения i и j равны 7 для Hamsi-256 и 15 для Hamsi-512. Затем над полученным сообщением будет произведена нелинейная перестановка P. Метод конкатенации определяет порядок следования битов на входе Р. В Hamsi-256 C: {0, 1}${\displaystyle ^{256}}$x{0, 1}${\displaystyle ^{256}}$ {0, 1}${\displaystyle ^{512}}$, а подробнее C(m${\displaystyle _{0}}$,m1, . . . ,m7, c0, c1, . . . , c7) = (m0,m1, c0, c1, c2, c3,m2,m3,m4, m5, c4, c5, c6, c7,m6,m7) Порядок слов легче всего запомнить с помощью следующей таблицы, результат из которой можно получить построчным считыванием: m0 m1 c0 c1 c2 c3 m2 m3 m4 m5 c4 c5 c6 c7 m6 m7 В Hamsi-512 C: {0, 1}${\displaystyle ^{512}}$ {0, 1}${\displaystyle ^{512}}$ {0, 1}${\displaystyle ^{1024}}$, а подробнее C(m0,m1, . . . ,m14,m15, c0, c1, . . . , c14, c15) = (m0,m1, c0, c1,m2,m3, c2, c3, c4, c5,m4,m5, c6, c7,m6,m7,m8, m9, c8, c9,m10,m11, c10, c11, c12, c13,m12,m13, c14, c15,m14,m15) Нелинейная перестановка P Нелинейная перестановка состоит из трех этапов Над входными битами, константами и счетчиком выполняется операция XOR Затем следует применение 4-битных S-боксов И наконец несколько применений линейного преобразования L Все это повторяется столько раз, сколько задано количество циклов. На вход каждый раз поступает сообщение (s0, s1, s2, . . . , sj), где j равно 15 для Hamsi-256 и 31 для Hamsi-512. На этом этапе над входным сообщением, константами и счетчиком выполняется операция XOR. Счетчик определяет номер выполненного цикла. Для первого цикла c равен 0, для второго с = 1 и так далее. Используемые константы приведены в следующей таблице: 0 = 0xff00f0f0 1 = 0xccccaaaa 2 = 0xf0f0cccc 3 = 0xff00aaaa 4 = 0xccccaaaa 5 = 0xf0f0ff00 6 = 0xaaaacccc 7 = 0xf0f0ff00 8 = 0xf0f0cccc 9 = 0xaaaaff00 10 = 0xccccff00 11 = 0xaaaaf0f0 12 = 0xaaaaf0f0 13 = 0xff00cccc 14 = 0xccccf0f0 15 = 0xff00aaaa 16 = 0xccccaaaa 17 = 0xff00f0f0 18 = 0xff00aaaa 19 = 0xf0f0cccc 20 = 0xf0f0ff00 21 = 0xccccaaaa 22 = 0xf0f0ff00 23 = 0xaaaacccc 24 = 0xaaaaff00 25 = 0xf0f0cccc 26 = 0xaaaaf0f0 27 = 0xccccff00 28 = 0xff00cccc 29 = 0xaaaaf0f0 30 = 0xff00aaaa 31 = 0xccccf0f0 В Hamsi-256 (s0, s1, . . . , s15) := (s0 0, s1 1 c, s2, . . . , s15 15) В Hamsi-512 (s0, s1, . . . , s31) := (s0 0, s1 1 c, s2, . . . , s31 31) На этом этапе происходит подстановка 4-битных S-боксов, взятых из алгоритма Serpent. Hamsi очень удобно спроектирован для параллельного вычисления. Все 128 идентичных S-боксов (256 для Hamsi-512) могут обсчитываться в одно и то же время, что ускоряет работу алгоритма. S-box используемый в Hamsi: x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 s[x] 8 6 7 9 3 C A F D 1 E 4 0 B 5 2 Этап преобразования основан на нескольких применениях линейного преобразования L: {0, 1}${\displaystyle ^{128}}$ {0, 1}${\displaystyle ^{128}}$. L оперирует с 32-битными словами. В общем виде преобразование можно записать в виде (si, sj, sk, sl) := L(si, sj, sk, sl). Более подробное описание преобразования L(a, b, c, d): a := a <<< 13 c := c <<< 3 b := b a c d := d c (a << 3) b := b <<< 1 d := d <<< 7 a := a b d c := c d (b << 7) a := a <<< 5 c := c <<< 22 Округление Округление T : {0, 1}512 {0, 1}256 в Hamsi-256 определяется следующим образом: T (s0, s1, s2, . . . , s14, s15) = (s0, s1, s2, s3, s8, s9, s10, s11) В Hamsi-512 округление T : {0, 1}1024 {0, 1}512 определяется так: T (s0, s1, s2, . . . , s30, s31) = (s0, s1, s2, s3, s4, s5, s6, s7, s16, s17, s18, s19, s20, s21, s22, s23) Округление осуществляется после финального цикла нелинейной перестановки. Нелинейная перестановка Pf Нелинейные перестановки P и Pf отличаются только константами. Также Pf применяется только к последнему блоку сообщений как финальное преобразование. Константы для Pf: 0 = 0xcaf9639c 1 = 0x0ff0f9c0 2 = 0x639c0ff0 3 = 0xcaf9f9c0 4 = 0x0ff0f9c0 5 = 0x639ccaf9 6 = 0xf9c00ff0 7 = 0x639ccaf9 8 = 0x639c0ff0 9 = 0xf9c0caf9 10 = 0x0ff0caf9 11 = 0xf9c0639c 12 = 0xf9c0639c 13 = 0xcaf90ff0 14 = 0x0ff0639c 15 = 0xcaf9f9c0 16 = 0x0ff0f9c0 17 = 0xcaf9639c 18 = 0xcaf9f9c0 19 = 0x639c0ff0 20 = 0x639ccaf9 21 = 0x0ff0f9c0 22 = 0x639ccaf9 23 = 0xf9c00ff0 24 = 0xf9c0caf9 25 = 0x639c0ff0 26 = 0xf9c0639c 27 = 0x0ff0caf9 28 = 0xcaf90ff0 29 = 0xf9c0639c 30 = 0xcaf9f9c0 31 = 0x0ff0639c Количество циклов Количество циклов для различных вариантов Hamsi приведены в таблице: Hamsi-256 Hamsi-512 P циклов 3 6 Pf циклов 6 12 Во втором туре соревнования SHA-3 появилась новая модификация алгоритма под названием Hamsi-256/8. Её отличие от Hamsi-256 в том, что количество Pf циклов теперь равно 8. Примечания L. R. Knudsen, C. Rechberger, S. S. Thomsen. Grindahl — a family of hash functions (неопр.) // Lecture Notes in Computer Science. — 2007. — Т. 4593. — С. 39—57. — doi:10.1007/978-3-540-74619-5_3. Архивировано из оригинала 15 сентября 2012 года. Serpent: A proposal for the advanced encryption standard Архивная копия от 13 января 2013 на Wayback Machine. NIST.gov — Computer Security Division — Computer Security Resource Center  (неопр.). Дата обращения: 28 ноября 2009. Архивировано 9 июля 2011 года. National Institute of Standards and Technology  (неопр.). Дата обращения: 28 ноября 2009. Архивировано 17 июня 2015 года. NIST.gov — Computer Security Division — Computer Security Resource Center  (неопр.). Дата обращения: 28 ноября 2009. Архивировано 10 апреля 2012 года. Status Report on the Second Round of the SHA-3  (неопр.). Дата обращения: 15 июня 2015. Архивировано 14 марта 2011 года. Merkle R.C. A Fast Software One-Way Hash Function. Journal of Cryptology, 3(1):43-58, 1990 J.H. van Lint. Introduction to Coding Theory Bounds on the minimum distance of linear codes. http://codetables.de.BKLC/ (недоступная ссылка) Литература zgl Kck. The Hash Function Hamsi  (неопр.) (PDF) (31 октября 2008). Дата обращения: 11 декабря 2008. Архивировано 11 апреля 2012 года. https://web.archive.org/web/20100825061836/http://homes.esat.kuleuven.be/~okucuk/hamsi/index.html http://www.cosic.esat.kuleuven.be/publications/article-1203.pdf