單向函數

單向函數定義：

一函數f若滿足下列二條件，則f稱為單向函數：

① 對於所有屬於 f 定義域的任一 x ，可以很容易計算 ；

②對於幾乎所有（Almost All）屬於 f 值域的任一 y ，則在計算上不可能（Computationally Infeasible）求出 x 使得；

單向函數的例子：

1、令 f 為一 n 階多項式，且。給出a[0]，a[1]， …，a[n-1]，p 及x，欲求 y ，只需最多n個乘法及n-1個加法。因為。此即為有名的Honer's Rule。但若已給[0]，a[1]， …，a[n-1]及y，欲求出 f( x )的 x，則至少需要次乘法，當n及p很大時，可知由y求x，比由x求y難上許多。

2、求離散對數問題（Discrete logarithm Problem, DLP )

令素數p滿足p-1含有另一大素因子q（即q整除p-1）及一整數g，1 此外，還有很多單向函數的數學問題，例如因子分解問題，背包問題等，在此無法一列舉。

單向函數本身在近代密碼學領域用處並不大。但若單向函數具有交換性，則其用處就很大。所謂交換性定義如下：

交換性（Commutatve Property )

令Z為一集合，F為將Z映射至Z本身的函數集合。令z∈Z，F[x](z)表示此函數集合的第x個函數，若，則稱此函數集合具有交換性。

具有關鍵性性的單向函數是進行數據加密/編碼的一種演演算法

單向函數一般用於產生消息摘要，密鑰加密等，常見的有：

MD5（Message Digest Algorithm 5）：是RSA數據安全公司開發的一種單向散列演演算法，MD5被廣泛使用，可以用來把不同長度的數據塊進行暗碼運算成一個128位的數值；

SHA（Secure Hash Algorithm）這是一種較新的散列演演算法，可以對任意長度的數據運算生成一個160位的數值；

MAC（Message Authentication Code）：消息認證代碼，是一種使用密鑰的單向函數，可以用它們在系統上或用戶之間認證文件或消息。HMAC（用於消息認證的密鑰散列法）就是這種函數的一個例子。

CRC（Cyclic Redundancy Check）：循環冗餘校驗碼，CRC校驗由於實現簡單，檢錯能力強，被廣泛使用在各種數據校驗應用中。佔用系統資源少，用軟硬體均能實現，是進行數據傳輸差錯檢測地一種很好的手段（CRC 並不是嚴格意義上的散列演演算法，但它的作用與散列演演算法大致相同，所以歸於此類）。