《單向陷門函數(shù)》word版

1、單向陷門函數(shù)單向陷門函數(shù)(One-way Trapdoor Function)定義：一“可逆”函數(shù)F若滿足下列二條件，則F稱為單向陷門函數(shù)：1.對于所有屬于F定義域的任一x，可以很容易算出F(x) = y;2.對于幾乎所有屬于F值域的任一y，則在計算上除非獲得陷門，否則不可能求出x，使得x = F(-1)(y)，F(xiàn)（-1）為F的反函數(shù)。但若有一額外數(shù)據(jù)z（稱為陷門），則可以很容易的求出 x = F(-1)(y)。單向函數(shù)與單向陷門函數(shù)的差異在于可逆與不可逆。若單向陷門函數(shù)存在，則任何單向陷門函數(shù)均可用來設(shè)計公開密鑰密碼系統(tǒng)。同時，若單向函數(shù)滿足交換性，則單向函數(shù)也可能用來設(shè)計公開密鑰密碼系統(tǒng)。

2、1單向陷門函數(shù)1976年，美國學者Diffie和Hellman為解決密鑰的分發(fā)與管理問題發(fā)表了著名論文密碼學的新方向New Direction in Cryptography，提出一種密鑰交換協(xié)議，允許在不安全的媒體上通過通訊雙方交換信息，安全地傳送秘密密鑰，并提出了建立“公開密鑰密碼體制”(Public Key)的新概念。這篇文章中提出的公鑰密碼的思想：若每一個用戶A有一個加密密鑰ka，不同于解秘密鑰ka，加密密鑰ka公開，ka保密，當然要求ka的公開不至于影響ka的安全。若B要向A保密送去明文m，可查A的公開密鑰ka，若用ka加密得密文c，A收到c后，用只有A自己才掌握的解密密鑰ka對x進

3、行解密得到m。當時他們還沒有實現(xiàn)這種體制的具體算法。公開密鑰密碼基于單向陷門函數(shù)。所謂單向函數(shù)，人們認為有許多函數(shù)正向計算上是容易的，但其求逆計算在計算上是不可行的，也就是很難從輸出推算出它的輸入。即已知x，我們很容易計算f（x）。但已知f（x），卻難于計算出x。在物質(zhì)世界中，這樣的例子是很普遍的，如將擠出的牙膏弄回管子里要比把牙膏擠出來困難得多；燃燒一張紙要比使它從灰燼中再生容易得多；把盤子打碎成數(shù)千片碎片很容易，把所有這些碎片再拼成為一個完整的盤子則很難。類似地，將許多大素數(shù)相乘要比將其乘積因式分解容易得多。數(shù)學上有很多函數(shù)看起來和感覺像單向函數(shù)，我們能夠有效地計算它們，但我們至今未找到有

4、效的求逆算法。我們把離散對數(shù)函數(shù)、RSA函數(shù)作為單向函數(shù)來使用，但是，目前還沒有嚴格的數(shù)學證明表明所謂這些單向函數(shù)真正難以求逆，即單向函數(shù)是否存在還是未知的。在密碼學中最常用的單向函數(shù)有兩類，一是公開密鑰密碼中使用的單向陷門函數(shù)、二是消息摘要中使用的單向散列函數(shù)。單向散列函數(shù)在下一章介紹。單向函數(shù)不能用作加密。因為用單向函數(shù)加密的信息是無人能解開它的。但我們可以利用具有陷門信息的單向函數(shù)構(gòu)造公開密鑰密碼。單向陷門函數(shù)是有一個陷門的一類特殊單向函數(shù)。它首先是一個單向函數(shù)，在一個方向上易于計算而反方向卻難于計算。但是，如果知道那個秘密陷門，則也能很容易在另一個方向計算這個函數(shù)。即已知x，易于計算f

5、（x），而已知f（x），卻難于計算x。然而，一旦給出f（x）和一些秘密信息y，就很容易計算x。在公開密鑰密碼中，計算f（x）相當于加密，陷門y相當于私有密鑰，而利用陷門y求f（x）中的x則相當于解密。1978年，美國麻省理工學院(MIT)的研究小組成員Ronald L Rivest、Adi Shamir、Leonard Adleman提出了一種基于公開密鑰密碼體制的優(yōu)秀加密算法棗RSA算法。RSA的取名就是來自于這三位發(fā)明者姓氏的第一個字母。該算法以其較高的保密強度逐漸成為一種廣為接受的公鑰密碼體制算法。RSA算法是一種分組密碼體制算法，它的保密強度是建立在具有大素數(shù)因子的合數(shù)，其因子分解是N

6、P(Nondeterministic Polynomial)完全問題這一數(shù)學難題的基礎(chǔ)上的，因此RSA算法具有很強的保密性。RSA算法研制的最初目標是解決DES算法秘密密鑰利用公開信道傳輸分發(fā)困難的難題，而實際結(jié)果不但很好地解決了這個難題；還可利用RSA來完成對消息的數(shù)字簽名以防對消息的抵賴；同時還可以利用數(shù)字簽名發(fā)現(xiàn)攻擊者對消息的非法篡改，以保護數(shù)據(jù)信息的完整性。RSA算法的保密強度隨其密鑰的長度增加而增強。但是，密鑰越長，其加解密所耗的時間也越長。因此，要根據(jù)所保護信息的敏感程度與攻擊者破解所要花的代價值不值得和系統(tǒng)所要求的反應(yīng)時間來綜合考慮決定。尤其對于商業(yè)信息領(lǐng)域更是如此。但是，RSA

7、同其它數(shù)學問題一樣，也是存在有條件、有特例的。即在不論其密鑰長度如何增加，以及如何選取其加、脫密參數(shù)，它至少存在有9個不能被加密的明文消息。RSA算法是第一個能同時用于加密和數(shù)字簽名的算法，也易于理解和操作。RSA是被研究得最廣泛的公鑰算法，普遍認為是目前最優(yōu)秀的公鑰方案之一。RSA得到了世界上的最廣泛的應(yīng)用，并于1992年ISO國際標準化組織在其頒布的國際標準X.509中，將RSA算法正式納入國際標準。    編輯本段什么是RSARSA算法是第一個能同時用于加密和數(shù)字簽名的算法，也易于理解和操作。RSA是被研究得最廣泛的公鑰算法，從提出到現(xiàn)在已近二十年

8、，經(jīng)歷了各種攻擊的考驗，逐漸為人們接受，普遍認為是目前最優(yōu)秀的公鑰方案之一。RSA的安全性依賴于大數(shù)的因子分解，但并沒有從理論上證明破譯RSA的難度與大數(shù)分解難度等價。即RSA的重大缺陷是無法從理論上把握它的保密性能如何，而且密碼學界多數(shù)人士傾向于因子分解不是NPC問題。RSA的缺點主要有：A)產(chǎn)生密鑰很麻煩，受到素數(shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密。B)分組長度太大，為保證安全性，n 至少也要 600 bits以上，使運算代價很高，尤其是速度較慢，較對稱密碼算法慢幾個數(shù)量級；且隨著大數(shù)分解技術(shù)的發(fā)展，這個長度還在增加，不利于數(shù)據(jù)格式的標準化。目前，SET(Secure Electroni

9、c Transaction)協(xié)議中要求CA采用2048比特長的密鑰，其他實體使用1024比特的密鑰。這種算法1978年就出現(xiàn)了，它是第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法。它易于理解和操作，也很流行。算法的名字以發(fā)明者的名字命名：Ron Rivest, AdiShamir 和Leonard Adleman。RSA算法是一種非對稱密碼算法，所謂非對稱，就是指該算法需要一對密鑰，使用其中一個加密，則需要用另一個才能解密。RSA的算法涉及三個參數(shù)，n、e1、e2。其中，n是兩個大質(zhì)數(shù)p、q的積，n的二進制表示時所占用的位數(shù)，就是所謂的密鑰長度。e1和e2是一對相關(guān)的值，e1可以任意取，但要求e

10、1與(p-1)*(q-1)互質(zhì)；再選擇e2，要求(e2*e1)mod(p-1)*(q-1)=1。(n及e1),(n及e2)就是密鑰對。RSA加解密的算法完全相同,設(shè)A為明文，B為密文，則：A=Be1 mod n；B=Ae2 mod n；e1和e2可以互換使用，即：A=Be2 mod n；B=Ae1 mod n;編輯本段一、RSA 的安全性RSA的安全性依賴于大數(shù)分解，但是否等同于大數(shù)分解一直未能得到理論上的證明，因為沒有證明破解 RSA就一定需要作大數(shù)分解。假設(shè)存在一種無須分解大數(shù)的算法，那它肯定可以修改成為大數(shù)分解算法。目前， RSA 的一些變種算法已被證明等價于大數(shù)分解。不管怎樣，分解n是

11、最顯然的攻擊方法?，F(xiàn)在，人們已能分解多個十進制位的大素數(shù)。因此，模數(shù)n 必須選大一些，因具體適用情況而定。編輯本段二、RSA的速度由于進行的都是大數(shù)計算，使得RSA最快的情況也比DES慢上好幾倍，無論是軟件還是硬件實現(xiàn)。速度一直是RSA的缺陷。一般來說只用于少量數(shù)據(jù)加密。編輯本段三、RSA的選擇密文攻擊RSA在選擇密文攻擊面前很脆弱。一般攻擊者是將某一信息作一下偽裝( Blind)，讓擁有私鑰的實體簽署。然后，經(jīng)過計算就可得到它所想要的信息。實際上，攻擊利用的都是同一個弱點，即存在這樣一個事實：乘冪保留了輸入的乘法結(jié)構(gòu)：( XM )d = Xd *Md mod n前面已經(jīng)提到，這個固有的問題來

12、自于公鑰密碼系統(tǒng)的最有用的特征-每個人都能使用公鑰。但從算法上無法解決這一問題，主要措施有兩條：一條是采用好的公鑰協(xié)議，保證工作過程中實體不對其他實體任意產(chǎn)生的信息解密，不對自己一無所知的信息簽名；另一條是決不對陌生人送來的隨機文檔簽名，簽名時首先使用One-Way HashFunction 對文檔作HASH處理，或同時使用不同的簽名算法。編輯本段四、RSA的公共模數(shù)攻擊若系統(tǒng)中共有一個模數(shù)，只是不同的人擁有不同的e和d，系統(tǒng)將是危險的。最普遍的情況是同一信息用不同的公鑰加密，這些公鑰共模而且互質(zhì)，那么該信息無需私鑰就可得到恢復(fù)。設(shè)P為信息明文，兩個加密密鑰為e1和e2，公共模數(shù)是n，則：C1

13、 = Pe1 mod nC2 = Pe2 mod n密碼分析者知道n、e1、e2、C1和C2，就能得到P。因為e1和e2互質(zhì)，故用Euclidean算法能找到r和s，滿足：r * e1 + s * e2 = 1假設(shè)r為負數(shù)，需再用Euclidean算法計算C1(-1)，則( C1(-1) )(-r) * C2s = P mod n另外，還有其它幾種利用公共模數(shù)攻擊的方法?？傊?，如果知道給定模數(shù)的一對e和d，一是有利于攻擊者分解模數(shù)，一是有利于攻擊者計算出其它成對的e和d，而無需分解模數(shù)。解決辦法只有一個，那就是不要共享模數(shù)n。RSA的小指數(shù)攻擊。 有一種提高 RSA速度的建議是使公鑰e取較小的

14、值，這樣會使加密變得易于實現(xiàn)，速度有所提高。但這樣作是不安全的，對付辦法就是e和d都取較大的值。編輯本段五、RSA 加密算法的缺點1)產(chǎn)生密鑰很麻煩，受到素數(shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密。2)安全性, RSA的安全性依賴于大數(shù)的因子分解，但并沒有從理論上證明破譯RSA的難度與大數(shù)分解難度等價，而且密碼學界多數(shù)人士傾向于因子分解不是NPC問題。目前，人們已能分解140多個十進制位的大素數(shù)，這就要求使用更長的密鑰，速度更慢；另外，目前人們正在積極尋找攻擊RSA的方法，如選擇密文攻擊，一般攻擊者是將某一信息作一下偽裝(Blind)，讓擁有私鑰的實體簽署。然后，經(jīng)過計算就可得到它所想要的信息。

15、實際上，攻擊利用的都是同一個弱點，即存在這樣一個事實：乘冪保留了輸入的乘法結(jié)構(gòu)：( XM )d = Xd *Md mod n前面已經(jīng)提到，這個固有的問題來自于公鑰密碼系統(tǒng)的最有用的特征-每個人都能使用公鑰。但從算法上無法解決這一問題，主要措施有兩條：一條是采用好的公鑰協(xié)議，保證工作過程中實體不對其他實體任意產(chǎn)生的信息解密，不對自己一無所知的信息簽名；另一條是決不對陌生人送來的隨機文檔簽名，簽名時首先使用One-Way Hash Function對文檔作HASH處理，或同時使用不同的簽名算法。除了利用公共模數(shù)，人們還嘗試一些利用解密指數(shù)或（n）等等攻擊.3)速度太慢,由于RSA 的分組長度太大，為保證安全性，n 至少也要 600 bitx以上，使運算代價很高，尤其是速度較慢，較對稱密碼算法慢幾個數(shù)量級；且隨著大數(shù)分解技術(shù)的發(fā)展，這個長度還在增加，不利于數(shù)據(jù)格式的標準化。目前，SET(Secure Electronic Transaction)協(xié)議中要求CA采用2048比特長的密鑰，其他實體使用1024比特的密鑰。為了速度問題,目前人們廣