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

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

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

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

Ek：{M}->{M}

Dk：{M}->{M}

滿足下列條件：

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

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

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

⑷對(duì)任意的K∈{K}，從K計(jì)算Ek和Dk是可行的

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

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

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

X=loga【Y*mod（q）】。不難得出由X計(jì)算Y是較容易的，約需要計(jì)算2×log2q次乘法；然而從Y得出X是困難的，因?yàn)樾鑡/2次運(yùn)算。這樣對(duì)每一個(gè)用戶，從[1，2，…，q-1]中隨機(jī)的選一個(gè)q，計(jì)算出Yi=aXi*modq，并將Yi公布，Xi保密。那么當(dāng)用戶i和j通信時(shí)，使用Kij=aXiXj*modq作為他們的公共密鑰。此密鑰用戶i通過(guò)j公布的Yj得到，即Kij=YjXi*modq=(aXj)Xi*modq=aXiXj*modq得到。用戶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é)中的不可逆是完全不同的（數(shù)學(xué)上的不可逆可能是有多個(gè)原像）。

公鑰密碼算法可用來(lái)產(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)此信息來(lái)源于A，也就建立了一個(gè)單向認(rèn)證體系。

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

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

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

⒊一個(gè)陷門密碼算法可用來(lái)產(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í)間求解的問(wèn)題定義為P類復(fù)雜度，在非確定型圖靈上可用多項(xiàng)式時(shí)間求解的問(wèn)題定義為NP類復(fù)雜度，顯然NP包括P。Karp還定義了一個(gè)NP完全集，即如果NP完全集中的任何一個(gè)問(wèn)題屬于P類，則NP中的所有問(wèn)題都屬于P?，F(xiàn)在大多數(shù)的加密算法用的是NP完全集中的問(wèn)題。關(guān)于密碼分析的難度有如下定理：一個(gè)加密和解密算法若是能在P時(shí)間內(nèi)完成的，那么密碼分析的難度不會(huì)大于NP時(shí)間。七、歷史回顧：

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