資源描述：
《公鑰密碼講座new》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、本科生課程劉建偉2010-10-14第8講：公鑰密碼技術(shù)（一）?公鑰密碼體制的基本概念?構(gòu)造公鑰密碼的困難問(wèn)題–離散對(duì)數(shù)、整數(shù)分解、橢圓曲線、…?主要的幾種公鑰算法–RSA公鑰算法–Diffie-Hellman密鑰交換–ElGamal公鑰算法–Rabin算法–橢圓曲線公鑰算法(ECC)一、雙鑰密碼體制的基本概念1、公鑰密碼的歷史?在對(duì)稱密鑰密碼體制中，加密運(yùn)算與解密運(yùn)算使用同樣的密鑰。但是，在公開(kāi)的計(jì)算機(jī)網(wǎng)絡(luò)上安全地傳送和保管密鑰是一個(gè)嚴(yán)峻的問(wèn)題。?1976年，Diffie和Hellman在奠基性論文“密碼學(xué)的新方向”中提出公開(kāi)密鑰密碼體制的概念：
2、使密鑰交換、管理容易，并可實(shí)現(xiàn)數(shù)字簽名。–NewDirectionsinCryptography,IEEEIT-22,1976?公鑰密碼體制的基礎(chǔ)，是計(jì)算復(fù)雜度理論。–單向函數(shù)/單向陷門(mén)函數(shù)–計(jì)算上困難問(wèn)題/NP完全問(wèn)題2、公鑰密碼學(xué)?WhitefieldDiffie，MartinHellman，《NewDirectionsinCryptography》，1976。?公鑰密碼學(xué)的出現(xiàn)使大規(guī)模的安全通信得以實(shí)現(xiàn)–解決了密鑰分發(fā)問(wèn)題；?公鑰密碼學(xué)還可用于另外一些應(yīng)用：數(shù)字簽名、防抵賴等；?公鑰密碼體制的基本原理–陷門(mén)單向函數(shù)(trapdoorone-w
3、ayfunction)?公鑰密碼是密碼學(xué)歷史上一個(gè)偉大的革命性成果。3、理論基礎(chǔ)——單向函數(shù)定義1：令函數(shù)f是集A到集B的映射，用f:A→B表示。若對(duì)于任意x≠x，x,x∈A，有f(x)≠f(x)，則稱f為單射，121212或1-1映射，或可逆的函數(shù)。定義2：一個(gè)可逆函數(shù)f:A→B，若它滿足：(1)對(duì)所有x∈A，易于計(jì)算f(x)；(()2)對(duì)“幾乎所有x∈A”，由f(x)求x極為困難，以至于幾乎是不可能的，則稱f是一個(gè)單向函數(shù)。注意：定義中的“極為困難”是相對(duì)現(xiàn)有的計(jì)算機(jī)資源和算法而言。4、理論基礎(chǔ)——陷門(mén)單向函數(shù)定義3：陷門(mén)單向函數(shù)是一類滿足下述
4、條件的單向函數(shù)：f:A→B，z∈Z，Z是陷門(mén)信息集合。zzz(1)對(duì)所有z∈Z，在給定z下容易找到一對(duì)算法E和D，使對(duì)zz所有x∈A，易于計(jì)算f及其逆，即：zf(x)?E(x)zzD(f(x))?xzz(2)對(duì)所有z∈Z，當(dāng)只給定E和D時(shí)，對(duì)所有x∈A，“很難zz”從y=f(x)計(jì)算出x。z區(qū)別：?jiǎn)蜗蚝瘮?shù)是求逆困難的函數(shù)，而陷門(mén)單向函數(shù)(trapdooronewayfunction)是在不知道陷門(mén)信息下求逆困難的函數(shù)。當(dāng)知道陷門(mén)信息后，求逆易于實(shí)現(xiàn)。5、用于構(gòu)造雙鑰密碼的單向函數(shù)1.多項(xiàng)式求根2.離散對(duì)數(shù)DL(DiscreteLogarithm)3
5、.大整數(shù)分解FAC(FactorizationProblem)4.背背問(wèn)包問(wèn)題題((ppKnapsackproblem))5.Diffie-Hellman問(wèn)題DHP6.二次剩余問(wèn)題QR(QQR(QuadratiiRcResidue)7.模n的平方根問(wèn)題(SQROOT)公鑰密碼體制的原理公鑰密碼技術(shù)，又稱非對(duì)稱密碼技術(shù)或雙鑰密碼技術(shù)（Public-key/Two-key/Asymmetric），其加密和解密數(shù)據(jù)使用不同的密鑰。不同abc#@&abc加密器解密器明文密文明文公鑰密鑰體制的密鑰管理?公鑰密鑰體制解決了密鑰的發(fā)布和管理問(wèn)題，通信雙方可以公開(kāi)
6、其公開(kāi)密鑰，而保留私有密鑰。?發(fā)送方可以用人人皆知的接受方公開(kāi)密鑰對(duì)發(fā)送的信息進(jìn)行加密，安全的傳送給該接受方，然后由接受方用自己的私有密鑰進(jìn)行解密。公鑰密碼體制的特點(diǎn)?包括兩個(gè)密鑰：–公開(kāi)密鑰(public-key)，可以被任何人知道，用于加密或驗(yàn)證簽名–私鑰(private-key)，只能被消息的接收者或簽名者知道，用于解密或簽名?由私鑰及其他密碼信息容易計(jì)算出公開(kāi)密鑰；?而由公鑰及算法描述，計(jì)算私鑰卻非常困難。公鑰加密方案公鑰算法的用途?用于公公分發(fā)鑰分發(fā)（Public-KeyDistributionSchemes—PKDS）–用于交換秘密信息
7、，常用于交換對(duì)稱加密算法的密鑰?用于公鑰加密((yPublicKeyEncrypyption—PKE)–用于加密任何消息–任何人可以用公鑰加密，私鑰的擁有者可以解密–任何公鑰加密方案能夠用于密鑰分配方案PKDS–許多公鑰加密方案也是數(shù)字簽名方案?用于數(shù)字簽名（SignatureSchemes）–用于生成對(duì)某消息的數(shù)字簽名–私鑰的擁有者生成數(shù)字簽名–任何人可以用公鑰驗(yàn)證簽名公鑰的安全性?依賴于數(shù)學(xué)上足夠大的困難性。?類似與對(duì)稱算法,窮搜索（exhaustivesearch）在理論上是能夠破解公鑰密碼，但實(shí)際上，當(dāng)密鑰足夠長(zhǎng)(()>512bits)時(shí)，
8、破解極其困難。?一般情況下，我們已經(jīng)找到了一些已知的困難問(wèn)題(hardproblem）?目前，通常要求足夠大的密鑰長(zhǎng)度(>
