現(xiàn)代密碼學(xué)-學(xué)習(xí)心得

通信0805鄒引08211132密碼學(xué)(Cryptology)一詞源自希臘語“krypto's”及“l(fā)ogos”兩詞，意思為“隱藏”及“消息”。它是研究信息系統(tǒng)安全保密的科學(xué)。其目的為兩人在不安全的信道上進(jìn)行通信而不被破譯者理解他們通信的內(nèi)容。從幾千年前到1949年，密碼學(xué)還沒有成為一門真正的科學(xué)，而是一門藝術(shù)。密碼學(xué)專家常常是憑自己的直覺和信念來進(jìn)行密碼設(shè)計，而對密碼的分析也多基于密碼分析者（即破譯者）的直覺和經(jīng)驗來進(jìn)行的。1949年，美國數(shù)學(xué)家、信息論的創(chuàng)始人Shannon,ClaudeElwood發(fā)表了《保密系統(tǒng)的信息理論》一文，它標(biāo)志著密碼學(xué)階段的開始。同時以這篇文章為標(biāo)志的信息論為對稱密鑰密碼系統(tǒng)建立了理論基礎(chǔ)，從此密碼學(xué)成為一門科學(xué)。由于保密的需要，這時人們基本上看不到關(guān)于密碼學(xué)的文獻(xiàn)和資料，平常人們是接觸不到密碼的。1967年Kahn出版了一本叫做《破譯者》的小說，使人們知道了密碼學(xué)。20世紀(jì)70年代初期，IBM發(fā)表了有關(guān)密碼學(xué)的幾篇技術(shù)報告，從而使更多的人了解了密碼學(xué)的存在。但科學(xué)理論的產(chǎn)生并沒有使密碼學(xué)失去藝術(shù)的一面，如今，密碼學(xué)仍是一門具有藝術(shù)性的科學(xué)。1976年，Diffie和Hellman發(fā)表了《密碼學(xué)的新方向》一文，他們首次證明了在發(fā)送端和接收端不需要傳輸密鑰的保密通信的可能性，從而開創(chuàng)了公鑰密碼學(xué)的新紀(jì)元。該文章也成了區(qū)分古典密碼和現(xiàn)代密碼的標(biāo)志。1977年，美國的數(shù)據(jù)加密標(biāo)準(zhǔn)（DES）公布。這兩件事情導(dǎo)致了對密碼學(xué)的空前研究。從這時候起，開始對密碼在民用方面進(jìn)行研究，密碼才開始充分發(fā)揮它的商用價值和社會價值，人們才開始能夠接觸到密碼學(xué)。這種轉(zhuǎn)變也促使了密碼學(xué)的空前發(fā)展。最早的加密技術(shù)，當(dāng)屬凱撒加密法了。秘密金輪，就是加解密的硬件設(shè)備可以公用，可以大量生產(chǎn)，以降低硬件加解密設(shè)備的生產(chǎn)與購置成本。破譯和加密技術(shù)從來就是共存的，彼此牽制，彼此推進(jìn)。錯綜復(fù)雜的加解密演算法都是為了能夠超越人力執(zhí)行能力而不斷演變的。Kerckhoffs原則、Shannon的完美安全性、DES算法、Rijndael算法……<<NewDirectionsinCryptography>>一文，正如密碼學(xué)的里程碑，佇立在密碼學(xué)者不斷探索的道路上，作為一種跨越，作為一種象征。文章大致翻譯：一、摘要：隨著遠(yuǎn)程通信的發(fā)展，特別是計算機(jī)網(wǎng)絡(luò)的發(fā)展，密碼學(xué)面臨著兩大難題：⒈可靠密鑰的傳輸通道問題。⒉如何提供與手寫簽名等效的認(rèn)證體系。為了解決這些問題，文中提出了公鑰密碼算法和公鑰分配算法，并且把公鑰密碼算法經(jīng)過變換成為一個單向認(rèn)證算法，來解決有效認(rèn)證問題。此外還討論了密碼學(xué)中各種問題之間的相互關(guān)系，陷門問題，計算復(fù)雜性問題，最后回顧了密碼學(xué)發(fā)展的歷史。

二、常規(guī)密碼體系：這一部分主要介紹了密碼學(xué)的一些基本知識，如密鑰、加密、解密，算法的無條件安全與計算性安全，三種攻擊法，即唯密文攻擊、已知明文攻擊、選擇明文攻擊。需要指出的是，本文給出了密碼學(xué)的一個定義：研究解決保密和認(rèn)證這兩類安全問題的“數(shù)學(xué)”方法的學(xué)科。還有一點需要指出的是，根據(jù)Shannon的理論：無條件安全的算法是存在的，但由于其密鑰過長而不實用，這也是發(fā)展計算上安全的算法的原因。

三、公鑰密碼學(xué)：公鑰密碼學(xué)主要包括兩部分：公鑰密碼算法和公鑰分配算法。公鑰密碼算法是指定義在有限信息空間{M}上的，基于算法{Ek}和{Dk}的可逆變換

Ek：{M}->{M}

Dk：{M}->{M}

滿足下列條件：

⑴對任給K∈{K}，Ek是Dk的互逆變換

⑵對任意的K∈{K}和M∈{M}，用Ek和Dk進(jìn)行加密和解密是容易計算的

⑶對幾乎所有的K∈{K}，從Ek推出Dk在計算上是不可行的

⑷對任意的K∈{K}，從K計算Ek和Dk是可行的

這里K是用以產(chǎn)生Ek和Dk的隨機(jī)數(shù)。性質(zhì)⑶保證了可公開Ek而不損害Dk的安全性，這樣才保證了公鑰密碼算法的安全性。

以加密二值n維向量為例，加密算法是乘一個n×n可逆矩陣，解密則乘其逆矩陣，所需運算時間為n2。此可逆矩陣可通過對單位矩陣做一系列的行和列的初等變換得到，而其逆矩陣是經(jīng)過逆序的行和列的逆變換得到。但是矩陣求逆只需要n3的時間，密碼分析者用時與正常解密用時之比是n。雖然這個例子并不實用，但對解釋公鑰密碼算法是有用的。一個更實用的方法是利用機(jī)器語言的難懂性，把加密算法編譯成機(jī)器語言公布，而解密算法保密，分析者要理解機(jī)器語言的全部運算過程是很困難的，所以要破解是困難的，當(dāng)然此算法必須足夠的復(fù)雜以免通過輸入和輸出對來破解。

公鑰分配算法是基于求對數(shù)再取模計算上的困難。令q是一個素數(shù)，在有限域GF(q)上任取q，計算Y=ax*mod（q），其中a是GF(q)上的一個固定基元。則

X=loga【Y*mod（q）】。不難得出由X計算Y是較容易的，約需要計算2×log2q次乘法；然而從Y得出X是困難的，因為需q/2次運算。這樣對每一個用戶，從[1，2，…，q-1]中隨機(jī)的選一個q，計算出Yi=aXi*modq，并將Yi公布，Xi保密。那么當(dāng)用戶i和j通信時，使用Kij=aXiXj*modq作為他們的公共密鑰。此密鑰用戶i通過j公布的Yj得到，即Kij=YjXi*modq=(aXj)Xi*modq=aXiXj*modq得到。用戶j的計算同理。對于第三方要獲得此密鑰就必須計算，而這在計算上是不可行的，從而達(dá)到了在公共信道上分配私鑰的效果。四、單向認(rèn)證：現(xiàn)有的認(rèn)證體系只能保證不被第三方冒名頂替，但不能解決發(fā)送者和接收者之間的沖突，為此引入單向函數(shù)的概念，即對定義域中的任意x，f(x)是容易計算的，但對幾乎所有的值域中的y，求滿足y=f(x)的x在計算上是不可行的。例如已知多項式p(x)和x，求y=p(x)是容易的，但若已知y求出x是困難的。值得注意的是，這里的計算上不可逆與數(shù)學(xué)中的不可逆是完全不同的（數(shù)學(xué)上的不可逆可能是有多個原像）。

公鑰密碼算法可用來產(chǎn)生一個真正的單向認(rèn)證體系。當(dāng)用戶A要發(fā)信息M給用戶B時，他用其保密的解密密鑰解密“M”并傳給B，B收到時用A公布的加密密鑰“加密”此消息從而得到信息M。因為解密密鑰是保密的，只有A發(fā)送的消息才具有這樣的性質(zhì)，從而確認(rèn)此信息來源于A，也就建立了一個單向認(rèn)證體系。

LeslieLamport還提出另一種單向信息認(rèn)證方法，它是應(yīng)用在k維二值空間上的單向函數(shù)f到其自身的映射來實現(xiàn)的。若發(fā)送者發(fā)送N比特的信息m，他要產(chǎn)生2N個隨機(jī)k維二值向量x1,X1，x2，X2，……xn,Xn,并保密，隨后把這些向量在f下的像y1，Y1，y2，Y2，……yn,Yn，發(fā)送給接收者。當(dāng)發(fā)送信息m=(m1,m2,…,mN)時，m1=0發(fā)送x1，m1=1發(fā)送X1，依次類推。接收者把收到的信息用f映射之，若為y1則m1=0，Y1則m1=1，如此下去便得到了m。由于函數(shù)f的單向性，接收者無法從y推出x，因此就無法改動接收到的任何收據(jù)。當(dāng)然在N比較大時這種方法的額外開銷是很大的，為此有必要引入單向映射g，用來把N比特的信息映射成n比特(n約為50)，但這里要求g有比一般的單向函數(shù)更強(qiáng)的性質(zhì)。

五、問題的相關(guān)性和陷門：⒈一個對已知明文攻擊安全的密碼算法能產(chǎn)生一個單向函數(shù)。設(shè):{P}->{K}是這樣的一個算法，取P=P0?？紤]映射f：{K}->{C}定義為f(x)=Sx(P0)，則f是一個單向函數(shù)，因為要由f(x)得到x和已知明文攻擊是等價的(即已知P=P0和SK(P0)求不出K)。Evans還提出過另一種方法，他用的映射是f(x)=Sx(X)，這增加了破解的難度，但這個單向函數(shù)卻破壞了對已知明文攻擊安全的要求。

⒉一個公鑰密碼算法可用來產(chǎn)生一個單向認(rèn)證體系。這一點在（四）中已經(jīng)討論過了。

⒊一個陷門密碼算法可用來產(chǎn)生一個公鑰分配算法。所謂陷門密碼算法是指只有知道陷門信息才能正確還原明文，不掌握陷門信息要破解出明文在計算上是不可行的。比如A要和B建立公共私鑰，A任選一個密鑰，用B公布的含有陷門信息的加密密鑰加密之，并將密文發(fā)送給B，B由保密的陷門信息解密得到此密鑰，于是A和B建立了公共的私鑰。不難發(fā)現(xiàn)公鑰密碼算法是一個陷門單向函數(shù)。

六、計算復(fù)雜度：現(xiàn)代密碼算法的安全性是基于計算上的不可行性，因此就有必要對計算復(fù)雜度進(jìn)行研究。在確定型圖靈機(jī)上可用多項式時間求解的問題定義為P類復(fù)雜度，在非確定型圖靈上可用多項式時間求解的問題定義為NP類復(fù)雜度，顯然NP包括P。Karp還定義了一個NP完全集，即如果NP完全集中的任何一個問題屬于P類，則NP中的所有問題都屬于P?，F(xiàn)在大多數(shù)的加密算法用的是NP完全集中的問題。關(guān)于密碼分析的難度有如下定理：一個加密和解密算法若是能在P時間內(nèi)完成的，那么密碼分析的難度不會大于NP時間。七、歷史回顧：

密碼學(xué)的發(fā)展經(jīng)歷了早期的加密過程保密，到60年代對明文攻擊安全的算法，到現(xiàn)在算法公開的基于計算復(fù)雜度的算法，可見其發(fā)展趨勢是秘密性越來越弱的。并且隨著許多曾經(jīng)被證明為安全的算法被相繼攻破，密碼安全性的分析也經(jīng)歷了早期的純數(shù)學(xué)證明到后來的密碼分析攻擊，再到計算復(fù)雜度分析。這里還有一個有趣的現(xiàn)象就是密碼分析方法大多是由專業(yè)人事發(fā)現(xiàn)的，而密碼算法則主要是由非專業(yè)人員提出的。對于這篇經(jīng)典之作，我的認(rèn)知顯得很是粗陋。要想真正讀通這篇巨作，恐怕自己還需要修煉些時日。但是，加密解密已經(jīng)滲入到如今這個電子化信息化的生活中來，又無時無刻不在感受著密碼學(xué)帶來的快感。信息安全技術(shù)作為一門綜合學(xué)科，它涉及信息論、計算機(jī)科學(xué)和密碼學(xué)等多方面知識，研究計算機(jī)系統(tǒng)和通信網(wǎng)絡(luò)內(nèi)信息的保護(hù)方法以實現(xiàn)系統(tǒng)內(nèi)信息的安全、保密、真實和完整。21世紀(jì)是信息時代，信息的傳遞在人們?nèi)粘Ｉ钪凶兊梅浅Ｖ匾Ｈ纾弘娮由虅?wù)，電子郵件，電子政務(wù)，銀行證券等，無時無刻不在影響著人們的生活。這樣信息安全問題也就成了最重要的問題之一。在信息交換中，“安全”是相對的，