字符串hash函數

2021-02-19 黑客技術與網絡安全
來自：標點符的《字符串hash函數》

連結：https://www.biaodianfu.com/hash.html（點擊尾部閱讀原文前往）


什麼是Hash？


Hash，一般翻譯做「散列」，也有直接音譯為」哈希」的，就是把任意長度的輸入（又叫做預映射， pre-image），通過散列算法，變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。

數學表述為：h = H(M) ，其中H( )–單向散列函數，M–任意長度明文，h–固定長度散列值。

在信息安全領域中應用的Hash算法，還需要滿足其他關鍵特性：

單向性(one-way)，從預映射，能夠簡單迅速的得到散列值，而在計算上不可能構造一個預映射，使其散列結果等於某個特定的散列值，即構造相應的M=H-1(h)不可行。這樣，散列值就能在統計上唯一的表徵輸入值，因此，密碼學上的 Hash 又被稱為」消息摘要(message digest)」，就是要求能方便的將」消息」進行」摘要」，但在」摘要」中無法得到比」摘要」本身更多的關於」消息」的信息。

抗衝突性(collision-resistant)，即在統計上無法產生2個散列值相同的預映射。給定M，計算上無法找到M』，滿足H(M)=H(M』) ，此謂弱抗衝突性；計算上也難以尋找一對任意的M和M』，使滿足H(M)=H(M』) ，此謂強抗衝突性。要求」強抗衝突性」主要是為了防範所謂」生日攻擊(birthday attack)」，在一個10人的團體中，你能找到和你生日相同的人的概率是4%，而在同一團體中，有2人生日相同的概率是11.7%。類似的，當預映射的空間很大的情況下，算法必須有足夠的強度來保證不能輕易找到」相同生日」的人。

映射分布均勻性和差分分布均勻性，散列結果中，為 0 的 bit 和為 1 的 bit ，其總數應該大致相等；輸入中一個 bit 的變化，散列結果中將有一半以上的 bit 改變，這又叫做」雪崩效應(avalanche effect)」；要實現使散列結果中出現 1bit 的變化，則輸入中至少有一半以上的 bit 必須發生變化。其實質是必須使輸入中每一個 bit 的信息，儘量均勻的反映到輸出的每一個 bit 上去；輸出中的每一個 bit，都是輸入中儘可能多 bit 的信息一起作用的結果。

Damgard 和 Merkle 定義了所謂「壓縮函數(compression function)」，就是將一個固定長度輸入，變換成較短的固定長度的輸出，這對密碼學實踐上 Hash 函數的設計產生了很大的影響。Hash函數就是被設計為基於通過特定壓縮函數的不斷重複「壓縮」輸入的分組和前一次壓縮處理的結果的過程，直到整個消息都被壓縮完畢，最後的輸出作為整個消息的散列值。儘管還缺乏嚴格的證明，但絕大多數業界的研究者都同意，如果壓縮函數是安全的，那麼以上述形式散列任意長度的消息也將是安全的。

Hash函數的應用錯誤校正

使用一個散列函數可以很直觀的檢測出數據在傳輸時發生的錯誤。在數據的發送方，對將要發送的數據應用散列函數，並將計算的結果同原始數據一同發送。在數據的接收方，同樣的散列函數被再一次應用到接收到的數據上，如果兩次散列函數計算出來的結果不一致，那麼就說明數據在傳輸的過程中某些地方有錯誤了。這就叫做冗餘校驗。

語音識別

對於像從一個已知列表中匹配一個MP3文件這樣的應用，一種可能的方案是使用傳統的散列函數——例如MD5，但是這種方案會對時間平移、CD讀取錯誤、不同的音頻壓縮算法或者音量調整的實現機制等情況非常敏感。使用一些類似於MD5的方法有利於迅速找到那些嚴格相同（從音頻文件的二進位數據來看）的音頻文件，但是要找到全部相同（從音頻文件的內容來看）的音頻文件就需要使用其他更高級的算法了。

信息安全

Hash算法在信息安全方面的應用主要體現在以下的3個方面：

（1)文件校驗

我們比較熟悉的校驗算法有奇偶校驗和CRC校驗，這2種校驗並沒有抗數據篡改的能力，它們一定程度上能檢測並糾正數據傳輸中的信道誤碼，但卻不能防止對數據的惡意破壞。MD5 Hash算法的」數字指紋」特性，使它成為目前應用最廣泛的一種文件完整性校驗和(Checksum)算法。

（2)數字籤名

Hash 算法也是現代密碼體系中的一個重要組成部分。由於非對稱算法的運算速度較慢，所以在數字籤名協議中，單向散列函數扮演了一個重要的角色。對 Hash 值，又稱」數字摘要」進行數字籤名，在統計上可以認為與對文件本身進行數字籤名是等效的。而且這樣的協議還有其他的優點。

（3) 鑑權協議

鑑權協議又被稱作挑戰–認證模式：在傳輸信道是可被偵聽，但不可被篡改的情況下，這是一種簡單而安全的方法。

常見Hash函數介紹

MD5 和 SHA1 可以說是目前應用最廣泛的Hash算法，而它們都是以 MD4 為基礎設計的。

MD4(RFC 1320)是 MIT 的Ronald L. Rivest在 1990 年設計的，MD 是 Message Digest（消息摘要） 的縮寫。它適用在32位字長的處理器上用高速軟體實現——它是基於 32位操作數的位操作來實現的。

MD5(RFC 1321)是 Rivest 於1991年對MD4的改進版本。它對輸入仍以512位分組，其輸出是4個32位字的級聯，與 MD4 相同。MD5比MD4來得複雜，並且速度較之要慢一點，但更安全，在抗分析和抗差分方面表現更好。

SHA1是由NIST NSA設計為同DSA一起使用的，它對長度小於264的輸入，產生長度為160bit的散列值，因此抗窮舉(brute-force)性更好。SHA-1 設計時基於和MD4相同原理,並且模仿了該算法。

現代化的Hash算法Jenkins Hash

1997年Bob Jenkins在《 Dr. Dobbs Journal》雜誌上發表了一片關於散列函數的文章《A hash function for hash Table lookup》，這篇文章自從發表以後現在網上有更多的擴展內容。這篇文章中，Bob廣泛收錄了很多已有的散列函數，這其中也包括了他自己所謂的「lookup2」。隨後在2006年，Bob發布了lookup3，由於它即快速（Bob自稱，0.5 bytes/cycle）又無嚴重缺陷，被廣泛使用。lookup3即為Jenkins Hash。更多有關Bob’s散列函數的內容請參閱維基百科：Jenkins hash function。memcached的hash算法，支持兩種算法：jenkins, murmur3，默認是jenkins。

MurmurHash

Austin Appleby在2008年發布了一個新的散列函數——MurmurHash。其最新版本大約是lookup3速度的2倍（大約為1 byte/cycle），它有32位和64位兩個版本。32位版本只使用32位數學函數並給出一個32位的哈希值，而64位版本使用了64位的數學函數，並給出64位哈希值。根據Austin的分析，MurmurHash具有優異的性能，雖然Bob Jenkins 在《Dr. Dobbs article》雜誌上聲稱「我預測[MurmurHash ]比起lookup3要弱，但是我不知道具體值，因為我還沒測試過它」。MurmurHash能夠迅速走紅得益於其出色的速度和統計特性。當前的版本是MurmurHash3，Redis、Memcached、Cassandra、HBase、Lucene都在使用它。

CityHash

CityHash是2011年Google發布的字符串散列算法，和murmurhash一樣，屬於非加密型hash算法。CityHash算法的開發是受到了 MurmurHash的啟發。其主要優點是大部分步驟包含了至少兩步獨立的數學運算。現代 CPU 通常能從這種代碼獲得最佳性能。CityHash 也有其缺點：代碼較同類流行算法複雜。Google 希望為速度而不是為了簡單而優化，因此沒有照顧較短輸入的特例。Google發布的有兩種算法：cityhash64 與 cityhash128。它們分別根據字串計算 64 和 128 位的散列值。這些算法不適用於加密，但適合用在散列表等處。CityHash的速度取決於CRC32 指令，目前為SSE 4.2（Intel Nehalem及以後版本）。

SpookyHash

2011年Bob Jenkins發布了他自己的一個新散列函數SpookyHash（這樣命名是因為它是在萬聖節發布的）。它們都擁有2倍於MurmurHash的速度，但他們都只使用了64位數學函數而沒有32位版本，SpookyHash給出128位輸出。

FramHash

2014年Google發布了FarmHash，一個新的用於字符串的哈希函數系列。FarmHash從CityHash繼承了許多技巧和技術，是它的後繼。FarmHash有多個目標，聲稱從多個方面改進了CityHash。與CityHash相比，FarmHash的另一項改進是在多個特定於平臺的實現之上提供了一個接口。這樣，當開發人員只是想要一個用於哈希表的、快速健壯的哈希函數，而不需要在每個平臺上都一樣時，FarmHash也能滿足要求。目前，FarmHash只包含在32、64和128位平臺上用於字節數組的哈希函數。未來開發計劃包含了對整數、元組和其它數據的支持。

SuperFastHash
XXHash
該選用哪個Hash函數？

當然，發布時間更晚的，功能方面可能更優，但是也有可能存在某種限制。如果是32位的機器，建議使用MurmurHash，他要比lookup3的32位更快些。

●本文編號301，以後想閱讀這篇文章直接輸入301即可。

●輸入m可以獲取到文章目錄

Linux學習

推薦《15個技術類公眾微信》

涵蓋：程序人生、算法與數據結構、黑客技術與網絡安全、大數據技術、前端開發、Java、Python、Web開發、安卓開發、iOS開發、C/C++、.NET、Linux、資料庫、運維

相關焦點

  • Python文檔精要研讀系列:hash函數
    Python中的hash函數用於求取一個字符串或者數值的哈希值，由於Python中任何數據類型都可以轉換為字符串，所以我們利用這個函數來進行簡單的哈希值計算，比如：hash('test')如此便可以求得字符串'test'的哈希值
  • php字符串函數
    bin2hex — 將二進位數據轉換成十六進位表示chop — rtrim() 的別名函數chr — 返回一個字符的ASCII碼chunk_split — 按一定的字符長度將字符串分割成小塊convert_cyr_string — 將斯拉夫語字符轉換為別的字符convert_uudecode — 解密一個字符串
  • 對比python字符串函數,學習pandas的str矢量化字符串函數
    我們不僅要學會怎麼處理單個字符串，這個就需要學習「python字符串函數」，我們還要學會怎麼處理二維表格中每一列每一格的字符串，這個就需要學習「pandas的str矢量化字符串函數」。今天我們採用對比的方式，帶大家總結常用的字符串函數，希望這篇文章能夠對大家起到很好的作用。
  • MySQL函數基礎——字符串函數詳解
    昨天，咱們對MySQL的數學函數進行了講解，今天，咱們再來解析MySQL字符串函數。字符串函數主要用來處理資料庫中的字符串數據，MySQL中字符串函數有：計算字符串長度函數、字符串合併函數、字符串替換函數、字符串比較函數、查找指定字符串位置函數等。
  • 對比python字符串函數,輕鬆學習pandas的 str 矢量化字符串函數
    我們不僅要學會怎麼處理單個字符串，這個就需要學習「python字符串函數」，我們還要學會怎麼處理二維表格中每一列每一格的字符串，這個就需要學習「pandas的str矢量化字符串函數」。今天我們採用對比的方式，帶大家總結常用的字符串函數，希望這篇文章能夠對大家起到很好的作用。
  • 在字符串中搜索標記--labview字符串函數之一
    一直未能找到合適的字符串函數來解析出來有效數據，而昨天恰恰看到了這樣一個字符串函數——在字符串中搜索標記。運算符是字符串數組，如輸入字符串包含字符串數組，即使它們沒有被分隔符分隔，函數仍將其視為標記。如輸入字符串的一部分匹配多個運算符，函數將把最長的匹配作為標記。例如，如>、=和>=被定義為運算符，輸入字符串4>=0將生成>=作為下一個標記字符串，偏移量為1。運算符中的字符串可能包含下列特殊格式代碼，用於將整個數字作為單個標記進行掃描。
  • (基礎篇)PHP字符串函數
    PHP字符串函數包括查找字符位置函數；提取子字符函數；替換字符串；字符長度；比較字符函數；分割成數組字符；去除空格等等
  • useful R 字符串函數
    首先經常碰到字符分裂類的問題，一般分為兩種情況：按照固定字符分裂和按照固定長度分裂，前者表示指定一個分裂字符串，當字符串中出現該固定模式時就進行分裂；後者表示每隔多少個字符進行分裂；字符串分裂：按字符分裂mystring <- "前者表示指定一個分裂字符串，當字符串中出現該固定模式時就進行分裂；後者表示每隔多少個字符進行分裂"strsplit(mystring, split
  • VBA字符串函數
    Str函數將數值轉換成字符串，即返回代表一個數值的字符串。其語法為：str(Number) 當一個數字轉成字符串時，總會在前面保留一個空位來表示正負，即字符串的第一位一定是空格或正負號。如果參數number為正，返回的字符串前面包含一空格。Str函數將句點(.)作為有效的小數點。
  • php字符串常用處理,運算符和幾個常用的字符串函數
    本期分享的是php字符串的一些常用處理，運算符和幾個常用的字符串函數。php字符串運算符在php中，字符串就只有一個運算符，即並置運算符（.）。並置運算符（.）在php中是非常常用的，是使用來將兩個字符串連接起來，形成一個字符串。
  • php字符串函數匯總
    php字符串函數有哪些？php字符串函數：addcslashes — 以 C 語言風格使用反斜線轉義字符串中的字符addslashes — 使用反斜線引用字符串bin2hex — 函數把包含數據的二進位字符串轉換為十六進位值chop — rtrim 的別名
  • PHP部分字符串函數匯總
    我們大家知道無論哪種語言，字符串操作都是一個重要的基礎，往往是簡單而重要。查找字符位置函數strpos($str,search,[int]): 查找search在$str中的第一次位置從int開始stripos($str,search,[int]): 函數返回字符串在另一個字符串中第一次出現的位置strrpos($str,search,[int]): 查找search在$str中的最後一次出現的位置從int 2.
  • 字符串匹配的Rabin-Karp算法
    用在編譯器裡的有限自動機，也可以用來做字符串匹配。經典的字符串查找算法，時間複雜度是O(m(n - m + 1) )，粗略估計O(n^2)。m為要查找的字符串的長度，n為被查找的大字符串序列的長度。從字符數組的索引0一直遍歷到n-m，最後m個字符，每個索引比較一次，每次需要比較m個字符。
  • Stata函數之字符串函數(一)
    今天我們介紹Stata中字符串函數（string functions）的知識。在處理數據的過程中，好處理的數據（不論是整數還是浮點數）通常都好處理，你可以很方便的對其加減乘除、統計、應用計量模型等；但不好處理的數據通常讓人抓狂。字符串就屬於不好處理的數據。事實上，我們遇到的大多數原始數據（raw data）都是字符串形式的。
  • 漫畫:什麼是字符串匹配算法?
    為了統一概念，在後文中，我們把字符串A稱為主串，把字符串B稱為模式串。第二輪，我們把模式串後移一位，從主串的第二位開始，把主串和模式串的字符逐個比較：主串的第二位字符是b，模式串的第二位字符也是b，兩者匹配，繼續比較：主串的第三位字符是b，模式串的第三位字符也是c，兩者並不匹配。
  • 常用VB.NET字符串函數詳介
    常用VB.NET字符串函數詳介 這裡簡單的介紹了VB.NET字符串函數Val() 、Str$() 、Left$() 、Right$() 、Ltrim$() 、Rtrim$() 、Trim$() 、Asc() 、Chr$() 。
  • VBA字符串函數，你想學的都在這裡
    /字符串、提取字符串長度 1.1 Left函數left(字符串,長度) ：從[字符串]的左邊開始返回[長度]個字符 例如：Left("歡迎你關注我",3) 則返回 "歡迎你"1.2 Right函數right(字符串,長度)  : 從[字符串]的右邊開始返回[長度]個字符 例如 Right("歡迎你關注
  • 「值得收藏」的PHP常用字符串函數
    1.str_word_count 統計單詞個數2. count_chars 得到字符串裡面字符的有關情況3. str_len 得到字符串長度，就是有多少個字符4. substr_count統計有多少個子字符串， 比如 統計is， this is php裡面，就會出現2個is5. strpos 定義字符串出現的首次位置 （
  • C語言字符串處理函數之字符串轉換、查詢函數
    介紹完字符串整體操作函數，就該到字符串查詢函數和字符串轉換函數了，至於一些字符串轉換函數，如atoi()，atof(),strtod(),strtol(),tolower(),toupper()等，以後有時間再整理整理。
  • 辦公軟體分享:函數篇 字符串函數
    ①concatenate，該函數主要是把2個及2個以上字符串合併為一個。所以concatenate函數跟"&"的功能是一樣的。②left，right函數分別代表對特定的區域，從左第一個字符或者從右第一個字符開始，返回指定個數的字符，但是對於並不規律的字符組合，left、right和分列都解決不了問題，稍後我們會具體解決。