加密散列函式

散列函式（或散列算法，英語：Hash Function）是一種從任何一種數據中創建小的數字“指紋”的方法。該函式將數據打亂混合，重新創建一個叫做散列值的指紋。散列值通常用來代表一個短的隨機字母和數字組成的字元串。

基本介紹

• 中文名：加密散列函式
• 含義：創建小的數字“指紋”
• 利用：隨機字母和數字字元串
• 特性：散列值的原始輸入也是不相同

定義

好的散列函式在輸入域中很少出現散列衝突。在散列表和數據處理中，不抑制衝突來區別數據，會使得資料庫記錄更難找到。

散列函式的性質

所有散列函式都有如下一個基本特性：如果兩個散列值是不相同的（根據同一函式），那么這兩個散列值的原始輸入也是不相同的。這個特性是散列函式具有確定性的結果。但另一方面，散列函式的輸入和輸出不是一一對應的，如果兩個散列值相同，兩個輸入值很可能是相同的，但並不能絕對肯定二者一定相等。輸入一些數據計算出散列值，然後部分改變輸入值，一個具有強混淆特性的散列函式會產生一個完全不同的散列值。

典型的散列函式都有無限定義域，比如任意長度的位元組字元串，和有限的值域,比如固定長度的比特串。在某些情況下，散列函式可以設計成具有相同大小的定義域和值域間的一一對應。一一對應的散列函式也稱為排列。可逆性可以通過使用一系列的對於輸入值的可逆「混合」運算而得到。

散列函式的套用

由於散列函式的套用的多樣性，它們經常是專為某一套用而設計的。例如，加密散列函式假設存在一個要找到具有相同散列值的原始輸入的敵人。一個設計優秀的加密散列函式是一個「單向」操作：對於給定的散列值，沒有實用的方法可以計算出一個原始輸入，也就是說很難偽造。為加密散列為目的設計的函式，如MD5，被廣泛的用作檢驗散列函式。這樣軟體下載的時候，就會對照驗證代碼之後才下載正確的檔案部分。此代碼有可能因為環境因素的變化，如機器配置或者IP位址的改變而有變動。以保證源檔案的安全性。

錯誤監測和修複函數主要用於辨別數據被隨機的過程所擾亂的事例。當散列函式被用於校驗和的時候，可以用相對較短的散列值來驗證任意長度的數據是否被更改過。

加密

一個典型的加密單向函式是“非對稱”的，並且由一個高效的散列函式構成；一個典型的加密暗門函式是“對稱”的，並且由一個高效的隨機函式構成。

散列表

散列表是散列函式的一個主要套用，使用散列表能夠快速的按照關鍵字查找數據記錄。（注意：關鍵字不是像在加密中所使用的那樣是秘密的，但它們都是用來“解鎖”或者訪問數據的。）例如，在英語字典中的關鍵字是英文單詞，和它們相關的記錄包含這些單詞的定義。在這種情況下，散列函式必須把按照字母順序排列的字元串映射到為散列表的內部數組所建立的索引上。

散列表散列函式的幾乎不可能/不切實際的理想是把每個關鍵字映射到唯一的索引上（參考完美散列），因為這樣能夠保證直接訪問表中的每一個數據。

一個好的散列函式（包括大多數加密散列函式）具有均勻的真正隨機輸出，因而平均只需要一兩次探測（依賴於裝填因子）就能找到目標。同樣重要的是，隨機散列函式幾乎不可能出現非常高的衝突率。但是，少量的可以估計的衝突在實際狀況下是不可避免的（參考生日悖論）。

在很多情況下，heuristic散列函式所產生的衝突比隨機散列函式少的多。Heuristic函式利用了相似關鍵字的相似性。例如，可以設計一個heuristic函式使得像FILE0000.CHK, FILE0001.CHK, FILE0002.CHK, 等等這樣的檔案名稱映射到表的連續指針上，也就是說這樣的序列不會發生衝突。相比之下，對於一組好的關鍵字性能出色的隨機散列函式，對於一組壞的關鍵字經常性能很差，這種壞的關鍵字會自然產生而不僅僅在攻擊中才出現。性能不佳的散列函式表意味著查找操作會退化為費時的線性搜尋。

錯誤校正

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

對於錯誤校正，假設相似擾動的分布接近最小(a distribution of likely perturbations is assumed at least approximately)。 對於一個信息串的微擾可以被分為兩類，大的（不可能的）錯誤和小的（可能的）錯誤。我們對於第二類錯誤重新定義如下，假如給定 H(x) 和 x+s，那么只要s足夠小，我們就能有效的計算出x。那樣的散列函式被稱作錯誤校正編碼。這些錯誤校正編碼有兩個重要的分類：循環冗餘校驗和里德所羅門碼。

語音識別

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

那些並不緊隨IT工業潮流的人往往能反其道而行之，對於那些微小差異足夠魯棒的散列函式確實存在。現存的絕大多數散列算法都是不夠魯棒的，但是有少數散列算法能夠達到辨別從嘈雜房間裡的揚聲器里播放出來的音樂的魯棒性。有一個實際的例子是Shazam服務。用戶可以用電話機撥打一個特定的號碼，並將電話機的話筒靠近用於播放音樂的揚聲器。該項服務會分析正在播放的音樂，並將它於存儲在資料庫中的已知的散列值進行比較。用戶就能夠收到被識別的音樂的曲名（需要收取一定的費用）。

Rabin-Karp 字元串搜尋算法

Rabin-Karp 字元串搜尋算法 是一個相對快速的字元串搜尋算法，它所需要的平均搜尋時間是O(n).這個算法是建立在使用散列來比較字元串的基礎上的。