信息安全與密碼1

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

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

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

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

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

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

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

8、6古典密碼體制愷撒密碼體制采用同余符號，則上述密碼體制的加密運算為 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ù)字對應表字母數(shù)字對應表2012年8月信息安全與密碼27古典密碼體制愷撒密碼體制為方便起見，我們用英文來介紹這種密碼體制即將a,b,c,y,z依次用數(shù)字0，1，24，25表示a0b1c2d3e4f5g6h7i8j9k10l11m12n13o14p15q16

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

10、碼體制愷撒密碼體制解密運算 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ī)則互為逆運算，由于事先約定好運算規(guī)則，并且加密規(guī)則與解密規(guī)則互為逆運算，由于事先約定好運算規(guī)則，并且高度保密，所以這一對運算分別被稱為加密密鑰、解密密鑰，高度保密，所以這

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

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

13、6modkxy 2012年8月信息安全與密碼37深入探究比如：取k=3(1k25）明明 文文math對應數(shù)字對應數(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對應數(shù)字對應數(shù)字1005219yx9y(mod26)明明 文文 90 0 45 189120197 m a t h解密鑰匙：解密鑰匙：k=9；解密運算應該是解密運算應該是9y還是還是y/9呢？呢？2012年8月信息安全與密碼41深入探究課堂練習課堂練習自行選擇下列中一個自行選擇下列中一個k k值，將單詞值，將單詞mathmath進行加密和解密。進行加密和解密。k=4k=5k=6k=72012年8月信息安全與密碼42深入探究取k=4時，找不到正整數(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補充同余的性質(zhì)同余的性質(zhì)mabmbamaamod,mod;mo

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

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

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

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

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

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

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

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

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