信息安全導(dǎo)論（以問題為導(dǎo)向） 課件 04 公開密鑰密碼

1公開密鑰密碼

PublicKeyCryptography教學(xué)視頻、國家級一流在線課程鏈接：/course/FUDAN-12063578112內(nèi)容提要對稱密鑰密碼的密鑰交換問題公鑰密碼模型提出設(shè)計公鑰密碼的基本要求數(shù)字簽名RSA算法公鑰密碼的特征總結(jié)Diffie-Hellman密鑰交換算法3內(nèi)容提要1、對稱密鑰密碼的密鑰交換問題4回顧：對稱密鑰密碼對稱的,單密鑰,秘密密鑰,傳統(tǒng)密碼:發(fā)送方加密和接收方解密使用同一個的密鑰該密鑰需要事先由發(fā)送方和接收方實現(xiàn)共享，是發(fā)送方和接收方共同的秘密如果密鑰泄露，則不安全（無法提供保密性服務(wù)）對稱：通信雙方是對等的5回顧：對稱密鑰密碼模型雙方共享的秘密：KeyAliceBob發(fā)送方接收方安全的信道

加密容易實現(xiàn)，但密鑰交換是個問題6內(nèi)容提要2、公鑰密碼模型提出7BobAlice每個人有兩個密鑰公鑰，Publickey——公開私鑰，Privatekey——保密公開密鑰(非對稱)密碼模型8BobAliceBob’sPublickeyAlice’sPublickeyBob’sPrivatekeyAlice’sPrivatekey非對稱密碼模型公開9BobAliceBob’sPublickeyAlice’sPublickeyBob’sPrivatekeyAlice’sPrivatekey非對稱密碼模型公開保密保密10用非對稱密碼實現(xiàn)“保密通信”BobAlice提供“保密通信”安全服務(wù)攻擊者11兩種密碼體制據(jù)使用的密鑰數(shù)量對稱的,單密鑰,秘密密鑰,傳統(tǒng)密碼技術(shù):發(fā)送方和接收方使用同一個的密鑰非對稱的,雙密鑰,公鑰密碼技術(shù):發(fā)送方和接收方使用不同的密鑰加密密鑰和解密密鑰分割開來,且無法由一個推出另一個,使得不僅可以公開密碼算法,而且加密密鑰也可公開（公告牌、號碼簿）12公開密鑰密碼人類文明史3000年以來，密碼技術(shù)一個新的篇章兩個密鑰–apublic&aprivatekey非對稱：通信雙方的地位不平等往往應(yīng)用數(shù)論的一些函數(shù)精心構(gòu)造補充而非取代對稱密鑰密碼技術(shù)缺點：公鑰密碼的主要弱點是加密和解密速度慢13歷史1976年，Diffie和Hellman在論文“密碼學(xué)新方向（NewDirectioninCryptography）”中首次提出了公開密鑰密碼體制的思想；Diffie和Hellman提出了第一個基于公開密鑰思想的密碼算法，稱為DH算法，此算法可以用于實現(xiàn)密鑰交換。1977年，Rivest、Shamir和Adleman三個人實現(xiàn)了公開密鑰密碼體制，現(xiàn)在稱為RSA算法，它是第一個既能用于密鑰交換、也能用于數(shù)據(jù)加密和數(shù)字簽名的算法。14內(nèi)容提要3、設(shè)計公鑰密碼的基本要求一個公開密鑰系統(tǒng)由六要素組成：明文公開密鑰（記作：PU或KU）私有密鑰（記作：KR或PR）加密算法密文解密算法公開密鑰加密系統(tǒng)參與方B容易通過計算產(chǎn)生出一對密鑰（公開密鑰KUb

，私有密鑰KRb

）發(fā)送方A很容易計算產(chǎn)生密文接收方B通過計算解密密文敵對方即使知道公開密鑰KUb

，要確定私有密鑰KRb

在計算上是不可行的敵對方即使知道公開密鑰KUb

和密文C，要確定明文M在計算上是不可行的密鑰對互相之間可以交換使用公開密鑰算法的基本要求公鑰密碼構(gòu)建在計算復(fù)雜性理論基礎(chǔ)之上17往往讓敵方求解目前仍未找到多項式時間算法的NP完全問題18內(nèi)容提要4、數(shù)字簽名19密鑰對互相之間可以交換使用：20數(shù)字簽名BobAlice提供“數(shù)字簽名”安全服務(wù)21公鑰密碼能提供的安全服務(wù)保密通信本課程最初提出的安全需求，先前講解的密碼方案主要用于解決這個問題密鑰交換數(shù)字簽名能夠檢驗加密數(shù)據(jù)的來源（認(rèn)證）能夠抗抵賴22公鑰密碼原理總結(jié)公開密鑰密碼技術(shù)涉及兩個密鑰:公鑰：

公開，任何人可以知道,用于加密明文，驗證簽名私鑰,僅有接收者/擁有者自己知道，用于解密，簽名非對稱的含義：密鑰的不對稱：加／解密的密鑰不同用于加密的不能解密，用于解密的不能加密23本講內(nèi)容5、RSA算法5.1密鑰生成1977年由MIT的Rivest,Shamir和Adleman

三人提出是一個分組加密方法目前被最廣泛地采用理論基礎(chǔ)是數(shù)論中的下述論斷:要求得兩個大素數(shù)的乘積是容易的,但要分解一個合數(shù)為兩個大素數(shù)的乘積,則在計算上幾乎是不可能的。RSA算法25RSA密鑰生成每個用戶執(zhí)行：（1）生成兩個大素數(shù)p和q。（2）計算這兩個素數(shù)的乘積n=p×q。（3）計算小于n并且與n互質(zhì)的整數(shù)的個數(shù)，即歐拉函數(shù)φ(n)=(p-1)(q-1)。（4）選擇一個隨機數(shù)e滿足1<e<φ(n)，并且e和φ(n)互質(zhì)，即gcd(e,φ(n))=1。（5）解方程e·d

≡1modφ(n)，求出d26RSA密鑰（6）保密d，p和q（銷毀），公開n和e。公鑰公開:PU={e,n}私鑰保密:PR={d,n}密鑰生成的計算量如何得到足夠大的隨機素數(shù)如何求解方程e·d

≡1modφ(n)27如何得到足夠大的隨機素數(shù)實際應(yīng)用所采用的方法是：首先，產(chǎn)生一個足夠大的隨機數(shù)，然后，通過采用一個概率多項式時間算法來檢測該隨機數(shù)是否為素數(shù)（即是否具有素性）。常用的兩個素性測試算法：Solovay-Strassen素性測試；Miller-Rabin素性測試。索洛維-斯特拉森求解方程e·d

≡1modφ(n)擴展的歐幾里德算法（輾轉(zhuǎn)相除法）29當(dāng)e＝1001，?(n)＝3837時

方程為x*1001=1(mod3837)

求解過程：

3837=3*1001+834

1001=1*834+167

834=4*167+166

167=166+1

所以

1=167-166

=167-(834-4*167)

=5*167-834

=5*(1001-834)-834

=5*1001-6*834

=5*1001-6*(3837-3*1001)

=23*1001-6*383730本講內(nèi)容5、RSA算法5.2加解密算法31RSA使用公鑰公開:PU={e,n}私鑰保密:PR={d,n}加密一個報文M，發(fā)送方:獲取接收方的公鑰

PU={e,n}

計算:C=Memodn,where0≤M<n解密

密文C，接收方:用自己的私鑰

PR={d,n}

計算:M=Cdmodn

32RSA例子–密鑰挑選質(zhì)數(shù):p=17&q=11計算

n=?33RSA例子–密鑰挑選質(zhì)數(shù):p=17&q=11計算

n=pq=17x11=187計算?(n)=(p–1)(q-1)=16x10=160選擇e:

gcd(e,160)=1;不妨選e=7求解d:

ed=1mod160

且d

<160

d=23，顯然

23x7=161=10x160+1PublickeyPU={7,187}PrivatekeyPR={23,187}34RSA例子–加密/解密RSA加密/解密:M=88(注意:

88<187)加密:C=887mod187=11

解密:M=1123mod187=88

模指數(shù)運算簡化35在RSA密碼體制中，加密和解密運算都是模指數(shù)運算，即C=Memodn可以通過e-1次模乘來實現(xiàn)計算，然而，如果e非常大，其效率會很低下平方-乘算法可以把計算所需的模乘的次數(shù)降低1123mod187=[(111mod187)*(112mod187)*(114mod187)*(118mod187)*(118mod187)]mod187111mod187=11112mod187=121114mod187=14641mod187=55118mod187=214358881mod187=331123mod187=(11*121*55*33*33)mod187=79720245mod187=88求模指數(shù)實例37RSA注意RSA加密時，明文以分組的方式加密：每一個分組的比特數(shù)應(yīng)該小于log2n比特，即：M<n選取的素數(shù)p和q要足夠大，從而乘積n足夠大，在事先不知道p和q的情況下分解n是計算上不可行的。38本講內(nèi)容5、RSA算法5.3

RSA安全性討論39RSA算法的安全性在理論上,RSA的安全性取決于模n分解的困難性。若n被分解成功,則RSA被攻破。目前最快的分解因子算法其時間復(fù)雜性為并沒有證明分解大整數(shù)就是NP問題,并不能排除存在尚未發(fā)現(xiàn)的多項式時間算法。也沒有證明對RSA的攻擊的難度與分解n等價因此對RSA的攻擊的困難程度不比大數(shù)分解難目前，RSA的一些變種算法已被證明等價于大數(shù)分解。不管怎樣，分解n是最顯然的攻擊方法?，F(xiàn)在人們已能分解多個十進(jìn)制位的大素數(shù)，因此，模數(shù)n必須選大一些。40RSA因數(shù)分解挑戰(zhàn)分解挑戰(zhàn)獎金于2007終止ChallengeNumber Prize($US) StatusRSA-576(174Digits) $10,000 Factored(Dec2003)RSA-640(193Digits) $20,000 Factored(Nov2005)RSA-704(212Digits) $30,000 Factored(July2012)RSA-768(232Digits) $50,000 Factored(Dec2009)RSA-896(270Digits) $75,000 NotFactoredRSA-1024(309Digits) $100,000 NotFactoredRSA-1536(463Digits) $150,000 NotFactoredRSA-2048(617Digits) $200,000 NotFactoredRSA-704 DecimalDigits:212

7403756347956171282804679609742957314259318888923128908493623263897276503402826627689199641962511784399589433050212758537011896809828673317327310893090055250511687706329907239638078671008609696253793465056379635941RSA-232(768bits)hasnotbeenfactoredsofar.100988139787192354690956489430946858281823382195557395514112051620583102133852854537436610975715436366491338008491706516992170152473329438927028023438096090980497644054071120196541074755382494867277137407501157718230539834060616207942RSA算法的速度由于都是大數(shù)計算，RSA最快的情況也比DES慢許多倍，無論是軟件還是硬件實現(xiàn)。速度一直是RSA的缺陷。一般來說只用于少量數(shù)據(jù)加密。RSA是被研究得最廣泛的公鑰算法，提出到現(xiàn)在已近二十年，經(jīng)歷了各種攻擊的考驗，逐漸為人們接受，普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一43本講內(nèi)容6、公鑰密碼的特征總結(jié)公開密鑰算法設(shè)計需要有以下基本要求：加密與解密由不同的密鑰完成；知道加密算法，從加密密鑰得到解密密鑰在計算上是不可行的；兩個密鑰中任何一個都可以作為加密而另一個用作解密。公鑰密碼的特征公鑰密碼算法基礎(chǔ)單向函數(shù)

對于一個函數(shù)，如果對于其定義域上的任意x，都容易計算，同時，對于其值域中幾乎所有的取值

y

，計算其逆函數(shù)都是不可行的，則函數(shù)被稱為單向函數(shù)。

可以提供單向函數(shù)的三大數(shù)學(xué)難題大整數(shù)分解問題（簡稱IFP）；離散對數(shù)問題（簡稱DLP）；橢圓曲線離散對數(shù)問題（簡稱ECDLP）。

對于一個單向函數(shù)，如果其逆函數(shù)在已知某些輔助信息的情況下容易求解得出，則稱該單向函數(shù)為單向陷門函數(shù)。構(gòu)造公鑰密碼系統(tǒng)的關(guān)鍵是如何在求解某個單向函數(shù)的逆函數(shù)的NP完全問題中設(shè)置合理的“陷門”。單向陷門函數(shù)