Hamsi

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2012. április 12-én felülvizsgált verziótól ; az ellenőrzésekhez 10 szerkesztés szükséges .

A Hamsi egy Grindahl [1] és Serpent [2] algoritmusokon alapuló kriptográfiai hash függvény . Ez a hash funkció nem szabadalmaztatott , és nyilvános . Az algoritmusnak két változata van : Hamsi-256 és Hamsi-512. Az algoritmus a bővítési függvényen és a ciklikus transzformáción alapul . A ciklikus transzformáció az állapotmátrix négy sorával működik . A mátrix oszlopainak száma Hamsi-256 esetében 4, Hamsi-512 esetén 8. A mátrix elemei 32 bites szavak .

Történelem

Hamsi egyike volt a Nemzeti Szabványügyi és Technológiai Intézet [4] SHA-3 nyílt versenyének [ 4] , amelynek célja olyan új kriptográfiai hash függvények kifejlesztése volt , amelyek a változó hosszúságú üzeneteket rögzített hosszúságú tömörített szöveges karakterláncokká alakítják, amelyek elektronikusan használhatók. digitális aláírások , üzenet- hitelesítés és egyéb alkalmazások. A verseny első fordulójában 51 pályázó vett részt. Közülük 14-en (köztük Hamsi) jutottak tovább a második körbe [5] . Hamsi azonban nem volt a 2010. december 10-én bejelentett 5 utolsó fordulós jelölt között [6] .

Leírás

Általános szerkezet

Hamsi olyan transzformációkat használ, mint az összefűzés ( angol Concatenation ), a permutáció ( angol permutáció ) és a kerekítés ( angol csonkítás ), amelyeket más hash - algoritmusokban is használnak , mint például a Snefru [7] és a Grindahl . Az algoritmus minden iterációnál használja a Message expansion és Chaining value függvényeket is . A nemlineáris permutációkhoz ( eng. Non-linear Permitations ) lineáris transzformációkat és egy S-boxot használnak a Serpent blokk titkosításból . A Hamsi általános szerkezete a következőképpen ábrázolható:

egy	üzenetbővítés	E : {0, 1} → {0, 1} $^{m}$ $^{n}$
2	Összefűzés	C : {0, 1} x {0, 1} → {0, 1} $^{n}$ $^{n}$ $^{s}$
3	Nemlineáris permutációk	P,P : {0, 1} → {0, 1} ${\megjelenítési stílus _{f))$ $^{s}$ $^{s}$
négy	Csonkolás	T : {0, 1} → {0, 1} $^{s}$ $^{n}$

Megnevezések:

F ${\megjelenítési stílus _{n}}$	n elemből álló végső mező
<<<	Forgatás balra
$\oplus$	Exkluzív VAGY ( XOR )
<<	Kis eltolás balra
[n, m, d]	Az n hosszúság, az m méret és a d minimális távolság kódja

A különböző Hamsi-változatok m, n és s értékeit a következő táblázat tartalmazza:

	m	n	s
Hamsi-256	32	256	512
Hamsi-512	64	512	1024

A Legyen (M 1 ||M 2 ||M 3 || . . . ||M ||) már egy befejezett üzenet, akkor a Hamsi fajtái így írhatók le: ${\displaystyle _{\ell ))$

Hamsi-256:

h = (T ◦ P ◦ C(E(M ), h −1)) ⊕ h −1, h = v 256 , 0 < < ${\megjelenítési stílus _{i))$ ${\megjelenítési stílus _{i))$ ${\megjelenítési stílus _{i))$ ${\megjelenítési stílus _{i))$ $_{0}$ $én$ $én$ $\ell$

h = (T ◦ P ◦ C(E(M ), h −1)) ⊕ h −1 ${\megjelenítési stílus _{f))$ ${\displaystyle _{\ell ))$ ${\displaystyle _{\ell ))$ ${\displaystyle _{\ell ))$

Hamsi-512:

h = (T ◦ P ◦ C(E(M ), h −1)) ⊕ h −1, h = v 512 , 0 < < ${\megjelenítési stílus _{i))$ ${\megjelenítési stílus _{i))$ ${\megjelenítési stílus _{i))$ ${\megjelenítési stílus _{i))$ $_{0}$ $én$ $én$ $\ell$

h = (T ◦ P ◦ C(E(M ), h −1)) ⊕ h −1 ${\megjelenítési stílus _{f))$ ${\displaystyle _{\ell ))$ ${\displaystyle _{\ell ))$ ${\displaystyle _{\ell ))$

Kezdeti értékek

Az algoritmus kezdeti értéke a h $_{0}$ kötési érték kezdeti értéke . A következő üzenet UTF-8 kódolásával szerezhető be : "Ozgul Kucuk, Katholieke Universiteit Leuven, Departement Elektrotechniek, Computer Security and Industrial Cryptography, Kasteelpark Arenberg 10, bus 2446, B-3001 Leuven-Heverlee, Belgium." Az algoritmus különböző változatainak kezdeti értékeit a következő táblázat mutatja be:

én

v 256

0x76657273, 0x69746569, 0x74204c65, 0x7576656e

0x2c204b61, 0x74686f6c, 0x69656b65, 0x20556e69

én

v 512

0x73746565, 0x6c706172, 0x6b204172, 0x656e6265

0x72672031, 0x302c2062, 0x75732032, 0x3434362c

0x20422d33, 0x30303120, 0x4c657576, 0x656e2d48

0x65766572, 0x6c65652c, 0x2042656c, 0x6769756d

Az üzenet befejezése

A Hamsi 32 és 64 bites üzenetblokkon működik a Hamsi-256 és a Hamsi-512 algoritmusokhoz . Ha a blokk hossza kisebb a szükségesnél, akkor az üzenet kitöltése történik . A kiegészítés a következő. Egy '1' értékű bit hozzáadódik a jobb oldali üzenethez , majd '0' értékű biteket ad hozzá addig, amíg az üzenet hossza 32 vagy 64 lesz. Példa:

24 bites üzenet van

1010 0110 1110 1111 1111 0000

A 32 bites kitöltés után így fog kinézni

1010 0110 1110 1111 1111 0000	1000 0000

Üzenetbővítmény

Hamsi lineáris kódokat [8] használ az üzenetek kiterjesztésére. A Hamsi-256 esetében a 32 bites üzenet 256 bitessé történő kiterjesztése a [128, 16, 70] kód használatával történik az F [9] mező felett . A Hamsi-512 esetében a 64 bites üzenet 512 bites üzenetté való kiterjesztése a [256, 32, 131] kód használatával történik az F mező felett . ${\megjelenítési stílus _{4))$ ${\megjelenítési stílus _{4))$

Összefűzés

A kiterjesztett üzenet szavaihoz (m ,m , . . . ,m ) kapcsolódási érték (c , c , . . . , c ) van hozzárendelve . Az i és j értékek Hamsi-256 esetén 7, Hamsi-512 esetén 15. Ezután a kapott üzeneten egy nemlineáris permutációt hajtanak végre P. Az összefűzési módszer határozza meg a bitek sorrendjét a P bemeneten. $_{0}$ $_{egy}$ ${\megjelenítési stílus _{i))$ $_{0}$ $_{egy}$ ${\megjelenítési stílus _{j))$

Hamsi-256-nál

C: {0, 1} x{0, 1} → {0, 1} $^{256}$ $^{256}$ $^{512}$ , további részletek

C(m ,m1 , ...,m7 , c 0 , c 1 , ..., c 7 ) = (m 0 , m 1 , c 0 , c 1 , c 2 , c 3 , m 2 , m 3 , m 4 , m 5 , c 4 , c 5 , c 6 , c 7 , m 6 , m 7 ) $_{0}$

A szórendet a következő táblázat segítségével lehet a legkönnyebben megjegyezni, melynek eredményét soronkénti olvasással kaphatjuk meg:

m0 _	m 1	c 0	c 1
c 2	c 3	m2 _	m 3
m4 _	m 5	c 4	5 -től
6 -tól	7 -től	m6 _	m 7

Hamsi-512-nél

C: {0, 1} × {0, 1} → {0, 1} $^{512}$ $^{512}$ $^{1024}$ , további részletek

C(m 0 ,m 1 , ...,m 14 , m 15 , c 0 , c 1 , ..., c 14 , c 15 ) = (m 0 , m 1 , c 0 , c 1 , m 2 ,m 3 , c 2 , c 3 , c 4 , c 5 , m 4 , m 5 , c 6 , c 7 , m 6 , m 7 , m 8 , m 9 , c 8 , c 9 , m 10 , m 11 , s 10 , s 11 , s 12 , s 13 , m 12 , m 13 , s 14 , s 15 , m 14 , m 15 )

Nemlineáris permutáció P

A nemlineáris permutáció három szakaszból áll

A bemeneti bitek , a konstansok és a számláló XOR-re vannak állítva
Ezután a 4 bites S-boxok alkalmazása következik
És végül az L lineáris transzformáció számos alkalmazása

Mindez annyiszor ismétlődik, ahány ciklusszám adott. A bemenet minden alkalommal kap egy üzenetet (s 0 , s 1 , s 2 , . . . , s j ), ahol j értéke 15 a Hamsi-256 és 31 a Hamsi-512 esetében.

1) Állandók és számláló hozzáadása

Ebben a szakaszban a bemeneti üzenet, az állandók és a számláló XOR -re kerülnek . A számláló határozza meg a végrehajtott ciklus számát. Az első ciklusban c 0, a másodikban c = 1, és így tovább. A használt állandókat a következő táblázat mutatja:

α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-nál

(s 0 , s 1 , . . . , s 15 ) := (s 0 ⊕ α 0 , s 1 ⊕ α 1 ⊕ c, s 2 , ...

Hamsi-512-nél

(s 0 , s 1 , . . . , s 31 ) := (s 0 ⊕ α 0 , s 1 ⊕ α 1 ⊕ c, s 2 , ...

2) Helyettesítési szakasz

Ebben a szakaszban megtörténik a Serpent algoritmusból vett 4 bites S-boxok helyettesítése . A Hamsi nagyon jól megtervezett a párhuzamos számításokhoz . Mind a 128 egyforma S-box (256 a Hamsi-512-nél) egyszerre számítható, ami felgyorsítja az algoritmust. Hamsiban használt S-box :

x	0	egy	2	3	négy	5	6	7	nyolc	9	tíz	tizenegy	12	13	tizennégy	tizenöt
s[x]	nyolc	6	7	9	3	C	A	F	D	egy	E	négy	0	B	5	2

3) Konverziós szakasz

A transzformációs lépés az L $^{128}$ $^{128}$ lineáris transzformáció több alkalmazásán alapul : {0, 1} → {0, 1} . L 32 bites szavakkal működik. Általában a transzformációt így írhatjuk fel (s i , s j , s k , s l ) := L(s i , s j , s k , s l ) .

Az L(a, b, c, d) transzformáció részletesebb leírása :

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

Kerekítés

A T kerekítés : {0, 1} 512 → {0, 1} 256 Hamsi-256-ban a következőképpen definiálható:

T (s 0 , s 1 , s 2 , . . ., s 14 , s 15 ) = (s 0 , s 1 , s 2 , s 3 , s 8 , s 9 , s 10 , s 11 )

A Hamsi-512 T kerekítésben: {0, 1} 1024 → {0, 1} 512 a következőképpen van definiálva:

T (s 0 , s 1 , s 2 , ..., s 30 , s 31 ) = (s 0 , s 1 , s 2 , s 3 , s 4 , s 5 , s 6 , s 7 , s 16 , s 17 , s 18 , s 19 , s 20 , s 21 , s 22 , s 23 )

A kerekítés a nemlineáris permutáció utolsó ciklusa után történik.

Nemlineáris permutáció P f

A P és P f nemlineáris permutációk csak konstansokban különböznek egymástól. Ezenkívül a P f csak az utolsó üzenetblokkra vonatkozik végső transzformációként.

P f konstansai :

α 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

Ciklusok száma

A Hamsi különböző változataihoz tartozó ciklusok számát a táblázat tartalmazza:

	Hamsi-256	Hamsi-512
P ciklusok	3	6
P f ciklusok	6	12

Az SHA-3 verseny második fordulójában megjelent az algoritmus új módosítása, a Hamsi-256/8. A Hamsi-256-hoz képest az a különbség, hogy a Pf ciklusok száma most 8.

Jegyzetek

↑ L. R. Knudsen, C. Rechberger, S. S. Thomsen. Grindahl – a hash függvények családja (határozatlan) // Előadásjegyzetek a számítástechnikából. - 2007. - T. 4593 . - S. 39-57 . - doi : 10.1007/978-3-540-74619-5_3 . Az eredetiből archiválva: 2012. szeptember 15.
↑ Serpent: Javaslat a fejlett titkosítási szabványra Archiválva : 2013. január 13. a Wayback Machine -nél .
↑ NIST.gov – Computer Security Division – Computer Security Resource Center . Letöltve: 2009. november 28. Az eredetiből archiválva : 2011. július 9.. (határozatlan)
↑ Nemzeti Szabványügyi és Technológiai Intézet . Letöltve: 2009. november 28. Az eredetiből archiválva : 2015. június 17. (határozatlan)
↑ NIST.gov – Computer Security Division – Computer Security Resource Center . Letöltve: 2009. november 28. Az eredetiből archiválva : 2012. április 10.. (határozatlan)
↑ Állapotjelentés az SHA-3 második fordulójáról . Letöltve: 2015. június 15. Az eredetiből archiválva : 2011. március 14. (határozatlan)
↑ Merkle RC Gyors szoftver, egyirányú hash funkció. Journal of Cryptology, 3(1):43-58, 1990
↑ JH van Lint. Bevezetés a kódoláselméletbe
↑ A lineáris kódok minimális távolságának korlátai. http://codetables.de.BKLC/ (nem elérhető link)

Irodalom

Ozgül Kücük. The Hash Function Hamsi (PDF) (2008. október 31.). Letöltve: 2008. december 11. Az eredetiből archiválva : 2012. április 11.. (határozatlan)
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