我修改后的總結(jié)-密碼學(xué)的新方向

PAGEPAGE1密碼學(xué)的新方向Ⅰ簡介隨著遠(yuǎn)程通信的發(fā)展，特別是計(jì)算機(jī)網(wǎng)絡(luò)的發(fā)展，密碼學(xué)面臨著兩大難題：⒈可靠密鑰的傳輸通道問題。⒉如何提供與手寫簽名等效的認(rèn)證體系。為了解決這些問題，文中提出了公鑰密碼算法和公鑰分配算法，并且把公鑰密碼算法經(jīng)過變換成為一個(gè)單向認(rèn)證算法，來解決有效認(rèn)證問題。此外還討論了密碼學(xué)中各種問題之間的相互關(guān)系，陷門問題，計(jì)算復(fù)雜性問題，最后回顧了密碼學(xué)發(fā)展的歷史。Ⅱ常規(guī)密碼體系這一部分主要介紹了密碼學(xué)的一些基本知識(shí)，如密鑰、加密、解密，算法的無條件安全與計(jì)算性安全，三種攻擊法，即唯密文攻擊、已知明文攻擊、選擇明文攻擊。這些知識(shí)課堂上都講解過了，不再累述。這里需要指出的是，本文給出了密碼學(xué)的一個(gè)定義：研究解決保密和認(rèn)證這兩類安全問題的“數(shù)學(xué)”方法的學(xué)科。還有一點(diǎn)需要指出的是，根據(jù)Shannon的理論無條件安全的算法是存在的，但由于其密鑰過長而不實(shí)用，這也是發(fā)展計(jì)算上安全的算法的原因。解決安全性與效率間的矛盾！Ⅲ公鑰密碼學(xué)公鑰密碼學(xué)主要包括兩部分：公鑰密碼算法和公鑰分配算法。公鑰密碼算法是指定義在有限信息空間{M}上的，基于算法{}和{}的可逆變換：{M}{M}：{M}{M}滿足下列條件：⑴對(duì)任給K{K}，是的互逆變換⑵對(duì)任意的K{K}和M{M}，用和進(jìn)行加密和解密是容易計(jì)算的⑶對(duì)幾乎所有的K{K}，從推出在計(jì)算上是不可行的⑷對(duì)任意的K{K}，從K計(jì)算和是可行的這里K是用以產(chǎn)生和的隨機(jī)數(shù)。性質(zhì)⑶保證了可公開而不損害的安全性，這樣才保證了公鑰密碼算法的安全性。以加密二值n維向量為例，加密算法是乘一個(gè)nn可逆矩陣，解密則乘其逆矩陣，所需運(yùn)算時(shí)間為n。此可逆矩陣可通過對(duì)單位矩陣做一系列的行和列的初等變換得到，而其逆矩陣是經(jīng)過逆序的行和列的逆變換得到。但是矩陣求逆只需要n的時(shí)間，密碼分析者用時(shí)與正常解密用時(shí)之比是n。雖然這個(gè)例子并不實(shí)用，但對(duì)解釋公鑰密碼算法是有用的。一個(gè)更實(shí)用的方法是利用機(jī)器語言的難懂性，把加密算法編譯成機(jī)器語言公布，而解密算法保密，分析者要理解機(jī)器語言的全部運(yùn)算過程是很困難的，所以要破解是困難的，當(dāng)然此算法必須足夠的復(fù)雜以免通過輸入和輸出對(duì)來破解。公鑰分配算法是基于求對(duì)數(shù)再取模計(jì)算上的困難。令q是一個(gè)素?cái)?shù)，在有限域GF(q)上任取，計(jì)算Y=modq，其中是GF(q)上的一個(gè)固定基元。則X=modq。不難得出由X計(jì)算Y是較容易的，約需要計(jì)算次乘法；然而從Y得出X是困難的，因?yàn)樾枰芜\(yùn)算。這樣對(duì)每一個(gè)用戶，從[1，2，…，q-1]中隨機(jī)的選一個(gè)，計(jì)算出，并將公布，保密。那么當(dāng)用戶i和j通信時(shí)，使用作為他們的公共密鑰。此密鑰用戶i通過j公布的得到，即用戶j的計(jì)算同理。對(duì)于第三方要獲得此密鑰就必須計(jì)算，而這在計(jì)算上是不可行的，從而達(dá)到了在公共信道上分配私鑰的效果。Ⅳ單向認(rèn)證現(xiàn)有的認(rèn)證體系只能保證不被第三方冒名頂替，但不能解決發(fā)送者和接收者之間的沖突，為此引入單向函數(shù)的概念，即對(duì)定義域中的任意x，f(x)是容易計(jì)算的，但對(duì)幾乎所有的值域中的y，求滿足y=f(x)的x在計(jì)算上是不可行的。例如已知多項(xiàng)式p(x)和x，求y=p(x)是容易的，但若已知y求出x是困難的。值得注意的是，這里的計(jì)算上不可逆與數(shù)學(xué)中的不可逆是完全不同的。公鑰密碼算法可用來產(chǎn)生一個(gè)真正的單向認(rèn)證體系。當(dāng)用戶A要發(fā)信息M給用戶B時(shí)，他用其保密的解密密鑰”解密”M并傳給B，B收到時(shí)用A公布的加密密鑰”加密”此消息從而得到信息M。因?yàn)榻饷苊荑€是保密的，只有A發(fā)送的消息才具有這樣的性質(zhì)，從而確認(rèn)此信息來源于A，也就建立了一個(gè)單向認(rèn)證體系。LeslieLamport還提出另一種單向信息認(rèn)證方法，它是應(yīng)用在k維二值空間上的單向函數(shù)f到其自身的映射來實(shí)現(xiàn)的。若發(fā)送者發(fā)送N比特的信息m，他要產(chǎn)生2N個(gè)隨機(jī)k維二值向量，，，，…，，，并保密，隨后把這些向量在f下的像，，，，…，，發(fā)送給接收者。當(dāng)發(fā)送信息m=(,,…,)時(shí)，當(dāng)=0發(fā)送，=1發(fā)送，依次類推。接收者把收到的信息用f映射之，若為則=0，則=1，如此下去便得到了m。由于函數(shù)f的單向性，接收者無法從y推出x，因此就無法改動(dòng)接收到的任何收據(jù)。當(dāng)然在N比較大時(shí)這種方法的額外開銷是很大的，為此有必要引入單向映射g，用來把N比特的信息映射成n比特(n約為50)，但這里要求g有比一般的單向函數(shù)更強(qiáng)的性質(zhì)。Ⅴ問題的相關(guān)性和陷門⒈一個(gè)對(duì)已知明文攻擊安全的密碼算法能產(chǎn)生一個(gè)單向函數(shù)。設(shè):{P}{C}是這樣的一個(gè)算法，取P=P，考慮映射f：{K}{C}定義為f(x)=，則f是一個(gè)單向函數(shù)，因?yàn)橐蒮(x)得到x和已知明文攻擊是等價(jià)的。Evans還提出過另一種方法，他用的映射是f(x)=，這增加了破解的難度，但這個(gè)單向函數(shù)卻破壞了對(duì)已知明文攻擊安全的要求。⒉一個(gè)公鑰密碼算法可用來產(chǎn)生一個(gè)單向認(rèn)證體系。這一點(diǎn)在Ⅳ中已經(jīng)討論過了。⒊一個(gè)陷門密碼算法可用來產(chǎn)生一個(gè)公鑰分配算法。所謂陷門密碼算法是指只有知道陷門信息才能正確還原明文，不掌握陷門信息要破解出明文在計(jì)算上是不可行的。比如A要和B建立公共私鑰，A任選一個(gè)密鑰，用B公布的含有陷門信息的加密密鑰加密之，并將密文發(fā)送給B，B由保密的陷門信息解密得到此密鑰，于是A和B建立了公共的私鑰。不難發(fā)現(xiàn)公鑰密碼算法是一個(gè)陷門單向函數(shù)。Ⅵ計(jì)算復(fù)雜度現(xiàn)代密碼算法的安全性是基于計(jì)算上的不可行性，因此就有必要對(duì)計(jì)算復(fù)雜度進(jìn)行研究。在確定型圖靈機(jī)上可用多項(xiàng)式時(shí)間求解的問題定義為P類復(fù)雜度，在非確定型圖靈上可用多項(xiàng)式時(shí)間求解的問題定義為NP類復(fù)雜度，顯然PNP。Karp還定義了一個(gè)NP完全集，即如果NP完全集中的任何一個(gè)問題屬于P類，則NP中的所有問題都屬于P?，F(xiàn)在大多數(shù)的加密算法用的是NP完全集中的問題。關(guān)于密碼分析的難度有如下定理：一個(gè)加密和解密算法若是能在P時(shí)間內(nèi)完成的，那么密碼分析的難度不會(huì)大于NP時(shí)間。Ⅶ歷史回顧密碼學(xué)的發(fā)展經(jīng)歷了早期的加密過程保密，到60年代對(duì)明文攻擊安全的算法，到現(xiàn)在算法公開的基于計(jì)算復(fù)雜