第4章 非對稱密碼

非對稱密碼物聯(lián)網(wǎng)信息安全06檢查回顧新知學習合作探究過關測試五步教學法提綱考核點評1.DES是一種數(shù)據(jù)分組的加密算法，DES它將數(shù)據(jù)分為長度為（

）位的數(shù)據(jù)塊，其中一部分用作奇偶校驗，剩余部分作為密碼的長度

。56位64位112位128位ABCD提交單選題10分

五步教學法檢查回顧新知學習合作探究考核點評過關測試獨立完成單選題10分2.以下不屬于對稱密碼算法的是（

）。IDEAAESDESRSAABCD提交單選題10分

五步教學法檢查回顧新知學習合作探究考核點評過關測試獨立完成單選題10分知識目標1.了解非對稱加密算法概念；2.掌握RSA算法（重點）；3.了解Elgamal密碼系統(tǒng)和橢圓函數(shù)密碼算法。能力目標

了解密碼學，培養(yǎng)網(wǎng)絡安全意識，保護好自身安全。思政目標具備實現(xiàn)RSA算法的基本能力。第0章物理層

五步教學法檢查回顧新知學習合作探究考核點評過關測試問題引入

五步教學法檢查回顧新知學習合作探究考核點評過關測試網(wǎng)絡安全體系的五類服務訪問控制技術身份鑒別技術加密技術信息鑒別技術訪問控制服務對象認證服務保密性服務完整性服務防抵賴服務問題引入使用對稱加密：

密鑰分配密鑰管理簽名

五步教學法檢查回顧新知學習合作探究考核點評過關測試（投稿回答）對稱加密的優(yōu)缺點有哪些？對稱加密系統(tǒng)的特點：優(yōu)點：對稱較密算法使用起來簡單快捷，密鑰較短，且破譯困難。缺點：（1）密鑰難以安全傳送。（2）密鑰量太大，難以進行管理。（密鑰的分發(fā)和管理非常復雜、代價高昂，特別是針對大型網(wǎng)絡，當用戶群很大，分布很廣時，密鑰的分配和管理就成了大問題。）

（3）難以解決數(shù)字簽名驗證的問題。

五步教學法檢查回顧新知學習合作探究考核點評過關測試問題引入非對稱加密來解決這些問題！1.非對稱加密的基本概念

對稱加密系統(tǒng)的安全性主要是依賴于加密結構的混淆性、非線性等性質(zhì)。

而非對稱加密則依賴于計算復雜性理論。在非對稱加密中，由加密算法和公鑰計算出密文是“簡單的”，但是只知道密文和公鑰，計算出私鑰或者恢復出明文是“困難的”。

計算理論中概率多項式時間（ProbabilisticPolynomialTime，PPT）來表示一個函數(shù)是可計算的，否則稱之為是計算困難的。

五步教學法檢查回顧新知學習合作探究考核點評過關測試1.非對稱加密的基本概念

非對稱加密方案的安全強度隨著安全參數(shù)的增大而增大。這種安全其實是相對的。加密方案的安全限定了攻擊者的計算能力是安全參數(shù)的概率多項式倍，即PPT時間敵手。非對稱加密允許PPT時間敵手以一定的概率攻破加密方案，但是這個概率必須非常小，稱這種概率為可忽略的。

可忽略函數(shù)：如果對于每一個多項式p(?)，都存在一個N，使得對所有的n>N，都有f(n)<1/p(n)，則稱函數(shù)f是可忽略的。

五步教學法檢查回顧新知學習合作探究考核點評過關測試1.非對稱加密的基本概念非對稱加密：（公開密鑰系統(tǒng)）需要兩個密鑰：公開密鑰（Publickey）和私有密鑰（Privatekey）優(yōu)點：易于實現(xiàn)，使用靈活，密鑰較少。弱點：要取得較好的加密效果和強度，必須使用較長的密鑰。

五步教學法檢查回顧新知學習合作探究考核點評過關測試1.非對稱加密的基本概念困難問題：素因數(shù)分解問題：選定兩個長度為λ的素數(shù)p和q，計算n=pq。對于任意的PPT敵手，給定n，如果存在一個可忽略的函數(shù)negl(λ)，使得其計算出p′q′=n的概率不大于negl(λ)，則稱素因數(shù)分解問題是困難的。離散對數(shù)問題：對于一個階為q的循環(huán)群G，其中|q|=λ，g為G的一個生成元。隨機選取x∈

Z_q，設置?=g^x。對于任意的PPT敵手，給定(G,q,g,?)，如果存在一個可忽略的函數(shù)negl(λ)，使得其計算出x’，滿足g^x’=?的概率不大于negl(λ)，則稱離散對數(shù)問題在G群上是困難的。

五步教學法檢查回顧新知學習合作探究考核點評過關測試1.非對稱加密的基本概念困難問題：判定性Diffie-Hellman問題：對于一個階為q的循環(huán)群G，其中|q|=λ，g為G的一個生成元。隨機選取x,y,z∈

Z_q。對于任意的PPT敵手，給定(G,q,g,g^a,g^b,T)，如果存在一個可忽略的函數(shù)negl(λ)，使得其判斷出T=g^ab或T=g^z的概率不大于negl(λ)，則稱判斷性Diffie-Hellman（DDH）問題在G群上是困難的。計算性Diffie-Hellman問題：對于一個階為q的循環(huán)群G，其中|q|=λ，g為G的一個生成元。隨機選取x,y∈

Z_q。對于任意的PPT敵手，給定(G,q,g,g^a,g^b)，如果存在一個可忽略的函數(shù)negl(λ)，使得其計算出T=g^ab的概率不大于negl(λ)，則稱計算性Diffie-Hellman（CDH）問題在G群上是困難的。

五步教學法檢查回顧新知學習合作探究考核點評過關測試3.以下關于非對稱密鑰加密說法正確的是（

）。

加密方和解密方使用的是不同的算法加密密鑰和解密密鑰是不同的加密密鑰和解密密鑰是相同的加密密鑰和解密密鑰沒有任何關系ABCD提交單選題10分多選題10分

五步教學法檢查回顧新知學習合作探究考核點評過關測試單選題10分

五步教學法檢查回顧新知學習合作探究考核點評過關測試（隨機點名）單向陷門函數(shù)如果用作加密，應該如何設計呢？（哪些為公鑰，哪些為私鑰）1.非對稱加密的基本概念

五步教學法檢查回顧新知學習合作探究考核點評過關測試1.非對稱加密的基本概念

五步教學法檢查回顧新知學習合作探究考核點評過關測試1.非對稱加密的基本概念A容易計算產(chǎn)生一對密鑰B知道公開密鑰容易計算密文A接收后容易用私有密鑰解密

五步教學法檢查回顧新知學習合作探究考核點評過關測試1.非對稱加密的基本概念（彈幕回答）1.C知道公鑰要計算私有密鑰可行不？2.C知道公鑰要恢復明文可行不？網(wǎng)絡中的每一個終端系統(tǒng)都生成一對私鑰和公鑰，用于加密和對其所接收的消息進行解密每個終端系統(tǒng)都將其加密密鑰放入一個公開的注冊表或文件，通過訪問此注冊表或文件即可獲取公鑰用戶希望給另一個用戶發(fā)消息時，使用后者的公鑰進行加密正確的用戶接收到消息后，使用其私鑰進行解密，其他接收者都無法對此消息解密。

五步教學法檢查回顧新知學習合作探究考核點評過關測試1.非對稱加密的基本概念公鑰加密過程的魯棒性取決于對公共目錄的防護程度和算法的強度。已知密文，哪怕要計算出原始消息的部分信息都是極度困難的。要探測由同一對密鑰處理的消息信息流的簡單特征是非常困難的。加密算法的長度應當是不變的，即：加密算法的長度并不依賴于消息的長度。

五步教學法檢查回顧新知學習合作探究考核點評過關測試1.非對稱加密的基本概念2.RSA加密算法

1976年，Diffie和Hellman并未給出有效的加解密算法。

1978年，Rivest、Shamir和Adleman三人合作提出了第一個實用的公鑰密碼算法，即著名的RSA密碼算法。

素因數(shù)分解問題是困難的，然而如何基于素因數(shù)分解問題直接構造非對稱加密方案一直以來都還未實現(xiàn)。為此，RSA加密算法退而求其次，提出了與素因數(shù)分解問題相關的RSA假設，并在其基礎上構造了RSA加密算法。

五步教學法檢查回顧新知學習合作探究考核點評過關測試2.RSA加密算法RSA算法的理論基礎

較大的沒有明顯分解特征的大整數(shù)分解的算法時間復雜度;

指定一個大素數(shù)為私鑰，并選擇另外一個大素數(shù)，使之與私鑰的乘積為公鑰；

用素數(shù)判定定理選擇大素數(shù)。

五步教學法檢查回顧新知學習合作探究考核點評過關測試2.RSA加密算法

五步教學法檢查回顧新知學習合作探究考核點評過關測試2.RSA加密算法密鑰生成算法Gen(λ)：算法輸入安全參數(shù)λ，然后選取兩個長度為λ的大素數(shù)p,q，n=pq，?(n)=(p?1)(q?1)。隨機選取一個e，使得gcd(e,?(n))=1，并計算d，使得de

=

1

mod

?(n)。則RSA加密的公鑰pk=(n,e)，私鑰為sk=(n,d)。

五步教學法檢查回顧新知學習合作探究考核點評過關測試2.RSA加密算法

五步教學法檢查回顧新知學習合作探究考核點評過關測試2.RSA加密算法1.首先求出模數(shù)n=p*q=17*11=1872.求出(p-1)*(q-1)=16*10=160

3.e=7滿足與160互素4.找出d滿足e*d=1?mod?(p-1)*(q-1)且d<160，這里d=23因為23×7=161=10×160+1然后用n和e作為公鑰Pk={187,7}加密：c=m^e

mod

n=88^7mod187=11用n和d作為密鑰Sk={187,23}

解密：m=c^d

mod

n=11^23mod187=88

五步教學法檢查回顧新知學習合作探究考核點評過關測試ex:假設需要加密的明文信息為m=88，選擇：e=7，p=17，q=11，寫出其公鑰和私鑰，并且求出其密文和明文（加密和解密過程）。分組討論：假設需要加密的明文信息為m=85，選擇：e=7，p=11，q=13，說明使用RSA算法的加密和解密。

五步教學法檢查回顧新知學習合作探究考核點評過關測試2.RSA加密算法其他例子：P=43,q=59,n=43*59=2537,(p-1)(q-1)=2436e=13ed=1(mod2436)2436=187*13+5,13=2*5+3,5=3+2,3=2+11=3-2=3-(5-3)=…=2*13-5*(2436-187*13)=-5*2436+937*13d=937

五步教學法檢查回顧新知學習合作探究考核點評過關測試2.RSA加密算法M=134879475204m1=134,m2=879,m3=475,m4=204,c1=134^13mod2537=248,c2=879^13mod2537=……m1=248937mod2537=134……

五步教學法檢查回顧新知學習合作探究考核點評過關測試加密消息m時，首先將它分成比n小的數(shù)據(jù)分組（采用二進制數(shù)，選取小于n的2的最大次冪），也就是說，p和q為100位的素數(shù)，那么n將有200位，每個消息分組應小于200位長。如果需要加密固定長度的消息分組，可以在左邊填充一些0并確保該數(shù)比n小。2.1RSA加密算法的應用主要用于

數(shù)字簽名

密鑰交換

數(shù)據(jù)加密RSA算法用于數(shù)字簽名時，公鑰和私鑰的角色變換了。

五步教學法檢查回顧新知學習合作探究考核點評過關測試2.2RSA安全性分析80年代末，Rivest、Shamir和Adleman找到了一個129位數(shù)(428bits)的兩個素數(shù)的乘積，稱為RSA-129，設計了一套密鑰向世界挑戰(zhàn)。1994年3月，由Lenstra領導的一組數(shù)學家及世界各地600多個愛好者使用了1600臺機器，通過因特網(wǎng)協(xié)調(diào)各自計算機的工作,向這個129位數(shù)發(fā)動了進攻，花費了8個月的時間，他們就分解出了這個數(shù)的兩個素數(shù)因子，其中一個長64位，另一個長65位。

五步教學法檢查回顧新知學習合作探究考核點評過關測試2.2RSA安全性分析1999年，阿姆斯特丹的國家數(shù)學與計算機科學研究所（CWI）屬下的一個國際密碼研究小組宣布，他們在破譯RSA公鑰密碼系統(tǒng)使用的155位RSA密鑰的競賽中榮獲冠軍，他們使用了一臺克雷900-16超級計算機、300臺個人計算機以及專門設計的軟件。155位的RSA密鑰，雖然仍在保護著銀行、股票交易所和在線零售商每天價值幾十億美元的業(yè)務往來，雖然也不是普通人可以破譯的，但155位的密鑰長度也還是不富余的。

五步教學法檢查回顧新知學習合作探究考核點評過關測試（彈幕回答）破譯攻擊RSA的關鍵點在哪？2.2RSA安全性分析密碼分析者攻擊RSA體制的關鍵點在于如何分解n。若分解成功使n=pq，則可以算出φ(n)＝（p-1)(q-1)，然后由公開的e，解出秘密的d。（猜想：攻破RSA與分解n是多項式等價的。然而，這個猜想至今沒有給出可信的證明?。。。?/p>

五步教學法檢查回顧新知學習合作探究考核點評過關測試2.2RSA安全性分析強力攻擊數(shù)學攻擊定時攻擊迭代攻擊不動點問題

五步教學法檢查回顧新知學習合作探究考核點評過關測試2.2RSA安全性分析強力攻擊（窮舉法）：嘗試所有可能的私有密鑰數(shù)學分析攻擊：各種數(shù)學方法，等價于因子分解時間性攻擊：取決于解密算法的運算時間因子分解問題有三類方法：1、分解n，

n=pq,

(n)=(p-1)(q-1)d=e-1mod(n)2、直接確定(n)，

d=e-1mod(n)3、直接確定d

五步教學法檢查回顧新知學習合作探究考核點評過關測試2.2RSA安全性分析迭代攻擊序列c(0)=m,c(1)=E(c(0)),……,c(k+1)=E(c(k))滿足c(k+1)=c(1)最小的k≥1稱為m的迭代指數(shù)例m=0518,e=17,d=157,n=2773=47*59,φ(n)=2668=2*2*23*29c(0)=m=0518,c(1)=0518^17mod2773=1787c(2)=1787^17mod2773=0894c(3)=0894^17mod2773=1364c(4)=1364^17mod2773=0518c(5)=0518^17mod2773=1787

五步教學法檢查回顧新知學習合作探究考核點評過關測試2.2RSA安全性分析需要選擇足夠大的素數(shù)p,q(1075~10100)p,q不能太接近（p-1）和（q-1）應包含大素數(shù)因子gcd(p-1,q-1)應很小當e<n且d<n1/4時，d容易確定

五步教學法檢查回顧新知學習合作探究考核點評過關測試4.RSA加密體制是基于（

）。離散對數(shù)難題費馬最后定理大整數(shù)因子分解問題橢圓曲線問題ABCD提交單選題10分

五步教學法檢查回顧新知學習合作探究考核點評過關測試獨立完成單選題10分5.在RSA算法中，取P=3，q=11,e=3，則d等于多少（

）。3320147ABCD提交單選題10分

五步教學法檢查回顧新知學習合作探究考核點評過關測試獨立完成單選題10分3.Diffie-Hellman密鑰交換第一個公鑰方案Diffie&Hellman在1976發(fā)表note:nowknowthatJamesEllis(UKCESG)secretlyproposedtheconceptin1970公開交換一個秘密密鑰的使用方法大量使用在商業(yè)產(chǎn)品中

五步教學法檢查回顧新知學習合作探究考核點評過關測試3.Diffie-Hellman密鑰交換密鑰分發(fā)方案

不能用于交換任意消息可以建立共享密鑰(雙方共享)依賴于雙方的公、私鑰值基于有限域上的指數(shù)問題安全性是基于計算離散對數(shù)的困難性

五步教學法檢查回顧新知學習合作探究考核點評過關測試3.Diffie-Hellman密鑰交換兩個通信主體A&B,希望在公開信道上建立密鑰初始化:

選擇一個大素數(shù)p(200digits)一個生成元A選擇一個秘密鑰(secretkey(number)xA

<p)B選擇一個秘密鑰(secretkey(number)xB<pAandB計算他們的公開密鑰:

yA=axAmodpyB=axBmodpA,B分別公開yA，yB

五步教學法檢查回顧新知學習合作探究考核點評過關測試3.Diffie-Hellman密鑰交換兩個通信主體A&B,希望在公開信道上建立密鑰計算共享密鑰:KAB=axA.xBmodpKAB=yAxBmodp(whichBcancompute)KAB=yBxAmodp(whichAcancompute)KAB

可以用于對稱加密密鑰

五步教學法檢查回顧新知學習合作探究考核點評過關測試3.Diffie-Hellman密鑰交換舉例：Alice和Bob打算交換密鑰:達成協(xié)議，選取q=353，

α=3隨機選擇密鑰:A選xA=97,B選xB=233計算公鑰:yA=397mod353=40 (Alice)yB=3233mod353=248

(Bob)計算共享會話密鑰:KAB=yBxAmod353=24897=160 (Alice)KAB=yAxBmod353=40233=160 (Bob)

五步教學法檢查回顧新知學習合作探究考核點評過關測試分組討論：（投稿回答）選取素數(shù)p=97,及本根a=5Alice選取秘鑰xA=36，Bob選取秘鑰xB=58，計算Alice和Bob各自的公鑰及雙方的公享密鑰。

五步教學法檢查回顧新知學習合作探究考核點評過關測試3.Diffie-Hellman密鑰交換兩個主體每次可以選擇新的秘密密鑰(私鑰),并計算及交換新的公鑰可以抵抗被動攻擊,但不能抵抗主動攻擊每次可以給出新的密鑰為抵抗主動攻擊,需要其它新的協(xié)議也可以建立長期公鑰

五步教學法檢查回顧新知學習合作探究考核點評過關測試6.以下各種加密算法中屬于非對稱加密算法的是（

）。DES加密算法Caesar替代法Vigenere加密算法Diffie-Hellman加密算法ABCD提交單選題10分多選題10分

五步教學法檢查回顧新知學習合作探究考核點評過關測試單選題10分4.ElGamal加密方案Diffie-Hellmankeydistributionscheme的變形能夠用于安全交換密鑰publishedin1985byElGamal:

T.ElGamal,"APublicKeyCryptosystemandaSignatureSchemeBasedonDiscreteLogarithms",IEEETrans.InformationTheory,volIT-31(4),pp469-472,July1985.安全性是基于離散對數(shù)

五步教學法檢查回顧新知學習合作探究考核點評過關測試4.ElGamal加密方案--密鑰建立密鑰生成：選取一個大素數(shù)p及本原元gmodp選擇秘密秘鑰a0<g<p,1<a<p-1計算y=gamodp公鑰（g,p,y）

五步教學法檢查回顧新知學習合作探究考核點評過關測試4.ElGamal加密方案--加密為加密M

發(fā)送者選擇隨機數(shù)k,0<=k<=p-1計算消息密鑰key:Key=ykmodp=(ga)kmodp

計算密文對:C={C1,C2}C1=gkmodpC2=m×keymodp=m×(ga)kmodp發(fā)送到接收者k需要永久保密

五步教學法檢查回顧新知學習合作探究考核點評過關測試指數(shù)積分法（IndexCalculus）4.ElGamal加密方案--解密首先計算消息密鑰key

Key=C1amodp=gk.amodp計算明文:M=C2.Key-1modp=(m×(ga)k)×g-k.amodp=m

五步教學法檢查回顧新知學習合作探究考核點評過關測試4.ElGamal加密方案--舉例選擇p=97及本原根g=5Bob選擇秘密鑰a=58&計算并發(fā)布公鑰yB=558=44mod97Alice要加密M=3toBob首先得到Bob的公開密鑰yB=44選擇隨機k=36計算:

Key=4436=75mod97計算密文對:C1=536=50mod97C2=75×3mod97=31mod97發(fā)送{50,31}toBobBob恢復messagekeyKey=5058=75mod97Bob計算Key-1=22mod97Bob恢復明文M=31×22=3mod97

五步教學法檢查回顧新知學習合作探究考核點評過關測試7.若Alice想向Bob分發(fā)一個會話密鑰，采用ElGamal公鑰加密算法,那么Alice應該選用的密鑰是（

）。Alice的公鑰Alice的私鑰Bob的公鑰Bob的私鑰ABCD提交

五步教學法檢查回顧新知學習合作探究考核點評過關測試單選題10分5.橢圓函數(shù)密碼算法1985年，N.Koblitz和V.Miller分別獨立提出了橢圓曲線密碼體制(ECC)，其依據(jù)就是定義在橢圓曲線點群上的離散對數(shù)問題的難解性。隨后，Koyama等在Crypto91、Demytko在Eurocrypt93中分別提出了新的基于橢圓曲線的單項限門函數(shù)，生成了類似于RSA的公鑰密碼算法。

五步教學法檢查回顧新知學習合作探究考核點評過關測試5.橢圓函數(shù)密碼算法

密碼編碼學上我們關心的是一種受限形式的橢圓曲線——定義在有限域Fp上，滿足如下方程的元素加上無窮遠點θ：y2≡x3+ax+b(modp)

其中非負整數(shù)a,b滿足：4a3+27b2(modp)≠0

五步教學法檢查回顧新知學習合作探究考核點評過關測試5.1橢圓曲線上的D-H密鑰交換原始形式：本原元g,大素數(shù)p大家共享A：選取a（保密），把ga傳送給BB：選取b（保密），把gb傳送給AA與B分別計算(gb)a=(ga)b=gab，gab為共享密鑰橢圓曲線上：階數(shù)較大的點P,曲線E共享A：選取a（保密），把aP傳送給BB：選取b（保密），把bP傳送給AA與B分別計算abP為共享密鑰

五步教學法檢查回顧新知學習合作探究考核點評過關測試5.2橢圓曲線密碼的安全性ECC的安全性依賴于給定P和kP計算出k的難度，這被稱為橢圓曲線上的對數(shù)問題。

橢圓函數(shù)密碼算法運算速度大大加快，為達到與RSA密碼算法同等的安全性，它的密鑰長度可以縮短到RSA密鑰的六分之一。

橢圓函數(shù)密碼成為密碼學發(fā)展的新方向。

五步教學法檢查回顧新知學習合作探究考核點評過關測試5.2橢圓曲線密碼的安全性

五步教學法檢查回顧新知學習合作探究考核點評過關測試ECC密鑰長度RSA密鑰長計算機解密代價（年）按每秒100萬條指令計16010241E+1232051201E+36600210001E+7812001200001E+1688.在現(xiàn)有的計算能力條件下，對于橢圓曲線密碼算法(ECC)，被認為是安全的最小密鑰長度是（

）。128位160位512位1024位ABCD提交

五步教學法檢查回顧新知學習合作探究考核點評過關測試單選題10分加密算法在物聯(lián)網(wǎng)中的應用

滿足概率加密的非對稱加密方案中會存在密文擴張問題，且往往涉及到較為復雜的計算，如指數(shù)運算、模運算等。因此在物聯(lián)網(wǎng)中單獨使用非對稱加密，會受到硬件、通訊環(huán)境等限制。為了平衡加密效率、安全性和便捷性，混合加密方法被廣泛應用在各類系統(tǒng)中。設對稱加密方案的加密算法和解密算法為SE-Enc和SE-Dec，非對稱加密方案的算法分別為ASE-Gen、ASE-Enc和ASE-Dec，混合加密的過程如下：（1）Gen(λ)：混合加密的公私鑰對<pk,sk>由ASE-Gen(λ)產(chǎn)生。（2）Enc(pk,m)：算法首先隨機選取一個對稱加密密鑰k，運行ASE-Enc(pk,k)產(chǎn)生部分密文c_1。然后運行SE-Enc(k,m)產(chǎn)生c_2。最后輸出密文c=(c_1,c_2)。（3）Dec(sk,c)：算法將密文分為兩部分(c_1,c_2)，然后運行ASE-Dec(sk,c_1)解密得到對稱密鑰k，再使用對稱密鑰運行SE-Dec(k,c_2)得到明文。

五步教學法檢查回顧新知學習合作探究考核點評過關測試6.混合密碼系統(tǒng)（投稿回答）對稱密碼系統(tǒng)的優(yōu)點、缺點；非對稱密碼系統(tǒng)的優(yōu)點、缺點。

五步教學