第4講 公鑰密碼體制81364

《第4講 公鑰密碼體制81364》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第4講　公鑰密碼體制主講：謝昕課程主要內(nèi)容公鑰密碼體制概述背包公鑰密碼RSA公鑰密碼橢圓曲線密碼概率加密等§1　公鑰密碼體制概述對(duì)稱(chēng)密鑰密碼體制問(wèn)題：如何在網(wǎng)絡(luò)上安全地傳送和保管密鑰？無(wú)法實(shí)現(xiàn)抗抵賴(lài)的需求等…1976年，美國(guó)學(xué)者Diffie和Hellman發(fā)表了著名論文《密碼學(xué)的新方向》，提出了建立“公開(kāi)密鑰密碼體制”：若用戶(hù)A有加密密鑰PK(公開(kāi))，不同于解秘密鑰SK(保密)，要求PK的公開(kāi)不影響SK的安全。若B要向A保密送去明文m，可查A的公開(kāi)密鑰PKA，若用PKA加密得密文c，A收到密文c后，用只有A自己才掌握的解密密鑰SKA對(duì)x進(jìn)行解密得到明文m。

2、公開(kāi)密鑰密碼體制是現(xiàn)代密碼學(xué)最重要的發(fā)明離散數(shù)學(xué)盡人皆知的密鑰叫做公開(kāi)密鑰(publickey)；只有密鑰擁有者才知道的密鑰：私有密鑰(privatekey)這兩種密鑰合在一起稱(chēng)為密鑰對(duì)；公開(kāi)密鑰可以解決安全分配密鑰問(wèn)題（不需要與保密密鑰通信，所傳輸?shù)闹挥泄_(kāi)密鑰，它不需要保密），但對(duì)保證其真實(shí)性和完整性卻非常重要。如果某一信息用公開(kāi)密鑰加密，則必須用私有密鑰解密，這就是實(shí)現(xiàn)保密的方法。如果某一信息用私有密鑰加密，它必須用公開(kāi)密鑰解密，這就是實(shí)現(xiàn)驗(yàn)證的方法?！?　公鑰密碼體制概述離散數(shù)學(xué)算法特點(diǎn)：使用一個(gè)加密算法E和一個(gè)解密算法D，它們彼此完全不同，根據(jù)已

3、選定的E和D，即使已知E的完整描述，也不可能推導(dǎo)出D?！?　公鑰密碼體制概述離散數(shù)學(xué)§1　公鑰密碼體制概述數(shù)字簽名必須保證做到以下3點(diǎn)：（1）接收者能夠核實(shí)發(fā)送者對(duì)報(bào)文的簽名；（2）發(fā)送者事后不能抵賴(lài)對(duì)報(bào)文的簽名；（3）接收者不能偽造對(duì)報(bào)文的簽名。離散數(shù)學(xué)RSA是一種基于公鑰密碼體制的優(yōu)秀加密算法，1978年由美國(guó)(MIT)的李維斯特(Rivest)、沙米爾(Shamir)、艾德曼(Adleman)提的。RSA算法是一種分組密碼體制算法，它的保密強(qiáng)度是建立在具有大素?cái)?shù)因子的合數(shù)其因子分解是困難的（基于大數(shù)分解的難度）。公鑰和私鑰是一對(duì)大素?cái)?shù)的函數(shù)，從一個(gè)公

4、鑰和密文中恢復(fù)出明文的難度等價(jià)于分解兩個(gè)大素?cái)?shù)之積。RSA得到了世界上的最廣泛的應(yīng)用，ISO在1992年頒布的國(guó)際標(biāo)準(zhǔn)X.509中,將RSA算法正式納入國(guó)際標(biāo)準(zhǔn)。§2RSA公鑰密碼體制離散數(shù)學(xué)整數(shù)n的　　　　　　因子分解的　　　所需計(jì)算十進(jìn)制位數(shù)　　　　　運(yùn)算次數(shù)　　　　時(shí)間501.4x10103.9小時(shí)759.0x1012104天1002.3x101574年2001.2x10233.8x109年3001.5x10294.0x1015年5001.3x10394.2x1025年（每微秒一次）§2RSA公鑰密碼體制離散數(shù)學(xué)RSA密鑰體制的特點(diǎn)：（1）密鑰配發(fā)十

5、分方便，用戶(hù)的公開(kāi)密鑰可以像電話本那樣公開(kāi)，使用方便，每個(gè)用戶(hù)只需持有一對(duì)密鑰即可實(shí)現(xiàn)與網(wǎng)絡(luò)中任何一個(gè)用戶(hù)的保密通信。（2）RSA加密原理基于單向函數(shù)，非法接收者利用公開(kāi)密鑰不可能在有限時(shí)間內(nèi)推算出秘密密鑰。RSA在用戶(hù)確認(rèn)和實(shí)現(xiàn)數(shù)字簽名方面優(yōu)于現(xiàn)有的其他加密機(jī)制。§2RSA公鑰密碼體制離散數(shù)學(xué)單向函數(shù)：給定一個(gè)函數(shù)f，若對(duì)任意給定的x，計(jì)算y，使得y=f(x)是容易的；但對(duì)任意給定的y，計(jì)算x，使得f(x)=y是難解的，即計(jì)算f-1(y)是困難的。則稱(chēng)f為單向函數(shù)。例：f(x)=ax（x、a?GF(q)）為單向函數(shù)?！?RSA公鑰密碼體制陷門(mén)單向函數(shù)：給

6、定一個(gè)函數(shù)f，t為f相關(guān)的參數(shù)，任意給定的x，計(jì)算y=f(x)是容易的；當(dāng)t未知時(shí)，計(jì)算逆函數(shù)f-1(y)難解，而當(dāng)t已知時(shí)，計(jì)算f-1(y)容易。則稱(chēng)為f陷門(mén)單向函數(shù)。離散數(shù)學(xué)用于構(gòu)造雙鑰密碼的單向函數(shù)：（1）多項(xiàng)式求根（2）離散對(duì)數(shù)（3）大整數(shù)分解（4）背包問(wèn)題（5）Diffie-Hellman問(wèn)題（6）二次剩余問(wèn)題（7）模n的平方根問(wèn)題§2RSA公鑰密碼體制離散數(shù)學(xué)§2.1　RSA公鑰密碼算法描述（1）設(shè)計(jì)密鑰A、在離線方式下，先產(chǎn)生兩個(gè)足夠大的強(qiáng)質(zhì)數(shù)p、q；B、令n=p＊q。計(jì)算歐拉函數(shù)?(n)=(p-1)×(q-1)；C、選取一個(gè)與?(n)互素的

7、奇數(shù)e，稱(chēng)e為公開(kāi)指數(shù)；D、根據(jù)e×d=1mod(?(n))，找出d；E、舍棄p和q（但絕不能泄露），公開(kāi)(n，e)，公鑰；F、保密(n，d)私鑰。離散數(shù)學(xué)（2）加密對(duì)于明文M，用公鑰(n，e)加密可得到密文C。C=Memod(n)§2.1　RSA公鑰密碼算法描述（3）解密對(duì)于密文C，用私鑰(n，d)解密可得到明文M。M=Cdmod(n)當(dāng)定義用私鑰(n，d)先進(jìn)行解密后，然后用公鑰(n，e)進(jìn)行加密，就是數(shù)字簽名。離散數(shù)學(xué)舉例1：選取p=3,q=5，則n=p＊q=15，?(n)=(p-1)(q-1)=8選取e=11（大于p和q的質(zhì)數(shù)）；由d×11=1mo

8、d8，計(jì)算出d=3，得到公開(kāi)密鑰：（n，e）=（15，11）私有密