【正文】 10321032101S S盒按下述規(guī)則運算： 將第 1和第 4的輸入比特做為 2 bit數(shù) ， 指示為 S盒的一個行；將第 2和第 3的輸入比特做為 S盒的一 個列 。如此確定為 S盒矩陣的 （ i,j） 數(shù) 。 例如： （ P0,0, P0,3） =(00),并且 (P0,1,P0,2)=(1 0) 確定了 S0中的第 0行 2列 （ 0， 2） 的系數(shù)為 3， 記為（ 1 1） 輸出 。 由 S0, S1輸出 4bit經(jīng)置換 P4 2 4 3 1 它的輸出就是 F函數(shù)的輸出 。 Feistel 結(jié)構(gòu)圖 Feistel結(jié)構(gòu)定義 ?加密 : Li = Ri1。 Ri = Li1?F(Ri1,Ki) ?解密 : Ri1 = Li Li1 = Ri?F(Ri1,Ki) = Ri?F(Li,Ki) Feistel結(jié)構(gòu)分析 ? Block size(64 ? 128) ? Key size(56 ? 128~256) ? Number of rounds(16) ? Subkey generation ? Round function(F) ? Fast software encryption/decryption ? Easy hardware implementation ? Simple structure ? Ease of analysis DES示意圖 DES的描述 ? DES利用 56比特串長度的密鑰 K來加密長度為 64位的明文，得到長度為 64位的密文 輸入 64比特明文數(shù)據(jù) 初始置換 IP 在密鑰控制下 16輪迭代 初始逆置換 IP1 輸出 64比特密文數(shù)據(jù) DES算法框圖 交換左右 32比特 DES加解密過程 令 i表示迭代次數(shù) ， ?表示逐位模 2求和 ， f為加密函數(shù) 。 DES的加密和解密過程表示如下 。 加密過程： 解密過程： )(6416,2,1),(16,2,1)64(1616111100LRIPb i tikRfLRiRLb i tIPRLiiiiii???????????????密文輸入碼??)(641,15,16),(1,15,16)64(0011111616LRIPb i tikRfRLiLRb i tIPLRiiiiii???????????????明文密文??初始置換 IP和初始逆置換 IP—1 Li1（ 32比特） Ri1（ 32比特） Li（ 32比特） 48比特寄存器 選擇擴展運算 E 48比特寄存器 子密鑰 Ki （ 48比特） 32比特寄存器 選擇壓縮運算 S 置換運算 P Ri（ 32比特） Li=Ri1 DES的一輪迭代 DES: Function F Expansion: 32 ? 48 Sbox: 6 ? 4 Permutation: 選擇擴展運算 32 | 01 02 03 04 | 05 04 | 05 06 07 08 | 09 08 | 09 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 | 01 選擇壓縮運算 SBoxi SBoxii SBox ? 對每個盒， 6比特輸入中的第 1和第 6比特組成的二進制數(shù)確定的行，中間 4位二進制數(shù)用來確定的列。中相應行、列位置的十進制數(shù)的 4位二進制數(shù)表示作為輸出。例如的輸入為101001，則行數(shù)和列數(shù)的二進制表示分別是 11和 0100，即第 3行和第 4列，的第 3行和第 4列的十進制數(shù)為 3，用 4位二進制數(shù)表示為 0011，所以的輸出為 0011。 Permutation ? 16 07 20 21 29 12 28 17 01 15 23 26 05 18 31 10 02 08 24 14 32 27 03 09 19 13 30 06 22 11 04 25 子密鑰的產(chǎn)生 k1 （ 56 位） ( 4 8 位 ) ki （ 56 位） （ 48 位） 64 位密鑰置換選擇 1 C0（ 28 位） D0（ 28 位） 循環(huán)左移 循環(huán)左移 C1（ 28 位） D1（ 28 位） 循環(huán)左移 循環(huán)左移 Ci（ 28 位） Di（ 28 位）置換選擇 2置換選擇 2密鑰表的計算邏輯循環(huán)左移：1 1 9 12 1 10 23 2 1 1 24 2 12 25 2 13 26 2 14 27 2 15 28 2 16 1置換選擇 1（ PC1） 和置換選擇 2（ PC2） 對 DES的討論 ?F函數(shù) (SBox)設計原理未知 ?密鑰長度的爭論 ?DES的 破譯 ?弱密鑰與半弱密鑰 SBox問題 ? 1976年美國 NSA提出了下列幾條 S盒的設計準則： 1. S盒的每一行是整數(shù) 0， … ， 15的一個置換 2. 沒有一個 S盒是它輸入變量的線性函數(shù) S盒的一個輸入位至少要引起兩位的輸出改變 S盒和任何一個輸入 X， S（ X）和 S(X?001100）至少有兩個比特不同（這里 X是長度為 6的比特串） S盒，對任何一個輸入對 e,f屬于 {0,1}, S(X) S(X?11ef00) ? 6. 對任何一個 S盒，如果固定一個輸入比特，來看一個固定輸出比特的值，這個輸出比特為 0的輸入數(shù)目將接近于這個輸出比特為 1的輸入數(shù)目 。 ?密鑰長度 ? 關(guān)于 DES算法的另一個最有爭議的問題就是擔心實際 56比特的密鑰長度不足以抵御窮舉式攻擊，因為密鑰量只有 個 ? 早在 1977年， Diffie和 Hellman已建議制造一個每秒能測試 100萬個密鑰的 VLSI芯片。每秒測試 100萬個密鑰的機器大約需要一天就可以搜索整個密鑰空間。他們估計制造這樣的機器大約需要 2022萬 美元。 1756 102 ? ? 在 CRYPTO’93上， Session和 Wiener給出了一個非常詳細的密鑰搜索機器的設計方案，這個機器基于并行運算的密鑰搜索芯片，所以 16次加密能同時完成。此芯片每秒能測試 5000萬個密鑰，用 5760個芯片組成的系統(tǒng)需要花費 10萬 美元，它平均用 DES密鑰。 ? 1997年 1月 28日，美國的 RSA數(shù)據(jù)安全公司在 RSA安全年會上公布了一項 “ 秘密密鑰挑戰(zhàn) ” 競賽，其中包括懸賞 1萬美元破譯密鑰長度為 56比特的 DES。美國克羅拉多洲的程序員 Verser從 1997年 2月 18日起，用了 96天時間，在 Inter上數(shù)萬名志愿者的協(xié)同工作下，成功地找到了 DES的密鑰，贏得了懸賞的 1萬美元。 ? 1998年 7月電子前沿基金會 （ EFF） 使用一臺25萬美圓的電腦在 56小時內(nèi)破譯了 56比特密鑰的 DES。 ? 1999年 1月 RSA數(shù)據(jù)安全會議期間 ， 電子前沿基金會用 22小時 15分鐘就宣告破解了一個 DES的密鑰 。 DES的破譯 ? 1990年，以色列密碼學家 Eli Biham和 Adi Shamir提出了差分密碼分析法，可對 DES進行選擇明文攻擊。 ? 線性密碼分析比差分密碼分析更有效 弱密鑰與半弱密鑰 ? 弱密鑰 : EK?EK = I， DES存在 4個弱密鑰 ? 半弱密鑰 : EK1 = EK2， 至少有 12個半弱密鑰 Reference ? William Stallings, Cryptography and work security: principles and practice, Second Edition. ? Bruce Shneier, Applied cryptography: protocols, algorithms, and sourcecode in C, Second Edition. ? Thomas H. Barr,Invitation to Cryptology,Prentice Hall,2022 ? 李克洪主編 ,實用密碼學與計算機安全 ,東北大學出版社 , 1997,10 ? 王育民 劉建偉編著 , 通信網(wǎng)的安全 理論與技術(shù) ,2022,5 ? 思考和練習 1. 什么特性使得加密絕對不可攻破？什么特性將使得加密在實際應用中是不可攻破的？ 2. 解釋為什么雙字母替換密碼比單字母替換更安全？ 3. 解釋為什么兩個相對簡單的密碼（如代替和換位）的積可將安全提高到較高層次。 ? 習題