計算機密碼學(xué)課件

1、計算機密碼學(xué)8/19/20221密碼學(xué)的發(fā)展歷程第一次世界大戰(zhàn)前，密碼學(xué)重要的進(jìn)展很少出現(xiàn)在公開文獻(xiàn)中1918年，20世紀(jì)最有影響的分析文章，重合指數(shù)及其在密碼學(xué)中的應(yīng)用問世1949年，Shanon發(fā)表了題為“保密系統(tǒng)的通信理論”19491967密碼學(xué)文獻(xiàn)很少1976年，W.Diffie,M.Hellman提出了公開密鑰密碼1977年，美國聯(lián)邦政府正式頒布DES1977年至今，公開的密碼學(xué)研究爆炸性的增長8/19/20222密碼學(xué)的基本概念密碼學(xué)分類：密碼編制學(xué)和密碼分析學(xué)密碼系統(tǒng)的組成： （1）明文空間M； （2）密文空間C； （3）密鑰空間K，對任意kK，k=（kd，ke）； （4)加密算

2、法E，C=E（M，ke）； （5）解密算法D，M=D（C，kd）。8/19/20223密碼體制的分類根據(jù)密鑰分類： 1 ke=kd或ke kd稱為單鑰或?qū)ΨQ或傳統(tǒng)； 2 ke kd稱為雙鑰或非對稱，進(jìn)而由ke不能推出kd稱為公鑰密碼體制。根據(jù)對明文的劃分與密鑰的使用方法不同可將密碼體制分為分組密碼和序列密碼體制。8/19/20224密碼分析者攻擊密碼的方法主要有以下三種窮舉攻擊統(tǒng)計分析攻擊數(shù)學(xué)分析攻擊8/19/20225根據(jù)密碼分析者可利用的數(shù)據(jù)來分類，破譯密碼的類型分為三種僅知密文攻擊已知明文攻擊：計算機程序易受這種攻擊選擇明文攻擊：計算機文件系統(tǒng)和數(shù)據(jù)庫易受這種攻擊8/19/20226置換

3、密碼把明文中的字母重新排列，字母本身不變例：明文為this cryptosystem is not secure。 排成矩陣： thiscr yptosy stemis notsec ure密文為tysnu hptor itete soms csie rysc。 8/19/20227單表代替密碼首先構(gòu)造一個密文字母表，然后用密文字母表中的字母或字母組來代替明文字母表中的字母或字母組，各字母或字母組的相對位置不變，但其本身改變了。設(shè)A=a0，a1，an-1 為含n個字母的明文字母表，B=b0，b1，bn-1 為含n個字母的密文字母表，定義一個由A到B的一一映射。f：AB，f（ai）=bi設(shè)明文M

4、=（m0，m1，mn-1），則相應(yīng)的密文C=（f（m0），f（m1），f（mn-1）8/19/20228幾類單表代替密碼加法密碼：f（ai）=aj，ji+k（mod n），0kn，取n=26。乘法密碼：f（ai）=aj，jik（mod n），0kn，（k，n）=1。仿射密碼：f（ai）=aj，jik1+k0（mod n），（k1，n）=1。密鑰詞組代替密碼用一詞組或短語作密鑰，去掉密鑰中的重復(fù)字母，把結(jié)果作為矩陣的第一行，其次從明文字母表中補入其余字母，最后按某一順序從矩陣中取出字母構(gòu)成密文字母表。例：密鑰為red star，明文為data security。8/19/20229字母與數(shù)字對應(yīng)

5、表8/19/202210單表代替密碼的統(tǒng)計分析極高頻率字母組：e z次高頻率字母組：taonirsh jvbhdilc中等頻率字母組：dlucm xseyr低頻率字母組：pfywgbv tfkawnp甚低頻率字母組：jkqxz mqgou雙字母：th he in er an re ed 三字母：the ing and her are ent8/19/202211舉例YKHLBA JCZ SVIJ JZB LZVHI JCZ VHJ DR IZXKHLBA VSS RDHEI DR YVJV LBXSKYLBA YLALJVS IFZZXC CVI LEFHDNZY EVBTRDSY JCZ F

6、HLEVHT HZVIDB RDH JCLI CVI WZZB JCZ VYNZBJ DR ELXHDZSZXJHDBLXI JCZ XDEFSZQLJT DR JCZ RKBXJLDBI JCVJ XVB BDP WZ FZHRDHEZY WT JCZ EVXCLBZ CVI HLIZB YHVEVJLXVSST VI V HZIKSJ DR JCLI HZXZBJ YZNZSDFEZBJ LB JZXCBDSDAT EVBT DR JCZ XLFCZH ITIJZEI JCVJ PZHZ DBXZ CDBILYZHZY IZXKHZ VHZ BDP WHZVMVWSZ8/19/202212

7、Z：e，va，三字母單詞JCZ？e：the2字母單詞VIa？：an，as，am，at，I s三字母單詞VHZa？e：are，age Hr。三字母單詞JZBte？： Bn4字母單詞JCLIth？s： LI4字母單詞WZZB？een： Wb2字母單詞WTB？： Ty6字母單詞HZVIDBreas？n： Do2字母單詞DRo？： Rf3字母單詞BDPno？： Pw4字母單詞DBXZon？e： Xc4字母單詞EVBT？any： Em8/19/2022133字母單詞BDPno？： Pw4字母單詞DBXZon？e： Xc4字母單詞EVBT？any： EmIFZZXCs？eech： FpFZHRDHEZYp

8、erforme？：YdVSSa？： SlJZXCBDSDATtechnono？yAg3字母單詞結(jié)尾LBAi？g： BnYKHLBAd？ring： KuLEFHDNZYimpro？ed： NvWHZVMVWSZbrea？able Mk8/19/202214多表代替密碼構(gòu)造d個密文字母表設(shè)A=a0，a1，an-1 為含n個字母的明文字母表，Bj=bj0，bj1，bjn-1 ，j=0，1， ，d-1為d個含n個字母的密文字母表，定義d個映射。fj：ABj，fj（ai）=bji設(shè)明文M=（m0，m1，mn-1），則相應(yīng)的密文C=（f0（m0），f1（m1），fd-1（md-1）， fd（md）， ）8

9、/19/202215Vigenere密碼若K=k1k2km， M=m1m2mn， C=c1c2cn其中cimi+ki（mod 26）至于密鑰k可以通過周期性地延長，周而復(fù)始，反復(fù)以至無窮。即ki+lm=ki例：密鑰為cipher，明文為thiscrytosystem。8/19/202216對Vigenere密碼的分析確定密鑰字的長度：1Kasiski測試，2使用重合指數(shù)。確定密鑰。重合指數(shù)8/19/202217例：UFQUIUDWFHGLZARIHWLLWYYFSYYQATJPFKMUXSSWWCSVFAEVWWGQCMVVSWFKUTBLLGZFVITYOEIFASJWGGSJEPNSUET

10、PTMPOPHZSFDCXEPLZQWKDWFXWTHASPWIUOVSSSFKWWLCCEZWEUEHGVGLRLLGWOFKWLUWSHEVWSTTUARCWHWBVTGNITJRWWKCOTPGMILRQESKWGYHAENDIULKDHZIQASFMPRGWRVPBUIQQDSVMPFZMVEGEEPFODJQCHZIUZZM8/19/202218DWF：7，112 105LLG：64，149 85m？=5UUGIWYJ確定密鑰字母：考慮兩行的互重合指數(shù)是有用的，求出ij=kj-ki8/19/202219代數(shù)密碼或Vernam密碼若K=k1k2k3 ， M=m1m2m3 ，其中mi=0

11、或1， ki=0或1， C=c1c2c3 其中ci=mi+ki例：明文為cat，密鑰為key，于是M=0011K=1000C=10118/19/202220Hill加密算法Hill加密算法的基本思想是將l個明文字母通過線性變換將它們轉(zhuǎn)換為l個密文字母。解密只要作一次逆變換就可以了，密鑰就是變換矩陣本身。8/19/202221DES數(shù)據(jù)加密標(biāo)準(zhǔn)初始置換IP將置換輸出的64位數(shù)據(jù)分成左右兩半，左一半稱為L0，右一半稱為R0計算函數(shù)的16次迭代。Li=Ri-1， Ri=Li-1f（ Ri-1， Ki）。i=1，16最后一次的迭代L16放在右邊， R16放在左邊。再經(jīng)逆初始置換IP-1，產(chǎn)生64位密文

12、。8/19/202222密鑰編排函數(shù)KS算法置換選擇1：首先從64位密鑰中去掉8個奇偶校驗位，然后打亂重排，前28位作為C0，后28位作為D0。循環(huán)左移：Ci=LSi（ Ci-1）， Di=LSi（ Di-1）， i=1，16。置換選擇2：從Ci和Di（共56位）中選擇出一個48位的子密鑰Ki。8/19/202223加密函數(shù)f選擇置換E（ Ri-1）=48位 E（ Ri-1） Ki選擇函數(shù)組S，1）輸出不是輸入的線性和仿射函數(shù)；2）改變其中任一位，輸出至少有兩位發(fā)生變化；3）保持1位不變，其余5位變化，輸出中的0和1個數(shù)接近相等。8/19/202224IDEA密碼系統(tǒng)64bit的數(shù)據(jù)塊分成4個

13、子塊為x1， x2， x3， x4，作為迭代第一輪的輸入，全部共8輪迭代，每輪迭代都是4個子塊彼此間以及16bit的子密鑰進(jìn)行異或，mod216的加法運算， mod（216+1）的乘法運算。在每一輪中，執(zhí)行的順序如下：8/19/202225X1和第一個密鑰子塊相乘；X2和第二個密鑰子塊相加；X3和第三個密鑰子塊相加；X4和第四個密鑰子塊相乘；將第1）步和3）步的結(jié)果相異或；將第2）步和4）步的結(jié)果相異或；5）步的結(jié)果與第五個密鑰子塊相乘；將第6）步和7）步的結(jié)果相加；8）步的結(jié)果與第六個密鑰子塊相乘；8/19/20222610）將第7）步和9）步的結(jié)果相加；11）將第1）步和9）步的結(jié)果相異或

14、；12）將第3）步和9）步的結(jié)果相異或；13）將第2）步和10）步的結(jié)果相異或；14）將第4）步和10）步的結(jié)果相異或；第一輪的輸出是4個子塊，即11）、12） 、13） 、14）步的結(jié)果；將中間兩個塊交換（最后一輪除外）8/19/202227為下一輪輸入。在經(jīng)過8輪運算之后，有一個最后的輸出變換（1） X1和第一個密鑰子塊相乘；（2）X2和第二個密鑰子塊相加；（3）X3和第三個密鑰子塊相加；（4）X4和第四個密鑰子塊相乘；最后，這4個子塊連接到一起產(chǎn)生密文。8/19/202228分組密碼的工作方式電子密碼本模式（ECB）：設(shè)明文M=m1m2mn ， C=c1c2cn ，其中ci=E（mi，K

15、），i=1， ，n。電子密碼本模式是分組密碼的基本工作方式。輸出反饋模式（OFB）：在OFB模式中，先產(chǎn)生密鑰流，然后將它與明文進(jìn)行異或，定義Z0=IV，然后用Zi= E（Zi-1，K），i1計算Z1Z28/19/202229通過ci=mi+Zi ，i1，來加密明文序列m1m2。3密碼分組鏈接模式（CBC）：定義 C0=IV ，Ci=E（Mi+Ci-1，K），i1，使Mi=Mj，但因Ci-1Cj-1，故有Ci Cj。解密時Mi=D（Ci，K）+Ci-1， i1。4密碼反饋模式（CFB）： C0=IV ，Zi=E（Ci-1，K）i 1。像在OFB模式中一樣，Ci=Mi+Zi， i 1。即使Mi=Mj，但因Zi Zj，加密錯誤傳播無界。解密Mi=Ci+E（Ci-1，K）， i 1。8/19/202230短塊加密填充法：用無用的數(shù)據(jù)填充短塊，使之成為標(biāo)準(zhǔn)塊，然后在利用分組密碼進(jìn)行加密。通常用最后8位作為填充指示符。序列密碼加密法：