Википедија

Fauler–Nol–Vo heš funkcija

(преусмерено са Fowler–Noll–Vo heš funkcija)

FAuler–Nol–Vo (енгл. Fowler–Noll–Vo hash function) je ne kriptografska heš funkcija koju su razvili Glen Fauler, Landon Kart Nol i Fong Vo.

Osnova FNV heš algoritma preuzeta je iz ideje koja je poslata kao recenzija u IEEE POSIX P1003.2 koju su pregledali Glenn Fowler i Phong Vo 1991. godine. U sledećem krugu glasanja Landon Curt Noll Poboljšao je njihov algoritam. Neki ljudi su testirali ovu heš funkciju i ispostavilo se da radi više nego dobro.[1] U email poruci koja je poslata Landonu, funkcija je imenovana Fowler/Noll/Vo ili skraćeno FNV heš funkcija.[2]

Pregled уреди

Verzije koje se trenutno koriste su FNV-1 i FNV-1a. One omogućavaju sredstvo za kreiranje ne nula FNV neutralizovanih osnova. Trenutno su na raspolaganju FNV heš funkcije različitih širina (32, 64, 128, 256, 512, i 1024-bitova). Za čiste FNV implementacije, dužine se isključivo određuju po dostupnosti FNV prostih brojeva koji opisuju opseg (broj bitova koji se koristi). Međutim na mnogim FNV web stranicama se diskutuje o metodama prilagođavanja jednog od gore navedenih verzija u manje blokove koji mogu ali i ne moraju biti stepeni dvojke.[3][4] FNV heš algoritam kao i uzorak FNV izvornog koda javno su objavljeni. [5]FNV ne predstavlja kriptografski heš.

Heš уреди

Jedna od FNV prednosti je da se veoma jednostavno implementira. Obično se počinje sa inicijalnom vrednošću FNV osnove, nakon toga se svaki bit sa ulaza množi sa FNV prostim brojem da bi se na kraju vršila bitovska operacija XOR sa ulaznim bitovima. Alternativa algoritma, FNV-1a, menja mesta koraku množenja i bitovskoj operaciji XOR.

FNV-1 Heš уреди

FNV-1 heš algoritam je nešto nalik sledećem:[6] 

   hash = FNV_offset_basis
   for each octet_of_data to be hashed
   	hash = hash × FNV_prime
   	hash = hash XOR octet_of_data
   return hash

U gornjem pseudokodu, sve varijable su neoznačeni celi brojevi. Sve varijable osim "octet_of_data", imaju isti broj bitova kao FNV heš. Varijabla, "octet_of_data'", je osmobitni neoznačen ceo broj.

Kao primer, razmotrimo 64-bitni FNV-1 heš segment koda:

  • Sve promenljive osim "octet_of_data" su 64-bitni neoznačeni celi brojevi.
  • Promenljiva "octet_of_data", je osmobitni neoznačeni ceo broj.
  • FNV_offset_basis je 64-bitna promenljiva i njena vrednost iznosi: 14695981039346656037 (zapisano u heksadekadnom brojčanom sistemu, 0xcbf29ce484222325).
  • FNV_prime je 64-bitna promenljiva i njena vrednost iznosi: 1099511628211 (zapisano u heksadekadnom brojčanom sistem, 0x100000001b3).
  • Množenje vraća 64-bitova najmanje težine proizvoda.
  • XOR predstavlja 8-bitnu operaciju koja menja samo 8-bitova najmanje težine heš vrednosti.
  • Vrednost heša koje se vraćaju su 64-bitni neoznačeni celi brojevi..

Vrednosti FNV_prime i FNV_offset basis mogu se naći u sledećoj tabeli.[7]

FNV-1a heš уреди

FNV-1a heš se razlikuje od FNV-1 samo po redosledu izvršavanja koraka množenja i XOR[8] 

   hash = FNV_offset_basis
   for each octet_of_data to be hashed
   	hash = hash XOR octet_of_data
   	hash = hash × FNV_prime
   return hash

U pseudo kodu iznad imamo iste pretpostavke kao i u FNV-1 pseudokodu. Mala promena u redosledu dovodi do mnogo boljih performansi.[9]

Prikaz slabosti уреди

FNV heš algoritam ima nekoliko slabosti koje su otkrili sami autori i smatra se nepogodnim za kriptografske heš funkcije.[10]

  • Brzina izračunavanja - Kada je heš algoritam (funkcija) dizajniran primarna uloga mu je bila popunjavanje heš tabela, FNV-1 kao i 1a bile su dizajnirane tako da su mogle brzo da se izračunavaju. Međutim, ta ista brzina omogućava više mogućnosti računaru da pronađe različite heš vrednosti i zapadne u problem kolizije podataka.
  • Lepljivo stanje - Obzirom da se algoritam bazira na množenju i bitovskoj operaciji XOR, algoritam je veoma osetljiv na broj nula. Konkretno, ukoliko heširana vrednost postane nula u bilo kom trenutku izračunavanja, i sledeći heširan bajt će imati sve nule, tačnije heš se neće promeniti. Ovo će koliziju podataka učiniti čestom a samim tim i pogoršati performanse ove funkcije. Ukoliko bi nakon množenja ili bitovske operacije XOR dodali operaciju sabiranja sa nekom trećom konstantom u svakom koraku, mogli bi da izazvati lavinu nedeterminističkih ponašanja i veoma loše izračunavanje heš vrednosti.
  • Difuzija - Idealno zaštićena heš funkcija je ona koja za svaki bajt sa ulaza ima jednako kompleksan efekat na svaki bit heš funkcije. U FNV heš funkciji na jednom mestu (krajnji desni bit) je uvek isti rezultat XOR operacije sa svakim krajnje desnim bitom sa ulaza. Postoje načini da se ovo ublaži

Vidi još уреди

Reference уреди

  1. ^ Which hashing algorithm is best for uniqueness and speed? - Programmers Stack Exchange
  2. ^ FNV hash history
  3. ^ Changing the FNV hash size - xor-folding
  4. ^ Changing the FNV hash size - non-powers of 2
  5. ^ FNV put into the public domain
  6. ^ The core of the FNV hash
  7. ^ Parameters of the FNV-1 hash
  8. ^ FNV-1a alternate algorithm
  9. ^ „Avalanche”. Архивирано из оригинала 17. 12. 2009. г. Приступљено 20. 04. 2014. 
  10. ^ The FNV Non-Cryptographic Hash Algorithm - Why is FNV Non-Cryptographic?

Spoljašnje veze уреди

Преузето из „https://sr.wikipedia.org/w/index.php?title=Fauler–Nol–Vo_heš_funkcija&oldid=26742191”