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

1古典加密系統(tǒng)黃志雄2/46對稱式加密系統(tǒng)使用同一種演算法及金鑰進行加密、解密明文明文演算法及金鑰演算法及金鑰加密解密以密文傳輸3/46對稱式加密系統(tǒng)加密程序C=EK(P)P

為明文(Plaintext)訊息K

為金鑰(Key)E

為加密演算法(Encryptalgorithm)C

為密文(Ciphertext)解密程序P=DK(C)D

為解密演算法(Decryptalgorithm)4/46對稱式加密系統(tǒng)加解密演算法原則取代(substitution)：將明文中的每個元素，對應到另一個元素(如一個位元、字母)置換(transposition)：將明文中的元素重新排列5/46密碼破解想還原P或K的行為就稱為「密碼破解」密碼破解方式僅知密文(Ciphertextonly)已知明文(Plaintextonly)自選明文(Knownplaintext)自選密文(Chosenciphertext)自選文字(Chosentext)7/46暴力破解逐一嚐試可能的金鑰如學生Email密碼僅設成數(shù)字四位數(shù)猜測：0000~9999最大猜測數(shù)：10000次每秒猜測10次，需10000/10秒約17分鐘內(nèi)便能破解8/46暴力破解金鑰長度(bit)可能的金鑰數(shù)費時每微秒測試一次32232=4.3*1092.15毫秒56256=7.2*101610.01小時1282128=3.4*10385.4*1018年秒=1000毫秒=1000000微秒10/46埃及象形文字西元前19世紀，埃及人將象形文字寫在各處以聯(lián)絡族人11/46埃及象形文字因此埃及象形文字乃是我們有知以來最早的加密系統(tǒng)12/46舊約聖經(jīng)西元前5世紀，Adbash密文轉(zhuǎn)換成希伯來文使用“替換”方式加解密“HSIUPING”“SHRFKRMT”13/46斯巴達加密西元前5世紀，於希臘斯巴達，使用一種名為“Scytale”

的權仗，並將長條皮革寫上訊息，捲在權仗上便能解密。14/46PolybiusSquarePolybius(201BC~120BC)希臘人，發(fā)明一5x5方格加密，將字母轉(zhuǎn)換成數(shù)字。先取得列號，再取得欄號“TAIWAN”“441124521133”123451ABCDE2FGHI/JK3LMNOP4QRSTU5VWXYZ15/46凱撒加密法JuliusCaesar(100BC~44AD)，羅馬皇帝，發(fā)明「凱撒加密法」，亦稱「凱撒位移」將每個字元往後推三個字元明文：Meetmeafterthetogaparty密文：PHHWPHDIWHUWKHWRJDSDUWB17/46凱撒加密法應用將Caesar加密演算法表示為C=Ek(P)=(P+k)mod26解密P=Dk(C)=(C–k)mod26暴力破解必須嘗試25種k值k=1,2,…,2518/46凱撒加密法暴力破解PHHWPHDIWHUWKHWRJDSDUWBoggvogchvgtvjgvgicrctvanffunfbgufsuifuphbqbsuzmeetmeafterthetogapartylddsldzesdqsgdsnfzozqsxkccrkcydrcprfcrmeynyprwjbbqjbxcqboqebqldxmxoqv

：qiixqiejxivxlixsketevxc密文k=1k=2k=3k=4k=5k=6k=2520/46Monoalphabetic加密法有別於Caesar加密法的全部位移k個位置改為單一字母個別位移固定的位置如aSbAcHdV21/46破解Monoalphabetic密文UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ

VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX

EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ明文=?利用統(tǒng)計方式，分析字母出現(xiàn)頻率P13.33H5.83F3.33B1.67C0.00Z11.67D5.00W3.33G1.67L0.00S8.33E5.00Q2.50Y1.67K0.00U8.33V4.17T2.50I0.83N0.00O7.50X4.17A1.67J0.83R0.00M6.6722/46破解Monoalphabetic一般英文文章中，字元相對出現(xiàn)頻率23/46破解MonoalphabeticUZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ

taeeteathateeaa

VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX

ettathaeeeaethza

EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

eeetatethet逐一測試解密：itwasdisclosedyesterdaythatseveralinformalbut

directcontactshavebeenmadewithpolitical

representativesofthevietconginmoscow24/46跳舞小人歷險記摘自福爾摩斯(SherlockHolmes)“theAdventureoftheDancingMen”住在英國的HiltonCubitt先生最近娶了美國Chicago的ElsiePatrickCubitt在花園發(fā)現(xiàn)一張畫有跳舞的小人字條，Elsie一看，臉色大變25/46跳舞小人歷險記Cubitt寄給Holmes，並前往Holmes家說明所知的一切Holmes直覺認為這是一個訊息，而非小孩子的塗鴉因提供的字條太少，Holmes請Cubitt有看到新的，再傳給Holmes看27/46跳舞小人歷險記接下來的幾天，陸續(xù)在工具室發(fā)現(xiàn)小人圖，Cubitt全寄給Holmes看28/46跳舞小人歷險記Holmes將全部小人字條研究數(shù)天後，發(fā)現(xiàn)大事不妙，立即趕往Cubitt家，欲阻擋悲劇發(fā)生抵達Cubitt家後，Cubitt已受槍傷身亡，Elsie也身受重傷30/46跳舞小人歷險記Holmes分析所有的圖，發(fā)現(xiàn)

出現(xiàn)次數(shù)最多，便將此符號換成“E”因此圖4

能解讀成“_E_E_”

可能為“LEVER(槓桿)”,“NEVER(絕不)”,“SEVER(分開)”。Holmes猜測是NEVER。因此大膽假設

便是“ComeElsie”31/46跳舞小人歷險記所以第一張字條

可以解開成_M_ERE__ESL_NE_AM_EREA_ESL_NE_AMHEREABESLANEY32/46跳舞小人歷險記第二張字條亦可解讀A_ELRI_ESATELRIGES33/46跳舞小人歷險記最後一張ELSIE_RE_ARETOMEETTHYGO_ELSIEPREPARETOMEETTHYGOD34/46跳舞小人歷險記警察擔心兇手跳跑，Holmes說：「他等會兒就自己過來了」Holmes稍早早已寫了字條請兇手過來COMEHEREATONCE35/46跳舞小人歷險記AbeSlaney到場即被逮捕，才道出他是Elsie在Chicago的未婚夫。Elsie發(fā)現(xiàn)Slaney和她父親組幫派為非作歹，才逃出與Cubitt結(jié)婚36/46仿射密碼(AffineCipher)將字母轉(zhuǎn)換成數(shù)字(a=0,b=1,…,z=25)加密：C=E(M)=(aM+b)mod26a,b為整數(shù)，a必須與26互質(zhì)解密：M=D(C)=a-1(C-b)mod26a1357911151719212325a-1192115319723115172537/46仿射密碼(AffineCipher)A與B事先協(xié)定好密鑰為K=(3,8)加密函數(shù)E(M)=(3M+8)mod26傳輸明文“HIT”

(7,8,19)加密：(3*7+8)mod26=3

“D”(3*8+8)mod26=6

“G”(3*19+8)mod26=13

“N”38/46仿射密碼(AffineCipher)“HIT”

“DGN”(3,6,13)解密：9(3–8)mod26=7

“H”9(6–8)mod26=8“I”9(13–8)mod26=19“T”a1357911151719212325a-1192115319723115172539/46仿射密碼(AffineCipher)課堂練習C=E(M)=(aM+b)mod26K=(7,4)M=“HIT”(7,8,19)C=?M=D(C)=a-1(C-b)mod2640/46Vigenère密碼16世紀法國人Vigenère發(fā)展的多套字母替代法(Polyalphabeticsubstitution)使用區(qū)塊加密加密C=E(M)=M+k(mod26)解密M=D(C)=C-k(mod26)41/46Vigenère密碼舉例金鑰：“hsiuping”(7,18,8,20,15,8,13,6)wearefamily22401745012811247188201581367188322811191313181536DWILTNNSPDG明文金鑰密文42/46Vigenère密碼課堂練習明文為“ILOVETAIWAN”金鑰為“ROC”密文=?43/46Hill加密法由數(shù)學家LesterHill於1929年發(fā)明使用矩陣加密金鑰k=detk

必須與26互質(zhì)44/46Hill加密法加密範例明文為“hsiuping”(7,18,8,20,15,8,13,6)Ek(M)=Ek(M)=“hsiuping”加密成“ZPCAXZUL”45/46Hill加密法解密範例先取得k

之反矩陣46/46Hill加密法解密範例每四個字母解密一次“ZPCA”(25,15,2,0)“XZUL”(23,25,19,11)47/46Hill加密法課堂練習k=m=“LOVE”C=?

48/46Playfair加密法1854年由英國科學家SirCharlesWhe