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

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

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

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

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

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

6、P(Nondeterministic Polynomial)完全問(wèn)題這一數(shù)學(xué)難題的基礎(chǔ)上的，因此RSA算法具有很強(qiáng)的保密性。RSA算法研制的最初目標(biāo)是解決DES算法秘密密鑰利用公開(kāi)信道傳輸分發(fā)困難的難題，而實(shí)際結(jié)果不但很好地解決了這個(gè)難題；還可利用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

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

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

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

10、1與(p-1)*(q-1)互質(zhì)；再選擇e2，要求(e2*e1)mod(p-1)*(q-1)=1。(n及e1),(n及e2)就是密鑰對(duì)。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ù)分解一直未能得到理論上的證明，因?yàn)闆](méi)有證明破解 RSA就一定需要作大數(shù)分解。假設(shè)存在一種無(wú)須分解大數(shù)的算法，那它肯定可以修改成為大數(shù)分解算法。目前， RSA 的一些變種算法已被證明等價(jià)于大數(shù)分解。不管怎樣，分解n是

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

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

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

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

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