第8講 公鑰密碼學(xué)

《第8講 公鑰密碼學(xué)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、第8講公鑰密碼學(xué)1公鑰密碼學(xué)公鑰密碼學(xué)思想RSA算法公鑰的應(yīng)用2公鑰密碼學(xué)的發(fā)展是整個(gè)密碼學(xué)發(fā)展歷史中最偉大的一次革命。公鑰密碼體制公鑰算法基于數(shù)學(xué)函數(shù)而不是基于替換和置換它使用兩個(gè)獨(dú)立的密鑰，在消息的保密性、密鑰分配和認(rèn)證領(lǐng)域有重要意義。3公鑰密碼比傳統(tǒng)密碼更安全兩個(gè)誤解公鑰密碼是一種通用的方法，所以傳統(tǒng)密碼已經(jīng)過時(shí)。4密鑰分配問題：如果密鑰被偷，設(shè)計(jì)再好的密碼體制都沒有用傳統(tǒng)密碼中的兩個(gè)問題數(shù)字簽名問題：能否設(shè)計(jì)一種方法確保數(shù)字簽名出自某個(gè)特定的人，并且各方無異議？51976年Diffie和Hellman針對(duì)上述問題提出了一種方法，它是密碼學(xué)的一次革命密碼學(xué)革命6公鑰

2、密碼體制介紹7僅根據(jù)密碼算法和加密密鑰來確定解密密鑰在計(jì)算上是不可行的。公鑰密碼體制特點(diǎn)兩個(gè)密鑰中的任何一個(gè)可以用來加密，另一個(gè)用來解密。有6個(gè)組成部分：明文、加密算法、公鑰、私鑰、密文、解密算法8用公鑰進(jìn)行加密2Alice產(chǎn)生一對(duì)密鑰，用于加密和解密3Alice將一個(gè)密鑰公開，另一個(gè)密鑰私有BobAlice1Bob要發(fā)送消息給Alice4Bob用Alice的公鑰對(duì)消息加密，發(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需要對(duì)整條消息加密，占用大量存儲(chǔ)空間解決的方法：僅對(duì)消息的認(rèn)證符加密問題2不能提供保密性如何解決？？13公鑰體制：保密和認(rèn)證14公鑰密碼體制的應(yīng)用1加密/解密2數(shù)字簽名3密鑰交換算法RSA橢圓曲線Diffie-HellmanDSS是是是是是是否否是否是否15對(duì)公鑰密碼體制的要求：1B產(chǎn)生一對(duì)密鑰（KUb，KRb）在計(jì)算上是容易的2發(fā)送方A加密消息C=EKUb(M)在計(jì)算上是容易的3接收方B對(duì)密文解密M=DKRb(C)在計(jì)算上是容易的4攻擊者從KUb計(jì)算出

4、KRb在計(jì)算上不可行的5攻擊者從KUb和C計(jì)算出M在計(jì)算上不可行的6附加條件（并非所有都滿足）：加密解密順序可交換：M=EKUb(DKRb(M))=DKUb(EKRb(M))16公鑰密碼學(xué)的研究情況與計(jì)算復(fù)雜性理論密切相關(guān)計(jì)算復(fù)雜性理論可以提供指導(dǎo)但是需求不盡相同計(jì)算復(fù)雜性通常針對(duì)一個(gè)孤立的問題進(jìn)行研究而公鑰密碼學(xué)往往需要考慮一些相關(guān)的問題比如，密碼分析還需要考慮已知明文、選擇明文等相關(guān)的情形討論的情形不同計(jì)算復(fù)雜性考慮最壞的情形而對(duì)于公鑰密碼學(xué)則是不夠的一個(gè)困難問題必然會(huì)導(dǎo)致一個(gè)保密性很好的密碼系統(tǒng)嗎？不一定，還需要有好的構(gòu)造17背包(knapsack)問題0-1背包

5、問題：給定一個(gè)正整數(shù)S和一個(gè)背包向量A=(a1,…,an)，其中ai是正整數(shù)，求滿足方程S=∑aixi的二進(jìn)制向量X=(x1,…,xn)。這是一個(gè)NP完全問題，解決這個(gè)問題所需要的時(shí)間與n呈指數(shù)增長(zhǎng)背包問題用于公鑰密碼學(xué)做法方法：明文為X，S為密文奧妙在于有兩類背包，一類可以在線性時(shí)間內(nèi)求解，另一類則不能把易解的背包問題修改成難解的背包問題公開密鑰使用難解的背包問題私鑰使用易解的背包問題18易解的背包問題——超遞增背包滿足下列條件的背包ai>∑aj(j=1,…,i-1)這樣的背包也被稱為簡(jiǎn)單背包求解從最大的ai開始，如果S大于這個(gè)數(shù)，則減去ai,記xi為1，否則記xi為0

6、如此下去，直到最小的ai例如背包序列{2,3,6,13,27,52}求解70的背包結(jié)果為{2,3,13,52}所以，密文70對(duì)應(yīng)的明文為11010119轉(zhuǎn)換背包簡(jiǎn)單背包用作私鑰如何產(chǎn)生相應(yīng)的公鑰——轉(zhuǎn)換做法：選擇一個(gè)整數(shù)m>∑ai(i=1,…,n)然后選擇一個(gè)與m互素的整數(shù)w，然后ai’=wai(modm)(i=1,…,n)這里的ai’是偽隨機(jī)分布的這樣得到的背包是非超遞增背包20基于背包問題的公鑰密碼系統(tǒng)——MH公鑰算法加密將明文分為長(zhǎng)度為n的塊X=(x1,…,xn)然后用公鑰A’=(a1’,…,an’)，將明文變?yōu)槊芪腟S=E(X)=∑ai’xi解密先計(jì)算S’=w

7、-1Smodm再求解簡(jiǎn)單背包問題S’=∑aixi21背包密碼系統(tǒng)的意義是第一個(gè)公鑰密碼系統(tǒng)有較好的理論價(jià)值在實(shí)踐過程中，大多數(shù)的背包方案都已被破解，或者證明存在缺陷22只有兩個(gè)算法被普遍接受1RSA2橢圓曲線就是要找一個(gè)單向陷門函數(shù)：不太容易23單向陷門函數(shù)（1）Y=fk(X)容易(k和X已知)X=f-1k(Y)計(jì)算上不可行（k未知，Y已知）X=f-1k(Y)容易（k已知，Y已知）尋找合適的單向陷門函數(shù)是公鑰密碼體制應(yīng)用關(guān)鍵！24單向陷門函數(shù)（2）困難程度舉例打碎/拼接、平方/開方、乘法/分解*單向函數(shù)存在否尚無嚴(yán)格的數(shù)學(xué)證明