WikiSort.ru - Не сортированное

Общая структура

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₁||M₂||M₃|| . . . ||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}$ v₂₅₆, 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}$ v₅₁₂, 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 бита

После дополнения до 32-х битного оно будет выглядеть так

Расширение сообщения

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}}$ ,m₁, . . . ,m₇, c₀, c₁, . . . , c₇) = (m₀,m₁, c₀, c₁, c₂, c₃,m₂,m₃,m₄, m₅, c₄, c₅, c₆, c₇,m₆,m₇)

Порядок слов легче всего запомнить с помощью следующей таблицы, результат из которой можно получить построчным считыванием:

В Hamsi-512

C: {0, 1}${\displaystyle ^{512}}$ × {0, 1}${\displaystyle ^{512}}$ → {0, 1}${\displaystyle ^{1024}}$ , а подробнее

C(m₀,m₁, . . . ,m₁₄,m₁₅, c₀, c₁, . . . , c₁₄, c₁₅) = (m₀,m₁, c₀, c₁,m₂,m₃, c₂, c₃, c₄, c₅,m₄,m₅, c₆, c₇,m₆,m₇,m₈, m₉, c₈, c₉,m₁₀,m₁₁, c₁₀, c₁₁, c₁₂, c₁₃,m₁₂,m₁₃, c₁₄, c₁₅,m₁₄,m₁₅)

Нелинейная перестановка P

Нелинейная перестановка состоит из трех этапов

• Над входными битами, константами и счетчиком выполняется операция XOR
• Затем следует применение 4-битных S-боксов
• И наконец несколько применений линейного преобразования L

Все это повторяется столько раз, сколько задано количество циклов. На вход каждый раз поступает сообщение (s₀, s₁, s₂, . . . , s_j), где j равно 15 для Hamsi-256 и 31 для Hamsi-512.

Округление

Округление T : {0, 1}⁵¹² → {0, 1}²⁵⁶ в Hamsi-256 определяется следующим образом:

T (s₀, s₁, s₂, . . . , s₁₄, s₁₅) = (s₀, s₁, s₂, s₃, s₈, s₉, s₁₀, s₁₁)

В Hamsi-512 округление T : {0, 1}¹⁰²⁴ → {0, 1}⁵¹² определяется так:

T (s₀, s₁, s₂, . . . , s₃₀, s₃₁) = (s₀, s₁, s₂, s₃, s₄, s₅, s₆, s₇, s₁₆, s₁₇, s₁₈, s₁₉, s₂₀, s₂₁, s₂₂, s₂₃)

Округление осуществляется после финального цикла нелинейной перестановки.

Нелинейная перестановка P_f

Нелинейные перестановки P и P_f отличаются только константами. Также P_f применяется только к последнему блоку сообщений как финальное преобразование.

Константы для P_f:

Количество циклов

Количество циклов для различных вариантов Hamsi приведены в таблице:

Во втором туре соревнования SHA-3 появилась новая модификация алгоритма под названием Hamsi-256/8. Её отличие от Hamsi-256 в том, что количество P_f циклов теперь равно 8.