單向陷門函數(shù)

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

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

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

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

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

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

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

8、Shamir和LeonardAdleman。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可以任意取，但要求e1與(p1)(q1)互質(zhì)；再選擇e2，要求(e2e1)mod((p1)(q1))=1。(n及e1)(n及e2)

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