第三章 數據保密系統

簡介 評斷因素 保密系統 傳統密碼學 美國數據保密標準 RSA公開金鑰密碼系統 KNAPSACK公開金鑰密碼學 數位簽章

簡介 隱藏術： 特殊通訊技術： 數據保密技術： 明語 密語 把消息的存在性隱藏起來。例如，採用隱形墨水。 以方言或特殊電信設備交談。 寄託於金鑰(key)的保密。 明語 密語

簡介 (續) 加密過程 加密法 密文 明文 鑰匙 解密法 解密過程 密碼與日常生活的關係 “5” 表 1985 年 “C ”表3 月，A為一月 “05”表該月的第5天 5 C05

簡介 (續)

保密系統示意圖 情 書 密 語 密 語 情 書 加密器 解密器

評斷因素 保密技術的價值 度量保密性 保密程度：越高越好 金鑰大小：越小越好 加密器和解密器的複雜性：越簡單越好 錯誤傳播：越少越好 明語擴充：越少越好 度量保密性 密語攻擊 明語攻擊 選擇明語攻擊

保密系統 傳統保密系統 公開金鑰保密系統 加密器所使用的金鑰與解密器的金鑰相同 需要安全可靠的方法把金鑰從此端送到彼端 美國數據保密標準(DES) 公開金鑰保密系統 加密器所使用的金鑰與解密器的金鑰不同 不需要安全的方法來護送金鑰

傳統密碼學

換位法 反轉換位 幾何圖形換位 長方形加密 明文：MEET ME MONDAY MORNING 密文：GNINROM YADNOM EM TEEM 幾何圖形換位 明文：CONCEAL ALL MESSAGES CL OM NE CS ES AA LG AE LS CON CEA LAL LME SSA GES 長方形加密

換位法(續) 循路徑換位 明文：SEND HELP SOON 循途徑換位： S N H L S O E D E P O N 密文： CLOMNECSESAALGAELS 或CCLLSGOEAMSENALEAS 循路徑換位 明文：SEND HELP SOON 循途徑換位： S N H L S O E D E P O N 密文：SNHLSOEDEPON

換位法(續) 途徑的選取：水平途徑、垂直途徑、 對角線途徑、順反時鐘途徑…等。 s f(結束) f 例如： 密文：SEDLNHPOESON S E N D O O N H S P L E S O S P E O N L N D H E 密文：SEDLNHPOESON DNESHNOOELPS SOSPEONLNDHE

換位法(續) 行換位 EX1: 明文：SHIP EQUIPMENT ON THE FOURTH OF JULY 行數 1 2 3 4 5 S

換位法(續) 行換位： 行數 密文：TOFUS OFOIH NJUPI TURMP HLTEE EYHNQ(橫取) 或 TONTH EOFJU LYFOU RTHUI PMENS HIPEQ (直取) 金匙：3-5-4-2-1(數字) 3 5 4 2 1 T O F U S I H N J P R M L E Y Q

換位法(續) EX2: 明文：SHIP EQUIPMENT ON THE FOURTH OF JULY 行數 1 2 3 4 5 S U T

換位法(續) 原行數： 1 2 3 4 5 金匙： F I G H T (文字) 行換位： 1 4 2 3 5 (以該字母的 換位後的密文： 原行數： 1 2 3 4 5 金匙： F I G H T (文字) 行換位： 1 4 2 3 5 (以該字母的 大小順序排列) 換位後的密文： 密文：SFUTO HOIOF IUPNJ PRMTU ETEHL QHNEY 1 4 2 3 5 S F U T O H I P N J R M E L Q Y

換位法(續) EX3: (多文字換位法) 明文： NEGOTIATIONS STALLED SEND INSTRUCTIONS TODAY 幾何換位： NE NS EN TI GO ST DI ON TI AL NS ST AT LE TR OD IO DS UC AY 行換位： TI EN NS NE ON DI ST GO ST NS AL TI OD TR LE AT AY UC DS IO 密文： TIENNS NEONDI STGOST NSALTI ODTRLE ATAYUC DSIO

代換法 簡單代換 EX1: A={A,B,…,Z}=C f : A→C, f為簡單代換函數 A=ABCDEFGHIJKLMNOPQRSTUVWXYZ f(A)=HARPSICODBEFGJKLMNQTUVWXYZ 明文： HELP ME 密文： OSFL GS

代換法(續) EX2：(凱撒加密法) EX3: (Decimations法) f(a)=(a+k) mod n, a=該字在字集中原先位置；k=移動的位置；n=此字集的大小。 取 k=3 明文：SECURE ALL MESSAGES 密文：VHFXUH DOO PHVVDJHV EX3: (Decimations法) f(a)=(a．k) mod n, k=9, A=標準英文26個字母 =ABC DEF GHI JKL MNO PQR STU VWXYZ C=AJS BKT CLU DMV ENW FOX GPY HQZIR f: A→C

代換法(續) 明文： M=RENAISSANCE 密文：EK(M)=XKNAUGGANSK EX4: (Affine 轉換) f(a)=(aK1+K0) mod n, K1與n互質 密文： 依照下列取代法則取代而成

代換法(續) (2)同音代換 EX1: 字母 同 音 數 字 A 17, 19, 34, 41, 56, 60, 67, 83 I 同 音 數 字 A 17, 19, 34, 41, 56, 60, 67, 83 I 08, 22, 53, 65, 88, 90 L 03, 44, 76 N 02, 09, 15, 27, 32, 40, 59 O 01, 11, 23, 28, 42, 54, 70, 80 P 33, 91 T 05, 10, 20, 29, 45, 58, 64, 78, 99 分配方式：頻率出現愈大的分配的同音字愈 多， 而造成平均分佈。 明文=PLAINPILOT 密文= 91 44 56 65 59 33 08 76 28 78

同音替代(續) EX2: E I L M S E 10 22 18 02 11 I 12 01 25 05 20 19 06 23 13 07 L M 03 16 08 24 15 S 17 09 21 14 04 明文= SMILE 金匙= LIMES 密文= 21 16 05 19 11

多字母取代 觀念─加密碟子

多字母取代(續) EX1: Vigenere加密法 明文 M = RENA ISSA NCE 金匙 K = BAND BAND BAND 密文 Kk(M) = SEAD JSFD OCR BAND表示第一個字母平移1位， 第2個字母不平移， 第3個字母平移13位， 第4個字母平移3位。

多圖代換法 EX1: Playfair加密法 H A R P S I C O D B E F G K L I與J同,或捨去Z M N Q T U V W X Y Z 對於連續兩個明文字符以下列規則選取所對應的密文： 1,若此明文以對角出現，則取另兩個對角。 2.若此2明文在同一行(Row)，則分別向右取2個密文。

多圖代換法(續) 3.若此2明文在同一列(Column)，則分別向下取2個密文。 4.若此2明文為同樣字符，則在其中間插入任一字符(如X)。 5.如明文有奇數個，則在明文的最後加一個字符 (如X)，使成為偶數個。 明文 = RE NA IS SA NC EX，明文的最後加上一個X配成偶數個。 密文 = HG WC BH HR WF GV 分別使用規則 1, 3, 1, 2, 3, 1

美國數據保密標準 DES保密轉換程式由16次運算組成 DES的核心為保密函數 , 由四部份組成 擴充轉換 E: 32 bits  48 bits 二進位加法 ⊕ 代換轉換 S: 48 bits  32 bits 6 bits  4 bits 1 1 0 1 0 0 10 =“2” row 1010= “10” column (4) 排列轉換 P

DES功能的評估 (1) 保密性高: 金鑰 56 bits 256  1017 若查對速率106key/sec  3*1013key/yr 地毯式搜尋約3000年!! (2) 製作容易:歐美國家已製有 IC 應市，操作速度 達10M bps (3) 擴充性小 (4) 由於傳輸干擾易造成錯誤傳播

美國數據保密標準(DES)方塊圖

擴充轉換 E 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 代換表 S1 0 1 2 3 4 5 6 7 8 9 10 11 0 14 4 13 1 2 15 11 8 3 10 6 12 1 0 15 7 4 14 2 13 1 10 6 12 11 2 4 1 14 8 13 6 2 11 15 12 9 7 3 15 12 8 2 4 9 1 7 5 11 3 14 12 13 14 15 5 9 0 7 9 5 3 8 3 10 5 0 10 0 6 13

排列轉換表 P 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 PC-1 C0: 50 43 36 29 22 15 8   1 51 44 37 30 23 16 9 2 52 45 38 31 24 17 10 3 53 46 39 32 D0: 56 49 42 35 28 21 14 7 55 48 34 27 20 13 6 54 47 40 33 26 19 12 5 25 18 11 4

向左位移規則 i = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 位移數 = 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1

公開金鑰保密系統 ‧特性： (1)改進傳統保密系統缺點 ‧[Rivest, Shamir, Adleman 1978] (2)加密金鑰(e,m)，解密金鑰d (3)d控制的運算必須可以從(e,m)加密的密語解 得明語 (4)加密金鑰(e,m)的公開,不會造成洩密 ‧[Rivest, Shamir, Adleman 1978] choose p, q prime numbers 取e 使得(e, (p-1)(q-1))=1 令m=p*q 明語M 使得 0<M<m 其對應的密語 C = E(M) = Me mod m 令d滿足下式之整數 e*d ≡ 1 (mod (p-1)(q-1)) 解密的方法： M = D(C) = Cd mod m

公開金鑰保密系統(續) ‧實例 m = p*q = 5*11 =55 取e = 3 令明語M = 7 p = 5, q = 11 (p-1)(q-1) = 40 m = p*q = 5*11 =55 取e = 3 令明語M = 7 →密語 C = Me mod m = 73 mod 55 = 13 又 e*d ≡ 1 (mod 40) 3*d ≡ 1 (mod 40) → d = 27 所以解密M = Cd mod m = 1327 mod 55 = 7

公開金鑰保密系統(續) ‧評估 (1)若有人欲分解m = pq 設 m = 200位數 電腦106指令/sec 約需106 yr！！ (2) 保密性高：不需傳送金鑰 (3) 複雜性大：運算速度慢 (4) 易造成嚴重傳播錯誤：分段加密

數值簽章 C UA UB ‧公開加密系統的運用 ‧類似手稿或親筆函

Public-Key Cryptosystems之特性 1. D(d, E(e, M)) = M，可還原性 2. d和e很容易求得 3. 若公開e，別人很難從e求得d，即只有自己知道如何解密(以e加密) 4. E(e, D(d, M)) = M Public-key Cryptosystems一定要能忍受 Chosen-Plaintext Attack

Public-Key Cryptosystems之特性(續) ‧滿足1~3項稱之為trap-door one-way function ‧“one-way”因易加密而不易解密 ‧“trap-door”若知一些特別資訊即可解密 ‧滿足1~4項稱之為trap-door one-way permutation ‧1~3項為public-key cryptosystems之要求 ‧若同時滿足第4項要求，則該保密法可用來製作數位簽章。