單向陷門函式

單向陷門函式是有一個陷門的一類特殊單向函式。單向陷門函式包含兩個明顯特徵:一是單向性,二是存在陷門。所謂單向性,也稱不可逆性,即對於一個函式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函式作為單向函式來使用,但是,目前還沒有嚴格的數學證明表明所謂這些單向函式真正難以求逆,即單向函式是否存在還是未知的。
在密碼學中最常用的單向函式有兩類,一是公開密鑰密碼中使用的單向陷門函式、二是訊息摘要中使用的單向散列函式
單向函式不能用作加密。因為用單向函式加密的信息是無人能解開它的。但我們可以利用具有陷門信息的單向函式構造公開密鑰密碼。

相關詞條

熱門詞條

聯絡我們