信息安全與密碼1

1、1高中數(shù)學(xué)選修課程專題研究3-2 信息安全與密碼2012年8月信息安全與密碼2前 言密碼的歷史極為久遠(yuǎn)，其起源可以追溯到幾千年以前，人類有記載的通信密碼始于公元前405年。 2012年8月信息安全與密碼32012年8月信息安全與密碼4前 言第一次世界大戰(zhàn)是化學(xué)家的戰(zhàn)爭(zhēng)，第二次世界大戰(zhàn)是物理學(xué)家的戰(zhàn)爭(zhēng)，如果未來(lái)發(fā)生戰(zhàn)爭(zhēng)將是數(shù)學(xué)家的戰(zhàn)爭(zhēng)，其核心是信息戰(zhàn)中的軍事密碼學(xué)問(wèn)題。 2012年8月信息安全與密碼5生活中常見(jiàn)的密碼2012年8月信息安全與密碼6早期生活中的密碼 2012年8月信息安全與密碼7文學(xué)作品中的密碼2012年8月信息安全與密碼82012年8月信息安全與密碼9信息安全、密 碼v防止信息被

2、非授權(quán)地訪問(wèn)、使用、泄露、分解、修改和毀壞，以求保證信息的保密性、完整性、可用性和可追責(zé)性，使信息保障能正確實(shí)施、信息系統(tǒng)能如意運(yùn)行、信息服務(wù)能滿足要求。v按特定法則編成，用以對(duì)通信雙方的信息進(jìn)行明密變換的符號(hào)。目前新出現(xiàn)的定義又增加信息有效性和占有性之類的概念目前新出現(xiàn)的定義又增加信息有效性和占有性之類的概念（后者與偷竊、欺詐和舞弊相對(duì)應(yīng)）網(wǎng)絡(luò)經(jīng)濟(jì)當(dāng)然增加了（后者與偷竊、欺詐和舞弊相對(duì)應(yīng)）網(wǎng)絡(luò)經(jīng)濟(jì)當(dāng)然增加了電子交易信用和責(zé)任的需要。電子交易信用和責(zé)任的需要。 2012年8月信息安全與密碼10課程標(biāo)準(zhǔn)系列3-2：信息安全與密碼 內(nèi)容與要求初等數(shù)論的有關(guān)知識(shí) v了解整除和同余，模的完全同余系和簡(jiǎn)

3、化剩余系，歐拉定理和費(fèi)馬小定理，大數(shù)分解問(wèn)題。v了解歐拉函數(shù)的定義和計(jì)算公式，威爾遜定理及在素?cái)?shù)判別中的應(yīng)用，原根與指數(shù)，模的原根存在性，離散對(duì)數(shù)問(wèn)題。2012年8月信息安全與密碼11課程標(biāo)準(zhǔn)系列3-2：信息安全與密碼 內(nèi)容與要求數(shù)論在信息安全中的應(yīng)用v了解通訊安全中的有關(guān)概念（如明文、密文、密鑰）和通訊安全中的基本問(wèn)題（如保密、數(shù)字簽名、密鑰管理、分配和共享）。v了解古典密碼的一個(gè)例子：流密碼（利用模同余方式）。v理解公鑰體制（單項(xiàng)函數(shù)概念），以及加密和數(shù)字簽名的方法（基于大數(shù)分解的RSA方案）。v理解離散對(duì)數(shù)在密鑰交換和分配中的應(yīng)用棣弗-赫爾曼方案。v理解離散對(duì)數(shù)在加密和數(shù)字簽名中的應(yīng)用蓋

4、莫爾算法。v了解拉格朗日插值公式在密鑰共享中的應(yīng)用。2012年8月信息安全與密碼12知識(shí)框架圖凱撒密碼體制維吉尼亞密碼體制流密碼體制M序列公鑰密碼體制的思想RSA公鑰方案離散對(duì)數(shù)方案保密通訊的基本常識(shí)公公鑰鑰密密碼碼體體制制古古典典密密碼碼體體制制密碼管理密碼管理2012年8月信息安全與密碼13保密通訊的基本常識(shí)人類使用密碼的歷史，從今天已知的，最早可以一直追溯到古巴比倫人的泥板文字。古埃及人，古羅馬人，古阿拉伯人幾乎世界歷史上所有文明都使用過(guò)密碼。 和 一直是密碼應(yīng)用的最重要的領(lǐng)域。 軍事外交2012年8月信息安全與密碼14保密通訊的基本常識(shí)密碼體制發(fā)展簡(jiǎn)史原始的原始的密碼體制密碼體制古典古

5、典密碼體制密碼體制近代近代密碼體制密碼體制2012年8月信息安全與密碼15保密通訊的基本常識(shí)明文與密文在通訊過(guò)程中，當(dāng)甲方通過(guò)公共通道向乙方傳遞信息時(shí)，為了不被竊取或修改，往往可將信息改變?yōu)槊孛苄问剑@時(shí)將原信息稱為明文明文，明文的秘密形式稱為密文密文。明文明文密文密文加加 密密解解 密密2012年8月信息安全與密碼16保密通訊的基本常識(shí)保密通訊的基本模型兄妹好朋友小明小虹小強(qiáng)2012年8月信息安全與密碼17保密通訊的基本常識(shí)保密通訊的基本模型甲方甲方乙方乙方密文解密密文解密明文加密明文加密第三方第三方密文密文2012年8月信息安全與密碼18保密通訊的基本常識(shí)密碼體制評(píng)價(jià)標(biāo)準(zhǔn)v敵方難于破譯收發(fā)

6、雙方使用的密鑰v有足夠多的密鑰供收發(fā)雙方選擇使用v加密解密的運(yùn)算較為容易操作，不會(huì)誤譯 2012年8月信息安全與密碼19古典密碼體制古典密碼學(xué)是現(xiàn)代密碼學(xué)的淵源，這些密碼大多比較簡(jiǎn)單，用手工或機(jī)械操作即可實(shí)現(xiàn)。加密和解密的方式千差萬(wàn)別，但任何密碼體制本質(zhì)上都是采用了不同的數(shù)學(xué)模型。2012年8月信息安全與密碼20換位加密術(shù)柵欄加密法 明文 MEET ME TONIGHT ZQHIOETEXTGNTMEMEOIHQZMEMTNGTXET2012年8月信息安全與密碼21替換加密術(shù)豬圈加密法 2012年8月信息安全與密碼22原文CRYPTOGRAPHY 2012年8月信息安全與密碼23古典密碼體制愷

7、撒密碼體制加密方法：取一個(gè)整數(shù) ，然后將明文中每個(gè)英文字母改用在它 位之后的那個(gè)字母來(lái)代替。例如，取k=10，而明文為“battle”。這時(shí)，字母b改成它10位之后的字母l。251kkk思思 考考k k為何不能取為何不能取0 02012年8月信息安全與密碼24abcdefghijklmnopqrstuvwxyz12345678910注意英文中最后一個(gè)字母注意英文中最后一個(gè)字母z向后向后又回到字母又回到字母a25battle2012年8月信息安全與密碼25古典密碼體制愷撒密碼體制經(jīng)過(guò)這個(gè)字母代換方式,上述明文就成為密文“ ”。其中k=10即是加密密鑰。 lkddvo2012年8月信息安全與密碼2

8、6古典密碼體制愷撒密碼體制采用同余符號(hào)，則上述密碼體制的加密運(yùn)算為 26mod10 xxEy明文battleontuesdayXYx+10mod26密文1019191141413 19 20 4 18 3 0 24111033211424 23 3 4 14 2 13 10 8 L K D D V O Y X D E O C N K I？字母數(shù)字對(duì)應(yīng)表字母數(shù)字對(duì)應(yīng)表2012年8月信息安全與密碼27古典密碼體制愷撒密碼體制為方便起見(jiàn)，我們用英文來(lái)介紹這種密碼體制即將a,b,c,y,z依次用數(shù)字0，1，24，25表示a0b1c2d3e4f5g6h7i8j9k10l11m12n13o14p15q16

9、r17s18t19u20v21w22x23y24z252012年8月信息安全與密碼28補(bǔ)充同余的概念設(shè)m和n都是整數(shù)，如果有一個(gè)整數(shù)k，使得n=km，就說(shuō)n是m的倍數(shù)，也說(shuō)m是n的因數(shù)，也說(shuō)m整除n，記作設(shè)m是正整數(shù)，a和b是整數(shù)，如果就說(shuō)a和b同余模m，記作如果不成立，就說(shuō)nmbammbamod)(modmba 2012年8月信息安全與密碼29古典密碼體制愷撒密碼體制課堂練習(xí)取k=6，試將明文math進(jìn)行加密。 sgznabcdefghijklm0123456789101112nopqrstuvwxyz131415161718192021222324252012年8月信息安全與密碼30古典密

10、碼體制愷撒密碼體制解密運(yùn)算 26mod16yyDx密文LKDDVOYXDEOCNKIYY+16XY+16mod26明文 11 10 3 3 21 14 24 23 3 4 14 2 13 10 8 27 26 19 19 37 30 40 39 19 20 30 18 29 26 24 101919114 14 13 19 10 4 18 3 0 24 b a t t l e o n t u e s d a y加密規(guī)則與解密規(guī)則互為逆運(yùn)算，由于事先約定好運(yùn)算規(guī)則，并且加密規(guī)則與解密規(guī)則互為逆運(yùn)算，由于事先約定好運(yùn)算規(guī)則，并且高度保密，所以這一對(duì)運(yùn)算分別被稱為加密密鑰、解密密鑰，高度保密，所以這

11、一對(duì)運(yùn)算分別被稱為加密密鑰、解密密鑰，統(tǒng)稱為密鑰。統(tǒng)稱為密鑰。 26mod10yyDx2012年8月信息安全與密碼31古典密碼體制愷撒密碼體制課堂練習(xí)取k=6, 試將密文sgznksgzoiy進(jìn)行解密 mathematicsabcdefghijklm0123456789101112nopqrstuvwxyz131415161718192021222324252012年8月信息安全與密碼32古典密碼體制愷撒密碼體制缺點(diǎn)：是密鑰量太小，只有25個(gè)。如果知道密碼體制，可以逐個(gè)試k的值，很容易就恢復(fù)成明文。這種體制在公元9世紀(jì)才被阿拉伯人找到破譯方法，在阿拉伯科學(xué)家阿爾金迪關(guān)于破譯加密信息的手稿中有詳

12、細(xì)的描述。 破譯的方法是頻率統(tǒng)計(jì)分析頻率統(tǒng)計(jì)分析。思思 考考愷撒密碼體制愷撒密碼體制的不足之處的不足之處2012年8月信息安全與密碼33古典密碼體制愷撒密碼體制2012年8月信息安全與密碼34思 考愷撒密碼體制中是用“+”進(jìn)行加密，是否能夠?qū)ζ溥M(jìn)行改造，用“”進(jìn)行加密？如果可行，解密的過(guò)程應(yīng)該如何？ 2012年8月信息安全與密碼35深入探究愷撒密碼體制愷撒密碼體制加密方法：取一個(gè)整數(shù) ，然后將明文中每個(gè)英文字母改用在它k位之后的那個(gè)字母來(lái)代替。251 kk26modkxy2012年8月信息安全與密碼36深入探究思思 考考能否用乘法運(yùn)算來(lái)能否用乘法運(yùn)算來(lái)“改造改造”愷撒密碼體制呢愷撒密碼體制呢2

13、6modkxy 2012年8月信息安全與密碼37深入探究比如：取k=3(1k25）明明 文文math對(duì)應(yīng)數(shù)字對(duì)應(yīng)數(shù)字1201973xy3x(mod26)密密 文文 36 0 57 21100521 k a f v 2012年8月信息安全與密碼38深入探究如何將密文“kafv”還原為明文“math”呢？愷撒密碼體制愷撒密碼體制加密鑰匙加密鑰匙8解密鑰匙解密鑰匙18同余意義下的互為相反數(shù)同余意義下的互為相反數(shù))26(mod0188“改造改造”后的體制后的體制加密鑰匙加密鑰匙3解密鑰匙解密鑰匙？同余意義下的互為倒數(shù)同余意義下的互為倒數(shù))26(mod13 k2012年8月信息安全與密碼39深入探究尋找

14、k=3在模26意義下的倒數(shù)！3？（正整數(shù)）？（正整數(shù)） 1（mod26）9 9?31?2?12012年8月信息安全與密碼40深入探究密密 文文kafv對(duì)應(yīng)數(shù)字對(duì)應(yīng)數(shù)字1005219yx9y(mod26)明明 文文 90 0 45 189120197 m a t h解密鑰匙：解密鑰匙：k=9；解密運(yùn)算應(yīng)該是解密運(yùn)算應(yīng)該是9y還是還是y/9呢？呢？2012年8月信息安全與密碼41深入探究課堂練習(xí)課堂練習(xí)自行選擇下列中一個(gè)自行選擇下列中一個(gè)k k值，將單詞值，將單詞mathmath進(jìn)行加密和解密。進(jìn)行加密和解密。k=4k=5k=6k=72012年8月信息安全與密碼42深入探究取k=4時(shí)，找不到正整數(shù)

15、k，使得4k（正整數(shù)）（正整數(shù)）1（mod26）?4整數(shù)偶數(shù)，而整數(shù)偶數(shù)，而被被26除余數(shù)為除余數(shù)為1的數(shù)必為奇數(shù)，故的數(shù)必為奇數(shù)，故k不能取偶數(shù)不能取偶數(shù)2012年8月信息安全與密碼43深入探究aa-1模模26的倒數(shù)表的倒數(shù)表113952171593111915717231911215231725252012年8月信息安全與密碼44)26(modbkxy深入探究愷撒密碼體制愷撒密碼體制方法一方法一方法二方法二改造后的體制改造后的體制+Hill密碼體制密碼體制)26(modkxy)26(modkxy 2012年8月信息安全與密碼45補(bǔ)充同余的性質(zhì)同余的性質(zhì)mabmbamaamod,mod;mo

16、d那么如果mcamcbmbamod,modmod那么和如果那么和如果,modmodmdcmbambdacmdbcamdbcamodmod,mod和mbamnmnbnamod,mod互素，那么與而如果將同余性質(zhì)將同余性質(zhì)與等式性質(zhì)與等式性質(zhì)對(duì)比記憶對(duì)比記憶abbaaa那么如果,; cacbba那么和如果,那么和如果,dcbabdacdcbadbca和,2012年8月信息安全與密碼46維吉尼亞密碼體制1586年，法國(guó)外交家維吉尼亞把愷撒密碼的模型作另一種改進(jìn)。愷撒密碼的密鑰是用同一個(gè)數(shù)字k=10簡(jiǎn)單地重復(fù)成序列10，10，10，與明文逐位模26相加。維吉尼亞則增加密鑰的長(zhǎng)度。對(duì)于維吉尼亞密碼，密鑰

17、是一個(gè)字序 ，其中m為任意正整數(shù)。因此，在原理上存在無(wú)限多個(gè)密鑰。mkkkk,212012年8月信息安全與密碼47維吉尼亞密碼體制以finger作為密鑰,對(duì) “battleonTuesday”加密過(guò)程可表示如下：明文battleontuesdayx101919114141319204183024密鑰序列58136417581364175813Y=E(x)686251521192160898811密文GIGZPVTVGAIJIIL2012年8月信息安全與密碼48維吉尼亞密碼體制這種密碼體制克服了愷撒體制的缺點(diǎn)，明文中前兩個(gè)字母t被加密成不同的字母G和Z，而密文中前兩個(gè)G也來(lái)自明文中不同的字母b和

18、t，所以加密性能比愷撒體制要好。2012年8月信息安全與密碼49維吉尼亞密碼體制課堂練習(xí)以finger作為密鑰，試將明文Mathematics進(jìn)行加密rignidfbviw2012年8月信息安全與密碼50維吉尼亞密碼體制解密過(guò)程密文gigzpvtvgaijiilY686251521192160898811密鑰序列-5-8 -13-6-4-17X=D(y)明文21 16132022921 18 13 20 22 921 18 1310191911414 13 19 20 4 183 0 24b a t t l e o n t u e s d a y2012年8月信息安全與密碼51維吉尼亞密碼體制

19、課堂練習(xí)以finger作為密鑰，試將密文rignidfbviw進(jìn)行解密mathematics2012年8月信息安全與密碼52維吉尼亞密碼體制維吉尼亞密碼直到二百年后才找到破譯方法，破譯者是英國(guó)人巴比奇（1854年）和德國(guó)人卡西斯基（1863年）。破譯手段是采用更精細(xì)的數(shù)學(xué)統(tǒng)計(jì)方法，關(guān)鍵是首先設(shè)法決定密鑰的周期長(zhǎng)度。密文出現(xiàn)周期性變化，敵方找到密文出現(xiàn)周期性變化，敵方找到k值，便容易破譯值，便容易破譯 2012年8月信息安全與密碼53Hill密碼體制假設(shè)甲方要將信息“HELP”（明文）發(fā)送給乙方，則發(fā)送者事先與接受者約定某個(gè)二維函數(shù)，假如設(shè)（）2122115233xxyxxy2012年8月信息安

20、全與密碼54然后將HELP分為兩組（H,E）和（L,P），按上面的編碼方法得： H7 L11 E4 P15用前面的函數(shù)（）作用后，得Hill密碼體制1x2x1x2x21133xxy33437326mod721252xxy34457226mod8思考思考為什么要將為什么要將HELP分成兩組？分成兩組？2012年8月信息安全與密碼55Hill密碼體制從而將明文轉(zhuǎn)化為密文“HIAT”，這一過(guò)程稱為加密。IyHy826mod834726mod73321TyAy1926mod1997026mod07821思考思考解密過(guò)程又如何進(jìn)解密過(guò)程又如何進(jìn)行呢？行呢？2012年8月信息安全與密碼56Hill密碼體制

21、然后甲方將“HIAT”發(fā)送給乙方，乙方得到密文之后，仍將密文分成兩組并由（）解出2187yIyH21190yTyA2122119201715yyxyyx思 考如何由解出下式2012年8月信息安全與密碼57Hill密碼體制如何用Hill密碼體制進(jìn)行解密？2122115233xxyxxy21221131923195yyxyyx2012年8月信息安全與密碼58Hill密碼體制補(bǔ)充知識(shí)對(duì)于一個(gè)n階方陣A，若存在一個(gè)n階方陣B，使得AB=BA=E(mod m)，稱A為模m可逆，B為A的逆矩陣，記為B=A-1(mod m)。可驗(yàn)證：26mod11acbdbcadA2012年8月信息安全與密碼59Hill密

22、碼體制模26的倒數(shù)表a1357911 15 17 19 21 23 25a-11921 15319723 11517 252012年8月信息安全與密碼60上述例子也可用矩陣運(yùn)算表示如下：明文HELP的加密過(guò)程為：Hill密碼體制9201715,5233DyEx26mod733437326mod1997155112（密文）HAITTIAHExPELH1980715411752331541172012年8月信息安全與密碼61Hill密碼體制反過(guò)來(lái)，解密過(guò)程可計(jì)算如下：什么是矩陣？)(15411719807920171519807明文HELPPELHDyTIAH2012年8月信息安全與密碼62Hil

23、l密碼體制2122115233xxyxxy212211329359yyxyyx211915273yyx21296273yyx26mod9926mod17926mod151526mod1272122119201715yyxyyx2012年8月信息安全與密碼63Hill密碼體制練 習(xí)試將HIAT進(jìn)行解密2111715yyx24181771526mod7212920yyx2128972026mod42111715yyx323191701526mod11212920yyod152012年8月信息安全與密碼64Hill密碼體制再將 代入得到從而得到明文“HELP”，這一過(guò)程稱為

24、解密。21, yyExHx4721PxLx151121思 考當(dāng)明文字母?jìng)€(gè)數(shù)不是偶數(shù)時(shí)，怎樣進(jìn)行加密運(yùn)算？2012年8月信息安全與密碼65簡(jiǎn)單的機(jī)械加密普通的打字機(jī)可以提供多種簡(jiǎn)單的替換加密方法。例如，不要擊打表示正確字母的那個(gè)鍵，而是擊打它上頭偏左的鍵；也可以選擇擊打它的右旁鍵，或擊打上頭偏右的鍵。如果你選擇擊打上頭偏左鍵的方案，那么I LOVE YOU打字后成了：8 O9F3 697而如果選擇擊打右旁鍵的方案，那又成了O :PBR UPI2012年8月信息安全與密碼66流密碼體制M序列密碼體制在第一次世界大戰(zhàn)后又有了新的突破，這種新體制被稱為流密碼,在技術(shù)上依托于一種新的基本元件，稱為移位寄

25、存器。2012年8月信息安全與密碼67流密碼體制M序列一個(gè)n級(jí)的移位寄存器由兩部分組成：移位寄存部分計(jì)算反饋部分2012年8月信息安全與密碼68流密碼體制M序列移位寄存部分：可存放n個(gè)數(shù)字 ，這n個(gè)數(shù)字組成一個(gè)狀態(tài)，其中每個(gè)字母取值可為0或1。naaa,212012年8月信息安全與密碼69流密碼體制M序列計(jì)算反饋部分：位移寄存器的工作過(guò)程可用下圖表示,21aaa1a2 an-1an輸出x1x2x n-1x na1a2 an-1an反饋2012年8月信息安全與密碼70流密碼體制M序列例如：在一個(gè)3元移位寄存器中，取當(dāng)取初始狀態(tài)為 時(shí)， 32213211,xxxxxxxf1 , 1 , 1,321aaa3214,aaafa0,1 ,1,432aaa0,1 ,0,654aaa411112mod011a1 , 1 , 1將 輸出，初始狀態(tài) 變成1 , 0 , 1,543aaa如此類推，下一個(gè)狀態(tài)2012年8月信息安全與密碼71流密碼體制M序列