《傳統(tǒng)加密方法》ppt課件

1、古典加密系統(tǒng)黃志雄對(duì)稱式加密系統(tǒng)n運(yùn)用同一種演算法及金鑰進(jìn)行加密、解密明文明文演算法及金鑰演算法及金鑰加密解密以密文傳輸對(duì)稱式加密系統(tǒng)n加密程序 C = EK(P)nP 為明文(Plaintext)訊息nK 為金鑰(Key)nE 為加密演算法(Encrypt algorithm)nC 為密文(Ciphertext)n解密程序 P = DK(C)nD 為解密演算法(Decrypt algorithm)對(duì)稱式加密系統(tǒng)n加解密演算法原則n取代(substitution)：將明文中的每個(gè)元素，對(duì)應(yīng)到另一個(gè)元素(如一個(gè)位元、字母)n置換(transposition)：將明文中的元素重新陳列密碼破解n想還

2、原 P 或 K 的行為就稱為密碼破解n密碼破解方式n僅知密文(Ciphertext only)n知明文(Plaintext only)n自選明文(Known plaintext)n自選密文(Chosen ciphertext)n自選文字(Chosen text)計(jì)算上的平安n計(jì)算上的平安(Computationally secure)n破解密文所需本錢 密文本身價(jià)值n破解密文所需時(shí)間 訊息有效壽命暴力破解n逐一嚐試能夠的金鑰n如學(xué)生Email密碼僅設(shè)成數(shù)字四位數(shù)n猜測(cè)：00009999n最大猜測(cè)數(shù)：10000次n每秒猜測(cè)10次，需10000/10秒n約17分鐘內(nèi)便能破解暴力破解金鑰長(zhǎng)度(bit

3、)能夠的金鑰數(shù)費(fèi)時(shí)每微秒測(cè)試一次32232=4.3*1092.15毫秒56256=7.2*1016 10.01小時(shí)1282128=3.4*10385.4*1018年秒=1000毫秒=1000000微秒 古典加密技術(shù)埃及象形文字n西元前19世紀(jì)，埃及人將象形文字寫在各處以聯(lián)絡(luò)族人埃及象形文字n因此埃及象形文字乃是我們有知以來(lái)最早的加密系統(tǒng)舊約聖經(jīng)n西元前5世紀(jì)，Adbash密文轉(zhuǎn)換成希伯來(lái)文n運(yùn)用 “替換 方式加解密n“HSIUPINGn n“SHRFKRMT斯巴達(dá)加密n西元前5世紀(jì)，於希臘斯巴達(dá)，運(yùn)用一種名為 “Scytale 的權(quán)仗，並將長(zhǎng)條皮革寫上訊息，捲在權(quán)仗上便能解密。Polybius

4、 SquarenPolybius (201BC120BC)希臘人，發(fā)明一 5 x 5 方格加密，將字母轉(zhuǎn)換成數(shù)字。n先獲得列號(hào)，再獲得欄號(hào)n“TAIWANn n“441124521133123451ABCDE2FGHI/JK3LMNOP4QRSTU5VWXYZ凱撒加密法nJulius Caesar (100BC44AD)，羅馬皇帝，發(fā)明凱撒加密法，亦稱凱撒位移n將每個(gè)字元往後推三個(gè)字元n明文：Meet me after the toga partyn密文：PHHW PH DIWHU WKH WRJD SDUWB凱撒加密法n將每一字母設(shè)定為數(shù)字(A=0, B=1)n加密方法nC=E(P)=(P

5、+ 3) mod 26n解密方法nP=D(C)=(C 3) mod 26A B C D E F G H I J K L M N O P Q R S T U V W X Y Z012345678910111213141516171819202122232425凱撒加密法應(yīng)用n將 Caesar 加密演算法表示為nC=Ek(P)=(P + k) mod 26n解密nP=Dk(C)=(C k) mod 26n暴力破解必須嘗試25種k值nk=1, 2, , 25凱撒加密法暴力破解nPHHW PH DIWHU WKH WRJD SDUWBnoggv og chvgt vjg vgic rctvannffu

6、 nf bgufs uif uphb qbsuznmeet me after the toga partynldds ld zesdq sgd snfz ozqsxnkccr kc ydrcp rfc rmey nyprwnjbbq jb xcqbo qeb qldx mxoqvn ：nqiix qi ejxiv xli xske tevxc密文k=1k=2k=3k=4k=5k=6k=25凱撒加密法n凱撒加密法課堂練習(xí)n密文為 “QXFTXKn明文為？Mono alphabetic 加密法n有別於Caesar加密法的全部位移k個(gè)位置n改為單一字母?jìng)€(gè)別位移固定的位置n如 aS bA cH dV破

7、解Mono alphabeticn密文nUZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQn明文=?n利用統(tǒng)計(jì)方式，分析字母出現(xiàn)頻率P 13.33H 5.83F 3.33B 1.67C 0.00Z 11.67D 5.00W 3.33G 1.67L 0.00S 8.33E 5.00Q 2.50Y 1.67K 0.00U 8.33V 4.17T 2.50I 0.83N 0.00O 7.50X 4.17A 1.6

8、7J 0.83R 0.00M 6.67破解Mono alphabeticn普通英文文章中，字元相對(duì)出現(xiàn)頻率破解Mono alphabeticnUZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ t a e e te a that e e a aVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX e t ta t ha e ee a e th z aEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ e e e tat e the tn逐一測(cè)試解密：nit was disclosed yesterday t

9、hat several informal butdirect contacts have been made with politicalrepresentatives of the viet cong in moscow跳舞小人歷險(xiǎn)記n摘自福爾摩斯(Sherlock Holmes) “the Adventure of the Dancing Menn住在英國(guó)的Hilton Cubitt先生最近娶了美國(guó)Chicago的Elsie PatricknCubitt在花園發(fā)現(xiàn)一張畫有跳舞的小人字條，Elsie一看，臉色大變跳舞小人歷險(xiǎn)記nCubitt寄給Holmes，並前往Holmes家說(shuō)明所知的一切

10、nHolmes直覺認(rèn)為這是一個(gè)訊息，而非小孩子的塗鴉n因提供的字條太少，Holmes請(qǐng)Cubitt有看到新的，再傳給Holmes看跳舞小人歷險(xiǎn)記n幾日後，Cubitt又在工具室門上發(fā)現(xiàn)粉筆畫的小人，並臨摹下來(lái)寄給Holmes跳舞小人歷險(xiǎn)記n接下來(lái)的幾天，陸續(xù)在工具室發(fā)現(xiàn)小人圖，Cubitt全寄給Holmes看跳舞小人歷險(xiǎn)記nHolmes將全部小人字條研討數(shù)天後，發(fā)現(xiàn)大事不妙，立刻趕往Cubitt家，欲阻擋悲劇發(fā)生n抵達(dá)Cubitt家後，Cubitt已受槍傷身亡，Elsie也身受重傷跳舞小人歷險(xiǎn)記n幾番調(diào)查後，Holmes終將案情查清楚，便寫下一紙條，派馬童送至一間叫 “Elriges 旅館的

11、Abe Slaney 先生n警察詢問(wèn)Holmes為何對(duì)案情這麼了解，Holmes才開始說(shuō)明如何破解小人紙條跳舞小人歷險(xiǎn)記nHolmes分析一切的圖，發(fā)現(xiàn)出現(xiàn)次數(shù)最多，便將此符號(hào)換成 “En因此圖4能解讀成 “_E_E_ n能夠?yàn)?“LEVER(槓桿), “NEVER(絕不), “SEVER(分開)。Holmes猜測(cè)是NEVER。n因此大膽假設(shè)便是 “Come Elsie跳舞小人歷險(xiǎn)記n所以第一張字條可以解開成n_M _ERE _E SL_NE_nAM _ERE A_E SL_NE_nAM HERE ABE SLANEY跳舞小人歷險(xiǎn)記n第二張字條亦可解讀nA_ ELRI_ESnAT ELRIGE

12、S跳舞小人歷險(xiǎn)記n最後一張nELSIE _RE_ARE TO MEET THY GO_nELSIE PREPARE TO MEET THY GOD跳舞小人歷險(xiǎn)記n警察擔(dān)心兇手跳跑，Holmes說(shuō)：他等會(huì)兒就本人過(guò)來(lái)了nHolmes稍早早已寫了字條請(qǐng)兇手過(guò)來(lái)nCOME HERE AT ONCE跳舞小人歷險(xiǎn)記nAbe Slaney到場(chǎng)即被拘捕，才道出他是Elsie在Chicago的未婚夫。Elsie發(fā)現(xiàn)Slaney和她父親組幫派為非作歹，才逃出與Cubitt結(jié)婚仿射密碼(Affine Cipher)n將字母轉(zhuǎn)換成數(shù)字(a=0, b=1, , z=25)n加密：nC=E(M)=(aM+b) mod

13、26na, b為整數(shù)，a必須與 26 互質(zhì)n解密：nM=D(C)=a-1(C-b) mod 26a1357911151719212325a-11921153197231151725仿射密碼(Affine Cipher)nA與B事先協(xié)定好密鑰為 K=(3, 8)n加密函數(shù) E(M) = (3M+8) mod 26n傳輸明文 “HIT (7, 8, 19)n加密：n(3*7 + 8) mod 26 = 3 “Dn(3*8 + 8) mod 26 = 6 “Gn(3*19 + 8) mod 26 = 13 “N仿射密碼(Affine Cipher)n“HIT “DGN (3, 6, 13)n解密：n

14、9(3 8) mod 26 = 7 “Hn9(6 8) mod 26 = 8 “In9(13 8) mod 26 = 19 “Ta1357911151719212325a-11921153197231151725仿射密碼(Affine Cipher)n課堂練習(xí)nC=E(M)=(aM+b) mod 26nK = (7, 4)nM = “HIT (7, 8, 19)nC = ?nM=D(C)=a-1(C-b) mod 26Vigenre密碼n16世紀(jì)法國(guó)人Vigenre發(fā)展的多套字母替代法(Polyalphabetic substitution)n運(yùn)用區(qū)塊加密n加密nC=E(M)=M+k (mod

15、 26)n解密nM=D(C)=C-k (mod 26)Vigenre密碼n舉例n金鑰： “hsiuping (7, 18, 8, 20, 15, 8, 13, 6)wearefamily22401745012811247188201581367188322811191313181536DWILTNNSPDG明文金鑰密文Vigenre密碼n課堂練習(xí)n明文為 “ILOVETAIWANn金鑰為 “ROCn密文 = ?Hill 加密法n由數(shù)學(xué)家Lester Hill於1929年發(fā)明n運(yùn)用矩陣加密n金鑰 k=ndet k 必須與 26 互質(zhì)4311Hill 加密法n加密範(fàn)例n明文為 “hsiuping

16、(7, 18, 8, 20, 15, 8, 13, 6)nEk(M)=nEk(M)=n“hsiuping 加密成 “ZPCAXZULapcz)26(mod0152251049328252018874311lzux)26(mod11251923637719236813154311Hill 加密法n解密範(fàn)例n先獲得 k 之反矩陣13141314100113011011100143111kHill 加密法n解密範(fàn)例n每四個(gè)字母解密一次n“ZPCA (25, 15, 2, 0)n“XZUL (23, 25, 19, 11)usihCk)26(mod20188766088501522513141ginpCk)26(mod681315464465671125192313141Hill 加密法n課堂練習(xí)nk =nm = “LOVEnC = ? 4311Playfair加密法n1854年由英國(guó)科學(xué)家Sir Charles Wheatstone發(fā)明n運(yùn)用 5 x 5 階字元矩陣n選定一金鑰，如 “hsiupingn將金鑰從左上填入nI/J 視為同一字元n將剩餘字母一一填入(不得重覆)HSI/JUPNGABCDEFKLMOQRTVWXYZPlayfair加密法n每次兩個(gè)字母加密一次n如這兩個(gè)字母一樣，則在其間插入一