單向陷門函式是有一個陷門的一類特殊單向函式。單向陷門函式包含兩個明顯特徵：一是單向性，二是存在陷門。所謂單向性，也稱不可逆性，即對於一個函式y=f(x)，若已知x要計算出y很容易，但是已知y要計算出x=f ^(-1) (y)則很困難。單向函式的命名就是源於其只有一個方向能夠計算。所謂陷門，也成為後門。對於單向函式，若存在一個z使得知道z則可以很容易地計算出x=f ^(-1) (y)，而不知道z則無法計算出x=f ^(-1) (y)，則稱函式y=f(x)為單向陷門函式，而z稱為陷門。
基本介紹
- 中文名：單向陷門函式
- 外文名：One-way Trapdoor Function
- 提出者：Diffie和Hellman
- 提出時間：1976年
- 套用學科：高等數學、密碼學
- 適用領域範圍：密碼學與信息安全領域
簡介,詳解,
簡介
它首先是一個單向函式，在一個方向上易於計算而反方向卻難於計算。但是，如果知道那個秘密陷門，則也能很容易在另一個方向計算這個函式。即已知x，易於計算f（x），而已知f（x），卻難於計算x。然而，一旦給出f（x）和一些秘密信息y，就很容易計算x。在公開密鑰密碼中，計算f（x）相當於加密，陷門y相當於私有密鑰，而利用陷門y求f（x）中的x則相當於解密。
詳解
1976年，美國學者Diffie和Hellman為解決密鑰的分發與管理問題發表了著名論文《密碼學的新方向》New Direction in Cryptography，提出一種密鑰交換協定，允許在不安全的媒體上通過通訊雙方交換信息，安全地傳送秘密密鑰，並提出了建立“公開密鑰密碼體制”(Public Key)的新概念。這篇文章中提出的公鑰密碼的思想：若每一個用戶A有一個加密密鑰ka，不同於解秘密鑰ka’，加密密鑰ka公開，ka’保密，當然要求ka的公開不至於影響ka’的安全。若B要向A保密送去明文m，可查A的公開密鑰ka，若用ka加密得密文c，A收到c後，用只有A自己才掌握的解密密鑰ka’對c進行解密得到m。當時他們還沒有實現這種體制的具體算法。公開密鑰密碼基於單向陷門函式。
所謂單向函式，人們認為有許多函式正向計算上是容易的，但其求逆計算在計算上是不可行的，也就是很難從輸出推算出它的輸入。即已知x，我們很容易計算f（x）。但已知f（x），卻難於計算出x。
在物質世界中，這樣的例子是很普遍的，如將擠出的牙膏弄回管子裡要比把牙膏擠出來困難得多；燃燒一張紙要比使它從灰燼中再生容易得多；把盤子打碎成數千片碎片很容易，把所有這些碎片再拼成為一個完整的盤子則很難。類似地，將許多大素數相乘要比將其乘積因式分解容易得多。數學上有很多函式看起來和感覺像單向函式，我們能夠有效地計算它們，但我們至今未找到有效的求逆算法。我們把離散對數函式、RSA函式作為單向函式來使用，但是，目前還沒有嚴格的數學證明表明所謂這些單向函式真正難以求逆，即單向函式是否存在還是未知的。
單向函式不能用作加密。因為用單向函式加密的信息是無人能解開它的。但我們可以利用具有陷門信息的單向函式構造公開密鑰密碼。
