資源描述：
《第8講 公鑰密碼學(xué)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、第8講公鑰密碼學(xué)1公鑰密碼學(xué)公鑰密碼學(xué)思想RSA算法公鑰的應(yīng)用2公鑰密碼學(xué)的發(fā)展是整個密碼學(xué)發(fā)展歷史中最偉大的一次革命。公鑰密碼體制公鑰算法基于數(shù)學(xué)函數(shù)而不是基于替換和置換它使用兩個獨立的密鑰，在消息的保密性、密鑰分配和認(rèn)證領(lǐng)域有重要意義。3公鑰密碼比傳統(tǒng)密碼更安全兩個誤解公鑰密碼是一種通用的方法，所以傳統(tǒng)密碼已經(jīng)過時。4密鑰分配問題：如果密鑰被偷，設(shè)計再好的密碼體制都沒有用傳統(tǒng)密碼中的兩個問題數(shù)字簽名問題：能否設(shè)計一種方法確保數(shù)字簽名出自某個特定的人，并且各方無異議？51976年Diffie和Hellman針對上述問題提出了一種方法，它是密碼學(xué)的一次革命密碼學(xué)革命6公鑰
2、密碼體制介紹7僅根據(jù)密碼算法和加密密鑰來確定解密密鑰在計算上是不可行的。公鑰密碼體制特點兩個密鑰中的任何一個可以用來加密，另一個用來解密。有6個組成部分：明文、加密算法、公鑰、私鑰、密文、解密算法8用公鑰進(jìn)行加密2Alice產(chǎn)生一對密鑰，用于加密和解密3Alice將一個密鑰公開，另一個密鑰私有BobAlice1Bob要發(fā)送消息給Alice4Bob用Alice的公鑰對消息加密，發(fā)送給Alice。只有Alice能解密9公鑰進(jìn)行加密B的公鑰KUbB的私鑰KRb待發(fā)送的明文XA要發(fā)消息給BY=EKUb(X)X=DKRb(Y)破譯者10用公鑰進(jìn)行認(rèn)證BobAlice11用公鑰進(jìn)行認(rèn)
3、證A用自己的私鑰進(jìn)行加密Y=EKRa(X)B用A的公鑰鑰進(jìn)行解密認(rèn)證X=DKUa(Y)12用公鑰進(jìn)行認(rèn)證:問題？？問題1需要對整條消息加密，占用大量存儲空間解決的方法：僅對消息的認(rèn)證符加密問題2不能提供保密性如何解決？？13公鑰體制：保密和認(rèn)證14公鑰密碼體制的應(yīng)用1加密/解密2數(shù)字簽名3密鑰交換算法RSA橢圓曲線Diffie-HellmanDSS是是是是是是否否是否是否15對公鑰密碼體制的要求：1B產(chǎn)生一對密鑰（KUb，KRb）在計算上是容易的2發(fā)送方A加密消息C=EKUb(M)在計算上是容易的3接收方B對密文解密M=DKRb(C)在計算上是容易的4攻擊者從KUb計算出
4、KRb在計算上不可行的5攻擊者從KUb和C計算出M在計算上不可行的6附加條件（并非所有都滿足）：加密解密順序可交換：M=EKUb(DKRb(M))=DKUb(EKRb(M))16公鑰密碼學(xué)的研究情況與計算復(fù)雜性理論密切相關(guān)計算復(fù)雜性理論可以提供指導(dǎo)但是需求不盡相同計算復(fù)雜性通常針對一個孤立的問題進(jìn)行研究而公鑰密碼學(xué)往往需要考慮一些相關(guān)的問題 比如，密碼分析還需要考慮已知明文、選擇明文等相關(guān)的情形討論的情形不同計算復(fù)雜性考慮最壞的情形而對于公鑰密碼學(xué)則是不夠的一個困難問題必然會導(dǎo)致一個保密性很好的密碼系統(tǒng)嗎？不一定，還需要有好的構(gòu)造17背包(knapsack)問題0-1背包
5、問題：給定一個正整數(shù)S和一個背包向量A=(a1,…,an)，其中ai是正整數(shù)，求滿足方程S=∑aixi的二進(jìn)制向量X=(x1,…,xn)。這是一個NP完全問題，解決這個問題所需要的時間與n呈指數(shù)增長背包問題用于公鑰密碼學(xué)做法方法：明文為X，S為密文奧妙在于有兩類背包，一類可以在線性時間內(nèi)求解，另一類則不能把易解的背包問題修改成難解的背包問題公開密鑰使用難解的背包問題私鑰使用易解的背包問題18易解的背包問題——超遞增背包滿足下列條件的背包ai>∑aj(j=1,…,i-1)這樣的背包也被稱為簡單背包求解從最大的ai開始，如果S大于這個數(shù)，則減去ai,記xi為1，否則記xi為0
6、如此下去，直到最小的ai例如背包序列{2,3,6,13,27,52}求解70的背包結(jié)果為{2,3,13,52}所以，密文70對應(yīng)的明文為11010119轉(zhuǎn)換背包簡單背包用作私鑰如何產(chǎn)生相應(yīng)的公鑰——轉(zhuǎn)換做法：選擇一個整數(shù)m>∑ai(i=1,…,n)然后選擇一個與m互素的整數(shù)w，然后ai’=wai(modm)(i=1,…,n)這里的ai’是偽隨機分布的這樣得到的背包是非超遞增背包20基于背包問題的公鑰密碼系統(tǒng) ——MH公鑰算法加密將明文分為長度為n的塊X=(x1,…,xn)然后用公鑰A’=(a1’,…,an’)，將明文變?yōu)槊芪腟 S=E(X)=∑ai’xi解密先計算S’=w
7、-1Smodm再求解簡單背包問題S’=∑aixi21背包密碼系統(tǒng)的意義是第一個公鑰密碼系統(tǒng)有較好的理論價值在實踐過程中，大多數(shù)的背包方案都已被破解，或者證明存在缺陷22只有兩個算法被普遍接受1RSA2橢圓曲線就是要找一個單向陷門函數(shù)：不太容易23單向陷門函數(shù)（1）Y=fk(X)容易(k和X已知)X=f-1k(Y)計算上不可行（k未知，Y已知）X=f-1k(Y)容易（k已知，Y已知）尋找合適的單向陷門函數(shù)是公鑰密碼體制應(yīng)用關(guān)鍵！24單向陷門函數(shù)（2）困難程度舉例打碎/拼接、平方/開方、乘法/分解*單向函數(shù)存在否尚無嚴(yán)格的數(shù)學(xué)證明
