非對稱密碼體制第四章網(wǎng)絡(luò)09課件

第四章公開密鑰密碼體制一.基本要求與基本知識點（1）掌握公鑰密碼體制的基本概念；（2）掌握RSA的密鑰產(chǎn)生、加密及解密過程；（3）理解ELGamal體制的密鑰產(chǎn)生、加密及解密過程；（4）理解背包體制的密鑰產(chǎn)生、加密及解密過程。二.教學重點與難點（1）公鑰密碼體制的基本概念；（2）RSA體制；（3）ELGamal體制；（4）背包體制。14.1公鑰密碼體制的基本概念公鑰密碼體制是為了解決對稱密碼體制中最難解決的兩個問題而提出的。一是對稱密碼技術(shù)的密鑰分配問題。在對稱密碼體制中，加密密鑰和解密密鑰是相同的，任何人只要獲得加密密鑰，才能對密文進行解密，獲得明文。利用對稱密碼體制進行保密通信時，密鑰不能公開，要通過安全信道傳送給合法的接收者。若網(wǎng)絡(luò)中有n個人要互相進行保密通信的話，每一個人就須保存另外n-1的密鑰，因而網(wǎng)絡(luò)中就會有n(n-1)／2個密鑰，且為安全起見，密鑰需要經(jīng)常更換。因此當n較大時，大量密碼的產(chǎn)生、分發(fā)和更換十分困難，即密鑰管理變得十分復雜。二是對稱密碼不能實現(xiàn)數(shù)字簽名，無法證實信息的真實性。24.1公鑰密碼體制的基本概念Diffie和Hellmna于1976年在《密碼學的新方向》中首次提出了公鑰密碼的觀點，即為每個用戶分配兩個相互匹配又相互獨立的密鑰，其中：一個密鑰被公開，稱為公開密鑰（公鑰），用于加密，另一個密鑰被保密，稱為私有密鑰（私鑰），用于解密。 所有用戶的公鑰均登記在類似電話號碼簿的密鑰本上。當要給用戶A發(fā)送加密信息時，需要在密碼本上查找A用戶的公鑰，然后加密信息，并發(fā)給用戶A。用戶A接收到密文之后，用自己的私鑰進行解密即可得到明文。1977年由Rivest（李維斯特）、Shamir（沙米爾）和Adleman（埃德曼）共同提出了第一個公鑰密碼算法（即RSA密碼體制），是公鑰密碼中最優(yōu)秀的加密算法，被譽為密碼學發(fā)展史上的里程碑之一。此后，人們基于不同的計算問題提出了大量的公鑰密碼算法。34.1.2加密模型和認證模型一個公鑰密碼體制由6個部分構(gòu)成：明文，加密算法，公鑰和私鑰，密文，解密算法?？梢詷?gòu)成兩種基本的模型：加密模型和認證模型。1、加密模型---保密性在加密模型中，發(fā)送方用接收方的公鑰作為加密密鑰，接收方用自己的私鑰作解密密鑰，由于該私鑰只有接收方擁有，因此即只有接收者才能解密密文得到明文。54.1.2加密模型和認證模型如圖4-1所示，假設(shè)用戶A向用戶B發(fā)送消息M。在發(fā)送方，用戶A首先用用戶B的公鑰PUB加密消息M，得到密文：；在接收方，用戶B用自己的私鑰PRB解密密文C，得到明文：。由于只有B知道PRB，所以其他人不能解密C。6圖4-1公鑰加密模型

7圖4-2公鑰認證模型

94.2RSA密碼體制RSA密碼體制是1977年由Rivest、Shamir、Adleman提出的非常著名的公鑰密碼算法。RSA算法的安全性基于：求兩個大素數(shù)的乘積是容易的，但分解兩個大素數(shù)的乘積，求出其素因子則是困難的，它屬于NP完全類問題，至今沒有有效的算法。RSA算法是一種分組密碼，明文和密文是0到n-1之間的整數(shù)，通常n的大小為1024位二進制數(shù)或309位十進制數(shù)。104.2.1RSA算法1、密鑰的產(chǎn)生（1）隨機選擇兩個大素數(shù)（如100位十進制數(shù)）p和q，令n=p×q；（2）計算歐拉函數(shù)（見定理2.1.1） (n)=n(1-1/p)(1-1/q)=(p-1)(q-1)；（3）選擇e使得1<e<(n)，且gcd(e,(n))=1；（4）計算d e?d≡1mod(n)，且0≤d≤n（5）公開公鑰：PU={e,n}；（6）保存私鑰：PR={d,p,q}。11圖4-3RSA算法13【例4-1】選擇素數(shù)：p=47和q=71，求出RSA算法的公鑰和私鑰。【解】：（1）計算：n=pq=47×71=3337，

(n)=(p-1)(q-1)=46×70=3220。（2）選擇e：使gcd(e,3220)=1，選取e=79；（3）求解d：de≡1mod3220， 即79d≡1mod3220輾轉(zhuǎn)除法： 3220=40×79+60 79=1×60+19 60=3×19+3 19=6×3+1 14回代： 1=19-6×3=19-6×（60-3×19）=19×19-6×60 =19×(79-1×60)-6×60=19×79-25×60 =19×79-25×(3220-40×79)=19×79-25×(3220-40×79) =1019×79-25×3220兩邊同時對模3220進行求余運算得 1019×79≡1mod3220于是d=1019（4）公開公鑰PU={79，3337} 保存私鑰PR={1019，47，71}；15RSA密碼體制的特點（1）運算速度慢 由于進行的都是大數(shù)計算，使得RSA最快的情況也比DES慢上100倍，一般來說適用于少量數(shù)據(jù)的加密。（2）產(chǎn)生密鑰煩瑣 產(chǎn)生密鑰很麻煩，受到素數(shù)產(chǎn)生技術(shù)的限制。174.2.2RSA算法的安全性

RSA體制的安全性是基于大數(shù)的因子分解問題，大數(shù)的因子分解在數(shù)學上是一個難解問題，即無法從公鑰參數(shù)n中計算出素數(shù)因子（大于100個十進制位）p和q，于是無法計算出(n)=(p-1)(q-1)，也就無法計算出私鑰d，從而保證非法者不能對密文進行解密。RSA的安全性依賴于大數(shù)分解困難，即從一個密鑰和密文推斷出明文的難度等同于分解兩個大素數(shù)的積。顯然，分解n是最常遇到的攻擊方法。在算法中要求p和q均大于100位十進制數(shù)，這樣的話n至少200位十進制數(shù)，目前人們已能分解140多位的十進制數(shù)的大素數(shù)。最新記錄是129位十進制數(shù)的因數(shù)分解，在網(wǎng)絡(luò)通過分布計算被成功分解。估計對200位十進制數(shù)的因數(shù)分解，在億次計算機上也要進行55萬年。184.3EIGamal密碼體制該體制是1985年由EIGamal提出的一個著名的公鑰密碼算法。該算法既能用于數(shù)據(jù)加密也能用于數(shù)字簽名，其安全性依賴于離散對數(shù)這一難題?！倦x散對數(shù)問題：設(shè)g，x，p是正整數(shù)。已知g，x和p，可以容易地求出y，使得： y≡gx(modp)反之，如果已知y，g和p，求x，這就是離散對數(shù)問題，屬NP完全類問題，是難解的。】1.密鑰產(chǎn)生（1）任選一個大素數(shù)p（300位十進制數(shù)），使得p-1有大素因子，g是模p的一個本原根（即g是{0，1，2，…，p-1}中與p互素的數(shù)），公開p與g；（2）任選一私鑰x，x∈[0,p-1]；（3）計算y≡gx(modp)；（4）公開公鑰：y；（5）保密私鑰：x；194.3EIGamal密碼體制 與RSA方法比較，ElGamal方法具有以下優(yōu)點：（1）系統(tǒng)不需要保存秘密參數(shù)，所有的系統(tǒng)參數(shù)均可公開；（2）密文依賴于加密過程所選擇的隨機數(shù)r，加密相同的明文可能會產(chǎn)生不同的密文；（3）ElGamal方法的計算復雜度比RSA方法要大。21【例4-2】

假設(shè)Alice想要加密消息m=1299后傳送給Bob。（1）密鑰產(chǎn)生Alice任選一個大素數(shù)p為2579，g是模p的一個本原根，取g為2，公開參數(shù)p，g。任選私鑰x為765， 計算公鑰y≡gx(modp)≡2765(mod2579)≡949(mod2579)，公開：PU=949，保密：PR=765。22（2）加密Alice在[0,p-1]=[0,2578]內(nèi)任選r為853，計算： c1≡gr(modp)≡2853(mod2579)≡435(mod2579) c2≡m?yr(modp)≡1299*949853(mod2579)≡2396(mod2579)Alice將（c1，c2）=（435，2396）作為密文發(fā)給Bob。（3）解密Bob計算： m≡c2?w(modp)≡c2*(c1x)-1(modp) ≡(c2*c1p-1-x)(modp)≡(2396*4352579-1-765)(mod2579)≡(2396*4351813)(mod2579)≡1299(mod2579)234.4背包密碼體制定理4.3.1由超遞增序列a1，a2，…，an及k確定的超遞增背包問題是容易求解的。（即對于背包問題： 其中已知超遞增序列a1，a2，…，an及k，容易求出X=(x1,x2,……,xn)）254.4背包密碼體制1.密鑰產(chǎn)生（1）隨機選取一個超遞增序列（e1，e2，…，en），作為用戶的私鑰加以保存，記為PR；（2）選取一對大的互素的數(shù)w和N，把序列（e1，e2，…，en）變換為： T(ei)≡w?ei(modN)即做MH變換，將一個超遞增序列轉(zhuǎn)換為一個普通序列后作為公鑰，記為PU；（3）將公鑰PU=（T(e1)，T(e2)，…，T(en)）加以公布。264.4背包密碼體制【以下說明如何按超遞增序列（e1，e2，…，en）從c’中還原mi？ 因為c=E(m)=m1T(e1)+m2T(e2)+…+nT(en)=,而T(ei)≡w?ei(modN) 所以c≡,c?w-1≡

于是c’≡ 由已知w和N互素，則有w?w-1≡1(modN)， 因此c’≡ 其中，已知c’和ei，求mi，即按超遞增序列（e1，e2，…，en）從c’中還原mi，就變成求解特殊的背包問題，是容易求解的，因此解密是容易進行的?！?94.4背包密碼體制關(guān)于背包密碼體制的安全問題說明如下。由于 c=

是個普通背包問題，由公開信息c和T(ei)求出明文是難解問題，所以破譯是困難的。而解密時，是按超遞增序列（e1，e2，…，en）從c’中還原mi，即由私鑰ei和c’求解超遞增背包 問題c’≡，這是個易解問題，因此解密容易進行的。Merkle和Hellman的背包密碼體制提出后，懸賞以求破譯者，兩年后被RSA的發(fā)明者之一沙米爾攻破。盡管二人又做了改進，但最終出現(xiàn)了一種新的破譯方法，徹底結(jié)束了背包公鑰密碼體制的歷史使命。304.5本章總結(jié)（1）公開密鑰密碼體制的基本概念；（2）RSA的密鑰產(chǎn)生、加密及解密過程；（3）背包體制的密鑰產(chǎn)生、加密及解密過程；（4）ELGamal體制的密鑰產(chǎn)生、加密及解密過程；課堂練習： 如果選擇素數(shù)p=101和q=113，選取e=3533，計算RSA的公鑰和私鑰。314.6思考及作業(yè)題1、在使用RSA公鑰體制中，已截獲發(fā)給某用戶的密文為c=10，該用戶的公鑰為e=5，n=35，那么明文是多少？為