FNV

FNV ( Fowler–Noll–Vo ) on  yksinkertainen hash-funktio yleiseen käyttöön, jonka ovat kehittäneet Glen Fowler, London Kurt Nol ja Fogn Vo. Ei salaustoiminto. Vaihtoehtoja on 32-, 64-, 128-, 256-, 512- ja 1024-bittiset tiivisteet .

Matemaattinen merkintä

FNV-toiminto:

, , , - Alkuluku, on binäärisanojen syöttösekvenssi.

Muokattu FNV-toiminto:

, .

Esimerkkikoodi

Toiminto on helppo toteuttaa. Sen perusta on kertominen alkuluvulla ja modulo 2 yhteenlasku syötetyn tekstin kanssa.

const allekirjoittamaton FNV_32_PRIME = 0x01000193 ; allekirjoittamaton int FNV1Hash ( char * buf ) { unsigned int hval = 0x811c9dc5 ; // FNV0 hval = 0 kun ( * buf ) { hval *= FNV_32_PRIME ; hval ^= ( unsigned int ) * buf ++ ; } paluu hval ; }

Muutokset

Algoritmiin on tehty muunnelma, joka ratkaisee osan sen ongelmista. Erityisesti viimeisen tavun ongelma. Koko muutoksen tarkoitus on kääntää toimintojen järjestys. Ensin yhteenlasku, sitten hash-muunnos (alkuluvulla kertominen).

C -koodiesimerkki :

allekirjoittamaton int FNV1aHash ( char * buf ) { unsigned int hval = 0x811c9dc5 ; kun ( * buf ) { hval ^= ( unsigned int ) * buf ++ ; hval *= FNV_32_PRIME ; } paluu hval ; }

Delphi koodi esimerkki :

toiminto FNV1aHash ( const buf ; len : Integer ) : LongWord ; var pb : PByte ; i : Kokonaisluku ; begin pb := PByte ( @ buf ) ; Tulos := $811C9DC5 ; for i := len downto 1 do Aloita Tulos := ( Tulos xor pb ^ ) * $01000193 ; Inc ( pb ) ; loppu ; loppu ;

Yllä olevan muokkauksen lisäksi algoritmista on kehitetty joitakin suorituskykyä parantavia versioita. Esimerkkejä tällaisista funktioista ovat FNV1A_Jesteress ja FNV1A_Yorikke. Algoritmin kiihdytyksen lisäksi kirjoittaja kiinnitti huomiota jakauman laatuun [1] .

Törmäykset

Koska esimerkissä annettu hash-arvo on 32-bittinen, törmäyksen todennäköisyys on paljon suurempi kuin hajautusfunktioilla, jotka palauttavat esimerkiksi 128-bittisen hajautusarvon.

Linkit

Muistiinpanot

  1. ↑ FNV-muutokset ja ominaisuuksien testaus . Haettu 10. marraskuuta 2012. Arkistoitu alkuperäisestä 5. maaliskuuta 2012.
 Hash-funktiot
yleinen tarkoitus
Kryptografinen
Avainten luontitoiminnot
Tarkista numero ( vertailu )
Hashes