Hamsi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 12. huhtikuuta 2012 tarkistetusta versiosta . tarkastukset vaativat 10 muokkausta .

Hamsi on kryptografinen hajautusfunktio, joka perustuu Grindahlin [1] ja Serpent [2] algoritmeihin . Tätä hash-toimintoa ei ole patentoitu ja se on julkisessa käytössä . Algoritmeja on kaksi : Hamsi-256 ja Hamsi-512. Algoritmi perustuu laajennusfunktioon ja sykliseen muunnokseen . Syklinen muunnos toimii tilamatriisin neljällä rivillä . Tämän matriisin sarakkeiden lukumäärä on 4 Hamsi-256:lle, 8 Hamsi-512:lle. Matriisin elementit ovat 32- bittisiä sanoja .

Historia

Hamsi osallistui Kansallisen Standardi- ja teknologiainstituutin [4] SHA-3 avoimeen kilpailuun [ 4] kehittääkseen uusia kryptografisia hajautusfunktioita , jotka muuntavat muuttuvan pituiset viestit kiinteäpituisiksi pakatuiksi tekstijonoiksi, joita voidaan käyttää sähköisessä muodossa . digitaaliset allekirjoitukset , viestien todennus ja muut sovellukset. Kilpailun ensimmäiseen kierrokseen osallistui 51 ehdokasta. Heistä 14 (mukaan lukien Hamsi) eteni toiselle kierrokselle [5] . Hamsi ei kuitenkaan ollut 10.12.2010 julkistetun viiden viimeisen kierroksen ehdokkaan joukossa [6] .

Kuvaus

Yleinen rakenne

Hamsi käyttää muunnoksia, kuten ketjuttamista ( englanniksi Concatenation ), permutaatiota ( englanniksi Permutation ) ja pyöristystä ( englanniksi Truncation ), joita käytetään myös muissa hajautusalgoritmeissa , kuten Snefru [7 ] ja Grindahl . Algoritmi käyttää myös Message Expansion - ja Chaining value - funktioita kussakin iteraatiossa . Epälineaarisille permutaatioille ( eng. Non-linear Permitations ) käytetään lineaarisia muunnoksia ja yhtä S-laatikkoa Serpent - lohkosalauksesta . Hamsin yleinen rakenne voidaan esittää seuraavasti:

yksi	viestin laajennus	E : {0, 1} → {0, 1} ${\näyttötyyli ^{m}}$ ${\näyttötyyli ^{n}}$
2	Yhdistäminen	C : {0, 1} x {0, 1} → {0, 1} ${\näyttötyyli ^{n}}$ ${\näyttötyyli ^{n}}$ ${\näyttötyyli ^{s))$
3	Epälineaariset permutaatiot	P,P : {0, 1} → {0, 1} ${\näyttötyyli _{f))$ ${\näyttötyyli ^{s))$ ${\näyttötyyli ^{s))$
neljä	Katkaisu	T : {0, 1} → {0, 1} ${\näyttötyyli ^{s))$ ${\näyttötyyli ^{n}}$

Nimitykset:

F ${\näyttötyyli _{n}}$	n elementin lopullinen kenttä
<<<	Kierrä vasemmalle
$\oplus$	Yksinomainen OR ( XOR )
<<	Bittinen siirto vasemmalle
[n, m, d]	Pituuden n koodi , mitta m ja minimietäisyys d

Eri Hamsi-muunnelmien m-, n- ja s-arvot on esitetty seuraavassa taulukossa:

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

Olkoon (M 1 ||M 2 ||M 3 || . . . ||M ||) on jo valmis viesti, niin Hamsin lajikkeet voidaan kuvata seuraavasti: ${\näyttötyyli _{\ell ))$

Hamsi-256:

h = (T ◦ P ◦ C(E(M ), h −1)) ⊕ h −1, h = v 256 , 0 < < ${\näyttötyyli _{i))$ ${\näyttötyyli _{i))$ ${\näyttötyyli _{i))$ ${\näyttötyyli _{i))$ ${\näyttötyyli _{0}}$ $i$ $i$ $\ell$

h = (T ◦ P ◦ C(E(M ), h −1)) ⊕ h −1 ${\näyttötyyli _{f))$ ${\näyttötyyli _{\ell ))$ ${\näyttötyyli _{\ell ))$ ${\näyttötyyli _{\ell ))$

Hamsi-512:

h = (T ◦ P ◦ C(E(M ), h −1)) ⊕ h −1, h = v 512 , 0 < < ${\näyttötyyli _{i))$ ${\näyttötyyli _{i))$ ${\näyttötyyli _{i))$ ${\näyttötyyli _{i))$ ${\näyttötyyli _{0}}$ $i$ $i$ $\ell$

h = (T ◦ P ◦ C(E(M ), h −1)) ⊕ h −1 ${\näyttötyyli _{f))$ ${\näyttötyyli _{\ell ))$ ${\näyttötyyli _{\ell ))$ ${\näyttötyyli _{\ell ))$

Alkuarvot

Algoritmin alkuarvo on sidosarvon h ${\näyttötyyli _{0}}$ alkuarvo . Se saadaan käyttämällä seuraavan viestin UTF-8- koodausta : "Ozgul Kucuk, Katholieke Universiteit Leuven, Departement Elektrotechniek, Computer Security and Industrial Cryptography, Kasteelpark Arenberg 10, bus 2446, B-3001 Leuven-Heverlee, Belgia." Algoritmin eri muunnelmien alkuarvot on esitetty seuraavassa taulukossa:

i

v 256

0x76657273, 0x69746569, 0x74204c65, 0x7576656e

0x2c204b61, 0x74686f6c, 0x69656b65, 0x20556e69

i

v 512

0x73746565, 0x6c706172, 0x6b204172, 0x656e6265

0x72672031, 0x302c2062, 0x75732032, 0x3434362c

0x20422d33, 0x30303120, 0x4c657576, 0x656e2d48

0x65766572, 0x6c65652c, 0x2042656c, 0x6769756d

Viestin valmistuminen

Hamsi toimii 32- ja 64 - bittisillä sanomalohkoilla Hamsi-256- ja Hamsi-512- algoritmeille . Jos lohkon pituus on pienempi kuin on tarpeen, tapahtuu viestin täyttö . Lisäys on seuraava. Oikealla olevaan viestiin lisätään yksi bitti , jonka arvo on '1' ja sitten bittejä , joiden arvo on "0", kunnes viestin pituus on 32 tai 64. Esimerkki:

Siellä on 24- bittinen viesti

1010 0110 1110 1111 1111 0000

32- bittisen täytön jälkeen se näyttää tältä

1010 0110 1110 1111 1111 0000	1000 0000

Viestilaajennus

Hamsi käyttää lineaarisia koodeja [8] viestien laajentamiseen. Hamsi-256:ssa 32-bittisen viestin laajentaminen 256 - bittiseksi sanomaksi tehdään käyttämällä koodia [128, 16, 70] F [9] -kentän päällä . Hamsi-512:ssa 64-bittisen viestin laajentaminen 512 - bittiseksi viestiksi tehdään käyttämällä koodia [256, 32, 131] F-kentän päällä . ${\näyttötyyli _{4))$ ${\näyttötyyli _{4))$

Yhdistäminen

Laajennetun viestin sanoille (m ,m , . . . ,m ) on annettu linkitysarvo (c , c , . . . , c ). i- ja j-arvot ovat 7 Hamsi-256:lle ja 15 Hamsi-512:lle. Tämän jälkeen vastaanotetulle viestille suoritetaan epälineaarinen permutaatio P. Ketjutusmenetelmä määrittää bittien järjestyksen tulossa P. ${\näyttötyyli _{0}}$ $_{yksi}$ ${\näyttötyyli _{i))$ ${\näyttötyyli _{0}}$ $_{yksi}$ ${\näyttötyyli _{j))$

Osoitteessa Hamsi-256

C: {0, 1} x{0, 1} → {0, 1} $^{256}$ $^{256}$ $^{512}$ , lisätietoja

C(m ,m1 ,...,m7 , c0 , c1 , ...,c7 ) = (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 ) ${\näyttötyyli _{0}}$

Sanajärjestys on helpoin muistaa seuraavan taulukon avulla, jonka tuloksen saa rivi riviltä lukemalla:

m0_ _	m 1	c 0	c 1
c 2	c 3	m2 _	m 3
m4 _	m 5	c 4	alkaen 5
alkaen 6	alkaen 7	m6 _	m 7

Osoitteessa Hamsi-512

C: {0, 1} × {0, 1} → {0, 1} $^{512}$ $^{512}$ $^{1024}$ , lisätietoja

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 )

Epälineaarinen permutaatio P

Epälineaarinen permutaatio koostuu kolmesta vaiheesta

Syöttöbitit , vakiot ja laskuri on XOR - red
Sitten seuraa 4-bittisten S-laatikoiden soveltaminen
Ja lopuksi useita lineaarisen muunnoksen L sovelluksia

Kaikki tämä toistetaan niin monta kertaa kuin syklien lukumäärä on annettu. Tulo vastaanottaa joka kerta viestin (s 0 , s 1 , s 2 , . . . , s j ), jossa j on 15 Hamsi-256:lle ja 31 Hamsi-512:lle.

1) Vakioiden ja laskurin lisääminen

Tässä vaiheessa syöttöviesti, vakiot ja laskuri on XORed . Laskuri määrittää suoritetun jakson numeron. Ensimmäisellä jaksolla c on 0, toisessa c = 1 ja niin edelleen. Käytetyt vakiot on esitetty seuraavassa taulukossa:

α0 = 0xff00f0f0	α 1 = 0xccccaaaa	α 2 = 0xf0f0cccc	α 3 = 0xff00aaaa
α 4 = 0xccccaaaa	α 5 = 0xf0f0ff00	a 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

Osoitteessa Hamsi-256

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

Osoitteessa Hamsi-512

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

2) Korvausvaihe

Tässä vaiheessa tapahtuu Serpent -algoritmista otettujen 4-bittisten S-laatikoiden korvaaminen . Hamsi on erittäin hyvin suunniteltu rinnakkaislaskentaan . Kaikki 128 identtistä S-laatikkoa (256 Hamsi-512:lle) voidaan laskea samanaikaisesti, mikä nopeuttaa algoritmia. S-box käytössä Hamsissa:

x	0	yksi	2	3	neljä	5	6	7	kahdeksan	9	kymmenen	yksitoista	12	13	neljätoista	viisitoista
s[x]	kahdeksan	6	7	9	3	C	A	F	D	yksi	E	neljä	0	B	5	2

3) Muunnosvaihe

Muunnosvaihe perustuu lineaarisen muunnoksen L useisiin sovelluksiin: {0, 1} → {0, 1} $^{128}$ $^{128}$ . L toimii 32-bittisillä sanoilla. Yleensä muunnos voidaan kirjoittaa muodossa (s i , s j , s k , s l ) := L(s i , s j , s k , s l ) .

Tarkempi kuvaus muunnoksesta 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

Pyöristys

Pyöristys T : {0, 1} 512 → {0, 1} 256 Hamsi-256:ssa määritellään seuraavasti:

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 )

Hamsi-512 pyöristyksessä T : {0, 1} 1024 → {0, 1} 512 määritellään seuraavasti:

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 )

Pyöristys suoritetaan epälineaarisen permutaation viimeisen jakson jälkeen.

Epälineaarinen permutaatio P f

Epälineaariset permutaatiot P ja P f eroavat vain vakioista. Myös P f käytetään vain viimeiseen viestilohkoon viimeisenä muunnoksena.

P f : n vakiot :

α 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

Jaksojen lukumäärä

Hamsin eri muunnelmien syklien lukumäärä on annettu taulukossa:

	Hamsi-256	Hamsi-512
P sykliä	3	6
P f sykliä	6	12

SHA-3- kilpailun toisella kierroksella ilmestyi uusi muunnos algoritmista nimeltä Hamsi-256/8. Sen ero Hamsi-256:sta on, että Pf - jaksojen lukumäärä on nyt 8.

Muistiinpanot

↑ L. R. Knudsen, C. Rechberger, S. S. Thomsen. Grindahl - hash-funktioiden perhe (määrittämätön) // Tietojenkäsittelytieteen luentomuistiinpanot. - 2007. - T. 4593 . - S. 39-57 . - doi : 10.1007/978-3-540-74619-5_3 . Arkistoitu alkuperäisestä 15. syyskuuta 2012.
↑ Serpent: Ehdotus edistyneeksi salausstandardiksi Arkistoitu 13. tammikuuta 2013 Wayback Machinessa .
↑ NIST.gov - Computer Security Division - Computer Security Resource Center . Haettu 28. marraskuuta 2009. Arkistoitu alkuperäisestä 9. heinäkuuta 2011. (määrätön)
↑ National Institute of Standards and Technology . Haettu 28. marraskuuta 2009. Arkistoitu alkuperäisestä 17. kesäkuuta 2015. (määrätön)
↑ NIST.gov - Computer Security Division - Computer Security Resource Center . Haettu 28. marraskuuta 2009. Arkistoitu alkuperäisestä 10. huhtikuuta 2012. (määrätön)
↑ Tilaraportti SHA-3:n toisesta kierroksella . Haettu 15. kesäkuuta 2015. Arkistoitu alkuperäisestä 14. maaliskuuta 2011. (määrätön)
↑ Merkle RC Nopea ohjelmiston yksisuuntainen hajautustoiminto. Journal of Cryptology, 3(1):43-58, 1990
↑ JH van Lint. Johdatus koodausteoriaan
↑ Lineaaristen koodien vähimmäisetäisyyden rajat. http://codetables.de.BKLC/ (linkki ei saatavilla)

Kirjallisuus

Ozgül Kücük. Hash Function Hamsi (PDF) (31. lokakuuta 2008). Haettu 11. joulukuuta 2008. Arkistoitu alkuperäisestä 11. huhtikuuta 2012. (määrätön)
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