單向函數

在計算機科學中，單向函數是一種數學函數，根據復雜性理論“容易”計算，但“難以”逆轉。 在廣義上，函數也以這種方式指定，其中已知無法在合理的時間內執行反演。

一個很好的例子是大城市的經典紙質電話簿：如果您知道名字，您可以快速找到相應的電話號碼。 但是，如果只知道電話號碼，要查找關聯的姓名是非常耗時的。

單向數構成了非對稱密碼系統的基礎。

數學單向數 f 必須具有以下性質：

• 計算給定 x 的函數值 y = f ( x )是“簡單的”，即。 也就是說，有一種算法可以在多項式時間內計算它。
• 函數的反函數i的計算。給定 y 的原像 x 使得 f ( x ) = y? 是困難的，也就是說，沒有概率算法 F在多項式時間內運行并以不可忽略的概率輸出輸入圖像的原像。更準確地說，以下適用于每個概率算法 F具有合適的輸入和輸出格式：對于每個 c ∈ N

不知道是否有滿足單向條件的函數。 事實上，證明它們的存在意味著同時證明P≠NP。 反之，單向函數的存在不符合P≠NP：概率算法也可以用來反轉函數。 為了使逆過程足夠低效，NP 不能是復雜類 BPP 的子集。

單向數對密碼學中的應用程序特別感興趣。 然而，對于這樣的用途，就復雜性理論而言，另一個要求是必要的：所提到的復雜性類別考慮了最壞情況（worst case），即算法的最長運行時間。 對于密碼應用程序，算法在一般情況下也必須是低效的。

密碼中有一個單向函數的直接應用。 這些通常不會直接保存，而是作為密碼哈希函數的輸出，在其中輸入密碼（通常用鹽作為補充）。 登錄時的檢查不是通過比較明文密碼而是哈希值來執行的。 因此，管理員或具有系統訪問權限的未授權人員永遠無法讀取用戶的密碼。 充其量，他可以使用 crack 之類的程序嘗試可能的密碼。 加密哈希函數的行為類似于單向函數，更準確地說：沒有已知的方法可以有效地計算給定輸出的輸入（原像攻擊）。

在實踐中，已知的函數到目前為止已經充分滿足了單向函數的要求。 不過，要將它們反轉是否真的“難”，目前還無法證明。 這種函數的一個例子是兩個大質數的乘法，因為質因數分解被認為是一個“困難”的問題。 另一個例子是模冪及其倒數，即離散對數。

單向函數的一個變體是陷門單向函數，也稱為陷門函數。 如果您有某些附加信息，這些只能有效地逆轉。 Trapdoor 函數用于非對稱加密方法，例如 RSA。 活板門功能的類比是金庫的功能：任何人都可以鎖定金庫中的物品。 另一方面，把它拿出來幾乎是不可能的——除非你有鑰匙/鑰匙組合。

以下函數在擴展意義上稱為單向函數，目前尚無有效的反演：

• 像 SHA-2 這樣的加密散列函數
• 的兩個素數或兩個整數的乘法很容易，而逆向素因數分解則很困難
• 如果選擇適當的群，計算有限群元素的 n 次方很容易，而通過計算離散對數求指數則很復雜