古典加密系统.ppt

1、1,古典加密系統,黃志雄,2/46,對稱式加密系統,使用同一種演算法及金鑰進行加密、解密,明文,明文,演算法及金鑰,演算法及金鑰,加密,解密,以密文傳輸,3/46,對稱式加密系統,加密程序 C = EK(P) P 為明文(Plaintext)訊息 K 為金鑰(Key) E 為加密演算法(Encrypt algorithm) C 為密文(Ciphertext) 解密程序 P = DK(C) D 為解密演算法(Decrypt algorithm),4/46,對稱式加密系統,加解密演算法原則 取代(substitution)：將明文中的每個元素，對應到另一個元素(如一個位元、字母) 置換(trans

2、position)：將明文中的元素重新排列,5/46,密碼破解,想還原 P 或 K 的行為就稱為密碼破解 密碼破解方式 僅知密文(Ciphertext only) 已知明文(Plaintext only) 自選明文(Known plaintext) 自選密文(Chosen ciphertext) 自選文字(Chosen text),6/46,計算上的安全,計算上的安全(Computationally secure) 破解密文所需成本 密文本身價值 破解密文所需時間 訊息有效壽命,7/46,暴力破解,逐一嚐試可能的金鑰 如學生Email密碼僅設成數字四位數 猜測：00009999 最大猜測數：1

3、0000次 每秒猜測10次，需10000/10秒 約17分鐘內便能破解,8/46,暴力破解,秒=1000毫秒=1000000微秒,9/46,古典加密技術,10/46,埃及象形文字,西元前19世紀，埃及人將象形文字寫在各處以聯絡族人,11/46,埃及象形文字,因此埃及象形文字乃是我們有知以來最早的加密系統,12/46,舊約聖經,西元前5世紀，Adbash密文轉換成希伯來文 使用 “替換” 方式加解密 “HSIUPING” “SHRFKRMT”,13/46,斯巴達加密,西元前5世紀，於希臘斯巴達，使用一種名為 “Scytale” 的權仗，並將長條皮革寫上訊息，捲在權仗上便能解密。,14/46,Po

4、lybius Square,Polybius (201BC120BC)希臘人，發明一 5 x 5 方格加密，將字母轉換成數字。 先取得列號，再取得欄號 “TAIWAN” “441124521133”,15/46,凱撒加密法,Julius Caesar (100BC44AD)，羅馬皇帝，發明凱撒加密法，亦稱凱撒位移 將每個字元往後推三個字元 明文：Meet me after the toga party 密文：PHHW PH DIWHU WKH WRJD SDUWB,16/46,凱撒加密法,將每一字母設定為數字(A=0, B=1) 加密方法 C=E(P)=(P + 3) mod 26 解密方法

5、P=D(C)=(C 3) mod 26,17/46,凱撒加密法應用,將 Caesar 加密演算法表示為 C=Ek(P)=(P + k) mod 26 解密 P=Dk(C)=(C k) mod 26 暴力破解必須嘗試25種k值 k=1, 2, , 25,18/46,凱撒加密法暴力破解,PHHW PH DIWHU WKH WRJD SDUWB oggv og chvgt vjg vgic rctva nffu nf bgufs uif uphb qbsuz meet me after the toga party ldds ld zesdq sgd snfz ozqsx kccr kc ydrcp

6、 rfc rmey nyprw jbbq jb xcqbo qeb qldx mxoqv ： qiix qi ejxiv xli xske tevxc,密文,k=1,k=2,k=3,k=4,k=5,k=6,k=25,19/46,凱撒加密法,凱撒加密法課堂練習 密文為 “QXFTXK” 明文為？,20/46,Mono alphabetic 加密法,有別於Caesar加密法的全部位移k個位置 改為單一字母個別位移固定的位置 如 aS bA cH dV,21/46,破解Mono alphabetic,密文 UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVU

7、EPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ 明文=? 利用統計方式，分析字母出現頻率,22/46,破解Mono alphabetic,一般英文文章中，字元相對出現頻率,23/46,破解Mono alphabetic,UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ t a e e te a that e e a aVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX e t ta t ha e ee a e th z aEP

8、YEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ e e e tat e the t 逐一測試解密： it was disclosed yesterday that several informal butdirect contacts have been made with politicalrepresentatives of the viet cong in moscow,24/46,跳舞小人歷險記,摘自福爾摩斯(Sherlock Holmes) “the Adventure of the Dancing Men” 住在英國的Hilton Cubitt先生最近娶了美國

9、Chicago的Elsie Patrick Cubitt在花園發現一張畫有跳舞的小人字條，Elsie一看，臉色大變,25/46,跳舞小人歷險記,Cubitt寄給Holmes，並前往Holmes家說明所知的一切 Holmes直覺認為這是一個訊息，而非小孩子的塗鴉 因提供的字條太少，Holmes請Cubitt有看到新的，再傳給Holmes看,26/46,跳舞小人歷險記,幾日後，Cubitt又在工具室門上發現粉筆畫的小人，並臨摹下來寄給Holmes,27/46,跳舞小人歷險記,接下來的幾天，陸續在工具室發現小人圖，Cubitt全寄給Holmes看,28/46,跳舞小人歷險記,Holmes將全部小人字

10、條研究數天後，發現大事不妙，立即趕往Cubitt家，欲阻擋悲劇發生 抵達Cubitt家後，Cubitt已受槍傷身亡，Elsie也身受重傷,29/46,跳舞小人歷險記,幾番調查後，Holmes終將案情查清楚，便寫下一紙條，派馬童送至一間叫 “Elriges” 旅館的 Abe Slaney 先生 警察詢問Holmes為何對案情這麼了解，Holmes才開始說明如何破解小人紙條,30/46,跳舞小人歷險記,Holmes分析所有的圖，發現出現次數最多，便將此符號換成 “E” 因此圖4能解讀成 “_E_E_” 可能為 “LEVER(槓桿)”, “NEVER(絕不)”, “SEVER(分開)”。Holmes

11、猜測是NEVER。 因此大膽假設便是 “Come Elsie”,31/46,跳舞小人歷險記,所以第一張字條可以解開成 _M _ERE _E SL_NE_ AM _ERE A_E SL_NE_ AM HERE ABE SLANEY,32/46,跳舞小人歷險記,第二張字條亦可解讀 A_ ELRI_ES AT ELRIGES,33/46,跳舞小人歷險記,最後一張 ELSIE _RE_ARE TO MEET THY GO_ ELSIE PREPARE TO MEET THY GOD,34/46,跳舞小人歷險記,警察擔心兇手跳跑，Holmes說：他等會兒就自己過來了 Holmes稍早早已寫了字條請兇手過

12、來 COME HERE AT ONCE,35/46,跳舞小人歷險記,Abe Slaney到場即被逮捕，才道出他是Elsie在Chicago的未婚夫。Elsie發現Slaney和她父親組幫派為非作歹，才逃出與Cubitt結婚,36/46,仿射密碼(Affine Cipher),將字母轉換成數字(a=0, b=1, , z=25) 加密： C=E(M)=(aM+b) mod 26 a, b為整數，a必須與 26 互質 解密： M=D(C)=a-1(C-b) mod 26,37/46,仿射密碼(Affine Cipher),A與B事先協定好密鑰為 K=(3, 8) 加密函數 E(M) = (3M+8

13、) mod 26 傳輸明文 “HIT” (7, 8, 19) 加密： (3*7 + 8) mod 26 = 3 “D” (3*8 + 8) mod 26 = 6 “G” (3*19 + 8) mod 26 = 13 “N”,38/46,仿射密碼(Affine Cipher),“HIT” “DGN” (3, 6, 13) 解密： 9(3 8) mod 26 = 7 “H” 9(6 8) mod 26 = 8 “I” 9(13 8) mod 26 = 19 “T”,39/46,仿射密碼(Affine Cipher),課堂練習 C=E(M)=(aM+b) mod 26 K = (7, 4) M =

14、“HIT” (7, 8, 19) C = ? M=D(C)=a-1(C-b) mod 26,40/46,Vigenre密碼,16世紀法國人Vigenre發展的多套字母替代法(Polyalphabetic substitution) 使用區塊加密 加密 C=E(M)=M+k (mod 26) 解密 M=D(C)=C-k (mod 26),41/46,Vigenre密碼,舉例 金鑰： “hsiuping” (7, 18, 8, 20, 15, 8, 13, 6),明文,金鑰,密文,42/46,Vigenre密碼,課堂練習 明文為 “ILOVETAIWAN” 金鑰為 “ROC” 密文 = ?,43/

15、46,Hill 加密法,由數學家Lester Hill於1929年發明 使用矩陣加密 金鑰 k= det k 必須與 26 互質,44/46,Hill 加密法,加密範例 明文為 “hsiuping” (7, 18, 8, 20, 15, 8, 13, 6) Ek(M)= Ek(M)= “hsiuping” 加密成 “ZPCAXZUL”,45/46,Hill 加密法,解密範例 先取得 k 之反矩陣,46/46,Hill 加密法,解密範例 每四個字母解密一次 “ZPCA” (25, 15, 2, 0) “XZUL” (23, 25, 19, 11),47/46,Hill 加密法,課堂練習 k = m = “LOVE” C = ?,48/46,Playfair加密法,1854年由英國科學家Sir Charles Wheatstone發明 使用 5 x 5 階字元矩陣 選定一金鑰，如 “hsiuping” 將金鑰從左上填入 I/J 視為同一字元 將剩餘字母一一填入(不得重覆),49/46,Playfair加密法,每次兩個字母加密一次 如這兩個字母相同，則