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

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

2、要的最少比特?cái)?shù)例如對(duì)于一周中的時(shí)間或性別進(jìn)行有效編碼一條消息中的信息量可以通過熵來度量1 熵和不確定性v在1948年由克勞德克勞德艾爾伍德艾爾伍德香農(nóng)香農(nóng)第一次引入到信息論中來。 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）如英語有26個(gè)字母，假如每個(gè)字母在文章中出現(xiàn)次數(shù)平均的話，每個(gè)字母的信息量為：2）漢字常用的有2500個(gè)，假如每個(gè)漢字在文章中出現(xiàn)次數(shù)平均的話，每個(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年狄菲和赫爾曼首次提出公開密鑰體制，為密碼學(xué)的研究開辟了新的方向。v超大規(guī)模集成電路和高速計(jì)算機(jī)的應(yīng)用,促進(jìn)了保密編碼理論的發(fā)展,同時(shí)也給保密通信的安全性帶來很大的威脅。v70年

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

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

6、安全性。v定義：U=H(K)/Dv其中D是語言多余度， H(K)密碼體制的熵。v唯一解距很小，密碼體制不安全；但不一定是唯一解距大就一定安全。v4 語言信息率v語言信息率：r=H(M)/Nv其中H(M)是熵，N是消息的長(zhǎng)度v語言的絕對(duì)信息率：R=log2L 其中L是語言中字母數(shù)，R也是單個(gè)字母的最大熵。v語言的多余度：D=R-rv5 混亂和散布v混亂：也可以稱為替換v散布：也可以稱為置換，位置的變化。2.2 復(fù)雜性理論v分析不同密碼技術(shù)和算法的的“計(jì)算復(fù)雜性”的方法，通過對(duì)密碼算法及技術(shù)進(jìn)行比較，確定其安全性。v1）算法的復(fù)雜性v一個(gè)算法的復(fù)雜性由兩個(gè)變量來描述：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）問題的復(fù)雜性vP問題：能夠在多項(xiàng)式時(shí)間內(nèi)解決的問題（時(shí)間復(fù)雜度）vNP問題：多項(xiàng)式時(shí)間內(nèi)可驗(yàn)證的問題vNP完全問題：特殊的問題，如果NP完全問題解決了，則NP問題也解決了。vPSPACE問題：比NP復(fù)雜性更高的問題。v3） NP完全問題v1.整數(shù)分解的問題：大整數(shù)分解成素?cái)?shù)相乘，整數(shù)越大越難分解2.背包問題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ù)問題v設(shè)x,r,n是正整數(shù)，已知x,r,n可以很快求出 y=xr mod 但反過來求r屬于離散對(duì)數(shù)問題2.3 密碼學(xué)的必要性v一個(gè)問題-密碼學(xué)真的有必要嗎CD Universe信用卡數(shù)據(jù)泄漏案Visa International筆記本失竊案美加州大學(xué)資料庫被黑事件v有一個(gè)影響很大的例子，就是2000年1月發(fā)生的CDUniverse信用卡數(shù)據(jù)庫泄露案事件。 一名據(jù)稱是來自俄羅斯的攻擊者成功地通過因特網(wǎng)拷貝了CDUniverse數(shù)據(jù)庫中300000個(gè)信用卡號(hào)碼，然后他試圖向CDUniverse勒索保護(hù)費(fèi)。CD Universe拒絕支付這筆錢，結(jié)果該黑客就在Web上公布了2500

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

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

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

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

13、窩電話保報(bào)文加密算法，這個(gè)算法用來加密信用卡號(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é)問題。v不同密碼算法是基于不同的數(shù)學(xué)難題，但密碼算法都有一個(gè)陷門，可以利用陷門破解反方向的問題。v陷門陷門:計(jì)算機(jī)操作的陷門陷門設(shè)置是指進(jìn)入程序的秘密人口,它使得知道陷門陷門的人可以不經(jīng)過通常的安全檢查訪問過程而獲得訪問。v單向陷門函數(shù)是這樣的

14、函數(shù)，即除非知道某種附加某種附加的信息的信息，否則這樣的函數(shù)在一個(gè)方向上容易計(jì)算，而在反方向上要計(jì)算是不可行的。 v網(wǎng)絡(luò)上文件安全傳輸?shù)谋硎久芪?.5 數(shù)論1.模運(yùn)算兩位朋友在早上9：00相約，5個(gè)小時(shí)后在某地見面那么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之間，稱b為a模n的余數(shù)或a和b是模n的同于模運(yùn)算也和其他運(yùn)算一樣，具有交換、結(jié)合、可分配特性。P44頁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和他本身，沒有其他的數(shù)可以整數(shù)它。在密碼學(xué)中，特別是公開密鑰算法中，素?cái)?shù)通常都是512位、1024位的大素?cái)?shù)3.兩數(shù)互素如果這兩個(gè)數(shù)的最大公因子是1，則這兩個(gè)數(shù)互素 記為：g