信息加密技術(shù)基礎(chǔ)課件

第二章

信息加密技術(shù)基礎(chǔ)第二章

信息加密技術(shù)基礎(chǔ)1

引言信息加密是網(wǎng)絡(luò)安全體系中重要機(jī)制之一。信息加密的目的是為了保持信息的機(jī)密性，使用恰當(dāng)?shù)募用軜?biāo)準(zhǔn)將在計(jì)算機(jī)環(huán)境中增加安全性。信息加密通過(guò)使用一種編碼而使存儲(chǔ)或傳輸?shù)男畔⒆優(yōu)椴豢勺x的信息，解密是一個(gè)相反的過(guò)程。這些編碼就是將明文變成密文的加密算法或數(shù)學(xué)方法。引言信息加密是網(wǎng)絡(luò)安全體系中2引言(續(xù))

加密編碼在Shannon的信息論中有針對(duì)性的闡述，數(shù)論及基礎(chǔ)代數(shù)是加密算法的理論基礎(chǔ)。要將一段信息加密或解密，你會(huì)要用到密鑰，它是一個(gè)很大的值。一般來(lái)說(shuō)，密鑰越大，加密就越健壯。一般來(lái)說(shuō)加密體制分為對(duì)稱密鑰加密和公用密鑰加密，對(duì)稱密鑰加密在密鑰方面有一定的缺陷，但執(zhí)行效率高；公用密鑰加密加密執(zhí)行效率底，但保密性強(qiáng)，在報(bào)文和網(wǎng)絡(luò)方面對(duì)小量信息加密非常有效.引言(續(xù))32.1信息加密理論基礎(chǔ)信息安全的核心技術(shù)之一是加密技術(shù)，它涉及信息論、基礎(chǔ)數(shù)論和算法復(fù)雜性等多方面基礎(chǔ)知識(shí)。隨著計(jì)算機(jī)網(wǎng)絡(luò)不斷滲透到各個(gè)領(lǐng)域，加密技術(shù)的應(yīng)用也隨之?dāng)U大，應(yīng)用加密基礎(chǔ)理論知識(shí)，深入探索可靠可行的加密方法，應(yīng)用于數(shù)字簽名、身份鑒別等新技術(shù)中成為網(wǎng)絡(luò)安全研究重要的一個(gè)方面。2.1信息加密理論基礎(chǔ)信息安全的4加密的理論依據(jù)密碼學(xué)問(wèn)題就是隨機(jī)性的利用問(wèn)題.差不多每臺(tái)使用加密技術(shù)的計(jì)算機(jī)安全系統(tǒng)都需要隨機(jī)數(shù)，供密鑰、協(xié)議中的基礎(chǔ)參量等使用或者用做輔助信息或者初始化向量。這些系統(tǒng)的安全也經(jīng)常依賴于這些隨機(jī)數(shù)的隨機(jī)性及被保護(hù)程度。加密的理論依據(jù)密碼學(xué)問(wèn)題就是隨機(jī)性的利用問(wèn)題.5簡(jiǎn)單的加密舉例中秋日月編碼密鑰密文編碼詩(shī)月明明日01010110111111明日月明101010000000？明日明日101101000111日明月明110010011000通過(guò)這個(gè)例子我們看到一個(gè)簡(jiǎn)單的加密過(guò)程，原來(lái)的詩(shī)通過(guò)與密鑰的模二運(yùn)算實(shí)現(xiàn)了加密。簡(jiǎn)單的加密舉例中秋日月編碼密鑰62.1.1信息編碼基礎(chǔ)知識(shí)第二次世界大戰(zhàn)期間，美國(guó)為了提高信息儲(chǔ)存和傳遞的效率，發(fā)明了多種新的編碼方法，奠定了現(xiàn)代信息科學(xué)技術(shù)的基礎(chǔ)。Shannon還于1949年發(fā)表了“保密系統(tǒng)的通信理論”一文，奠定了現(xiàn)代密碼學(xué)基礎(chǔ)從而對(duì)加密過(guò)程中信息編碼有了明確的分析。在該文中他從信息論觀點(diǎn)，對(duì)信息系統(tǒng)的保密性問(wèn)題作了全面而深刻的闡述。2.1.1信息編碼基礎(chǔ)知識(shí)第二次7

1.信息熵基本知識(shí)信息論中最重要的內(nèi)容，是如何認(rèn)識(shí)和使用信息熵來(lái)表現(xiàn)信息。這里用Shannon最喜歡用的猜謎方法來(lái)說(shuō)明信息熵的基本概念。假如有：“我們大__都喜__使__計(jì)__機(jī)來(lái)管__數(shù)__。”不用很多努力，就可以猜出完整的句子:“我們大家都喜歡使用計(jì)算機(jī)來(lái)管理數(shù)據(jù)?！盨hannon在信息論中指出，能猜出來(lái)的字符不運(yùn)載信息，而不能猜出來(lái)的字符運(yùn)載信息。1.信息熵基本知識(shí)81.信息熵基本知識(shí)(續(xù))空格所隱藏的字符屬于多余度字符，不用那些字符也能運(yùn)載該句子的全部信息，比如：“我__大________使______機(jī)來(lái)____數(shù)__?！本秃茈y猜出完整的句子，在信息傳遞的時(shí)候，也很難做檢錯(cuò)和抗錯(cuò)。因此，保留一定的多余度(或冗余度)是非常重要的。1.信息熵基本知識(shí)(續(xù))9

2.

信息量和信息熵基本定義(1)信息熵（informationentropy）是對(duì)信息狀態(tài)“無(wú)序”與“不確定”的度量（從本質(zhì)上講，熵不是對(duì)信息的度量，但信息的增加而使產(chǎn)生的熵減小，熵可以用來(lái)度量信息的增益）。2.信息量和信息熵基本定義(1)10

2.

信息量和信息熵基本定義(2)定義：給定一離散集合X={xi;i=1,2,…,n}，令xi出現(xiàn)的概率是 且。事件xi包含的信息量通常=2，此時(shí)相應(yīng)的信息量單位是bit。Shannon定義信息的數(shù)學(xué)期望為信息熵，即信源的平均信息量。(2.1)2.信息量和信息熵基本定義(2)定義：給定112.信息量和信息熵基本定義(3)定義：將集合X中事件所包含的信息量統(tǒng)計(jì)平均，則平均值定義為集合X的熵.信息熵表征了信源整體的統(tǒng)計(jì)特征，集合X的熵H（x）表示X中事件所包含的平均信息量，或總體的平均不確定性的量度。(2.2)2.信息量和信息熵基本定義(3)定義：將集合X中122.信息量和信息熵基本定義(4)對(duì)某一特定的信源，其信息熵只有一個(gè)，因統(tǒng)計(jì)特性不同，其熵也不同。例如，兩個(gè)信源，其概率空間分別為：2.信息量和信息熵基本定義(4)132.信息量和信息熵基本定義(5)則信息熵為：可見(jiàn)，,說(shuō)明信源比信源的平均不確定性要大，即在事件發(fā)生之前，分析信源，由于事件是等概率的，難以猜測(cè)哪一個(gè)事件會(huì)發(fā)生.2.信息量和信息熵基本定義(5)則信息熵為：142.信息量和信息熵基本定義(6)而信源，雖然也存在不確定性，但大致可以知道,出現(xiàn)的可能性要大。正如兩場(chǎng)比賽，其中一場(chǎng)，雙方勢(shì)均力敵；而另一場(chǎng)雙方實(shí)力懸殊很大。當(dāng)然,人們希望看第一場(chǎng)，因?yàn)閯儇?fù)難卜，一旦賽完，人們獲得信息量大。也可以這樣理解，信息熵表征了變量的隨機(jī)性。因此，熵反映了變量的隨機(jī)性，也是表征隨機(jī)變量統(tǒng)計(jì)特性的一個(gè)特征參數(shù)。2.信息量和信息熵基本定義(6)而153.信息熵的基本性質(zhì)(1)對(duì)稱性當(dāng)概率空間中序任意互換時(shí)，熵函數(shù)的值不變，例如下面兩個(gè)信源空間:3.信息熵的基本性質(zhì)(1)163.信息熵的基本性質(zhì)(2)

其信息熵.該性質(zhì)說(shuō)明，熵只與隨機(jī)變量的總體結(jié)構(gòu)有關(guān)，與信源總體的統(tǒng)計(jì)特性有關(guān)，同時(shí)也說(shuō)明所定義的熵有其局限性，它不能描述事件本身的主觀意義。3.信息熵的基本性質(zhì)(2)173.信息熵的基本性質(zhì)(3)確定性如果信源的輸出只有一個(gè)狀態(tài)是必然的,即則信源的熵:此性質(zhì)表明，信源的輸出雖有不同形態(tài)，但其中一種是必然的，意味著其他狀態(tài)不可能出現(xiàn)。那么，這個(gè)信源是一個(gè)確知信源，其熵為零。(2.3)3.信息熵的基本性質(zhì)(3)確定性(2.3)183.信息熵的基本性質(zhì)(4)非負(fù)性即。因?yàn)殡S機(jī)變量的所有取值的概率分布為，當(dāng)取對(duì)數(shù)的底大于１時(shí)，,而,則得到的熵是正值，只有當(dāng)隨機(jī)變量是一確知量時(shí)，熵才等于零。這種非負(fù)性對(duì)于離散信源的熵來(lái)說(shuō)，這一性質(zhì)并不存在。3.信息熵的基本性質(zhì)(4)非負(fù)性193.信息熵的基本性質(zhì)(5)可加性獨(dú)立信源和的聯(lián)合信源的熵等于它們各自的熵之和。如果有兩個(gè)隨機(jī)變量和，它們彼此是統(tǒng)計(jì)獨(dú)立的，即的概率分布為,而的分布概率為,則聯(lián)合信源的熵:

可加性是熵函數(shù)的一個(gè)重要特性，正因?yàn)橛锌杉有?，所以可以證明熵函數(shù)的形式是唯一的。

3.信息熵的基本性質(zhì)(5)可加性203.信息熵的基本性質(zhì)(6)極值性信源各個(gè)狀態(tài)為零概率分布時(shí)，熵值最大，并且等于信源輸出狀態(tài)數(shù)，因?yàn)楫?dāng)時(shí)，

(2.5)3.信息熵的基本性質(zhì)(6)極值性21例題例，信源有兩種狀態(tài)時(shí)，概率空間其與關(guān)系如圖所示,，當(dāng)=1/2時(shí)熵有最大值；當(dāng)信源輸出是確定的，即，則，此時(shí)表明該信源不提供任何信息；反之，當(dāng)信源輸出為等概率發(fā)生時(shí)，即時(shí)信源的熵達(dá)到最大值，等于1bit信息量。信息熵函數(shù)曲線P(x)00.51明文H(x)例題例，信源有兩種狀態(tài)時(shí)，概率空間224.信息熵在信息加密編碼中的作用(1)

通過(guò)熵和信息量的概念，可計(jì)算加密系統(tǒng)中各部分的熵。令明文熵為，密鑰熵，密文熵。這里M、K和C分別是明文、密鑰和密文空間，m、k、c分別是它們的字母集，l,r和v分別是明文、密鑰、和密文的長(zhǎng)度。則明文和密文之間的互信息以及密鑰與密文之間的互信息分別是：(2.6)(2.7)4.信息熵在信息加密編碼中的作用(1)通過(guò)熵和信234.信息熵在信息加密編碼中的作用(2)

因?yàn)橹灰芪?、密鑰確定后，明文也就得到了，所以,故定理：對(duì)任意加密系統(tǒng)從該理論我們可以看出，密鑰熵越大，密文中所包含的明文信息量就越小。一個(gè)加密系統(tǒng)中，若其密文與明文之間的互信息，則密碼分析者無(wú)論截獲多大的密文，均不能得到有關(guān)明文的任何信息。這種加密系統(tǒng)稱為完善加密系統(tǒng)，或無(wú)條件加密系統(tǒng)。(2.8)4.信息熵在信息加密編碼中的作用(2)因?yàn)橹灰芪摹?44.信息熵在信息加密編碼中的作用(3)在對(duì)密文攻擊下，完善加密系統(tǒng)是安全的，但它不能保證在已知明文或選擇性明文攻擊下也是安全的。因此，完善保密系統(tǒng)存在的必要條件是

證明：若，則由前一個(gè)定理可得，，所以的必要條件是(2.9)4.信息熵在信息加密編碼中的作用(3)在對(duì)密文攻擊252.1.2數(shù)論基本術(shù)語(yǔ)數(shù)論是研究整數(shù)性質(zhì)的一個(gè)數(shù)學(xué)分支，同時(shí)也是加密技術(shù)的基礎(chǔ)學(xué)科之一。首先介紹一些數(shù)論的基本知識(shí).2.1.2數(shù)論基本術(shù)語(yǔ)261.整數(shù)定義：設(shè)。如果存在使得，那么就說(shuō)b可以被a整除，記為，且稱b是a的倍數(shù),a是b的因數(shù)(或稱約數(shù)、除數(shù)、因子)。b不能被a整除可以記作dFa。由定義及乘法運(yùn)算的性質(zhì)，可推出整除關(guān)系具有以下性質(zhì)（注：符號(hào)本身包含了條件）：（1）；（2）如果且，則；（3）設(shè),那么與等價(jià);（4）如果且,則對(duì)所有的,有;（5）設(shè),如果,那么;1.整數(shù)定義：設(shè)272.素?cái)?shù)定義:設(shè)整數(shù)。如果它除了顯然因數(shù)外沒(méi)有其他的因數(shù)，則p就稱為是素?cái)?shù)，也叫不可約數(shù)。若，且a不是素?cái)?shù)，則a稱為合數(shù)。關(guān)于素?cái)?shù)，有以下性質(zhì)：（1）如果p是素?cái)?shù)，且，則或，即p至少整除a與b中的一個(gè)。（2）任何一個(gè)整數(shù)，均可以分解成素?cái)?shù)冪之積：（3）若不計(jì)因數(shù)的順序，這個(gè)分解式是唯一的。其中,是兩兩互不相同的素?cái)?shù)，是正整數(shù)。（4）素?cái)?shù)有無(wú)窮多個(gè)。（5）設(shè)表示不大于的素?cái)?shù)的數(shù)目，則。2.素?cái)?shù)定義:設(shè)整數(shù)283.同余設(shè)，如果，則稱a和b模n同余，記為，整數(shù)n稱為模數(shù)。由于等價(jià)于，所以與等價(jià)。因此，一般我們總假定。如果，我們稱b是a對(duì)模n的最小非負(fù)剩余，有時(shí)也稱b為a對(duì)模n的余數(shù)。3.同余29同余式的一些基本性質(zhì)（1）反身性:；（2）對(duì)稱性:如果，那么；（3）傳遞性:如果，,那么；（4）如果，那么；。（5）如果，，gcd，(兩個(gè)不同時(shí)為0的整數(shù)a與b的最大公約數(shù)表示成gcd(a,b))那么，存在,當(dāng)且僅當(dāng)gcd。同余式的一些基本性質(zhì)（1）反身性:30一些關(guān)于同余的基本概念(1)

同余類可用其中任一元素a(經(jīng)常取)代替，記作。于是從中分別取一個(gè)數(shù)作為代表構(gòu)成一個(gè)集合，稱為模n的一個(gè)完全剩余系，記為，稱為模n的非負(fù)最小完全剩余系。

(2.11)一些關(guān)于同余的基本概念(1)同余類31一些關(guān)于同余的基本概念(2)在模n的完全剩余系中，去掉那些與n不互素的數(shù)，剩下的部分稱為模n的簡(jiǎn)化剩余系；的簡(jiǎn)化剩余系記為，讀為模n的非負(fù)最小簡(jiǎn)化剩余系。顯然,中的元便是不超過(guò)n并與n互素的那些數(shù)，它們的個(gè)數(shù)等于歐拉函數(shù)的值。（歐拉函數(shù)的定義為:小于自然數(shù)N并與N互質(zhì)(除1以外無(wú)其它公因子)的自然數(shù)的個(gè)數(shù)用函數(shù)表示,稱為歐拉函數(shù)。歐拉函數(shù)的具體性質(zhì)會(huì)在后面第6小節(jié)進(jìn)行闡述）一些關(guān)于同余的基本概念(2)在模n的完全剩余系中，324.模運(yùn)算給定正整數(shù)n，對(duì)任意a，若存在q，使得則稱r是a關(guān)于模n的余數(shù)，記為。若則稱整數(shù)a，b同余，記為整數(shù)集中所有與數(shù)a同余的整數(shù)集合稱為a的同余類，記為。4.模運(yùn)算給定正整數(shù)n，對(duì)任意a，若存33模運(yùn)算的性質(zhì)（1）當(dāng)且僅當(dāng)。（2）當(dāng)且僅當(dāng)。（3）如果，，則。

a模n的運(yùn)算給出了a對(duì)模n的余數(shù)。注意：模運(yùn)算的結(jié)果是從0到的一個(gè)整數(shù)。模運(yùn)算就像普通的運(yùn)算一樣，它是可交換，可結(jié)合，可分配的。而且，對(duì)每一個(gè)中間結(jié)果進(jìn)行模m運(yùn)算，其作用與先進(jìn)行全部運(yùn)算，然后再進(jìn)行模m運(yùn)算所得到結(jié)果是一樣的。模運(yùn)算的性質(zhì)345.最大公約數(shù)與最小公倍數(shù)設(shè)，是兩個(gè)整數(shù)，如果且，那么就稱b是和的公約數(shù).一般的，設(shè)，是K個(gè)整數(shù)，如果那么就稱b是的公約數(shù)。因?yàn)閷?duì)于任意一個(gè)不等于零的整數(shù)，它的因數(shù)是有限的。所以，任意一對(duì)整數(shù)，其中一個(gè)不為零時(shí)，它們的公約數(shù)的個(gè)數(shù)也必定是有限的；同理，當(dāng)中有一個(gè)不為零時(shí)，它們的公約數(shù)是有限的.這樣,我們引入最大公約數(shù)的概念。定義:設(shè)，是兩個(gè)整數(shù)，我們把和的公約數(shù)中最大的數(shù)稱為和的最大公約數(shù)，記為(,)或當(dāng)時(shí)，我們稱和是互素的。顯然5.最大公約數(shù)與最小公倍數(shù)35最大公約數(shù)的性質(zhì)（1）（2）若|,j=2,…,k，則（3）任意的整數(shù)x,有（4）對(duì)任意的整數(shù)x,有（5）設(shè),是不都為零的整數(shù)，則一定存在一對(duì)整數(shù),，使得：最大公約數(shù)的性質(zhì)36最小公倍數(shù)的概念設(shè)，是兩個(gè)均不等于零的整數(shù)，如果且，那么1就稱為是和的公倍數(shù)，一般地，設(shè)是k個(gè)均不等于零的整數(shù)。如果，則稱l是的公倍數(shù)。公倍數(shù)的集合是無(wú)窮集合，但根據(jù)自然數(shù)的理論，存在最小的正的公倍數(shù)。我們把和的正的公倍數(shù)中最小的數(shù)稱為和的最小公倍數(shù)，記為或最小公倍數(shù)的概念設(shè)，是兩376.歐拉（Euler）函數(shù)歐拉（Euler）函數(shù)

設(shè)n≥1,歐拉函數(shù)表示在區(qū)間中與n互素的整數(shù)的個(gè)數(shù)。歐拉函數(shù)具有以下性質(zhì)：(1)如果p是素?cái)?shù)，則；(2)如果p是素?cái)?shù)，。那么；(3)對(duì)于整數(shù),根據(jù)算術(shù)基本定理，n可以分解成惟一的形如的分解式，則(4)若和互素，則。6.歐拉（Euler）函數(shù)歐拉（Euler）函382.1.3算法復(fù)雜性基礎(chǔ)知識(shí)所謂問(wèn)題，是指一個(gè)要求給出解釋的一般性提問(wèn)，通常含有若干個(gè)未定參數(shù)或自由變量。它由兩個(gè)要素組成，第一個(gè)要素是描述所有的參數(shù)，也就是對(duì)所有未定參數(shù)的一般性描述;第二個(gè)要素是解答必須滿足的性質(zhì)。一個(gè)問(wèn)題可以看成是由無(wú)窮多個(gè)問(wèn)題實(shí)例組成的一個(gè)類。2.1.3算法復(fù)雜性基礎(chǔ)知識(shí)391.算法的定義所謂算法是由明確指出操作的規(guī)則所組成的若干語(yǔ)句的集合，只要按照規(guī)則一步一步執(zhí)行一定數(shù)目的語(yǔ)句，便可求出問(wèn)題的答案。通常的計(jì)算機(jī)程序都可以看作是算法的表達(dá)形式，在問(wèn)題的兩要素中，對(duì)算法而言，第一個(gè)要素就是“輸入”，第二個(gè)要素就是“輸出”。如果把問(wèn)題P的任意一個(gè)實(shí)例作為算法A的輸入，A在有限步驟之內(nèi)總能輸出關(guān)于此實(shí)例的正確答案，我們就說(shuō)算法A可解問(wèn)題P。對(duì)于一個(gè)問(wèn)題P，如果存在一個(gè)算法A可解問(wèn)題P，我們稱問(wèn)題P是算法可解的。1.算法的定義所402.算法復(fù)雜性算法的復(fù)雜性表征了算法在實(shí)際執(zhí)行時(shí)所需計(jì)算能力方面的信息，通常它由該算法所要求的最大時(shí)間與存取空間來(lái)確定。由于算法所需的時(shí)間和空間往往取決于問(wèn)題實(shí)例的規(guī)模n(n表示了該實(shí)例的輸入數(shù)據(jù)長(zhǎng)度)，同時(shí)，算法在用于相同規(guī)模n的不同實(shí)例時(shí)。其時(shí)間和空間需求也可能會(huì)有很大差異，因此，實(shí)際中我們常常研究的是算法關(guān)于輸入規(guī)模的所有實(shí)例的時(shí)間與空間需求的平均值。2.算法復(fù)雜性算法41算法復(fù)雜性的構(gòu)成通常情況下，一個(gè)算法的計(jì)算復(fù)雜性由兩個(gè)變量度量：時(shí)間復(fù)雜性和空間復(fù)雜性。它們定義如下：（1）時(shí)間復(fù)雜性：以某特定的基本步驟為單元，完成計(jì)算過(guò)程所需的總單元數(shù)稱為算法的時(shí)間復(fù)雜性，或時(shí)間復(fù)雜度。n為輸入的規(guī)?；虺叽?。（2）空間復(fù)雜性:以某特定的基本存儲(chǔ)空間為單元，完成計(jì)算過(guò)程所用的存儲(chǔ)單元數(shù)，稱為算法的空間復(fù)雜性或空間復(fù)雜度。n是輸入的規(guī)模或尺寸。算法復(fù)雜性的構(gòu)成通常情42算法復(fù)雜性的基本符號(hào)（1）一個(gè)算法的計(jì)算復(fù)雜性用“O”符號(hào)表示其數(shù)量級(jí)?！癘”的意思是：對(duì)于兩個(gè)任意的實(shí)值函數(shù)f和g，若記號(hào)，則存在有一個(gè)值a，對(duì)充分大的n，有。計(jì)算復(fù)雜性的數(shù)量級(jí)就是這種類型的函數(shù)，即當(dāng)n變大時(shí)增長(zhǎng)得最快的函數(shù)，所有常數(shù)和較低階形式的函數(shù)可以忽略不計(jì)。算法復(fù)雜性的基本符號(hào)（1）一個(gè)算法的計(jì)算復(fù)雜性用“O43算法復(fù)雜性的基本符號(hào)（2）另一個(gè)符號(hào)是“o”。它的定義是：當(dāng)且僅當(dāng)，這意味著在時(shí)，比可以忽略不計(jì)。時(shí)間復(fù)雜度有時(shí)也用工作因子W表示，這時(shí)。如果一個(gè)算法的復(fù)雜性不依賴于n，那么它是常數(shù)級(jí)的用表示之，而表示復(fù)雜性隨n線性增長(zhǎng)，因而是線性型算法。復(fù)雜性隨n線性增長(zhǎng)的其他一些算法也稱為二次方或三次方等，所有這些算法都是多項(xiàng)式的，它們的時(shí)間復(fù)雜性是。有多項(xiàng)式時(shí)間復(fù)雜性的算法稱為多項(xiàng)式時(shí)間算法或有效算法。算法復(fù)雜性的基本符號(hào)（2）另一個(gè)符號(hào)是“o”。它的定443.問(wèn)題的復(fù)雜性問(wèn)題的復(fù)雜性是問(wèn)題固有的性質(zhì)。問(wèn)題的復(fù)雜性理論利用算法復(fù)雜性作為工具，將大量典型的問(wèn)題按照求解的代價(jià)進(jìn)行分類。問(wèn)題的復(fù)雜性由在圖靈機(jī)上解其最難實(shí)例所需的最小時(shí)間與空間決定，還可以理解為由解該問(wèn)題的最有效的算法所需的時(shí)間與空間來(lái)度量。3.問(wèn)題的復(fù)雜性問(wèn)題的復(fù)45NP問(wèn)題在確定型圖靈機(jī)上可用多項(xiàng)式時(shí)間求解的問(wèn)題，稱為易處理的問(wèn)題。易處理的問(wèn)題的全體稱為確定性多項(xiàng)式時(shí)間可解類，記為P類。在非確定性圖靈機(jī)上可用多項(xiàng)式時(shí)間求解的問(wèn)題，稱為非確定性多項(xiàng)式時(shí)間可解問(wèn)題，記為NP問(wèn)題。NP問(wèn)題的全體稱為非確定性多項(xiàng)式時(shí)間可解類，記為NP類。顯然，，因?yàn)樵诖_定型圖靈機(jī)上多項(xiàng)式時(shí)間可解的任何問(wèn)題在非確定型圖靈機(jī)上也是多項(xiàng)式時(shí)間可解的。NP問(wèn)題在確定型圖靈機(jī)上可用多46NPC問(wèn)題NP類中還有一類問(wèn)題稱為NP完全類，記為NPC。所有的NP問(wèn)題都可以通過(guò)多項(xiàng)式時(shí)間轉(zhuǎn)換為NPC中的問(wèn)題。NPC是NP類中困難程度最大的一類問(wèn)題,但NPC中的問(wèn)題困難程度相當(dāng)，都可以多項(xiàng)式時(shí)間轉(zhuǎn)化為稱為可滿足性問(wèn)題的NPC問(wèn)題，此類NPC具有如下性質(zhì)，若其中的任何一個(gè)問(wèn)題屬于P，則所有的NP問(wèn)題都屬于P，且?，F(xiàn)在的密碼算法的安全性都是基于NPC問(wèn)題的，破譯一個(gè)密碼相當(dāng)于求解一個(gè)NPC問(wèn)題,如果，則破譯密碼就是一件很容易的事情.NPC問(wèn)題NP類中還有一類問(wèn)題稱為NP完全類472.2信息加密方式與標(biāo)準(zhǔn)經(jīng)典的信息加密理論主要用于通信保密，而現(xiàn)代信息加密技術(shù)的應(yīng)用已深入到信息安全的各個(gè)環(huán)節(jié)和對(duì)象，信息的加密方式和標(biāo)準(zhǔn)也有了深入廣泛的發(fā)展，特別是現(xiàn)代加密和信息隱藏技術(shù)的結(jié)合，實(shí)現(xiàn)信息隱蔽傳輸使人類對(duì)信息的加密技術(shù)有了新的認(rèn)識(shí)和要求，下面介紹信息加密技術(shù)的基本概念、方式和標(biāo)準(zhǔn)。2.2信息加密方式與標(biāo)準(zhǔn)482.2.1信息加密基本概念（1）研究安全信息的加密技術(shù)和研究破解安全信息密碼的密碼分析技術(shù)的學(xué)科稱為密碼學(xué)。信息加密是通過(guò)使用一種編碼而使某些可讀的信息(明文)變?yōu)椴豢勺x的信息(密文)。這些編碼就是將明文變成密文的加密算法(也稱為密碼)或數(shù)學(xué)方法。密碼使用隱蔽語(yǔ)言、文字、圖象的特種符號(hào)，目標(biāo)是接收數(shù)據(jù)作為輸入，產(chǎn)生密文作為輸出，以便數(shù)據(jù)的原始意義得以隱藏。在計(jì)算機(jī)通訊中，采用密碼（密鑰為參數(shù)）將信息隱蔽起來(lái)，再將隱蔽后的信息傳輸出去，使信息在傳輸過(guò)程中即使被竊取或載獲，也不能了解信息的內(nèi)容，從而保證信息傳輸?shù)陌踩?.2.1信息加密基本概念（1）492.2.1信息加密基本概念（2）

通信兩端將信息編碼時(shí)，發(fā)送端使用簡(jiǎn)單的信息加密；接收端收到傳來(lái)的信息后通過(guò)解密看到編碼前的信息，整個(gè)過(guò)程中加密或解密是由密鑰控制實(shí)現(xiàn)的。密鑰是用戶按照一種密碼體制隨機(jī)選取，它通常是一隨機(jī)字符串，是控制明文變換（加密）和密文變換（解密）的唯一參數(shù)。密鑰全體稱為密鑰空間。一般來(lái)說(shuō)，密鑰越大，加密就越健壯。2.2.1信息加密基本概念（2）50加密系統(tǒng)的組成部分

如上所述，一個(gè)加密系統(tǒng)實(shí)際上是某種加密算法在密鑰控制下實(shí)現(xiàn)的從明文到密文的映射，它至少包括下面四個(gè)組成部分：（1）加密的報(bào)文，也稱明文；（2）加密后的報(bào)文，也稱密文；（3）加密解密設(shè)備或算法；（4）加密解密的密鑰；一般情況下，密鑰由K表示，明文由m表示，加密算法由()表示，解密算法由

()表示，；則，

(

(m))=m

加密系統(tǒng)的組成部分如上所述，一個(gè)51加密系統(tǒng)示意圖一個(gè)完整的加密系統(tǒng)如下圖所示:信源加密解密信宿密文明文竊聽(tīng)干擾明文密鑰K1密鑰K2圖2.2加密系統(tǒng)示意圖加密系統(tǒng)示意圖一個(gè)完整的加密系統(tǒng)如下圖所示:信源加密解密信宿52加密系統(tǒng)的安全規(guī)則（1）任何一個(gè)加密系統(tǒng)必須基本具備四個(gè)安全規(guī)則：（1）機(jī)密性(confidentiality)：加密系統(tǒng)在信息的傳送中提供一個(gè)或一系列密鑰來(lái)把信息通過(guò)密碼運(yùn)算譯成密文，使信息不會(huì)被非預(yù)期的人員所讀取，只有發(fā)送者和接收者應(yīng)該知曉此信息的內(nèi)容。加密系統(tǒng)的安全規(guī)則（1）任何一個(gè)加密系53加密系統(tǒng)的安全規(guī)則（2）（2）完整性(integrity)：數(shù)據(jù)在傳送過(guò)程中不應(yīng)被破壞，收到的信宿數(shù)據(jù)與信源數(shù)據(jù)是一致的。應(yīng)該選取健壯的密碼和加密密鑰，以確保入侵者無(wú)法攻破密鑰或找出一個(gè)相同的加密算法，阻止入侵者會(huì)改變數(shù)據(jù)后對(duì)其重新加密。有時(shí)，數(shù)據(jù)完整性可以通過(guò)適當(dāng)?shù)姆椒ㄔ谛畔⑦€未被完全修改時(shí)檢測(cè)到，如：密碼散列函數(shù)是單向密碼，它為明文產(chǎn)生惟一的“指紋”，當(dāng)明文被攔截和讀取，要修改它將改變散列，致使有意向的接收者很容易看出散列之間的差異。加密系統(tǒng)的安全規(guī)則（2）（2）完整性(integrity)54加密系統(tǒng)的安全規(guī)則（3）

（3）認(rèn)證性(authentication)：加密系統(tǒng)應(yīng)該提供數(shù)字簽名技術(shù)來(lái)使接收信息用戶驗(yàn)證是誰(shuí)發(fā)送的信息，確定信息是否被第三者篡改。只要密鑰還未泄露或與別人共享，發(fā)送者就不能否認(rèn)他發(fā)送的數(shù)據(jù)。實(shí)際應(yīng)用中，假如發(fā)送者和接收者都使用一個(gè)對(duì)稱密鑰，對(duì)于整體信息加密或計(jì)算機(jī)網(wǎng)絡(luò)上的鏈路級(jí)加密，在兩個(gè)路由器之間建立一個(gè)加密會(huì)話，以通過(guò)因特網(wǎng)發(fā)送加密信息。連接到網(wǎng)絡(luò)的計(jì)算機(jī)發(fā)送明文給路由器，明文被轉(zhuǎn)換為密文，然后通過(guò)因特網(wǎng)發(fā)送到另一端的路由器。在整個(gè)加密數(shù)據(jù)形成和傳遞過(guò)程中，加密方網(wǎng)絡(luò)內(nèi)部和非加密方的任一節(jié)點(diǎn)都能插入信息，并在這一層次分析，但對(duì)于接收者這一節(jié)點(diǎn)來(lái)說(shuō)你只能判定信息是否來(lái)自某個(gè)特定的網(wǎng)絡(luò)，而要確認(rèn)信息的發(fā)送節(jié)點(diǎn)，這將使驗(yàn)證機(jī)制變得很復(fù)雜。加密系統(tǒng)的安全規(guī)則（3）（3）認(rèn)證性(authenti55加密系統(tǒng)的安全規(guī)則（4）（4）非否定(non-repudiation)：加密系統(tǒng)除了應(yīng)該驗(yàn)證是誰(shuí)發(fā)送的信息外，還要進(jìn)一步驗(yàn)證收到的信息是否來(lái)自可信的源端，實(shí)際上是通過(guò)必要的認(rèn)證確認(rèn)信息發(fā)送者是否可信?，F(xiàn)代健壯的驗(yàn)證方法用加密算法來(lái)比較一些已知的信息段，如PIN(個(gè)人識(shí)別號(hào))判斷源端是否可信。非否定規(guī)則應(yīng)屬于認(rèn)證性規(guī)則中的一部分。一般來(lái)說(shuō)，前三個(gè)規(guī)則一起被稱為CIA。從技術(shù)的角度來(lái)看，所有的加密都提供了私有性和完整性，其余的均由此衍生，這包括非否定和認(rèn)證性規(guī)則。加密系統(tǒng)的安全規(guī)則（4）（4）非否定(non-repud562.2.2信息加密方式

1.信息加密方式分類

對(duì)存儲(chǔ)的文件和網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)包實(shí)施信息加密，其加密方式可以根據(jù)加密系統(tǒng)不同的特征劃分：（1）按密鑰方式劃分

對(duì)稱式加密：收發(fā)雙方使用相同密鑰。加密和解密使用同一密鑰。加密算法和解密算法在對(duì)稱式加密中是相同的，加密和解密使用同一密鑰K表示。

非對(duì)稱式加密：也稱公用密鑰加密，加密和解密使用不同密鑰。它通常有兩個(gè)密鑰，稱為“公鑰”和“私鑰”。它們兩個(gè)必需配對(duì)使用，否則不能打開(kāi)加密文件。這里的“公鑰”是指可以對(duì)外公布的，“私鑰”則不對(duì)外公布，只有持有人知道。加密算法和解密算法在非對(duì)稱式加密中是不相同的；K1是加密密鑰,是公開(kāi)的，稱為公鑰，K2是解密密鑰，稱為私鑰，則須保密。2.2.2信息加密方式

1.信息加密方式分類572種不同方式的加密示意圖

明文解密密鑰K2明文加密密鑰K2KK密文傳輸圖2.2對(duì)稱式加密示意圖明文解密密鑰K2K1K2加密密鑰K2明文

圖2.3非對(duì)稱式加密示意圖2種不同方式的加密示意圖明文解密明文加密KK密文581.信息加密方式分類（2）按保密程度劃分理論上保密的加密：無(wú)論獲取多少密文和有多大的計(jì)算能力，對(duì)于明文始終不能得到唯一解的加密方法。如：采用客觀隨機(jī)一次出來(lái)的密碼就屬于這種加密方式。實(shí)際上保密的加密：從理論的角度是可以破解的，但在現(xiàn)有客觀條件下，無(wú)法通過(guò)計(jì)算來(lái)確定唯一解。（3）按明文形態(tài)劃分模擬信息加密：用來(lái)加密模擬信息。如：動(dòng)態(tài)范圍之內(nèi)，連續(xù)變化的語(yǔ)音信號(hào)的加密。數(shù)字信息加密：用來(lái)加密數(shù)字信息。如：兩個(gè)離散電平構(gòu)成0、1二進(jìn)制關(guān)系的電報(bào)信息的加密。1.信息加密方式分類（2）按保密程度劃分592.數(shù)字簽名

數(shù)字簽名是對(duì)原信息附上加密信息的過(guò)程，是一種身份認(rèn)證技術(shù)，支持加密系統(tǒng)認(rèn)證性和非否定；簽名者對(duì)發(fā)布的原信息的內(nèi)容負(fù)責(zé)，不可否認(rèn)。數(shù)字簽名采用非對(duì)稱式加密（也稱公鑰加密標(biāo)準(zhǔn)）對(duì)信息m使用私鑰K2加密，運(yùn)算如下：S=DK2(m)其中S為簽名，D為解密算法；接收者收到發(fā)送者發(fā)來(lái)的S和m信息，同時(shí)從公開(kāi)媒體找到了發(fā)送者的公鑰K1,發(fā)送者用K2對(duì)S進(jìn)行如下運(yùn)算：EK1(S)=E

K1(DK2(m))=m,E為加密算法；收到的m對(duì)應(yīng)計(jì)算出來(lái)的m，結(jié)果說(shuō)明信息確實(shí)來(lái)源于發(fā)送者，第三方不可能知道私鑰K2，無(wú)法篡改S，發(fā)送者無(wú)法否認(rèn)發(fā)送m信息。在實(shí)際工作中，由于解密計(jì)算緩慢，為了提高簽名速度，m信息往往要經(jīng)過(guò)壓縮或散列處理或盡量取簡(jiǎn)短信息，如公鑰數(shù)據(jù)等。2.數(shù)字簽名60數(shù)字簽名工作流程圖

信息m密鑰K2私鑰K2公鑰K1信息m密鑰K2解密算法密鑰K2簽名S密鑰K2簽名S密鑰K2加密算法密鑰K2圖2.4數(shù)字簽名工作流程圖數(shù)字簽名工作流程圖信息m私鑰K2公鑰K1信息m解密算法簽613.網(wǎng)絡(luò)信息加密

網(wǎng)絡(luò)信息加密的目的是保護(hù)網(wǎng)內(nèi)的數(shù)據(jù)、文件、口令和控制信息，保護(hù)網(wǎng)上傳輸?shù)臄?shù)據(jù)。網(wǎng)絡(luò)加密常用的方式有鏈路加密和端點(diǎn)加密。（1）鏈路加密鏈路加密對(duì)鏈路層數(shù)據(jù)單元進(jìn)行加密保護(hù)，其目的是保護(hù)網(wǎng)絡(luò)節(jié)點(diǎn)之間的鏈路信息安全。這種加密不但對(duì)節(jié)點(diǎn)之間之間傳輸?shù)臄?shù)據(jù)報(bào)文加密，還要把路由信息、校驗(yàn)和控制信息包括數(shù)據(jù)鏈路層的幀頭、位填充和控制序列等都進(jìn)行加密；當(dāng)密文傳輸?shù)侥骋还?jié)點(diǎn)時(shí)，全部解密獲得鏈信息和明文，然后全部加密后發(fā)送往下一個(gè)節(jié)點(diǎn)；對(duì)于這種加密，加密設(shè)備的設(shè)計(jì)相對(duì)復(fù)雜，必須理解鏈路層協(xié)議和必要的協(xié)議轉(zhuǎn)換。3.網(wǎng)絡(luò)信息加密62鏈路加密的優(yōu)缺點(diǎn)鏈路加密非常有效，是因?yàn)閹缀跞魏斡杏孟⒍急患用鼙Ｗo(hù)。加密范圍包括用戶數(shù)據(jù)、路由信息和協(xié)議信息等。因此，攻擊者將不知道通信的發(fā)送和接受者的身份、不知道信息的內(nèi)容、甚至不知道信息的長(zhǎng)度以及通信持續(xù)的時(shí)間。而且，系統(tǒng)的安全性將不依賴任何傳輸管理技術(shù)。密鑰管理也相對(duì)簡(jiǎn)單，僅僅是線路的兩端需要共同的密鑰。線路兩端可以獨(dú)立于網(wǎng)絡(luò)的其他部分更換密鑰。鏈路加密的缺點(diǎn)是：整個(gè)連接中的每段連接都需要加密保護(hù)。對(duì)于包含不同體系機(jī)構(gòu)子網(wǎng)絡(luò)的較大型網(wǎng)絡(luò)，加密設(shè)備、策略管理、密鑰量等方面的開(kāi)銷都是巨大的。另外，在每個(gè)加密節(jié)點(diǎn)，都存在加密的空白段：明文信息，這是及其危險(xiǎn)的，特別是對(duì)于跨越不同安全域的網(wǎng)絡(luò)。后來(lái)，為解決節(jié)點(diǎn)中數(shù)據(jù)是明文的缺點(diǎn)，在節(jié)點(diǎn)內(nèi)增加了加解裝置，避免了節(jié)點(diǎn)明文，這種加密方式稱為節(jié)點(diǎn)加密；但和鏈－鏈加密一樣，同樣依靠公共網(wǎng)絡(luò)節(jié)點(diǎn)資源的配合，開(kāi)銷依然很大。鏈路加密的優(yōu)缺點(diǎn)63端點(diǎn)加密

端點(diǎn)加密的是對(duì)源端用戶到目的端用戶的數(shù)據(jù)提供加密保護(hù)。既將加密模塊置于網(wǎng)絡(luò)以上的加密方式。端點(diǎn)加密中，數(shù)據(jù)從加密的端節(jié)點(diǎn)，一直到對(duì)應(yīng)的解密節(jié)點(diǎn)，數(shù)據(jù)在整個(gè)傳輸過(guò)程中都保持密文形式，從而克服了鏈路加密出現(xiàn)加密空白段（中間節(jié)點(diǎn)明文信息）的問(wèn)題。由于加密和解密只發(fā)生在兩個(gè)端節(jié)點(diǎn)，因此對(duì)中間節(jié)點(diǎn)是透明的。這樣大大減少了安裝設(shè)備的開(kāi)銷（特別是中間節(jié)點(diǎn)設(shè)備開(kāi)銷），以及復(fù)雜的策略管理和密鑰管理所引起的麻煩。由于加密范圍往往集中在高層協(xié)議數(shù)據(jù)，還極易為不同流量提供QoS服務(wù)，實(shí)現(xiàn)按特定流量進(jìn)行加密和不同強(qiáng)度的加密。從而有利于提高系統(tǒng)的效能，優(yōu)化系統(tǒng)的性能。端點(diǎn)加密端點(diǎn)加密的是對(duì)源64端點(diǎn)加密的缺點(diǎn)

端點(diǎn)加密的缺點(diǎn)是：由于通信環(huán)境往往比較復(fù)雜，要在跨越網(wǎng)絡(luò)的兩個(gè)端用戶之間成功地完成密鑰的建立是需要付出性能代價(jià)的。其次，端點(diǎn)加密不能保護(hù)數(shù)據(jù)傳輸過(guò)程中的某些信息，如路由信息、協(xié)議信息等，一個(gè)訓(xùn)練有素的攻擊者可以借助這些信息發(fā)動(dòng)某些流量分析攻擊。另外，端點(diǎn)加密設(shè)備（模塊）的實(shí)現(xiàn)十分復(fù)雜，要求設(shè)備必須理解服務(wù)的提供層的協(xié)議，并且成功調(diào)用這些服務(wù)，然后在設(shè)備中對(duì)對(duì)應(yīng)的數(shù)據(jù)進(jìn)行密碼處理，并且將處理后的數(shù)據(jù)傳送給上層協(xié)議。如果加密設(shè)備不能為上層協(xié)議提供良好的服務(wù)接口，則將對(duì)通信的性能產(chǎn)生較大的影響。

端點(diǎn)加密的缺點(diǎn)端點(diǎn)加密的缺點(diǎn)652.2.3數(shù)據(jù)加密標(biāo)準(zhǔn)

1.對(duì)稱密鑰加密DES

DES(dataencryptionstandard)是1976年由美國(guó)國(guó)家標(biāo)準(zhǔn)局頒布的一種加密算法，屬于對(duì)稱密鑰加密算法體制，早期被公認(rèn)為較好的加密算法，經(jīng)過(guò)長(zhǎng)期嚴(yán)驗(yàn)證后，被國(guó)際標(biāo)準(zhǔn)化組織接受作為國(guó)際標(biāo)準(zhǔn)。DES自它應(yīng)用20多年來(lái)，不斷經(jīng)受了許多科學(xué)家破譯，同時(shí)也成為密碼界研究的重點(diǎn)。DES對(duì)稱密鑰加密算法廣泛的應(yīng)用在民用密碼領(lǐng)域，為全球貿(mào)易、金融等非官方部門提供了可靠的通信安全保障。2.2.3數(shù)據(jù)加密標(biāo)準(zhǔn)

1.對(duì)稱密鑰加密DES66DES的相關(guān)知識(shí)DES主要采用替換和移位的加密方法用56位密鑰對(duì)64位二進(jìn)制數(shù)據(jù)塊進(jìn)行加密，加密每次可對(duì)64位的輸入數(shù)據(jù)進(jìn)行16輪編碼，經(jīng)過(guò)一系列替換和移位后，原始的64位輸入數(shù)據(jù)轉(zhuǎn)換成了完全不同的64位輸出數(shù)據(jù)。DES算法運(yùn)算速度快，生成密鑰容易，適合于在當(dāng)前大多數(shù)計(jì)算機(jī)上用軟件方法和專用芯片上實(shí)現(xiàn)。但DES密鑰太短（56位），密鑰健壯性不夠好，降低保密強(qiáng)度；同時(shí)，DES安全性完全依賴于對(duì)密鑰的保護(hù)，在網(wǎng)絡(luò)環(huán)境下使用，分發(fā)密鑰的信道必須具備有力的可靠性才能保證機(jī)密性和完整性。DES算法還有一些變形，如：三重DES和廣義DES等。目前，DES應(yīng)用領(lǐng)域主要包括：計(jì)算機(jī)網(wǎng)絡(luò)通信中的數(shù)據(jù)保護(hù)（只限于民用敏感信息）；電子資金加密傳送；保護(hù)用戶存儲(chǔ)文件，防止了未授權(quán)用戶竊密；計(jì)算機(jī)用戶識(shí)別等。DES的相關(guān)知識(shí)DES主要采用替672.Clipper加密芯片標(biāo)準(zhǔn)這種數(shù)據(jù)加密標(biāo)準(zhǔn)對(duì)用戶只提供加密芯片（Clipper）和硬件設(shè)備，它的密碼算法不公開(kāi)，密鑰量比DES多1000多萬(wàn)倍，是美國(guó)國(guó)家保密局（NSA）在1993年正式使用的新的商用數(shù)據(jù)加密標(biāo)準(zhǔn)，目的是取代DES，提高密碼算法的安全性，主要用于通信交換系統(tǒng)中電話、傳真和計(jì)算機(jī)通信信息的安全保護(hù)。為確保更可靠的安全性，加密設(shè)備的制作方法按照Clipper芯片由一個(gè)公司制造裸片，再由另一公司編程嚴(yán)格規(guī)定來(lái)實(shí)施。Clipper芯片主要特點(diǎn)是充分利用高的運(yùn)算能力的設(shè)備資源加大密鑰量，從而用于計(jì)算機(jī)通信網(wǎng)上的信息加密，如：政府和軍事通信網(wǎng)中數(shù)據(jù)加密芯片的研究不斷換代使它還實(shí)現(xiàn)了數(shù)字簽名標(biāo)準(zhǔn)和保密的哈希函數(shù)標(biāo)準(zhǔn)以及用純?cè)肼曉串a(chǎn)生隨機(jī)數(shù)據(jù)的算法等。2.Clipper加密芯片標(biāo)準(zhǔn)683.國(guó)際數(shù)據(jù)加密標(biāo)準(zhǔn)這種算法是在DES算法的基礎(chǔ)上發(fā)展的。與DES相同，國(guó)際數(shù)據(jù)加密算法IDEA（internationaldataencryptionalgorithm）也是針對(duì)數(shù)據(jù)塊加密；它采用128位密鑰，設(shè)計(jì)了一系列加密輪次，每輪加密都使用從完整的加密密鑰中生成的一個(gè)子密鑰，基于這種算法，采用軟件實(shí)現(xiàn)和采用硬件實(shí)現(xiàn)同樣快速，非常適合于對(duì)大量的明文信息的快速加密。它在1990年正式公布并在以后得到了增強(qiáng)。3.國(guó)際數(shù)據(jù)加密標(biāo)準(zhǔn)69傳統(tǒng)加密方法的缺點(diǎn)

在網(wǎng)絡(luò)通信中，傳統(tǒng)的對(duì)稱加密方法是發(fā)送者加密、接收者解密使用同樣的密鑰，這種方法雖然有運(yùn)算快的特點(diǎn)，隨著用戶的增加，大量密鑰的分配是一個(gè)難以解決的問(wèn)題。例如，若系統(tǒng)中有n個(gè)用戶，其中每?jī)蓚€(gè)用戶之間需要建立密碼通信，則系統(tǒng)中每個(gè)用戶須掌握(n-1)/2個(gè)密鑰，而系統(tǒng)中所需的密鑰總數(shù)為n*(n-1)/2個(gè)。對(duì)10個(gè)用戶，每個(gè)用戶必須有9個(gè)密鑰，系統(tǒng)中密鑰的總數(shù)為45個(gè)。對(duì)100個(gè)用戶，每個(gè)用戶必須有99個(gè)密鑰，系統(tǒng)中密鑰的總數(shù)為4950個(gè)。這還僅考慮用戶之間的通信只使用一種會(huì)話密鑰的情況。如此龐大數(shù)量的密鑰生成、管理、分發(fā)確實(shí)是一個(gè)難處理的問(wèn)題。因此，對(duì)稱加密方法所帶來(lái)的密鑰的弱的健壯性和密鑰管理的復(fù)雜性局限了它的發(fā)展。傳統(tǒng)加密方法的缺點(diǎn)在網(wǎng)絡(luò)通信704.公開(kāi)密鑰加密標(biāo)準(zhǔn)早在20世紀(jì)70年代，美國(guó)斯坦福大學(xué)的兩名學(xué)者迪菲和赫爾曼提出了一種加密方法――公開(kāi)密鑰加密方法，解決了傳統(tǒng)加密體系的密匙分配復(fù)雜的缺點(diǎn)。公開(kāi)密鑰加密方法是非對(duì)稱加密方式，該技術(shù)采用不同的加密密鑰和解密密鑰對(duì)信息加密和解密，每個(gè)用戶有一個(gè)對(duì)外公開(kāi)的加密算法E和對(duì)外保密的解密算法D，它們須滿足條件：（1）D是E的逆，即D[E（X）]=X。（2）E和D容易計(jì)算。（3）如果由E出發(fā)求解D十分困難。4.公開(kāi)密鑰加密標(biāo)準(zhǔn)早在20世紀(jì)771公鑰及私鑰的概念若加密密鑰可對(duì)外公開(kāi)，稱為公鑰；一個(gè)用戶向另一用戶傳送信息，首先通過(guò)開(kāi)放途徑(如BBS)的獲得另一用戶的公開(kāi)密鑰，對(duì)明文加密后發(fā)送，而另一用戶唯一保存的解密密鑰是保密的，稱為私鑰，另一用戶通過(guò)安全的方法驗(yàn)證信源可靠后，私鑰將密文復(fù)原、解密。理論上解密密鑰可由加密密鑰推算出來(lái)，但這種算法設(shè)計(jì)在實(shí)際上是不可能的，或者雖然能夠推算出，但要花費(fèi)很長(zhǎng)的時(shí)間和代價(jià)，所以，將加密密鑰公開(kāi)不會(huì)危害密鑰的安全。公鑰及私鑰的概念若加密密鑰可對(duì)外公開(kāi)，72RSA算法著名的RSA正是基于這種理論，算法以發(fā)明者的名字命名：RonRivest,AdiShamir和LeonardAdleman.這種算法為公用網(wǎng)絡(luò)上信息的加密和鑒別提供了一種基本的方法。為提高保密強(qiáng)度，RSA密鑰至少為500位長(zhǎng)，一般推薦使用1024位，這就使加密的計(jì)算量很大。同時(shí)，為減少計(jì)算量，在傳送信息時(shí)，常采用傳統(tǒng)對(duì)稱加密方法與RSA公開(kāi)密鑰加密方法相結(jié)合的方式，信息明文加密采用改進(jìn)的DES或IDEA加密方法，使用RSA用于加密密鑰和信息摘要。對(duì)方收到信息后，用各自相關(guān)的密鑰解密并可核對(duì)信息。但是RSA并不能替代DES等對(duì)稱算法，RSA的密鑰長(zhǎng)，加密速度慢，而采用DES等對(duì)稱算法加密速度快，適合加密較長(zhǎng)的報(bào)文，彌補(bǔ)了RSA的缺點(diǎn)。美國(guó)的保密增強(qiáng)郵件系統(tǒng)（PEM）就是采用了RSA和DES結(jié)合的方法，目前已成為E-MAIL保密通信標(biāo)準(zhǔn)。RSA算法著名的RSA735.量子加密方法

量子加密與公鑰加密標(biāo)準(zhǔn)同期出現(xiàn)，適用于網(wǎng)絡(luò)上加密普通寬帶數(shù)據(jù)信道所傳送的信息，工作原理是兩端用戶各自產(chǎn)生一個(gè)私有的隨機(jī)數(shù)字符串，兩個(gè)用戶向?qū)Ψ降慕邮苎b置發(fā)送代表數(shù)字字符串的單個(gè)量子序列（光脈沖），接受裝置從兩個(gè)字符串中取出相匹配的比特值組成了密鑰。實(shí)現(xiàn)了會(huì)話或交換密鑰的傳遞。由于這種方法依賴的是量子力學(xué)定律，傳輸?shù)墓饬孔邮菬o(wú)法被竊聽(tīng)的；如果有人進(jìn)行竊聽(tīng)，就會(huì)對(duì)通信系統(tǒng)造成干擾，對(duì)通信系統(tǒng)的量子狀態(tài)造成不可挽回的變化，通信雙方就會(huì)得知有人進(jìn)行竊聽(tīng)，從而結(jié)束通信，重新生成密鑰。這種加密技術(shù)不久的將來(lái)應(yīng)該有應(yīng)用和發(fā)展，但是如何實(shí)現(xiàn)數(shù)字簽名有待于研究。5.量子加密方法742.3公鑰信息加密算法

隨著密碼技術(shù)的發(fā)展，Diffie和Hellman在IEEE提出提出了公鑰密碼系統(tǒng)，即加密密鑰和解密密鑰不是同一把密鑰。現(xiàn)在公鑰密碼系統(tǒng)被廣泛的應(yīng)用，其中RSA加密算法，Diffie-Hellman算法，ElGamal加密算法，橢圓曲線加密算法被廣泛研究和應(yīng)用。2.3公鑰信息加密算法隨著密碼技術(shù)752.3.1RSA加密算法RSA的安全性依賴于大數(shù)分解。公鑰及私鑰都是兩個(gè)大素?cái)?shù)（大于100個(gè)十進(jìn)制位）的函數(shù)，從一個(gè)密鑰和密文推斷出明文的難度等同于分解兩個(gè)大素?cái)?shù)的積。算法如下：

１.生成密鑰（1）秘密的選取兩個(gè)大數(shù)p,q（2）計(jì)算,,這指的是Euler函數(shù)（3）選取整數(shù)e，滿足且。（4）計(jì)算d,滿足。即d是e關(guān)于模乘的逆元，（乘法逆元：設(shè)，如果存在，滿足，則稱x是a的模n乘法逆元，記為

(modn)

）由e的定義，d唯一。（5）輸出公鑰,私鑰。2.3.1RSA加密算法RSA的76具體加密解密操作

加密操作選定,把明文分成長(zhǎng)度為k的組塊。對(duì)每個(gè)明文分組M,M在0到(n-1)之間。加密操作為：

解密操作得到密文分組C，解密操作為：

(2.14)

(2.15)具體加密解密操作加密操作(2.14)(2.177RSA算法的局限性（1）（1）有限的安全性

RSA是一種分組密碼算法，它的安全是基于數(shù)論中大的整數(shù)n分解為兩個(gè)素?cái)?shù)之積的難解性。目前，RSA的一些變種算法已被證明等價(jià)于大數(shù)分解。同樣，分解n也是最顯然的攻擊方法?，F(xiàn)在，人們已能分解140多個(gè)十進(jìn)制位的大素?cái)?shù)。因此，適用具體情況而定，模數(shù)n必須選盡可能大。同時(shí)要注意，如果系統(tǒng)中共享一個(gè)模數(shù)，不同的人擁有不同的公鑰e1和e2，這些公鑰共模而且互質(zhì)，假如普遍的情況是同一信息用不同的公鑰加密，那么該信息無(wú)需私鑰就可得到恢復(fù)。即設(shè)P為信息明文，C1和C2為密文，公共模數(shù)是n，則：C1=P^e1modn；C2=P^e2modn密碼分析者知道n、e1、e2、C1和C2，就能得到P。解決辦法只有一個(gè)，那就是不要共享模數(shù)n。RSA算法的局限性（1）（1）有限的安全性78RSA算法的局限性（2）

（2）運(yùn)算速度慢

RSA算法進(jìn)行的都是大數(shù)計(jì)算，使得其最快的情況也比DES慢上100倍，無(wú)論是軟件實(shí)現(xiàn)還是硬件實(shí)現(xiàn)。速度一直是RSA算法的缺陷。一般來(lái)說(shuō)RSA算法只用于少量數(shù)據(jù)加密。有一種提高RSA速度的建議是使公鑰e取較小的值，這樣會(huì)使加密變得易于實(shí)現(xiàn)，速度有所提高。但這樣作是不安全的，公鑰e和私鑰d還是都取較大的值為好。但是，RSA算法是第一個(gè)能同時(shí)用于加密和數(shù)字簽名的算法，也易于理解和操作。經(jīng)歷了各種攻擊的考驗(yàn)和最廣泛的研究，從提出到現(xiàn)在已近二十年，逐漸為人們認(rèn)為是目前最適用的公鑰算法之一。RSA算法的局限性（2）（2）運(yùn)算速度慢792.3.2Diffie-Hellman算法Diffie和Hellman在1976年公開(kāi)發(fā)表的第一個(gè)公鑰密碼算法定義了公鑰密碼學(xué)。論文中提出一個(gè)密鑰交換系統(tǒng)，讓網(wǎng)絡(luò)互不相見(jiàn)的兩個(gè)通信體，可以共享一把鑰匙，用以證明公開(kāi)密鑰的概念的可行性。這個(gè)算法本身基于計(jì)算對(duì)數(shù)難度，其目的是實(shí)現(xiàn)兩個(gè)用戶之間安全地交換密鑰以便于后續(xù)的數(shù)據(jù)加密。Diffie-Hellman密鑰交換算法在現(xiàn)在的許多商用產(chǎn)品中使用。2.3.2Diffie-Hellman算法80Diffie-Hellman算法描述

算法描述如下：給定公開(kāi)素?cái)?shù)q和q的本原根r。即r∈{1,2,3,4,…(q-1)},且{1,2,3,4,…(q-1)}＝{modq,modq,modq,…modq}則對(duì)b∈{1,2,3,4,…(q-1)},可以唯一的指數(shù)i，使得b=modq。

用戶A,B交換密鑰的方法如下：（1）用戶A選擇一個(gè)隨機(jī)數(shù),計(jì)算,A將秘密保存而將公開(kāi)。（2）用戶B選擇一個(gè)隨機(jī)數(shù),計(jì)算,B將秘密保存而將公開(kāi)。（3）A將送給B，B將送給A,（A并不知道,B并不知道）（4）用戶A計(jì)算密鑰：；（5）用戶B計(jì)算密鑰：；Diffie-Hellman算法描述算法描述如下：812.3.3ElGamal加密算法EIGamal體制是T.EIGamal在1985年發(fā)表的“Apublic-keycryptosystemandasignaturesschemebasedondiscretelogarithms”(一個(gè)基于離散對(duì)數(shù)的共鑰密碼體制和數(shù)學(xué)簽名方案)論文中提出的公開(kāi)密匙密碼體制。下面給出的EIGamal體制在論文中用于數(shù)據(jù)加密的算法。采用EIGamal公開(kāi)密匙密碼體制的密碼系統(tǒng)中，所有的用戶都共享一個(gè)素?cái)?shù)P以及一個(gè)Z的生成元g,明文空間P=Z,密文空間

,選定0<a<p,計(jì)算秘密密鑰：a公開(kāi)密鑰：b2.3.3ElGamal加密算法82ElGamal加密解密算法加密算法：設(shè)明文為m,0≤m<p,隨機(jī)的選取正整數(shù)k,0≤k<p,gcd(k,p-1)=1,計(jì)算密文對(duì)y1,y2：

密文。

解密算法：可見(jiàn)，EIGamal體制的密文不是唯一的，這是一種非確定性加密方式。顯然增加了系統(tǒng)的安全性，但是，代價(jià)是密文膨脹了兩倍。ElGamal加密解密算法加密算法：設(shè)明文為m,0≤832.3.4橢圓曲線加密算法定義

定義：橢圓曲線指的是由韋爾斯特拉斯方程所確定的平面曲線。其中，系數(shù)（i=1，2，…，6）定義在基域K上（K可以是有理數(shù)域、實(shí)數(shù)域、復(fù)數(shù)域，還可以是有限域，橢圓曲線密碼體制中用到的橢圓曲線都定義在有限域上）2.3.4橢圓曲線加密算法定義84橢圓曲線加密算法相關(guān)知識(shí)

1985年，Koblitz和Miller相互獨(dú)立地開(kāi)發(fā)提出了在密碼學(xué)中應(yīng)用橢圓曲線（ElipticalCurve）構(gòu)造公開(kāi)密鑰密碼體制的思想。這一算法一出現(xiàn)便受到關(guān)注，由于基于橢圓曲線的公開(kāi)密鑰密碼體制開(kāi)銷?。ㄋ璧挠?jì)算量?。?、安全性高等優(yōu)點(diǎn)，隨著橢圓曲線的公開(kāi)密鑰密碼體制極大的發(fā)展，它將替代RSA成為通用的公鑰密碼算法。實(shí)踐表明，在32位的PC機(jī)上和16位微處理器上運(yùn)行橢圓曲線密碼算法，其中16位微處理器上的數(shù)字簽名不足500ms。因此，應(yīng)用橢圓曲線的數(shù)字簽名可以很容易地在小的有限資源的設(shè)備中使用。橢圓曲線加密算法相關(guān)知識(shí)1985851.有限域上的橢圓曲線算法的提出

設(shè)K表示一個(gè)有限域，E是域K上的橢圓曲線，則E是一個(gè)點(diǎn)的集合：E/K={(x,y)|y2+a1xy+a3y=x3+a2x2+a4x+a6,a1,a3,a2,a4,a6

x,y

K}{O}其中O表示無(wú)窮遠(yuǎn)點(diǎn)。在E上定義‘+’運(yùn)算，P+Q=R，R是過(guò)P、Q的直線與曲線的另一交點(diǎn)關(guān)于x軸的對(duì)稱點(diǎn)，當(dāng)P=Q時(shí)R是P點(diǎn)的切線與曲線的另一交點(diǎn)關(guān)于x軸的對(duì)稱點(diǎn)。這樣，(E,+)構(gòu)成可換群(Abel群)，O是加法單位元(零元)。橢圓曲線離散對(duì)數(shù)問(wèn)題定義如下：給定定義在K上的橢圓曲線E，一個(gè)n階的點(diǎn)PE/K，和點(diǎn)QE/K，如果存在l，確定整數(shù)l,0,l,n-1,Q=lP。我們知道，RSA是基于因子分解，其算法的核心就是如何尋找大數(shù)的因子分解，但大數(shù)的因子分解是比因子分解難得多的問(wèn)題。橢圓曲線上的加法:P+Q=R是橢圓曲線上一點(diǎn)的2倍:P+P=R.基于該難題，1985年N.Koblitz和Miller提出將橢圓曲線用于密碼算法，分別利用有限域上橢圓曲線的點(diǎn)構(gòu)成的群實(shí)現(xiàn)了離散對(duì)數(shù)密碼算法。1.有限域上的橢圓曲線算法的提出862.橢圓曲線上的密碼算法

橢圓曲線加密系統(tǒng)由很多依賴于橢圓曲線離散對(duì)數(shù)算法問(wèn)題的加密系統(tǒng)組成:（1）知E(Fn)對(duì)點(diǎn)的“

”運(yùn)算形成一個(gè)Abel群，設(shè)p∈E(Fn)，若p的周期很大，即使p

p

……

p=θ

(共有t個(gè)p相加)成立的最小正整數(shù)t，希望t很大(t=p的周期，表示為∏(p)=t)，并且對(duì)Q∈E(Fq)，定有某個(gè)正整數(shù)m使Q=m?p=p

……

p(共有m個(gè)p相加)定義m=㏒n

Q(m為以n為底Q的對(duì)數(shù))橢圓曲線上的點(diǎn)形成的群E(Fn)，相關(guān)它的離散對(duì)數(shù)問(wèn)題是難處理的。2.橢圓曲線上的密碼算法87建立橢圓曲線密碼體制

選取基域Fn，F(xiàn)n的橢圓曲線具體給定為確定的形式。在E(Fn)中選一個(gè)周期很大的點(diǎn)，如選了一個(gè)點(diǎn)P=(xn,yn)，它的周期為一個(gè)大的素?cái)?shù)n，記∏(P)=n(素?cái)?shù))。注意：在這個(gè)密碼體制中，具體的曲線及點(diǎn)P和它的n都是公開(kāi)信息。密碼體制的形式采用EIGamal體制，是完全類比過(guò)來(lái)。建立橢圓曲線密碼體制88建立橢圓曲線密碼的方法使用者執(zhí)行了下列計(jì)算：a)在區(qū)間[1,n-1]中隨機(jī)選取一個(gè)整數(shù)d；b)計(jì)算點(diǎn)Q:=dP(d個(gè)P相

)；c)使用者公開(kāi)自己的公開(kāi)密鑰——(E(Fn),p,n,Q)；d)使用者的私鑰為整數(shù)d；發(fā)送者要發(fā)送消息m給使用者，執(zhí)行：a)查找使用者的公鑰(E(Fn),p,n,Q),b)將m表示成一個(gè)域元素m∈Fn，c)在區(qū)間[1，n-1]內(nèi)選取一個(gè)隨機(jī)數(shù)k,d)依據(jù)使用者的公鑰計(jì)算點(diǎn)(x1,y1):=kP(k個(gè)P相

)，e)計(jì)算點(diǎn)(x2，y2):=kQ,如果x2=0,則回到第c步計(jì)算C:=m?x2；f)傳送加密數(shù)據(jù)(x1,y1,C)給使用者；使用者收到發(fā)送者的密文(x,y,C)后，執(zhí)行解密過(guò)程：a)使用私鑰d，計(jì)算點(diǎn)(x2，y2):=d(x1,y1)，再計(jì)算Fn中

，b)通過(guò)計(jì)算m:=C?

，恢復(fù)出明文數(shù)據(jù)m。建立橢圓曲線密碼的方法使用者執(zhí)行了下列計(jì)算：892.4信息加密產(chǎn)品簡(jiǎn)介

信息加密產(chǎn)品隨著加密技術(shù)的應(yīng)用和發(fā)展出現(xiàn)了良好的商業(yè)化趨勢(shì)，比較常用的信息加密軟件有PGP和CryptoAPI，作為開(kāi)放的軟件工具，它們的使用為深入開(kāi)展信息加密技術(shù)的研究提供了幫助。下面分別介紹PGP和CryptoAPI。2.4信息加密產(chǎn)品簡(jiǎn)介信息加密902.4.1PGP加密軟件簡(jiǎn)介PGP(pretty

good

privacy)是一個(gè)對(duì)郵件和傳輸?shù)奈膿踹M(jìn)行加密的軟件，可以用來(lái)對(duì)郵件和文擋保密以防止非授權(quán)者閱讀，讓你可以安全地和你從未見(jiàn)過(guò)的人們通信。PGP軟件綜合了目前健壯的加密方法和加密系統(tǒng)認(rèn)證性方面的新手段，功能強(qiáng)大有很快的速度，是一種比較實(shí)用和安全的加密工具。PGP軟件創(chuàng)始人是美國(guó)的Phil

Zimmermann，由于許多版本不受密碼出口管制，源代碼也是免費(fèi)的，獲取比較方便。2.4.1PGP加密軟件簡(jiǎn)介911.PGP采用的加密標(biāo)準(zhǔn)PGP

用的是公匙加密和傳統(tǒng)加密的雜合算法，這種算法創(chuàng)造性在于他把公匙加密體系的方便和傳統(tǒng)加密體系的高速度結(jié)合起來(lái)，充分利用多個(gè)算法各自的優(yōu)點(diǎn)應(yīng)用于明文加密和密匙認(rèn)證管理機(jī)制中，形成了整個(gè)加密系統(tǒng)巧妙的設(shè)計(jì)。PGP實(shí)際上用來(lái)對(duì)明文加密采用了IDEA的傳統(tǒng)加密算法。IDEA的加（解）密速度比公匙加密算法如RSA快得多，但主要缺點(diǎn)就是密匙的傳遞渠道解決不了安全性問(wèn)題，不適合網(wǎng)絡(luò)環(huán)境加密需要。因此，PGP每次加密都可以隨機(jī)生成密匙用IDEA算法對(duì)明文加密，然后在用密匙的傳遞中用公匙加密算法，一般是使用不適合加密大量數(shù)據(jù)的RSA或Diffie-Hellman算法對(duì)該密匙加密來(lái)保證傳遞渠道的安全性，這樣收件人同樣是用RSA或Diffie-Hellman解密出這個(gè)隨機(jī)密匙，再用IDEA解密出明文。1.PGP采用的加密標(biāo)準(zhǔn)PGP92PGP加密方法示意圖

解密密鑰K2明文密鑰K加密密鑰K2明文加密密鑰K2發(fā)送者接收者IDEA加密密文接收者的公鑰K1公鑰加密密文解密密鑰K2接收者的私鑰K2密鑰K圖4.1PGP加密方法示意圖PGP加密方法示意圖解密明文密鑰K加密明文加密932.PGP的密匙管理（1）在PGP中如果IDEA密匙是通過(guò)網(wǎng)絡(luò)傳送而不加密，網(wǎng)絡(luò)黑客們就會(huì)“監(jiān)聽(tīng)”而獲取密匙，整個(gè)傳輸肯定危險(xiǎn)，因此，必須通過(guò)必要可靠的密匙管理來(lái)保證信息發(fā)送和接收的安全性。一個(gè)成熟的加密系統(tǒng)必然要有一個(gè)成熟的密匙管理機(jī)制配套，公匙加密體系可以解決傳統(tǒng)加密體系的密匙分配難保密的缺點(diǎn)，PGP中應(yīng)用RSA或Diffie-Hellman算法實(shí)施密匙分配。2.PGP的密匙管理（1）在PG942.PGP的密匙管理（2）但是，分配過(guò)程中首先要獲取對(duì)方公匙，如果公匙被篡改，所獲得的公匙成了偽造的，密匙分配就會(huì)傳遞給篡改者，篡改者可以用自己的私匙解密獲得密匙。這可能是公匙密碼體系中最大的漏洞和安全性問(wèn)題，你必須確信你拿到的公匙屬于它看上去屬于的那個(gè)人。防止這種情況出現(xiàn)的最好辦法是避免讓任何其他人有機(jī)會(huì)篡改公匙，比如直接從要接收信息的人手中得到公匙，然而當(dāng)在千里之外或無(wú)法見(jiàn)到時(shí)，這是很困難的。2.PGP的密匙管理（2）但是，952.PGP的密匙管理（3）解決這個(gè)問(wèn)題一般方法是數(shù)字簽名，直接認(rèn)證你的信息接收者的公匙，防止篡改公匙；而PGP則在此基礎(chǔ)上發(fā)展了一種公匙介紹機(jī)制來(lái)解決這個(gè)問(wèn)題，舉例來(lái)說(shuō)：如果你和接收信息的人有一個(gè)共同的朋友，而朋友知道他手中的你的接收信息的人的公匙是正確的，這樣朋友可以用他自己的私匙在你的接收信息的人的公匙上加