單向陷門函數(shù)01177

1、1單向陷門函數(shù)單向陷門函數(shù)1976年，美國(guó)學(xué)者Diffie和Hellman為解決密鑰的分發(fā)與管理問(wèn)題發(fā)表了著名論文《密碼學(xué)的新方向》NewDirectioninCryptography，提出一種密鑰交換協(xié)議，允許在不安全的媒體上通過(guò)通訊雙方交換信息，安全地傳送秘密密鑰，并提出了建立“公開密鑰密碼體制”(PublicKey)的新概念。這篇文章中提出的公鑰密碼的思想：若每一個(gè)用戶A有一個(gè)加密密鑰ka，不同于解秘密鑰ka’，加密密鑰ka公開，

2、ka’保密，當(dāng)然要求ka的公開不至于影響ka’的安全。若B要向A保密送去明文m，可查A的公開密鑰ka，若用ka加密得密文c，A收到c后，用只有A自己才掌握的解密密鑰ka’對(duì)x進(jìn)行解密得到m。當(dāng)時(shí)他們還沒(méi)有實(shí)現(xiàn)這種體制的具體算法。公開密鑰密碼基于單向陷門函數(shù)。所謂單向函數(shù)，人們認(rèn)為有許多函數(shù)正向計(jì)算上是容易的，但其求逆計(jì)算在計(jì)算上是不可行的，也就是很難從輸出推算出它的輸入。即已知x，我們很容易計(jì)算f（x）。但已知f（x），卻難于計(jì)算出x。

3、在物質(zhì)世界中，這樣的例子是很普遍的，如將擠出的牙膏弄回管子里要比把牙膏擠出來(lái)困難得多；燃燒一張紙要比使它從灰燼中再生容易得多；把盤子打碎成數(shù)千片碎片很容易，把所有這些碎片再拼成為一個(gè)完整的盤子則很難。類似地，將許多大素?cái)?shù)相乘要比將其乘積因式分解容易得多。數(shù)學(xué)上有很多函數(shù)看起來(lái)和感覺(jué)像單向函數(shù)，我們能夠有效地計(jì)算它們，但我們至今未找到有效的求逆算法。我們把離散對(duì)數(shù)函數(shù)、RSA函數(shù)作為單向函數(shù)來(lái)使用，但是，目前還沒(méi)有嚴(yán)格的數(shù)學(xué)證明表明所謂這

4、些單向函數(shù)真正難以求逆，即單向函數(shù)是否存在還是未知的。在密碼學(xué)中最常用的單向函數(shù)有兩類，一是公開密鑰密碼中使用的單向陷門函數(shù)、二是消息摘要中使用的單向散列函數(shù)。單向散列函數(shù)在下一章介紹。單向函數(shù)不能用作加密。因?yàn)橛脝蜗蚝瘮?shù)加密的信息是無(wú)人能解開它的。但我們可以利用具有陷門信息的單向函數(shù)構(gòu)造公開密鑰密碼。單向陷門函數(shù)是有一個(gè)陷門的一類特殊單向函數(shù)。它首先是一個(gè)單向函數(shù)，在一個(gè)方向上易于計(jì)算而反方向卻難于計(jì)算。但是，如果知道那個(gè)秘密陷門，則

5、也能很容易在另一個(gè)方向計(jì)算這個(gè)函數(shù)。即已知x，易于計(jì)算f（x），而已知f（x），卻難于計(jì)算x。然而，一旦給出f（x）和一些秘密信息y，就很容易計(jì)算x。在公開密鑰密碼中，計(jì)算f（x）相當(dāng)于加密，陷門y相當(dāng)于私有密鑰，而利用陷門y求f（x）中的x則相當(dāng)于解密。1978年，美國(guó)麻省理工學(xué)院(MIT)的研究小組成員RonaldLRivest、AdiShamir、LeonardAdleman提出了一種基于公開密鑰密碼體制的優(yōu)秀加密算法棗RSA算法

6、。RSA的取名就是來(lái)自于這三位發(fā)明者姓氏的第一個(gè)字母。該算法以其較高的保密強(qiáng)度逐漸成為一種廣為接受的公鑰密碼體制算法。RSA算法是一種分組密碼體制算法，它的保密強(qiáng)度是建立在具有大素?cái)?shù)因子的合數(shù)，其因子分解是NP(NondeterministicPolynomial)完全問(wèn)題這一數(shù)學(xué)難題的基礎(chǔ)上的，因此RSA算法具有很強(qiáng)的保密性。RSA算法研制的最初目標(biāo)是解決DES算法秘密密鑰利用公開信道傳輸分發(fā)困難的難題，而實(shí)際結(jié)果不但很好地解決了這個(gè)

7、難題；還可利用RSA來(lái)完成對(duì)消息的數(shù)字簽名以防對(duì)消息的抵賴；同時(shí)還可以利用數(shù)字簽名發(fā)現(xiàn)攻擊者對(duì)消息的非法篡改，以保護(hù)數(shù)據(jù)信息的完整性。RSA算法的保密強(qiáng)度隨其密鑰的長(zhǎng)度增加而增強(qiáng)。但是，密鑰越長(zhǎng)，其加解密所耗的時(shí)間也越長(zhǎng)。因此，要根據(jù)所保護(hù)信息的敏感程度與攻擊者破解所要花的代價(jià)值不值得和系統(tǒng)所要求的反應(yīng)時(shí)間來(lái)綜合考慮決定。尤其對(duì)于商業(yè)信息領(lǐng)域更是如此。但是，RSA同其它數(shù)學(xué)問(wèn)題一樣，也是存在有條件、有特例的。即在不論其密鑰長(zhǎng)度如何增加，