單向函式 (One-way function)是一種具有下述特點的單射函式：對於每一個輸入，函式值都容易計算（多項式時間），但是給出一個隨機輸入的函式值，算出原始輸入卻比較困難（無法在多項式時間內使用確定性圖靈機計算）。 單向函式是否存在仍然是計算機科學中的一個開放性問題。事實上，如果單向函式存在，將證明複雜性類P/NP問題中，P不等於NP。
基本介紹
- 中文名：單向函式
- 外文名：One-way function
- 表達式：F（x）=y
- 套用學科：數學，高數
- 適用領域範圍：密碼學
簡介,背景,單向函式公式定義,陷門單向函式,密碼套用中的單項函式,陷門單向函式與公鑰密碼體制,
簡介
背景
1976年，Diffie W.和Hellman M.E.在他們的《密碼學的新方向》一文中提出了公鑰密碼的概念。隨後，在1978年，Rivest R.L.，Shamir A.和Adleman L.M.在其文《實現數字簽名和公鑰密碼體制的一種方法》中最先提出了一種可行的實現方法，這就是我們廣泛使用的RSA體制。RSA體制的提出真正使得互不相識的通信雙方在一個不安全的信道上進行安全通信最終成為可能，也是CA服務的源泉。然而，人們很少關心當前幸福生活的背後有一位默默的奉獻者—單向函式。
給定任意兩個集合
和
。 函式
稱為單向的，如果對每一個
屬於 ，很容易計算出函式
的值，而對大多數y屬於 ， 要確定滿足
的 是計算上困難的(假設至少有這樣一個x存在)。注意，不能將單向函式的概念與數學意義上的不可逆函式的概念混同，因為單向函式可能是一個數學意義上可逆或者一對一的函式，而一個不可逆函式卻不一定是單向函式。
還沒有人能夠從理論上證明單向函式是存在的。單向函式存在性的證明將意味著計算機科學中一個最具挑戰性的猜想
，即
完全問題的解決，而關於 完全性的理論卻不足以證明單向函式的存在。有幸的是，現實中卻存在幾個單向函式的“候選”。說他們是“候選”，是因為他們表現出了單向函式的性質，但還沒有辦法從理論上證明它們一定是單向函式。
一個最簡單的、大家熟知的“侯選”單向函式就是整數相乘。眾所周知，不管給定兩個多大的整數，我們很容易計算出它們的乘積，而對於一個300位左右的十進制整數，即使已知它是兩個大小差不多（150位左右的十進制數）的素數之積，用世界上計算能力最強的計算機，也沒有辦法在一個合理的時間內分解出構成這個整數的兩個素數因子來。這裡講的“合理的時間”是指一個可度量的相當長的時間，比如人類或者地球的壽命等。
單向函式公式定義
函式
是一個單向函式若且唯若
可以用一個多項式時間的算法計算，但是對於任意一個以
為輸入的隨機化多項式算法
，任意一個多項式
，和足夠大
,使得
陷門單向函式
顯然，單向函式不能直接用作密碼體制，因為如果用單向函式對明文進行加密，即使是合法的接收者也不能還原出明文了，因為單向函式的逆運算是困難的。與密碼體制關係更為密切的概念是陷門單向函式。一個函式 稱為是陷門單向的，如果該函式及其逆函式的計算都存在有效的算法，而且可以將計算
的方法公開，即使由計算f的完整方法也不能推導出其逆運算的有效算法。其中，使得雙向都能有效計算的秘密信息叫做陷門(trap door)。
只要 和 是固定的，學過計算機的人都很容易設計出一個算法，對任何
，可以有效地計算出
,
的值。與前面的離散對數問題相反，我們確切知道，也存在有效算法，對任何 ，可以容易地求出 模 的 次根。有意思的是，如果只知道 和 ，如何構造出該有效的算法卻不得而知。換言之，
不是單向函式，因為它的求逆不是困難的，儘管我們還不知道如何去做。然而，如果除了知道 和 以外，還知道構成n的素因子，就很容易構造出求模 的 次根的有效算法。因此， 可以作為陷門單向函式，其中 和 可以用做公開信息，而 的因子分解就是秘密的陷門。
模指數的一個特殊情況是當模
具有特殊形式，僅由兩個素數
和
構成，即
。著名的RSA體制就是根據這個陷門單向函式設計出來的。
需要提醒的是，不能顧名思義地認為陷門單向函式是單向函式。事實上，陷門單向函式不是單向函式，它只是對於那些不知道陷門的人表現出了單向函式的特性。
密碼套用中的單項函式
前面說過，單向函式不能直接用作密碼體制，因為它的求逆困難，用它加密的信息誰都不能解密。但是，單向函式在密碼學領域裡卻發揮著非常重要的作用。一個最簡單的套用就是口令保護。我們熟知的口令保護方法是用對稱加密算法進行加密。然而，對稱算法加密一是必須有密鑰，二是該密鑰對驗證口令的系統必須是可知的，因此意味著驗證口令的系統總是可以獲取口令的明文的。這樣在口令的使用者與驗證口令的系統之間存在嚴重的信息不對稱，姑且不說系統提供者非法獲取用戶口令的情況，一旦系統被攻破，可能造成所有用戶口令的泄露。使用單向函式對口令進行保護則可以很好地解決這一問題。系統方只存放口令經單向函式運算過的函式值，驗證是將用戶口令重新計算函式值與系統中存放的值進行比對。動態口令認證機制多是基於單向函式的套用來設計的。
單向函式的另一個套用是大家熟知的用於數字簽名時產生信息摘要的單向散列函式。由於公鑰密碼體制的運算量往往比較大，為了避免對待簽檔案進行全文簽名，一般在簽名運算前使用單向散列算法對簽名檔案進行摘要處理，將待簽檔案壓縮成一個分組之內的定長位串，以提高簽名的效率。MD5和SHA-1就是兩個曾被廣泛使用的、具有單向函式性質的摘要算法。有些學者把現實中使用的密碼算法分成三類，單向散列函式就是其中很重要的一類，另外兩類分別是公開鑰(或非對稱、雙鑰)算法和秘密鑰(或對稱、單鑰)算法。
陷門單向函式與公鑰密碼體制
可以毫不誇張地說，公鑰密碼體制的設計就是尋找陷門單向函式。1976年，Diffie W.和Hellman M.E.提出公鑰密碼思想和陷門單向函式概念時，並沒能給出一個陷門單向函式的實例。第一個陷門單向函式和第一個公鑰密碼體制RSA是Rivest R.L.，Shamir A.和Adleman L.M.在1978年才提出的。此後，人們又嘗試過很多種單向函式的設計方法，比如利用背包問題、糾錯碼問題、因子分解問題、離散對數問題、有限自動機合成問題等，但當前除了離散對數和因子分解問題，其他陷門單向函式都被證明存在安全缺陷或者因為其複雜性不能歸約到某個困難問題而無法得到廣泛的認可。
基於離散對數問題的密碼體制主要有數字簽名標準（DSS）、橢圓曲線密碼體制（ECC）和Diffie-Hellman密鑰交換算法等。也有人認為Diffie-Hellman算法是第一個公鑰密碼算法，它發表的時間要早於RSA體制，但實際上，它並不能用於加密解密，而只能用於在非安全信道上進行密鑰分配，真正第一個可以用於加密解密的公鑰算法是RSA。
基於因子分解問題的密碼體制除了大家熟知的RSA以外，還有Rabin算法、Feige-Fiat-Shamir算法等。後兩個算法不被大家熟悉的主要原因是，一個只能用於身份認證，另一個雖然被證明其破譯難度與大整數因子分解一樣，但不能抵抗選擇密文攻擊。
基於有限自動機的密碼體制FAPKC是我國著名學者陶仁驥教授於1985年首次提出的，該體制在1995年被攻破。後來有一些變種，但因為所基於的自動機理論不是廣泛熟悉的理論，以及其前身被破解等原因，沒有能夠從安全性上得到人們廣泛的認同。
背包密碼體制是基於一般背包問題求解是NP難的，而遞增背包的求解存在快速算法的原理來設計的。該體制提出後不久就被破解，而且破解方法同樣適用於其所有變種。基於糾錯碼的第一個體制是McEliece體制，它是基於Goppa的解碼存在快速算法而一般線性碼的解碼是NP難的原理設計的。該體制也在1992年被破解。基於類似的方法，國內知名學者王新梅等也提出了一系列基於糾錯碼的公鑰密碼體制，但在1992年前後都被破解。
有關陷門單向函式的具體設計有興趣的讀者可以參考有關文獻。只有了解了單向和陷門單向函式的概念以及陷門單向函式的設計，才能真正了解公鑰密碼體制的安全性。
