第二章信息論及數(shù)學(xué)基礎(chǔ)

1、信息論與數(shù)學(xué)基礎(chǔ)熵v“熵”是德國(guó)物理學(xué)家克勞修斯在年創(chuàng)造的一個(gè)定義，他用熵的定義來(lái)表示任何一種能量在空間中分布的均勻程度。v能量分布得越均勻，熵就越大。v如果對(duì)于我們所考慮的那個(gè)系統(tǒng)來(lái)說(shuō)，能量完全均勻地分布，那么，這個(gè)系統(tǒng)的熵就達(dá)到最大值。 2.1 信息論v1948年由香農(nóng)（claude elmwood shannon）確立了信息論v從通信的實(shí)質(zhì)意義來(lái)講，如果接收者收到的消息是已知的，則等于沒(méi)有收到任何消息。v因此，人們更感興趣的是消息中所包含的未知成分，用概率論的術(shù)語(yǔ)來(lái)講，就是具有不確定性的成分，香農(nóng)將該成分稱(chēng)為信息，并進(jìn)行了數(shù)量描述。2.1 信息論信息量：對(duì)消息的所有可能含義進(jìn)行編碼時(shí)所需

2、要的最少比特?cái)?shù)例如對(duì)于一周中的時(shí)間或性別進(jìn)行有效編碼一條消息中的信息量可以通過(guò)熵來(lái)度量1 熵和不確定性v在1948年由克勞德克勞德艾爾伍德艾爾伍德香農(nóng)香農(nóng)第一次引入到信息論中來(lái)。 v定義 如果有一個(gè)系統(tǒng)S內(nèi)存在多個(gè)事件S = E1,.,En，每個(gè)事件的機(jī)率分布 P = p1, ., pn，則每個(gè)事件本身的信息為：Ie= log2pi（對(duì)數(shù)以2為底，單位是位元(bit)） Ie = lnpi（對(duì)數(shù)以e為底， 單位是納特/nats） v例如1）如英語(yǔ)有26個(gè)字母，假如每個(gè)字母在文章中出現(xiàn)次數(shù)平均的話(huà)，每個(gè)字母的信息量為：2）漢字常用的有2500個(gè)，假如每個(gè)漢字在文章中出現(xiàn)次數(shù)平均的話(huà)，每個(gè)漢字的信

3、息量為 v熵是整個(gè)系統(tǒng)的平均消息量，即：v熵均大于等于零， HS=0v設(shè)N是系統(tǒng)S內(nèi)的事件總數(shù)，則熵HS =log2N。當(dāng)且僅當(dāng)p1=p2=.=pn時(shí)，等號(hào)成立，此時(shí)系統(tǒng)S的熵最大。v 安全角度看消息的熵值描述了明文的不確定性，熵值越小不確定越低，被攻擊的可能性越大。信息熵大，意味著不確定性也大。 v2. 密碼體制的安全性v在密碼學(xué)方面，1949年香農(nóng)發(fā)表保密系統(tǒng)的通信理論，通常它被認(rèn)為是密碼學(xué)的先驅(qū)性著作。v1976年狄菲和赫爾曼首次提出公開(kāi)密鑰體制，為密碼學(xué)的研究開(kāi)辟了新的方向。v超大規(guī)模集成電路和高速計(jì)算機(jī)的應(yīng)用,促進(jìn)了保密編碼理論的發(fā)展,同時(shí)也給保密通信的安全性帶來(lái)很大的威脅。v70年

4、代以來(lái)把計(jì)算機(jī)復(fù)雜性理論引入密碼學(xué),出現(xiàn)了所謂P類(lèi)、NP類(lèi)和NP完全類(lèi)問(wèn)題。算法的復(fù)雜性函數(shù)呈指數(shù)型增長(zhǎng)，因此密鑰空間擴(kuò)大，使密碼的分析和搜索面臨嚴(yán)重的挑戰(zhàn)。密碼學(xué)開(kāi)始向縱深方向發(fā)展。保密編碼:為了防止竊譯而進(jìn)行的再編碼稱(chēng)為保密編碼。其目的是為了隱藏敏感的信息。v常采用替換或亂置或兩者兼有的方法。v一個(gè)密碼體制通常包括兩個(gè)基本部分：加（解）密算法和可以更換的控制算法的密鑰。v密碼根據(jù)它的結(jié)構(gòu)分為序列密碼和分組密碼兩類(lèi)。序列密碼是算法在密鑰控制下產(chǎn)生的一種隨機(jī)序列，并逐位與明文混合而得到密文。其主要優(yōu)點(diǎn)是不存在誤碼擴(kuò)散，但對(duì)同步有較高的要求。它廣泛用于通信系統(tǒng)中。分組密碼是算法在密鑰控制下對(duì)明文

5、按組加密。這樣產(chǎn)生的密文位一般與相應(yīng)的明文組和密鑰中的位有相互依賴(lài)性，因而能引起誤碼擴(kuò)散。它多用于消息的確認(rèn)和數(shù)字簽名中。v密碼學(xué)還研究通過(guò)破譯來(lái)截獲密文的方法。v破譯方法有確定性分析法和統(tǒng)計(jì)性分析法兩類(lèi)。v確定性分析法是利用一個(gè)或幾個(gè)未知量來(lái)表示所期望的未知量從而破譯密文。v統(tǒng)計(jì)分析法是利用存在于明文與密文或密鑰之間的統(tǒng)計(jì)關(guān)系破譯密文。v3 唯一解距離v定義：進(jìn)行強(qiáng)力攻擊時(shí)，可能解密出唯一有意義的明文所需要的最少密文量。v一般來(lái)說(shuō)，唯一解距離越大，密碼體制越好v比解距長(zhǎng)的密文可以合理的確定唯一的有意義的解密文本，比解距短的密文可能會(huì)有多個(gè)同樣等效的解密文本，這樣增加了選擇正確的難度，可以獲得

6、安全性。v定義：U=H(K)/Dv其中D是語(yǔ)言多余度， H(K)密碼體制的熵。v唯一解距很小，密碼體制不安全；但不一定是唯一解距大就一定安全。v4 語(yǔ)言信息率v語(yǔ)言信息率：r=H(M)/Nv其中H(M)是熵，N是消息的長(zhǎng)度v語(yǔ)言的絕對(duì)信息率：R=log2L 其中L是語(yǔ)言中字母數(shù)，R也是單個(gè)字母的最大熵。v語(yǔ)言的多余度：D=R-rv5 混亂和散布v混亂：也可以稱(chēng)為替換v散布：也可以稱(chēng)為置換，位置的變化。2.2 復(fù)雜性理論v分析不同密碼技術(shù)和算法的的“計(jì)算復(fù)雜性”的方法，通過(guò)對(duì)密碼算法及技術(shù)進(jìn)行比較，確定其安全性。v1）算法的復(fù)雜性v一個(gè)算法的復(fù)雜性由兩個(gè)變量來(lái)描述：T(時(shí)間復(fù)雜度)、S（空間復(fù)雜

7、度）， T和S表示為n的函數(shù)，n是輸入尺寸。v一個(gè)算法的復(fù)雜度可以用O符號(hào)表示，O(n2)v時(shí)間復(fù)雜度和空間復(fù)雜度與輸入的尺寸有關(guān)v2）問(wèn)題的復(fù)雜性vP問(wèn)題：能夠在多項(xiàng)式時(shí)間內(nèi)解決的問(wèn)題（時(shí)間復(fù)雜度）vNP問(wèn)題：多項(xiàng)式時(shí)間內(nèi)可驗(yàn)證的問(wèn)題vNP完全問(wèn)題：特殊的問(wèn)題，如果NP完全問(wèn)題解決了，則NP問(wèn)題也解決了。vPSPACE問(wèn)題：比NP復(fù)雜性更高的問(wèn)題。v3） NP完全問(wèn)題v1.整數(shù)分解的問(wèn)題：大整數(shù)分解成素?cái)?shù)相乘，整數(shù)越大越難分解2.背包問(wèn)題v設(shè)長(zhǎng)度為N的向量A=(a1,a2,an),任意給定一個(gè)正整數(shù)K,求解方程xiai=k,即求解向量x=(x1,x2,xn)v當(dāng)n很小可以用窮舉法，但n很大時(shí)

8、就不行了3.離散對(duì)數(shù)問(wèn)題v設(shè)x,r,n是正整數(shù)，已知x,r,n可以很快求出 y=xr mod 但反過(guò)來(lái)求r屬于離散對(duì)數(shù)問(wèn)題2.3 密碼學(xué)的必要性v一個(gè)問(wèn)題-密碼學(xué)真的有必要嗎CD Universe信用卡數(shù)據(jù)泄漏案Visa International筆記本失竊案美加州大學(xué)資料庫(kù)被黑事件v有一個(gè)影響很大的例子，就是2000年1月發(fā)生的CDUniverse信用卡數(shù)據(jù)庫(kù)泄露案事件。 一名據(jù)稱(chēng)是來(lái)自俄羅斯的攻擊者成功地通過(guò)因特網(wǎng)拷貝了CDUniverse數(shù)據(jù)庫(kù)中300000個(gè)信用卡號(hào)碼，然后他試圖向CDUniverse勒索保護(hù)費(fèi)。CD Universe拒絕支付這筆錢(qián)，結(jié)果該黑客就在Web上公布了2500

9、0個(gè)信用卡號(hào)碼。v對(duì)于CDUniverse的顧客來(lái)說(shuō)，風(fēng)險(xiǎn)不大，因?yàn)樾庞每ㄊ怯斜Ｗo(hù)的，這種保護(hù)將使用信用卡所要承擔(dān)的風(fēng)險(xiǎn)限制在一個(gè)比較小的范圍內(nèi)，一般是50美元或者更少。v然而對(duì)于CDUniverse來(lái)說(shuō)非常不幸，顧客對(duì)公司的信任度降低了，因面對(duì)他們的業(yè)務(wù)造成了顯著影響。v而如果已經(jīng)使用密碼技術(shù)加密了信用卡號(hào)碼數(shù)據(jù)庫(kù)，那么即使攻擊者能夠拷貝商家的數(shù)據(jù)庫(kù)，他們恐怕也無(wú)法提取其中的信用卡號(hào)碼。Visa International筆記本失竊案v1996年11月，VisaInternational的一臺(tái)筆記本電腦被盜。v不幸的是這臺(tái)筆記本電腦保存了超過(guò)314000個(gè)信用卡號(hào)碼。v公布的替換一張信用卡的

10、成本是20美元，因此這一次盜竊造成的掘失大約為630萬(wàn)美元。v同樣，只要對(duì)存儲(chǔ)在這臺(tái)筆記本電腦硬盤(pán)上的信用卡信息進(jìn)行了加密就不會(huì)有這樣的問(wèn)題發(fā)生，從而會(huì)節(jié)省上百萬(wàn)美元的費(fèi)用。 美加州大學(xué)資料庫(kù)被黑事件v一個(gè)例子v把九陰真經(jīng)發(fā)給我v網(wǎng)絡(luò)環(huán)境下數(shù)據(jù)安全性的要求我要接受來(lái)自黃裳的九陰真經(jīng)安全的要求：1）我能確保經(jīng)文來(lái)自黃裳u 確保文件來(lái)自正確的方向2）我能確保經(jīng)文在因特網(wǎng)上傳輸u 接收方確保接收方確保文件在互聯(lián)網(wǎng)上傳輸時(shí)，沒(méi)有被修改3）沒(méi)有別人能夠看到經(jīng)文，因?yàn)槟鞘前l(fā)送給我的，這樣就防止了經(jīng)文被竊u只有指定的接收者可以看到經(jīng)文，防止文件被竊4）黃裳事后不能否認(rèn)發(fā)送了經(jīng)文給我u發(fā)送方不能否認(rèn)發(fā)送過(guò)文件

11、2.4 密碼學(xué)1.基本概念算法：是解決一個(gè)數(shù)學(xué)問(wèn)題所需要的一組步驟。在計(jì)算機(jī)科學(xué)領(lǐng)域中，算法通常被看作程序的一個(gè)組成部分，通常作為一個(gè)例程或者一個(gè)庫(kù)被引用。 密碼算法(cryptographic algorithm)：是數(shù)學(xué)算法，設(shè)計(jì)密碼算法是為了能夠用不同的數(shù)據(jù)集合作為參數(shù)來(lái)調(diào)用它們，從而在這些數(shù)據(jù)集合上進(jìn)行相應(yīng)的運(yùn)算 密碼服務(wù)提供者(Cryptographic Service Provider，CSP)：從本質(zhì)上講就是可以通過(guò)一套定義良好的接口進(jìn)行調(diào)用的，執(zhí)行特定密碼計(jì)算功能的密碼算法(加密算法、簽名算法等)庫(kù)。 密碼學(xué)家(cryptologist)：是一些數(shù)學(xué)家和研究者，他們絞盡腦汁地發(fā)

12、明新的密碼算法 。密碼破譯者就登場(chǎng)了。他們裝備了強(qiáng)大的工具，全力以赴地分析算法的弱點(diǎn)，圍繞算法的設(shè)計(jì)進(jìn)行各種各樣的拷問(wèn)和攻擊以求攻破該算法。v密碼學(xué)是計(jì)算機(jī)科學(xué)中有著兩個(gè)平行、對(duì)立而又共生的子分支的分支學(xué)科。包括密碼編碼學(xué)密碼編碼學(xué)(cryptography)和密碼分析學(xué)密碼分析學(xué)(cryptanalysis)。2.朦朧安全發(fā)明了一個(gè)加密算法，但卻不提交給密碼破譯者審核但這些算法都是復(fù)雜的數(shù)學(xué)運(yùn)算，一個(gè)人無(wú)法了解該運(yùn)算的所有方面，因此無(wú)法了解所有可能的攻擊。這種算法的安全就稱(chēng)為朦朧安全。朦朧算法不安全的例子1997年counterpane sysytem公司和UC berkeley合作破解了蜂

13、窩電話(huà)保報(bào)文加密算法，這個(gè)算法用來(lái)加密信用卡號(hào)2000年adi shamir破解了A5系列算法當(dāng)中的一個(gè)，A5系列算法是整個(gè)歐洲和美國(guó)所使用的保護(hù)數(shù)字蜂窩通信的算法。v密碼學(xué)是這樣一個(gè)概念，某些計(jì)算在一個(gè)方向是容易的，然而在相反的方向確實(shí)及其困難的。v例如：兩個(gè)大的素?cái)?shù)相乘的乘積確定，請(qǐng)確定這兩個(gè)大的素?cái)?shù)。v求一個(gè)數(shù)的素因子被人們認(rèn)為是一個(gè)極為困難的數(shù)學(xué)問(wèn)題。v不同密碼算法是基于不同的數(shù)學(xué)難題，但密碼算法都有一個(gè)陷門(mén)，可以利用陷門(mén)破解反方向的問(wèn)題。v陷門(mén)陷門(mén):計(jì)算機(jī)操作的陷門(mén)陷門(mén)設(shè)置是指進(jìn)入程序的秘密人口,它使得知道陷門(mén)陷門(mén)的人可以不經(jīng)過(guò)通常的安全檢查訪問(wèn)過(guò)程而獲得訪問(wèn)。v單向陷門(mén)函數(shù)是這樣的

14、函數(shù)，即除非知道某種附加某種附加的信息的信息，否則這樣的函數(shù)在一個(gè)方向上容易計(jì)算，而在反方向上要計(jì)算是不可行的。 v網(wǎng)絡(luò)上文件安全傳輸?shù)谋硎久芪?.5 數(shù)論1.模運(yùn)算兩位朋友在早上9：00相約，5個(gè)小時(shí)后在某地見(jiàn)面那么14：00和下午2：00可以表示同一時(shí)間。為什么會(huì)相等取模運(yùn)算 9+5=14=2（mod 12）或表示為142(mod12)v若a=b+kn對(duì)某些整數(shù)k成立，則有 (mod )abn如果a,b都是正整數(shù)，b在0到n之間，稱(chēng)b為a模n的余數(shù)或a和b是模n的同于模運(yùn)算也和其他運(yùn)算一樣，具有交換、結(jié)合、可分配特性。P44頁(yè)v特性a=amodn若a=bmodn ,則b=amod n若a=bmodn ,b=cmod n,則a=cmodna=bmodn ,c=dmodn,則 a+c=(b+d)modn a-c=(b-d)modn a*c=(b*d)modnax modn可以將其分解成系列乘法和除法取模8222mod(mod ) mod ) )modanannn2.素?cái)?shù)素?cái)?shù)是這樣一種數(shù)，比1大但因子除了1和他本身，沒(méi)有其他的數(shù)可以整數(shù)它。在密碼學(xué)中，特別是公開(kāi)密鑰算法中，素?cái)?shù)通常都是512位、1024位的大素?cái)?shù)3.兩數(shù)互素如果這兩個(gè)數(shù)的最大公因子是1，則這兩個(gè)數(shù)互素 記為：g