【正文】 APPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ， 試破譯該密文 ? 首先統(tǒng)計密文中字母出現(xiàn)的頻率，然后與英文字母出現(xiàn)頻率比較。就這樣邊試邊改，最后得到明文如下： ? it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the viet cong in moscow ? 在嘗試過程中，如果同時使用雙字母和三字母的統(tǒng)計規(guī)律，那么更容易破譯密文。 2023/2/25 Ch3(1)對稱加密技術(shù) 35 乘法密碼 ? 對每個 c, m ∈ Zn，乘法密碼的加密和解密算法是： C= Ek(m)= (mk) mod n M= Dk(c)= (ck1) mod n 其中 k和 n互素，即 gcd(k, n)=1，否則不存在模逆元，不能正確解密 ? 乘法密碼的密碼空間大小是 φ(n)， φ(n)是歐拉函數(shù)。 ? 乘法密碼也稱 采樣密碼 ，因為密文字母表是將明文字母按照下標每隔 k位取出一個字母排列而成。當(dāng)k1=0時， 仿射密碼變?yōu)榧臃艽a，當(dāng) k2=0時， 仿射密碼變?yōu)槌朔艽a。 2023/2/25 Ch3(1)對稱加密技術(shù) 38 仿射密碼舉例 ? 例 K= (7, 3), 用仿射密碼加密明文hot。分別加密如下： (7 7 + 3) mod 26 = 52 mod 26 =0 (7 14 + 3) mod 26 = 101 mod 26 =23 (7 19 + 3) mod 26 =136 mod 26 =6 ? 三個密文數(shù)值為 0、 23和 6，對應(yīng)的密文是AXG。 2023/2/25 Ch3(1)對稱加密技術(shù) 42 維吉尼亞密碼 ? 維吉尼亞 (Vigen232。那么密鑰為： 明文： senderandrecipientshareamonkey 密鑰： puterputerputerputerc 2023/2/25 Ch3(1)對稱加密技術(shù) 43 ? 維吉尼亞密碼加密過程簡述如下： 寫下明文，表示為數(shù)字形式； 在明文之上重復(fù)寫下密鑰字，也表示為數(shù)字形式； 加密相對應(yīng)的明文：給定一個密鑰字母 k和一個明文字母 m，那么密文字母則是(m+k)mod 26計算結(jié)果所對應(yīng)的字母 2023/2/25 Ch3(1)對稱加密技術(shù) 44 維吉尼亞密碼舉例 ? 例 設(shè)密鑰字是 cipher，明文串是 this cryptosystem is not secure, 求密文。 明文 M： thiscryptosystemisnotsecure 密鑰 K： cipherciphercipherciphercip ? 將明文和密鑰轉(zhuǎn)化為數(shù)字 明文M=(19,7,8,18,2,17,24,15,19,14,18,24,18,19,4,12,8,18,13,14,19,18,4,2,20,17,4) 密鑰K=(2,8,15,7,4,17,2,8,15,7,4,17,2,8,15,7,4,17,2,8,15,7,4,17,2,8,15) 2023/2/25 Ch3(1)對稱加密技術(shù) 45 ? 對每個明文數(shù)字和對應(yīng)的密鑰數(shù)字，使用ci=(mi+ki )mod 26加密 ? 得到密文數(shù)字為 C=(21,15,23,25,6,8,0,23,8,21,22,15,21,1,19,19,12,9,15,22,8,25,8,19,22,25,19) ? 于是密文為： VPXZGIAXIVWPUBTTMJPWIZITWZT 2023/2/25 Ch3(1)對稱加密技術(shù) 46 維吉尼亞密碼的安全性 ? 維吉尼亞密碼是將 每個明文字母映射為幾個密文字母 ? 如果密鑰字的長度是 m，明文中的一個字母能夠映射成這 m個可能的字母中的一個 ? 密文中字母出現(xiàn)的頻率被隱蔽了，它的安全性明顯比單表代換密碼提高了 ? 維吉尼亞密碼的密鑰空間比較大，對于長度是 m的密鑰字，密鑰空間為 26m ? 當(dāng) m=5，密鑰空間所含密鑰的數(shù)量大于 2023/2/25 Ch3(1)對稱加密技術(shù) 47 一次一密 ? 一次一密 是非周期多表代換密碼 ? 使用與明文一樣長且無重復(fù)的隨機密鑰來加密明文，并且該密鑰使用一次后就不再使用 ? 一次一密的安全性是取決于密鑰的隨機性 ? 但產(chǎn)生大規(guī)模隨機密鑰是一件很困難的事情，目前還沒有很好的辦法來解決這個問題 ? 密鑰分配也是一個難點，由于密鑰不允許重復(fù)使用，因此存在大量的密鑰分配問題。這樣可以構(gòu)成如下的密鑰矩陣。 (1) 如果這兩個字母一樣，則在中間插入一個字母 x(事先約定的一個字母 ), 如“ balloon‖ 變成 “ ba lx lo on‖。如“ table‖變?yōu)椤?ta bl ex‖。 (4) 如果兩個字母在同一列，用它下面的字母來代替它 (最底下的字母的下一個是該列第 1個字母 ), 如“ mu‖ 加密變?yōu)椤?CM‖。 2023/2/25 Ch3(1)對稱加密技術(shù) 56 Hillm 密碼加密過程 ? 將明文字母以 m個字母為單位進行分組，若最后一組沒有 m個字母，則補足沒有任何實際意義的啞字母（雙方事先可以約定這些字母），并用數(shù)字表示這些字母； ? 選擇一個 m階可逆方陣 K，稱為 Hillm密碼的加密矩陣； ? 對每 m個字母為一組的明文字母，用它對應(yīng)的值構(gòu)成一個 m維向量； ? 計算密文的值 C=km mod26，然后反查字母表的值，得到對應(yīng)的 m個密文字母； ? 同樣明文的其他組的密文。 2023/2/25 Ch3(1)對稱加密技術(shù) 60 數(shù)據(jù)加密標準 ? 美國國家標準局 (NBS)，即現(xiàn)在的國家標準和技術(shù)研究所 (NIST)于 1973年 5月向社會公開征集標準加密算法 ? 并公布了它的設(shè)計要求： 算法必須提供高度的安全性 算法必須有詳細的說明，并易于理解 算法的安全性取決于密鑰，不依賴于算法 算法適用于所有用戶 算法適用于不同應(yīng)用場合 算法必須高效、經(jīng)濟 算法必須能被證實有效 2023/2/25 Ch3(1)對稱加密技術(shù) 61 ? 1974年 8月 27日 , NBS開始第二次征集， IBM提交了算法 LUCIFER，該算法由 Feistel領(lǐng)導(dǎo)的團隊研究開發(fā)，采用 64位分組以及 128位密鑰 ? IBM用改版的 Lucifer算法參加競爭，最后獲勝，成為數(shù)據(jù)加密標準 (Data Encryption Standard, DES) ? 1976年 11月 23日，采納為聯(lián)邦標準，批準用于非軍事場合的各種政府機構(gòu)?，F(xiàn)代大多數(shù)對稱分組密碼也是基于 Feistel密碼結(jié)構(gòu) 2023/2/25 Ch3(1)對稱加密技術(shù) 62 DES加密過程 ? DES同時使用了 代換 和 置換 兩種技巧 ? 它用 56位密鑰加密 64位明文，最后輸出 64位密文 ? 整個過程分為兩大部分組成：一是 加密過程 ，另一是 子密鑰產(chǎn)生過程 ? 圖 DES加密算法簡圖 2023/2/25 Ch3(1)對稱加密技術(shù) 63 2023/2/25 Ch3(1)對稱加密技術(shù) 64 ? 圖 的處理過程可以分三個部分 ： (1) 64位明文經(jīng)過初始置換被重新排列，然后分左右兩半，每半各 32位； (2) 左右兩半經(jīng)過 16輪置換和代換迭代，即 16次實施相同的變換。 ? 圖 則由 56位密鑰，產(chǎn)生 16個 48位子密鑰，分別供左半邊的 16輪迭代加密使用 2023/2/25 Ch3(1)對稱加密技術(shù) 65 初始置換 ? 初始置換 (Initial Permutation, IP) 是數(shù)據(jù)加密的第1步 ? 將 64位的明文按照圖 。劃分方法原則是 偶數(shù)位移到左半部，奇數(shù)位移到右半部，即： 2023/2/25 Ch3(1)對稱加密技術(shù) 67 DES每輪結(jié)構(gòu) ? 上一輪的右邊 Ri1直接變換為下一輪的左邊Li ? 上一輪的左邊 Li1與加密函數(shù) F異或后作為下一輪的右邊 Ri ? 加密函數(shù) F則是上一輪右邊 Ri1和子密鑰 Ki的函數(shù)。 2023/2/25 Ch3(1)對稱加密技術(shù) 70 加密函數(shù) F的計算過程 Ki (48 bits) Ri1 (32 bits) 48 bits E + S1 S2 S3 S4 S5 S8 S6 S7 F (32 bits) P 2023/2/25 Ch3(1)對稱加密技術(shù) 71 圖 擴展置換 E 圖 置換函數(shù) P 2023/2/25 Ch3(1)對稱加密技術(shù) 72 S盒 ? 在加密函數(shù)計算過程中使用了 8個 S盒 ? S盒 是 DES保密性的關(guān)鍵所在 ? S盒是一種非線性變換，也是 DES中唯一的非線性運算 ? S盒有 6 位輸入， 4 位輸出 ? 48位數(shù)據(jù)經(jīng)過 8個 S盒后輸出 32位數(shù)據(jù) ? 每個 S盒 都由 4行 (表示為 0,1,2,3)和 16列(0,1,…,15) 組成，如圖 2023/2/25 Ch3(1)對稱加密技術(shù) 73 2023/2/25 Ch3(1)對稱加密技術(shù) 74 ? 每行都是全部的 16個長為 4比特串的一個全排列 ? 每個比特串用它對應(yīng)的二進制整數(shù)表示 ,如 1001用9表示。用中間的 4位選擇 S盒 16列中的某一列，行列交叉處的十進制數(shù)轉(zhuǎn)換為二進制數(shù)可得到 4位輸出。 2023/2/25 Ch3(1)對稱加密技術(shù) 80 圖 圖 2 2023/2/25 Ch3(1)對稱加密技術(shù) 81 DES解密 ? DES解密過程與加密過程本質(zhì)上一致 ? 加密和解密使用同一個算法，使用相同的步驟和相同的密鑰 ? 主要不同點是將密文作為算法的輸入，但是逆序使用子密鑰 ki，即第 1輪使用子密鑰k16，第 2輪使用子密鑰 k15，最后一輪使用子密鑰 k1 2023/2/25 Ch3(1)對稱加密技術(shù) 82 DES的強度 ? 從發(fā)布時起， DES就備受爭議 ? 爭論的焦點主要集中在密鑰的長度、迭代次數(shù)以及 S盒的設(shè)計等方面 ? DES的安全性是依賴 S盒 ,但是 S盒設(shè)計詳細標準至今沒有公開 ? 有人懷疑 S盒里隱藏了陷門（ trapdoors）。事實上，后來表明 S盒是被設(shè)計成能夠防止差分密碼分析 ? DES是將 Lucifer算法作為標準， Lucifer算法的密鑰長度 128位，但 DES將密鑰長度改為 56位 , 這不能抵抗窮盡密鑰搜索攻擊 2023/2/25 Ch3(1)對稱加密技術(shù) 83 ? 1997年，克羅拉多州的程序員 Verser在 Inrer上數(shù)萬名志愿者的協(xié)作下用 96天的時間找到了密鑰長度為 40位和 48位的 DES密鑰 ? 1998年電子邊境基金會（ EFF）使用一臺價值 25萬美元的計算機在 56小時之內(nèi)破譯了 56位的 DES ? 1999年，電子邊境基金會（ EFF）通過互聯(lián)網(wǎng)上的 10萬臺計算機合作，僅用 22小時 15分破譯了 56位的 DES ? 另外， DES存在 弱密鑰 。如果每一半的所有位都是“ 0‖或者“ 1‖，那么在算法的任意一輪所有的子密鑰都是相同的 2023/2/25 Ch3(1)對稱加密技術(shù) 84 三重 DES ? DES由于安全問題，美國政府于 1998年 12月宣布DES不再作為聯(lián)邦加密標準 ? 新的美國聯(lián)邦加密標準是高級加密標準 (ASE) ? 在新的加密標準實施之前，為了使已有的 DES算法投資不浪費， NIST在 1999年發(fā)布了一個新版本的 DES標準（ FIPS PUB463），該標準指出DES僅能用于遺留的系統(tǒng)，同時將三重 DES（簡寫為 3DES）取代 DES成為新的標準 ? 3DES存在幾個優(yōu)點。其次， 3DES的底層加密算法與 DES的加密算法相同，該加密算法比任何其它加密算法受到分析的時間要長得多，也沒有發(fā)現(xiàn)有比窮舉攻擊更有效的密碼分析攻擊方法 2023/2/25 Ch3(1)對稱加密技術(shù) 85 ? 但是雙重 DES不安全 ? 雙重 DES存在中間相遇攻擊，使它的強度跟一個56位 DES強度差不多 ? 如果 C=EK2[EK1[M]]，令 X=EK1[M]=DK2[C]。這種加密方案窮舉攻擊代價是 2112 E E K1 K1 C M B 加密 解密 D K2 A D D K1 K1 M C A E K2 B 2023/