【正文】 8 69 The mapping F Input: 4bit number (n1n2n3n4). 先做一個(gè) expansion/permutation(E/P) 的運(yùn)算 然後和 subkey SK 做 exclusiveor ? 運(yùn)算 例 : Input: 1 1 0 1 1 1 1 0 1 0 1 1 1 2 3 4 0 1 0 1 0 0 1 1 SK E/P 1 0 1 1 1 0 0 0 4 1 2 3 2 3 4 1 1 1 1 0 1 0 1 1 EP(1101) ? SK = (10111000) ? 70 71 Sbox 左邊 4 bits 餵進(jìn) Sbox S0 來產(chǎn)生 2bit output. 右邊 4 bits 餵進(jìn) Sbox S1來產(chǎn)生另外 2bit output. Sbox 的 4bit input中 , 第 4 bits 用來決定要參考矩陣中的哪一列 , 第 3 bits 則用來決定要參考矩陣中的哪一行 , 由此得出矩陣中的某一項(xiàng) , 然後將其化為二進(jìn)位表示式 . 72 ??????????????????????????301201033102321032103210S1 231331200123230132103210S0? Example: S0(0100)=3 or (11)2 S1(0100)=2 or (10)2 73 P4 function: a 4bit permutation P4(b1b2b3b4)=b2b4b3b1 例 : P4(Sbox(01000100)) =P4(1110) =1011 74 75 The switch function SW 左邊 4 bits 和右邊 4 bits 互換 . 76 2nd Round 接著用相同的步驟再做一次 , 只是所使用的 subkey 不一樣 . 最後再經(jīng)過 IP1 的運(yùn)算 77 78 例子 密鑰 : 1010000010 Subkey generation K1 = P8(LS1(P10(1010000010))) = (10100100) K2 = P8(LS2(LS1(P10(1010000010)))) = (01000011) 明文 : 11110011 IP(11110011) = (10111101) E/P(1101)?K1= (11101011)?(10100100) = (01001111) S0(0100) = (11), S1(1111) = (11), P4(1111) = (1111) F(1101, K1) = P4(Sbox(E/P(1101)?K1)) = (1111) fK(10111101) = (L?(F(R, K1), R) = (1011?1111, 1101) = (01001101) SW(01001101) = (11010100) ???????Round 1 79 E/P(0100)?K2= (00101000)?(01000011) = (01101011) S0(0110) = (10), S1(1011) = (01), P4(1001) = (0101) F(0100, K2) = P4(Sbox(E/P(0100)?K2)) = (0101) fK(11010100) = (L?(F(R, K1), R) = (1101?0101, 0100) = (10000100) IP1(10000100) = (01000001) 密文 : 01000001 ???????Round 2 80 分析 暴力攻擊法 只有 210 = 1024 個(gè)可能的 Key K1, K2,… 給定 (P, C), 檢查 ? E(K1, P)=C ? ? E(K2, P)=C ? ? … ? E(K1024, P)=C ? 81 Block cipher (區(qū)塊密碼 )的原理 Confusion (混亂 ): Substitution Diffusion (擴(kuò)散 ): Switch Feistel Cipher Structure: DES中 ffunction 的結(jié)構(gòu) 能夠保持 DK(EK(P))=P 而不用考慮函數(shù)是否可逆 82 83 Block size Key size Number of rounds Subkey generation algorithm Round function Fast software/hardware encryption/decryption 84 85 Data Encryption Standard (DES) 背景 1977 NBS (National Bureau of Standards, ., now NIST National Institute of Standards and Technology). 規(guī)格 64bit 明文及密文 56bit 密鑰 16 rounds 86 87 Initial final Permutations IP and IP1: 64bit?64bit 58 50 42 34 26 18 10 260 52 44 36 28 20 12 462 54 46 38 30 22 14 664 56 48 40 32 24 16 857 49 41 33 25 17 9 159 51 43 35 27 19 11 361 53 45 37 29 21 13 563 55 47 39 31 23 15 7IP 40 8 48 16 56 24 64 3239 7 47 15 55 23 63 3138 6 46 14 54 22 62 3037 5 45 13 53 21 61 2936 4 44 12 52 20 60 2835 3 43 11 51 19 59 2734 2 42 10 50 18 58 2633 1 41 9 49 17 57 25IP1 88 Expansion permutation (E): 32 bits48bits Permutation function (P): 32 bits32 bits 32 1 2 3 4 54 5 6 7 8 98 9 10 11 12 1312 13 14 15 16 1716 17 18 19 20 2120 21 22 23 24 2524 25 26 27 28 2928 29 30 31 32 116 7 20 21 29 12 28 171 15 23 26 5 18 31 102 8 24 14 32 27 3 919 13 30 6 22 11 4 25E P 89 90 91 令明文 P = L0R0 , 第 i 個(gè) round 之後產(chǎn)生的中間值表示成 LiRi 則密文 C = R16L16 Key generation 由密鑰 K 產(chǎn)生 16 個(gè) 48bit subkeys Ki, 1?i?16. Single round i 的設(shè)計(jì) (Feistel cipher structure) Li=Ri1 Ri=Li1?F(Ri1, Ki) 92 8個(gè)「 6進(jìn) 4出」的 Sboxes Si, 0?i?7 Encryption: Decryption: ? ?PIPfSWfSWfIPC 11516 KKK1 ????????? ? ?CIPfSWfSWfIPP1621 KKK1 ?????????93 Avalanche effect(雪崩效應(yīng) ) 明文或密鑰中一點(diǎn)小小的改變會(huì)造成產(chǎn)生的密文很大的改變 尤其我們希望明文或密鑰中一個(gè) bit 的改變能造成密文中一半的 bits 都改變 94 For example P1=0000 0000 ??? 0000 P2=1000 0000 ??? 0000 K=0000001 1001011 0100100 1100010 0011100 0011000 0011100 0110010 結(jié)果在 L3R3 中有 21 bits 改變而在 L16R16 中則有 34 bits 改變 95 C h a n g e i n P l a i n te x t C h a n g e i n K e yRo u n d b i t s t h a t d i ffe r Ro u n d b i t s t h a t d i ffe r0 1 0 01 6 1 22 21 2 143 35 3 284 39 4 325 34 5 306 32 6 327 31 7 358 29 8 349 42 9 4010 44 10 3811 32 11 3112 30 12 3313 30 13 2814 26 14 2615 29 15 3416 34 16 3596 運(yùn)作的方式 Electronic codebook mode (ECB) Cipher block chaining mode (CBC) Cipher feedback mode (CFB) Output feedback mode (OFB) 97 ECB mode 最簡(jiǎn)單的方式 把明文切成每 64 bits 一個(gè)區(qū)塊 使用相同的密鑰來對(duì)區(qū)塊加密 加密過程就如同在查一本很大的密碼書 (codebook) 98 ECB mode Encryption: If P=P1P2???Pm, where Pi’ s are 64bit blocks, then C=C1C2???Cm=EK(P1)EK(P2)???EK(Pm). 99 ECB mode Decryption: P= DK(C1)DK(C2)???DK(Cm)=P1P2???Pm. 100 CBC mode 把要加密的區(qū)塊先跟前一個(gè)區(qū)塊所產(chǎn)生的密文做 ?, 然後再跟密鑰做加密 區(qū)塊 Pi 的加密和先前所有的區(qū)塊有關(guān) 101 CBC mode Encryption: IV: 固定的 64bit 初始向量 (initial vector), 可以是公開的值或由發(fā)送方隨著密文傳給收受方 C1=EK(IV?P1) Ci=EK(Ci1?Pi), for i?2. 102 CBC mode Decryption: P1=DK(C1)?IV Pi=D(Ci1)?Ci1=Ci1?Pi?Ci1 103 CFB mode 明文切成每 j 個(gè) bits 一個(gè)區(qū)塊 , 一般令 j=8 這種方式可說是 DES的 stream cipher version 104 CFB mode Encryption: P=P1P2???Pm, where Pi’ s are jbit blocks, 1?j?64. 定義 Sj(X) 表示 X 前 j 個(gè) bits R 是一個(gè) 64bit 的暫存器 , 初始值為 IV. R=IV C1=P1?Sj(EK(R)) R=ShiftLeftj||Ci1 Ci=Pi?Sj(EK(R)) i=i+1 Decryption 105 106 107 OFB mode 和 CFB 類似 , 除了當(dāng)作下一個(gè) encryption 的 input 是前一個(gè) DES 的 output 而不是 cipher 優(yōu)點(diǎn) 在密文傳送過程中產(chǎn)生的 error 不會(huì)影響到所有區(qū)塊的解密 108 OFB mode Encryption R=IV C1=P1?Sj(EK(R)) R=ShiftLeftj||Sj(EK(R)) Ci=Pi?Sj(EK(R)) i=i+1 Decryption 109 110 111 Why 56bit keys? At that time, It seems that 56bit keys are secure. Facts: 1997: distributed exhaustive key search all over the world takes 3 months. 1998: speciali