單向函數

1976年，Diffie W.和Hellman M.E.在他們的《密碼學的新方向》一文中提出了公鑰密碼的概念。隨後，在1978年，Rivest R.L.，Shamir A.和Adleman L.M.在其文《實現數字簽名和公鑰密碼體制的一種方法》中最先提出了一種可行的實現方法，這就是我們廣泛使用的RSA體制。RSA體制的提出真正使得互不相識的通信雙方在一個不安全的信道上進行安全通信最終成為可能，也是CA服務的源泉。然而，人們很少關心當前幸福生活的背後有一位默默的奉獻者—單向函數。 ^[1] 

給定任意兩個集合

和

。 函數

稱為單向的，如果對每一個

屬於

，很容易計算出函數

的值，而對大多數y屬於

， 要確定滿足

的

是計算上困難的(假設至少有這樣一個x存在)。注意，不能將單向函數的概念與數學意義上的不可逆函數的概念混同，因為單向函數可能是一個數學意義上可逆或者一對一的函數，而一個不可逆函數卻不一定是單向函數。

還沒有人能夠從理論上證明單向函數是存在的。單向函數存在性的證明將意味着計算機科學中一個最具挑戰性的猜想

，即

完全問題的解決，而關於

完全性的理論卻不足以證明單向函數的存在。有幸的是，現實中卻存在幾個單向函數的“候選”。説他們是“候選”，是因為他們表現出了單向函數的性質，但還沒有辦法從理論上證明它們一定是單向函數。

一個最簡單的、大家熟知的“侯選”單向函數就是整數相乘。眾所周知，不管給定兩個多大的整數，我們很容易計算出它們的乘積，而對於一個300位左右的十進制整數，即使已知它是兩個大小差不多（150位左右的十進制數）的素數之積，用世界上計算能力最強的計算機，也沒有辦法在一個合理的時間內分解出構成這個整數的兩個素數因子來。這裏講的“合理的時間”是指一個可度量的相當長的時間，比如人類或者地球的壽命等。

函數

是一個單向函數當且僅當

可以用一個多項式時間的算法計算，但是對於任意一個以

為輸入的隨機化多項式算法

，任意一個多項式

，和足夠大

,使得

顯然，單向函數不能直接用作密碼體制，因為如果用單向函數對明文進行加密，即使是合法的接收者也不能還原出明文了，因為單向函數的逆運算是困難的。與密碼體制關係更為密切的概念是陷門單向函數。一個函數

稱為是陷門單向的，如果該函數及其逆函數的計算都存在有效的算法，而且可以將計算

的方法公開，即使有計算f的完整方法也不能推導出其逆運算的有效算法。其中，使得雙向都能有效計算的秘密信息叫做陷門(trap door)。

第一個陷門單向函數與上面介紹過的第二個單向函數候選類似：固定指數和模數的模指數運算。不同的是這次是固定指數和模數，前面是固定基數和模數。設

和

是整數，

同上，關於指數

和模

的模指數運算函數

,由

,

定義。又與實數域上概念類似，其逆運算也叫作求

模

的

次根，即：給定整數

、

和

，求整數

使得

成立(如果這樣的a存在的話)。例如，5就是16模21的4次根，因為

mod 21=16。顯然，2也是16模21的4次根。大家可以嘗試着求出16模21的另一個4次根，或者求一個整數

，它模21沒有4次根。

只要

和

是固定的，學過計算機的人都很容易設計出一個算法，對任何

，可以有效地計算出

,

的值。與前面的離散對數問題相反，我們確切知道，也存在有效算法，對任何

，可以容易地求出

模

的

次根。有意思的是，如果只知道

和

，如何構造出該有效的算法卻不得而知。換言之，

不是單向函數，因為它的求逆不是困難的，儘管我們還不知道如何去做。然而，如果除了知道

和

以外，還知道構成n的素因子，就很容易構造出求模

的

次根的有效算法。因此，

可以作為陷門單向函數，其中

和

可以用做公開信息，而

的因子分解就是秘密的陷門。

模指數的一個特殊情況是當模

具有特殊形式，僅由兩個素數

和

構成，即

。著名的RSA體制就是根據這個陷門單向函數設計出來的。

需要提醒的是，不能顧名思義地認為陷門單向函數是單向函數。事實上，陷門單向函數不是單向函數，它只是對於那些不知道陷門的人表現出了單向函數的特性。

前面説過，單向函數不能直接用作密碼體制，因為它的求逆困難，用它加密的信息誰都不能解密。但是，單向函數在密碼學領域裏卻發揮着非常重要的作用。一個最簡單的應用就是口令保護。我們熟知的口令保護方法是用對稱加密算法進行加密。然而，對稱算法加密一是必須有密鑰，二是該密鑰對驗證口令的系統必須是可知的，因此意味着驗證口令的系統總是可以獲取口令的明文的。這樣在口令的使用者與驗證口令的系統之間存在嚴重的信息不對稱，姑且不説系統提供者非法獲取用户口令的情況，一旦系統被攻破，可能造成所有用户口令的泄露。使用單向函數對口令進行保護則可以很好地解決這一問題。系統方只存放口令經單向函數運算過的函數值，驗證是將用户口令重新計算函數值與系統中存放的值進行比對。動態口令認證機制多是基於單向函數的應用來設計的。

單向函數的另一個應用是大家熟知的用於數字簽名時產生信息摘要的單向散列函數。由於公鑰密碼體制的運算量往往比較大，為了避免對待籤文件進行全文簽名，一般在簽名運算前使用單向散列算法對簽名文件進行摘要處理，將待籤文件壓縮成一個分組之內的定長位串，以提高簽名的效率。MD5和SHA-1就是兩個曾被廣泛使用的、具有單向函數性質的摘要算法。有些學者把現實中使用的密碼算法分成三類，單向散列函數就是其中很重要的一類，另外兩類分別是公開鑰(或非對稱、雙鑰)算法和秘密鑰(或對稱、單鑰)算法。 ^[2] 

可以毫不誇張地説，公鑰密碼體制的設計就是尋找陷門單向函數。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年前後都被破解。

有關陷門單向函數的具體設計有興趣的讀者可以參考有關文獻。只有瞭解了單向和陷門單向函數的概念以及陷門單向函數的設計，才能真正瞭解公鑰密碼體制的安全性。