密碼學(xué)基本理論

1、回憶上次課內(nèi)容回憶上次課內(nèi)容v 古典密碼時期古典密碼時期v 近代密碼時期近代密碼時期 從從2020世紀(jì)初到世紀(jì)初到2020世紀(jì)世紀(jì)5050年代，年代，即一戰(zhàn)及二戰(zhàn)時期即一戰(zhàn)及二戰(zhàn)時期 手工或電動機(jī)械實(shí)現(xiàn)的復(fù)雜的代手工或電動機(jī)械實(shí)現(xiàn)的復(fù)雜的代替或換位替或換位 通信手段：電報(bào)通信通信手段：電報(bào)通信v 現(xiàn)代密碼時期現(xiàn)代密碼時期v 古典密碼時期古典密碼時期 從古代到從古代到19世紀(jì)末，長達(dá)幾千年世紀(jì)末，長達(dá)幾千年 紙、筆或簡單器械實(shí)現(xiàn)的代替和換位紙、筆或簡單器械實(shí)現(xiàn)的代替和換位 通信手段：信使通信手段：信使v 近代密碼時期近代密碼時期 從從20世紀(jì)初到世紀(jì)初到20世紀(jì)世紀(jì)50年代，即一戰(zhàn)及二戰(zhàn)時期年代

2、，即一戰(zhàn)及二戰(zhàn)時期 手工或電動機(jī)械實(shí)現(xiàn)的復(fù)雜的代替或換位手工或電動機(jī)械實(shí)現(xiàn)的復(fù)雜的代替或換位 通信手段：電報(bào)通信通信手段：電報(bào)通信v 現(xiàn)代密碼時期現(xiàn)代密碼時期 從從20世紀(jì)世紀(jì)50年代初至今年代初至今 分組密碼、序列密碼及公開密鑰密碼，有數(shù)學(xué)理論基礎(chǔ)分組密碼、序列密碼及公開密鑰密碼，有數(shù)學(xué)理論基礎(chǔ) 通信手段：無線通信、有線通信、計(jì)算機(jī)網(wǎng)絡(luò)等通信手段：無線通信、有線通信、計(jì)算機(jī)網(wǎng)絡(luò)等密碼學(xué)基本理論密碼學(xué)基本理論v現(xiàn)代密碼學(xué)起始于現(xiàn)代密碼學(xué)起始于20世紀(jì)世紀(jì)50年代，年代，1949年年Shannon的的The Communication Theory of Secret Systems奠定了現(xiàn)代密

3、碼學(xué)的數(shù)學(xué)理論奠定了現(xiàn)代密碼學(xué)的數(shù)學(xué)理論基礎(chǔ)?；A(chǔ)。 密碼體制的分類密碼體制的分類現(xiàn)代密碼體制的數(shù)學(xué)理論現(xiàn)代密碼體制的數(shù)學(xué)理論密碼破譯密碼破譯香農(nóng)保密理論香農(nóng)保密理論密碼體制分類密碼體制分類(1)v換位與代替密碼體制換位與代替密碼體制v序列與分組密碼體制序列與分組密碼體制v對稱與非對稱密鑰密碼體制對稱與非對稱密鑰密碼體制換位：打破明文中的某些固定結(jié)構(gòu)模式，使來自明文或密鑰的換位：打破明文中的某些固定結(jié)構(gòu)模式，使來自明文或密鑰的信息信息擴(kuò)散擴(kuò)散到密文中。到密文中。代替：使明文和密鑰的信息混雜（代替：使明文和密鑰的信息混雜（混淆混淆）在一起。）在一起。序列：明文與密鑰進(jìn)行序列：明文與密鑰進(jìn)行bit

4、對對bit的運(yùn)算。的運(yùn)算。核心是密鑰生成算法設(shè)計(jì)核心是密鑰生成算法設(shè)計(jì)。分組：所有明文分組在相同密鑰控制下分別進(jìn)行加密變換。分組：所有明文分組在相同密鑰控制下分別進(jìn)行加密變換。核核心是設(shè)計(jì)一個復(fù)雜而又高效的加密解密算法心是設(shè)計(jì)一個復(fù)雜而又高效的加密解密算法。密碼體制分類密碼體制分類(2)v換位與代替密碼體制換位與代替密碼體制v序列與分組密碼體制序列與分組密碼體制v對稱與非對稱對稱與非對稱密鑰密鑰密碼體制密碼體制對稱密鑰密碼體制（單密鑰密碼體制、私鑰密碼體制）對稱密鑰密碼體制（單密鑰密碼體制、私鑰密碼體制）非對稱密鑰密碼體制（雙密鑰密碼體制、公開密鑰密碼體制）非對稱密鑰密碼體制（雙密鑰密碼體制、

5、公開密鑰密碼體制）加密密鑰解密密鑰加密密鑰解密密鑰數(shù)學(xué)理論數(shù)學(xué)理論v數(shù)論數(shù)論v信息論信息論v復(fù)雜度理論復(fù)雜度理論研究整數(shù)性質(zhì)的一個數(shù)學(xué)分支。用于密碼算法設(shè)計(jì)。研究整數(shù)性質(zhì)的一個數(shù)學(xué)分支。用于密碼算法設(shè)計(jì)。從概率統(tǒng)計(jì)的觀點(diǎn)出發(fā)研究信息的傳輸和保密問題。從概率統(tǒng)計(jì)的觀點(diǎn)出發(fā)研究信息的傳輸和保密問題。分析密碼算法的復(fù)雜度，并能確定算法的安全性。分析密碼算法的復(fù)雜度，并能確定算法的安全性。數(shù)數(shù) 論論-數(shù)學(xué)皇后數(shù)學(xué)皇后v素?cái)?shù)素?cái)?shù)v互素互素v模運(yùn)算，模逆元模運(yùn)算，模逆元v同余方程組，孫子問題，中國剩余定理同余方程組，孫子問題，中國剩余定理v因子分解因子分解素素 數(shù)數(shù)公鑰密碼中為了安全必須使用大素?cái)?shù)（公鑰密

6、碼中為了安全必須使用大素?cái)?shù)（1024bit的素?cái)?shù)）的素?cái)?shù)）梅森數(shù)是根據(jù)17世紀(jì)法國數(shù)學(xué)家馬蘭梅森的名字命名的 梅森數(shù)是指形如2n 1的數(shù)，記為Mn；如果一個梅森數(shù)是素?cái)?shù)那么它稱為梅森素?cái)?shù)。 挪威計(jì)算機(jī)專家奧德挪威計(jì)算機(jī)專家奧德斯特林德莫通過參加一個名為斯特林德莫通過參加一個名為“因特因特網(wǎng)梅森素?cái)?shù)大搜索網(wǎng)梅森素?cái)?shù)大搜索”(GIMPS)的國際合作項(xiàng)目，在的國際合作項(xiàng)目，在2009年年4月發(fā)現(xiàn)了第月發(fā)現(xiàn)了第47個梅森素?cái)?shù)，該素?cái)?shù)為個梅森素?cái)?shù)，該素?cái)?shù)為“2的的42643801次次方減方減1”。它有。它有12837064位數(shù)，如果用普通字號將這個巨數(shù)位數(shù)，如果用普通字號將這個巨數(shù)連續(xù)寫下來，它的長度超

7、過連續(xù)寫下來，它的長度超過50公里公里! 梅森素?cái)?shù)列表（梅森素?cái)?shù)列表（1） 1772年，被譽(yù)為年，被譽(yù)為“數(shù)學(xué)英雄數(shù)學(xué)英雄”的歐拉在雙目失明的情況下的歐拉在雙目失明的情況下，以驚人的毅力靠心算證明了，以驚人的毅力靠心算證明了“2的的31次方減次方減1”是第是第8個梅個梅森素?cái)?shù)，該素?cái)?shù)有森素?cái)?shù)，該素?cái)?shù)有10位位 。梅森素?cái)?shù)列表（梅森素?cái)?shù)列表（2） 計(jì)算機(jī)的發(fā)明革命化的改進(jìn)了梅森素?cái)?shù)的尋找。第一個成功的例子是M521的證明，它是在萊默萊默指導(dǎo)下，使用R.M. R.M. RobinsonRobinson教授編寫的軟件，利用坐落在洛杉磯加利福尼亞大學(xué)加利福尼亞大學(xué)的數(shù)據(jù)分析協(xié)會數(shù)據(jù)分析協(xié)會的，屬于美國

8、國家標(biāo)準(zhǔn)局國家標(biāo)準(zhǔn)局的西部自動計(jì)算機(jī)（SWAC）于1952年1月30日晚上10:00獲得。 并且在隨后不到兩小時，下一個梅森素?cái)?shù)M607被發(fā)現(xiàn)。在隨后的幾個月里，使用同樣的程序發(fā)現(xiàn)了另外三個梅森素?cái)?shù)M1279、M2203和M2281。 梅森素?cái)?shù)列表（梅森素?cái)?shù)列表（3） 電子新領(lǐng)域基金會(EFF)向第一個找到超過1000萬位數(shù)的個人或機(jī)構(gòu)頒發(fā)10萬美元獎金。被時代周刊評為“年度50項(xiàng)最佳發(fā)明”之一數(shù)數(shù) 論論-數(shù)學(xué)皇后數(shù)學(xué)皇后v素?cái)?shù)素?cái)?shù)v互素互素v模運(yùn)算，模逆元模運(yùn)算，模逆元v同余方程組，孫子問題，中國剩余定理同余方程組，孫子問題，中國剩余定理v因子分解因子分解互互 素素v互素互素：指任意兩個正整

9、數(shù)：指任意兩個正整數(shù)a和和b，當(dāng)它們除了，當(dāng)它們除了1之之外沒有其它的公因子，記為外沒有其它的公因子，記為gcd(a,b)=1，稱，稱a和和b互素?；ニ?。vgcd(15,28)=1vgcd(15,27)=3數(shù)數(shù) 論論-數(shù)學(xué)皇后數(shù)學(xué)皇后v素?cái)?shù)素?cái)?shù)v互素互素v模運(yùn)算，模逆元模運(yùn)算，模逆元v同余方程組，孫子問題，中國剩余定理同余方程組，孫子問題，中國剩余定理v因子分解因子分解模運(yùn)算模運(yùn)算v模運(yùn)算：簡單的說，就是求余數(shù)。模運(yùn)算：簡單的說，就是求余數(shù)。v設(shè)設(shè)r是是a除以除以b的余數(shù)，的余數(shù)，a與與b的關(guān)系可表示為的關(guān)系可表示為a=r(mod b)，這就是，這就是模運(yùn)算模運(yùn)算。v例：例：23=11(mod

10、12) 29 (mod 26) = 3 10 (mod 26) = 3 -1 (mod 26) = 25模運(yùn)算在數(shù)論和程序設(shè)計(jì)中都有著廣泛的應(yīng)用，從奇偶數(shù)的判別到素?cái)?shù)的判別，從模冪運(yùn)算到最大公約數(shù)的求法，從孫子問題到凱撒密碼問題，無不充斥著模運(yùn)算的身影。 模逆元模逆元(1)v在公鑰密碼體制中，往往需要求解模逆元。在公鑰密碼體制中，往往需要求解模逆元。v求模逆元，即尋找一個求模逆元，即尋找一個x，使得，使得 a*x=1(mod n) 或或 1=(a*x) mod n 其中其中a和和n是正整數(shù)，是正整數(shù)，x稱為稱為a的模的模n逆元。逆元。 也寫作：也寫作：a-1=x mod n例：例：4-1mod

11、7=? 5-1mod14=? 2-1mod14=?4*2(mod 7)=123沒有逆元！沒有逆元！求解模逆元問題很困難，有時有結(jié)果，有時沒有結(jié)果。模逆元模逆元(2)v如果如果a和和n互素，那么互素，那么a模模n的逆元存在。的逆元存在。v如果如果a和和n不不是互素的，那么是互素的，那么a模模n的逆元的逆元不不存在。存在。v如果如果n是一個素?cái)?shù)，那么從是一個素?cái)?shù)，那么從1到到n-1的每個數(shù)與的每個數(shù)與n都都是互素的，在這個范圍內(nèi)恰好都有一個逆元。是互素的，在這個范圍內(nèi)恰好都有一個逆元。v例：例：n=5 1 2 3 4 模逆元模逆元 1 3 2 4gcd(a,n)=1擴(kuò)展歐幾里德算法數(shù)數(shù) 論論-數(shù)學(xué)

12、皇后數(shù)學(xué)皇后v素?cái)?shù)素?cái)?shù)v互素互素v模運(yùn)算，模逆元模運(yùn)算，模逆元v同余方程組，孫子問題，中國剩余定理同余方程組，孫子問題，中國剩余定理v因子分解因子分解同余方程組同余方程組v聯(lián)立聯(lián)立k個同余式個同余式 x=b1(mod n1)， x=b2(mod n2)， x=bk(mod nk) 稱為稱為同余方程組同余方程組。v孫子問題孫子問題-孫子算經(jīng)孫子算經(jīng) “今有物不知其數(shù)今有物不知其數(shù), , 三三數(shù)之剩二三三數(shù)之剩二, , 五五數(shù)之剩三五五數(shù)之剩三, , 七七數(shù)之剩二七七數(shù)之剩二. . 問物幾何？問物幾何？” “” “答日二十三答日二十三.”.”設(shè)所求數(shù)為設(shè)所求數(shù)為x，用同余方程組表示：，用同余方程組

13、表示： x=2(mod 3)， x=3(mod 5)， x=2(mod 7)孫子問題孫子問題v孫子問題孫子問題-孫子算經(jīng)孫子算經(jīng) “今有物不知其數(shù)今有物不知其數(shù), 三三數(shù)之剩二三三數(shù)之剩二, 五五數(shù)之剩三五五數(shù)之剩三, 七七七數(shù)之剩二七數(shù)之剩二. 問物幾何？問物幾何？” “答日二十三答日二十三.”解法在明朝程大位解法在明朝程大位算法統(tǒng)宗算法統(tǒng)宗(1593)(1593)里的一首詩歌里的一首詩歌: : 三人同行七十稀，三人同行七十稀， 五樹梅花甘一枝，五樹梅花甘一枝， 七子團(tuán)圓整半月，七子團(tuán)圓整半月， 除百零五便得知。除百零五便得知。x=70*2+21*3+15*2(mod105) =233mod

14、105 =23定理（中國剩余定理）定理（中國剩余定理） 設(shè)設(shè)m1,m2,mk是兩兩互素的正整數(shù)是兩兩互素的正整數(shù)， ，則一次同余方程組則一次同余方程組對模對模M有惟一解有惟一解:其中其中ei滿足滿足1122modmodmodkkamxamxamx1kiiMm1 12212modkkkMMMxe ae ae aMmmm1 mod1, 2,iiiMemikm令令Mi=M/mi ; ei=Mi=Mi-1(modmi)x=M1M1a1+M2M2a2+MkMkak (modM)x 70a+21b+15c (mod 105)中國剩余定理中國剩余定理v用途用途 若已知某個數(shù)關(guān)于一些兩兩互素的數(shù)的同余集若已知

15、某個數(shù)關(guān)于一些兩兩互素的數(shù)的同余集，可重構(gòu)此數(shù)。，可重構(gòu)此數(shù)。 大數(shù)用小數(shù)表示、大數(shù)的運(yùn)算通過小數(shù)實(shí)現(xiàn)。大數(shù)用小數(shù)表示、大數(shù)的運(yùn)算通過小數(shù)實(shí)現(xiàn)。思考題思考題v 韓信點(diǎn)兵韓信點(diǎn)兵:有兵一隊(duì)有兵一隊(duì), 若列成五行縱隊(duì)若列成五行縱隊(duì), 則末行則末行一人一人; 成六行縱隊(duì)成六行縱隊(duì), 則末行五人則末行五人; 成七行縱隊(duì)成七行縱隊(duì),則末行則末行四人四人; 成十一行縱隊(duì)成十一行縱隊(duì),則末行十人則末行十人, 求兵數(shù)求兵數(shù).v解解 設(shè)設(shè)x是所求兵數(shù)是所求兵數(shù), 則依題意則依題意:v x 1(mod 5), x 5(mod 6), x 4(mod 7), x 10(mod 11)2100數(shù)數(shù) 論論-數(shù)學(xué)皇后數(shù)學(xué)

16、皇后v素?cái)?shù)素?cái)?shù)v互素互素v模運(yùn)算，模逆元模運(yùn)算，模逆元v同余方程組，孫子問題，中國剩余定理同余方程組，孫子問題，中國剩余定理v因子分解因子分解因子分解因子分解v因子分解就是對合數(shù)的分解。因子分解就是對合數(shù)的分解。v例：例：18=2*32，96=25*3，110=2*5*11v較好的因子分解方法：試除法、數(shù)域篩選法、橢圓較好的因子分解方法：試除法、數(shù)域篩選法、橢圓曲線法等。曲線法等。v但對于很大的數(shù)（但對于很大的數(shù)（1024bit以上的數(shù)）進(jìn)行因子分解以上的數(shù)）進(jìn)行因子分解，所需計(jì)算時間在目前條件下是一個天文數(shù)字。，所需計(jì)算時間在目前條件下是一個天文數(shù)字。v所以，已知兩個大素?cái)?shù)所以，已知兩個大素

17、數(shù)p和和q，求其積很容易；，求其積很容易；v反之，知道反之，知道n求求p和和q就很困難。就很困難。RSA公鑰密碼體制這樣的分解是獨(dú)一無二數(shù)學(xué)理論數(shù)學(xué)理論v數(shù)論數(shù)論v信息論信息論v復(fù)雜度理論復(fù)雜度理論研究整數(shù)性質(zhì)的一個數(shù)學(xué)分支。用于密碼算法設(shè)計(jì)。研究整數(shù)性質(zhì)的一個數(shù)學(xué)分支。用于密碼算法設(shè)計(jì)。從概率統(tǒng)計(jì)的觀點(diǎn)出發(fā)研究信息的傳輸和保密問題。從概率統(tǒng)計(jì)的觀點(diǎn)出發(fā)研究信息的傳輸和保密問題。分析密碼算法的復(fù)雜度，并能確定算法的安全性。分析密碼算法的復(fù)雜度，并能確定算法的安全性。信息論信息論v信息論是運(yùn)用概率論與數(shù)理統(tǒng)計(jì)的方法研究信息信息論是運(yùn)用概率論與數(shù)理統(tǒng)計(jì)的方法研究信息、信息熵、通信系統(tǒng)、數(shù)據(jù)傳輸、密

18、碼學(xué)、數(shù)據(jù)、信息熵、通信系統(tǒng)、數(shù)據(jù)傳輸、密碼學(xué)、數(shù)據(jù)壓縮等問題的應(yīng)用數(shù)學(xué)學(xué)科。壓縮等問題的應(yīng)用數(shù)學(xué)學(xué)科。 v人們通常將香農(nóng)于人們通常將香農(nóng)于1948年年10月月發(fā)表于發(fā)表于貝爾系統(tǒng)技術(shù)學(xué)報(bào)貝爾系統(tǒng)技術(shù)學(xué)報(bào)上的論文上的論文A Mathematical Theory of Communication（通信的數(shù)學(xué)理論）作為現(xiàn)代（通信的數(shù)學(xué)理論）作為現(xiàn)代信息論研究的開端。信息論研究的開端。 信息與消息信息與消息v信息與消息是緊密相連的兩個不同概念。信息與消息是緊密相連的兩個不同概念。物質(zhì)物質(zhì)能源能源信息信息信息論在密碼學(xué)中的應(yīng)用信息論在密碼學(xué)中的應(yīng)用(1)v多余度多余度v熵熵v唯一解距離唯一解距離多余

19、度在密碼學(xué)中不是好事。the、of、and、to、a、in、that、it、is、I任何一篇文章中有1/4的篇幅被這10個詞占據(jù)。多余度越小，破譯分析的困難就越大，對保密有利！信息論在密碼學(xué)中的應(yīng)用信息論在密碼學(xué)中的應(yīng)用(2)v熵熵：一種表示信息量的方法。：一種表示信息量的方法。v即為了表示不同的信息所需的二進(jìn)制位的數(shù)目。即為了表示不同的信息所需的二進(jìn)制位的數(shù)目。例：表示一周中的某一天，熵H(X)3星期日000星期一001星期二010星期三011星期四100星期五101星期六110狀態(tài)111沒有使用信息論在密碼學(xué)中的應(yīng)用信息論在密碼學(xué)中的應(yīng)用(3)v熵：表示某些事件的不確定性。熵：表示某些事件

20、的不確定性。不確定性大熵值大 當(dāng)一個系統(tǒng)中所有事件等概率發(fā)生時，不確定性最大，熵最大，達(dá)到最大熵。 當(dāng)一個事件必然發(fā)生，不確定程度為0，熵為0如果一個密碼系統(tǒng)的H(M)越大，表示哪些密文對應(yīng)哪些明文的不確定程度就越大，即由密文分析明文的概率越小，這樣密碼系統(tǒng)就越安全！信息論在密碼學(xué)中的應(yīng)用信息論在密碼學(xué)中的應(yīng)用(4)v 唯一解距離唯一解距離衡量破譯分析的困難性 含義：當(dāng)密碼分析者進(jìn)行窮舉攻擊時，可能解密出唯一有意義的明文所需要的最少的密文量。描述了被截獲的密文量和成功破譯的可能性之間的關(guān)系 DKHU U：唯一解距離H(K)：密鑰的熵D：語言的多余度明文的多余度越大，唯一解距離就越小。因此，為提

21、高密碼體制的安全性，應(yīng)盡量減少明文的多余度。數(shù)學(xué)理論數(shù)學(xué)理論v數(shù)論數(shù)論v信息論信息論v復(fù)雜度理論復(fù)雜度理論研究整數(shù)性質(zhì)的一個數(shù)學(xué)分支。用于密碼算法設(shè)計(jì)。研究整數(shù)性質(zhì)的一個數(shù)學(xué)分支。用于密碼算法設(shè)計(jì)。從概率統(tǒng)計(jì)的觀點(diǎn)出發(fā)研究信息的傳輸和保密問題。從概率統(tǒng)計(jì)的觀點(diǎn)出發(fā)研究信息的傳輸和保密問題。分析密碼算法的復(fù)雜度，并能確定算法的安全性。分析密碼算法的復(fù)雜度，并能確定算法的安全性。復(fù)雜度理論復(fù)雜度理論v算法復(fù)雜度算法復(fù)雜度O 時間復(fù)雜度時間復(fù)雜度T 空間復(fù)雜度空間復(fù)雜度Sv問題復(fù)雜度問題復(fù)雜度 P類問題類問題 NP類問題類問題 NPC問題問題T和S通常是n的函數(shù)n是輸入算法中的數(shù)的尺寸例：T=O(n

22、)衡量算法的安全性，抗破譯能力評定不同的算法之間在時間成本上，哪個消耗的評定不同的算法之間在時間成本上，哪個消耗的時間理論上少些，哪個多些。時間理論上少些，哪個多些。密碼學(xué)基本理論密碼學(xué)基本理論v現(xiàn)代密碼學(xué)起始于現(xiàn)代密碼學(xué)起始于20世紀(jì)世紀(jì)50年代，年代，1949年年Shannon的的The Communication Theory of Secret Systems奠定了現(xiàn)代密碼學(xué)的數(shù)學(xué)理論奠定了現(xiàn)代密碼學(xué)的數(shù)學(xué)理論基礎(chǔ)?；A(chǔ)。 密碼體制的分類密碼體制的分類現(xiàn)代密碼體制的數(shù)學(xué)理論現(xiàn)代密碼體制的數(shù)學(xué)理論密碼破譯密碼破譯香農(nóng)保密理論香農(nóng)保密理論密碼破譯（密碼分析）密碼破譯（密碼分析）密碼編碼學(xué)c

23、ryptography密碼分析學(xué)cryptanalysis區(qū)分：解密（脫密）和密碼破譯區(qū)分：解密（脫密）和密碼破譯p密碼破譯規(guī)律p密碼破譯方式p密碼破譯步驟賄賂拷打入室搶劫鍵盤記錄器密碼破譯規(guī)律密碼破譯規(guī)律v密碼規(guī)律密碼規(guī)律 單表代替密碼單表代替密碼明密異同規(guī)律明密異同規(guī)律 換位密碼換位密碼一階頻次不變的規(guī)律一階頻次不變的規(guī)律v文字規(guī)律文字規(guī)律 字母統(tǒng)計(jì)特性字母統(tǒng)計(jì)特性 電報(bào)公文格式電報(bào)公文格式v情況規(guī)律情況規(guī)律 戰(zhàn)爭期間戰(zhàn)爭期間 發(fā)生重大案件發(fā)生重大案件 兩國會談期間兩國會談期間明密字母雖不同，但出現(xiàn)頻率相同各字母在明文頻率等于在密文的頻率考慮：單字母、雙字母、三字母考慮：報(bào)頭、報(bào)尾、常用字

24、、詞軍事電報(bào)軍事電報(bào)/ /政府報(bào)告政府報(bào)告/ /外交報(bào)告外交報(bào)告密碼破譯方式密碼破譯方式v唯密文攻擊唯密文攻擊 攻擊者僅獲得一些加密后的密文攻擊者僅獲得一些加密后的密文v已知明文攻擊已知明文攻擊 攻擊者有一些密文并且知道相對應(yīng)的明文攻擊者有一些密文并且知道相對應(yīng)的明文 v選擇明文攻擊選擇明文攻擊 攻擊者在開始攻擊之前可以選擇一些明文并從系攻擊者在開始攻擊之前可以選擇一些明文并從系統(tǒng)中獲得相對應(yīng)的密文。統(tǒng)中獲得相對應(yīng)的密文。 v選擇密文攻擊選擇密文攻擊 攻擊者在開始攻擊之前可以選擇一些密文并從系攻擊者在開始攻擊之前可以選擇一些密文并從系統(tǒng)中獲得相對應(yīng)的明文。統(tǒng)中獲得相對應(yīng)的明文。 最困難！密碼破

25、譯步驟密碼破譯步驟v整理分類整理分類 同一密碼體制加密的密文歸一類。同一密碼體制加密的密文歸一類。v統(tǒng)計(jì)分析統(tǒng)計(jì)分析 對密文進(jìn)行單、雙、三字母等統(tǒng)計(jì)，以確定密碼對密文進(jìn)行單、雙、三字母等統(tǒng)計(jì)，以確定密碼編制的方法，暴露密碼規(guī)律。編制的方法，暴露密碼規(guī)律。v假設(shè)和反證假設(shè)和反證 選在規(guī)律性強(qiáng)的地方進(jìn)行，如報(bào)頭報(bào)尾、可能字選在規(guī)律性強(qiáng)的地方進(jìn)行，如報(bào)頭報(bào)尾、可能字、大段重復(fù)信息，作為突破口。、大段重復(fù)信息，作為突破口。密碼學(xué)基本理論密碼學(xué)基本理論v現(xiàn)代密碼學(xué)起始于現(xiàn)代密碼學(xué)起始于20世紀(jì)世紀(jì)50年代，年代，1949年年Shannon的的The Communication Theory of Secret Systems奠定了現(xiàn)代密碼學(xué)的