我修改后的總結-密碼學的新方向

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