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

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

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

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

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

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

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

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

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

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

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

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

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

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

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