FNV算法實戰

HASH算法介紹

Hash，一般翻譯做“散列”，也有直接音譯為“哈希”的，就是把任意長度的輸入（又叫做預映射， pre-image），通過雜湊演算法，變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出，而不可能從散列值來唯一地确定輸入值。
數學表述為：h = H(M) ，其中H( )--單向散列函數，M--任意長度明文，h--固定長度散列值。

HASH算法的實際應用-加密

常見的哈希加密算法：MD5，SHA-1，SHA-2，SHA-256，SHA-X（系列）
1) 檔案校驗:MD5 Hash算法的“數字指紋”特性，使它成為目前應用最廣泛的一種檔案完整性校驗和(Checksum)算法，不少Unix系統有提供計算md5 checksum的指令；
2) 數字簽名：在這種簽名協定中，雙方必須事先協商好雙方都支援的Hash函數和簽名算法。簽名方先對該資料檔案進行計算其散列值，然後再對很短的散列值結果--如Md5是16個位元組，SHA1是20位元組，用非對稱算法進行數字簽名操作。對方在驗證簽名時，也是先對該資料檔案進行計算其散列值，然後再用非對稱算法驗證數字簽名；（實際是HASH+非對稱加密）
3) 鑒權協定:需要鑒權的一方，向将被鑒權的一方發送随機串（“挑戰”），被鑒權方将該随機串和自己的鑒權密碼字一起進行 Hash 運算後，返還鑒權方，鑒權方将收到的Hash值與在己端用該随機串和對方的鑒權密碼字進行 Hash 運算的結果相比較（“認證”），如相同，則可在統計上認為對方擁有該密碼字，即通過鑒權。（摘要）
HASH加密算法與其他加密算法的主要不同點是：哈希(Hash)算法是一種單向密碼體制,即隻有加密過程,沒有解密過程

HASH算法的實際應用-查找

常見的哈希查找算法：BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash等
1) 基本思想是：以資料對象的關鍵詞 key 為自變量，通過一個确定的函數關系 $h$ ,計算出對應的函數值 $h(key)$ ，把這個值解釋為資料對象的存儲位址，并按此存放，即“$存儲位置=h(key)$”。
Gdb下函數符号實際對應的是一個記憶體位址，映射大小為32bit或64bit（即32位系統或64位系統）

FNV算法介紹

FNV雜湊演算法全名為Fowler-Noll-Vo算法，是以三位發明人Glenn Fowler，Landon Curt Noll，Phong Vo的名字來命名的，最早在1991年提出
特點和用途：FNV能快速hash大量資料并保持較小的沖突率，它的高度分散使它适用于hash一些非常相近的字元串，比如URL，hostname，檔案名，text，IP位址等。
适用範圍：比較适用于字元串比較短的哈希場景

　　FNV雜湊演算法有如下兩種，FNV-1a相比FNV-1，散列分布更好。二者不同點為：for循環兩行代碼的順序相反

　　哈希函數一般适用移位和乘除法來實作。哈希函數一般都比較精簡，算法複雜度比較低。哈希函數的移位和乘除法可能會導緻資料丢失，這也是哈希不可逆的原因

FNV算法說明-1

hash值：一個n位的unsigned int型hash值，初始值為offset_basis.
offset_basis：初始的哈希值，該值在最早的版本中是0，為了增強哈希的可靠性，後續修改為非0的值，通過如下算法擷取

參見《生成offset_basis.py》

FNV算法說明-2

　　octet_of_data：8位資料（即一個位元組）：即需要被哈希的字元串

　　FNV_prime：FNV用于散列的質數（質數在雜湊演算法中發揮着重要作用，在一般使用的哈希除留餘數法中： H(key) = key MOD p，p也要求是一個質數（質數也稱為素數））

32 bit FNV_prime = 224 + 28 + 0x93 = 16777619
64 bit FNV_prime = 240 + 28 + 0xb3 = 1099511628211
128 bit FNV_prime = 288 + 28 + 0x3b = 309485009821345068724781371
256 bit FNV_prime = 2168 + 28 + 0x63 = 374144419156711147060143317175368453031918731002211
512 bit FNV_prime = 2344 + 28 + 0x57 = 35835915874844867368919076489095108449946327955754392558399825615420669938882575126094039892345713852759

FNV算法使用

支援将字元串哈希為32/64/128/256/512/1024bit的數字
支援将字元串哈希為任意bit的數字，比如11/33bit
支援将字元串哈希為特定範圍的數字，比如[0,99999]

将字元串哈希為32bit的數字

hash = offset_basis 

for each octet_of_data to be hashed

    hash = hash xor octet_of_data

    hash = hash * FNV_prime

return hash

　　參見《生成32位哈希.py》

将字元串哈希為特定範圍的數字

将字元串哈希為[0,999]的數字
#define TRUE_HASH_SIZE ((u_int32_t)50000) /* range top plus 1 */
#define FNV_32_PRIME ((u_int32_t)16777619)
#define FNV1_32_INIT ((u_int32_t)2166136261)
#define MAX_32BIT ((u_int32_t)0xffffffff) /* largest 32 bit unsigned value */
#define RETRY_LEVEL ((MAX_32BIT / TRUE_HASH_SIZE) * TRUE_HASH_SIZE)
u_int32_t hash;
void *data;
size_t data_len;

hash = fnv_32_buf(data, data_len, FNV1_32_INIT);
while (hash >= RETRY_LEVEL) {
    hash = (hash * FNV_32_PRIME) + FNV1_32_INIT;
}
hash %= TRUE_HASH_SIZE;

參見《生成任意範圍哈希.py》，代碼附件連結

參考：

http://www.isthe.com/chongo/tech/comp/fnv/index.html#lazy-mod