單向陷門函數(shù)

1、單向陷門函數(shù)單向陷門函數(shù)(OnewayTrapdoFunction)定義：一“可逆”函數(shù)F若滿足下列二條件，則F稱為單向陷門函數(shù)：1.對于所有屬于F定義域的任一x，可以很容易算出F(x)=y2.對于幾乎所有屬于F值域的任一y，則在計算上除非獲得陷門，否則不可能求出x，使得x=F^(1)(y)，F(xiàn)^（1）為F的反函數(shù)。但若有一額外數(shù)據(jù)z（稱為陷門），則可以很容易的求出x=F^(1)(y)。單向函數(shù)與單向陷門函數(shù)的差異在于可逆與不可逆。若單

2、向陷門函數(shù)存在，則任何單向陷門函數(shù)均可用來設(shè)計公開密鑰密碼系統(tǒng)。同時，若單向函數(shù)滿足交換性，則單向函數(shù)也可能用來設(shè)計公開密鑰密碼系統(tǒng)。1單向陷門函數(shù)單向陷門函數(shù)1976年，美國學(xué)者Diffie和Hellman為解決密鑰的分發(fā)與管理問題發(fā)表了著名論文《密碼學(xué)的新方向》NewDirectioninCryptography，提出一種密鑰交換協(xié)議，允許在不安全的媒體上通過通訊雙方交換信息，安全地傳送秘密密鑰，并提出了建立“公開密鑰密碼體制”(P

3、ublicKey)的新概念。這篇文章中提出的公鑰密碼的思想：若每一個用戶A有一個加密密鑰ka，不同于解秘密鑰ka’，加密密鑰ka公開，ka’保密，當(dāng)然要求ka的公開不至于影響ka’的安全。若B要向A保密送去明文m，可查A的公開密鑰ka，若用ka加密得密文c，A收到c后，用只有A自己才掌握的解密密鑰ka’對x進(jìn)行解密得到m。當(dāng)時他們還沒有實現(xiàn)這種體制的具體算法。公開密鑰密碼基于單向陷門函數(shù)。所謂單向函數(shù)，人們認(rèn)為有許多函數(shù)正向計算上是容易

4、的，但其求逆計算在計算上是不可行的，也就是很難從輸出推算出它的輸入。即已知x，我們很容易計算f（x）。但已知f（x），卻難于計算出x。在物質(zhì)世界中，這樣的例子是很普遍的，如將擠出的牙膏弄回管子里要比把牙膏擠出來困難得多；燃燒一張紙要比使它從灰燼中再生容易得多；把盤子打碎成數(shù)千片碎片很容易，把所有這些碎片再拼成為一個完整的盤子則很難。類似地，將許多大素數(shù)相乘要比將其乘積因式分解容易得多。數(shù)學(xué)上有很多函數(shù)看起來和感覺像單向函數(shù)，我們能夠有效

5、地計算它們，但我們至今未找到有效的求逆算法。我們把離散對數(shù)函數(shù)、RSA函數(shù)作為單向函數(shù)來使用，但是，目前還沒有嚴(yán)格的數(shù)學(xué)證明表明所謂這些單向函數(shù)真正難以求逆，即單向函數(shù)是否存在還是未知的。在密碼學(xué)中最常用的單向函數(shù)有兩類，一是公開密鑰密碼中使用的單向陷門函數(shù)、二是消息摘要中使用的單向散列函數(shù)。單向散列函數(shù)在下一章介紹。編輯本段什么是什么是RSARSA算法是第一個能同時用于加密和數(shù)字簽名的算法，也易于理解和操作。RSA是被研究得最廣泛的公

6、鑰算法，從提出到現(xiàn)在已近二十年，經(jīng)歷了各種攻擊的考驗，逐漸為人們接受，普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一。RSA的安全性依賴于大數(shù)的因子分解，但并沒有從理論上證明破譯RSA的難度與大數(shù)分解難度等價。即RSA的重大缺陷是無法從理論上把握它的保密性能如何，而且密碼學(xué)界多數(shù)人士傾向于因子分解不是NPC問題。RSA的缺點主要有：A)產(chǎn)生密鑰很麻煩，受到素數(shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密。B)分組長度太大，為保證安全性，n至少也要600bi

7、ts以上，使運算代價很高，尤其是速度較慢，較對稱密碼算法慢幾個數(shù)量級；且隨著大數(shù)分解技術(shù)的發(fā)展，這個長度還在增加，不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化。目前，SET(SecureElectronicTransaction)協(xié)議中要求CA采用2048比特長的密鑰，其他實體使用1024比特的密鑰。這種算法1978年就出現(xiàn)了，它是第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法。它易于理解和操作，也很流行。算法的名字以發(fā)明者的名字命名：RonRivestAdi

8、Shamir和LeonardAdleman。RSA算法是一種非對稱密碼算法，所謂非對稱，就是指該算法需要一對密鑰，使用其中一個加密，則需要用另一個才能解密。RSA的算法涉及三個參數(shù)，n、e1、e2。其中，n是兩個大質(zhì)數(shù)p、q的積，n的二進(jìn)制表示時所占用的位數(shù)，就是所謂的密鑰長度。e1和e2是一對相關(guān)的值，e1可以任意取，但要求e1與(p1)(q1)互質(zhì)；再選擇e2，要求(e2e1)mod((p1)(q1))=1。(n及e1)(n及e2)

9、就是密鑰對。RSA加解密的算法完全相同設(shè)A為明文，B為密文，則：A=B^e1modn；B=A^e2modn；e1和e2可以互換使用，即：A=B^e2modn；B=A^e1modn編輯本段一、一、RSA的安全性的安全性RSA的安全性依賴于大數(shù)分解，但是否等同于大數(shù)分解一直未能得到理論上的證明，因為沒有證明破解RSA就一定需要作大數(shù)分解。假設(shè)存在一種無須分解大數(shù)的算法，那它肯定可以修改成為大數(shù)分解算法。目前，RSA的一些變種算法已被證明等價