網(wǎng)絡安全原理與應用-第2章-密碼學導論

第2章密碼學導論(1)

密碼學基本概念沈蘇彬南京郵電大學信息網(wǎng)絡技術研究所1主要問題密碼學由哪幾個部分構成？這幾個部分相互之間的關系？密碼系統(tǒng)由哪幾個部分構成？這幾個部分相互之間如何關聯(lián)？密碼系統(tǒng)如何進行數(shù)據(jù)加密？這種加密能夠保證數(shù)據(jù)的保密性嗎？密碼系統(tǒng)可以分成哪幾種類型？這些類型有何特點？2關鍵知識點加密是數(shù)據(jù)通信安全和網(wǎng)絡安全中最為重要的安全手段?，F(xiàn)在實用的是相對安全的加密系統(tǒng)?，F(xiàn)代密碼學包括兩個體系:傳統(tǒng)加密體系,公鑰加密體系。3主要內(nèi)容密碼學的組成數(shù)據(jù)加密基本概念密碼破譯技術加密系統(tǒng)的安全性現(xiàn)代密碼學分類4密碼學的組成密碼學包括兩個部分:數(shù)據(jù)加密和密碼破譯數(shù)據(jù)加密:對信息進行加密和解密的技術加密算法,解密算法,密鑰管理技術密碼破譯:攻破加密信息的技術破解加密信息,破解密鑰明文加密算法密文解密算法明文加密密鑰解密密鑰破譯算法破譯明文破譯密鑰5密碼學的組成(續(xù))加密與破譯是一對矛盾體從密碼學的完整性看,研究密碼學,必須研究密碼破譯,否則無法客觀地評判各類加密算法的嚴密程度明文加密算法密文解密算法明文加密密鑰解密密鑰破譯算法破譯明文破譯密鑰6數(shù)據(jù)加密基本概念明文(Plaintext,P):未加密的信息或數(shù)據(jù)。密文(Ciphertext,C):加密后的信息或數(shù)據(jù)。加密算法(E):將明文轉(zhuǎn)換成為密文的處理過程。明文加密算法密文解密算法明文加密密鑰解密密鑰7密碼學基本概念(續(xù)2)解密算法(D):將密文轉(zhuǎn)換成為明文的處理過程加密密鑰(KE):控制加密處理過程的一種信息或數(shù)據(jù)解密密鑰(KD):控制解密處理過程的一種信息或數(shù)據(jù)明文加密算法密文解密算法明文加密密鑰解密密鑰8密碼學中符號表示加密算法:C=E(KE,P)=KE{P}解密算法:P=D(KD,C)=D(KD,E(KE,P))從以上加密和解密的公式可以看出，經(jīng)過數(shù)學抽象表示的加密和解密過程更加簡潔、明了，便于梳理思路，掌握本質(zhì)內(nèi)容。PEC=E(KE,P)DP=D(KD,C)KEKD9密碼破譯技術安全都是指在某種環(huán)境和條件下相對某種風險模型的安全。同樣，必須根據(jù)目前常用的密碼破譯技術設計和評測加密算法。Diffie和Hellman在1976年羅列了3種密碼分析(也稱為密碼攻擊)方式已知密文:攻擊者僅僅掌握密文,試圖破譯對應的明文、加密算法和密鑰已知明文:攻擊者掌握了大量的明文和對應的采用相同加密算法和密鑰加密的密文，試圖破譯加密這些密文的算法和密鑰10密碼破譯技術(續(xù))選擇明文:攻擊者可以向被攻擊的加密系統(tǒng)提交無數(shù)個選擇的明文并且可以檢查對應生成的密文，試圖破譯該加密系統(tǒng)采用的加密算法和密鑰。已知明文攻擊屬于“被動系統(tǒng)識別”類攻擊，而選擇明文攻擊屬于“主動系統(tǒng)識別”類攻擊。作為一個安全的加密系統(tǒng)應該是一類難以識別的系統(tǒng)，至少必須防范“被動系統(tǒng)識別”(已知明文)類攻擊，最好能夠防范“主動系統(tǒng)識別”(選擇明文)類攻擊。11非技術性密碼分析實際常用的最為成功密碼分析是非技術性密碼分析:SocialEngineering(社交計謀)例如:竊取密鑰,打探密鑰,選擇明文(提供假情報)啟示:信息安全不僅僅是一項技術工作,更是一項管理工作.雖然密碼分析也是一門學問,但是,本課程主要介紹密碼學原理和算法12加密系統(tǒng)的安全性W.Diffie和M.Hellman將加密系統(tǒng)的安全性分成兩種類型：相對安全(或計算安全)的加密系統(tǒng)該類系統(tǒng)由于破譯者的計算成本限制或者計算能力限制而看作是安全的。如果破譯者不考慮計算成本，或者由于計算技術發(fā)展使得計算能力有大幅度提高，則這類系統(tǒng)就不再安全了。絕對安全(或無條件安全)的加密系統(tǒng)無論攻擊者花費多少時間、使用多么高級的計算技術都無法破譯的加密系統(tǒng)。13加密系統(tǒng)的安全性(續(xù)1)無條件安全加密系統(tǒng)源于某種密文存在多種有意義的明文，例如，對于簡單替換而成的密文XMD可以對應于有意義的明文：now,and,the等等。在計算安全的加密系統(tǒng)中，密文就一定存在確定的信息唯一決定的明文和密鑰，其安全性只是依賴于計算的成本。14加密系統(tǒng)的安全性(續(xù)2)一種可以證明的無條件安全加密系統(tǒng)是“一次性覆蓋數(shù)”系統(tǒng)。由于計算成本過高而無法實用。該系統(tǒng)設計的密鑰必須與明文同樣長度，通過該密鑰與明文進行“異或”操作，完成對明文的加密。該加密系統(tǒng)必須保證“一次一密鑰”，即對于不同的明文采用不同的加密密鑰。目前實際可行的、并且得到廣泛應用的還是相對安全(計算安全)的加密系統(tǒng)。為了對于計算安全加密系統(tǒng)有一個量化的概念，需要了解一些典型常數(shù)和參數(shù)的數(shù)量級別。15加密系統(tǒng)的安全性(續(xù)3)表2.1典型常數(shù)和參數(shù)數(shù)量級別一覽表典型常數(shù)和參數(shù)數(shù)量級別一年的秒鐘數(shù)3.15×107主頻為3.0GHz的CPU的一年運轉(zhuǎn)的時鐘循環(huán)次數(shù)9.46×101656個比特長度的二進制數(shù)個數(shù)7.21×101664個比特長度的二進制數(shù)個數(shù)1.84×101980個比特長度的二進制數(shù)個數(shù)1.21×1024128個比特長度的二進制數(shù)個數(shù)3.40×1038192個比特長度的二進制數(shù)個數(shù)6.28×1057256個比特長度的二進制數(shù)個數(shù)1.16×107716現(xiàn)代密碼學分類密碼學有多種分類方法，例如可以根據(jù)加密數(shù)據(jù)過程中對明文的處理方式，分成塊加密方法和流加密方法；也可以根據(jù)加密和解密數(shù)據(jù)過程中采用的密鑰數(shù)目，分成對稱密鑰加密方法和不對稱密鑰加密方法。塊加密方法是指對某個固定長度的數(shù)據(jù)塊進行一系列復雜的運算生成對應的相同長度密文塊的方法。通常采用的固定長度是64個比特，現(xiàn)在建議采用128個比特。17現(xiàn)代密碼學分類(續(xù)1)流加密方法是指不間斷地對數(shù)據(jù)流中的某個較小的數(shù)據(jù)單元進行簡單運算生成密文流的方法。這里的較小數(shù)據(jù)單元可能是1個八位位組（即一個8比特長度的字節(jié)）或者2個八位位組。對稱密鑰加密方法是指加密和解密過程都采用相同的密鑰，即在圖2.2中KE=KD。不對稱密鑰加密方法是指加密和解密過程采用不同的密鑰，即在圖2.2中KE

KD。18現(xiàn)代密碼學分類(續(xù)2)現(xiàn)代密碼學本質(zhì)上可以分成兩個部分:傳統(tǒng)密碼學,公鑰密碼學傳統(tǒng)密碼學對稱密鑰,單個密鑰進行加密和解密,密鑰保密才能保證密文保密優(yōu)點：加密和解密運算簡單、高效缺點：初始密鑰協(xié)商和后續(xù)密鑰更新困難19現(xiàn)代密碼學分類(續(xù)2)公鑰密碼學不對稱密鑰,公鑰和私鑰分別用于加密和解密過程。不僅可應用于數(shù)據(jù)加密,還可以應用于數(shù)字簽名。私鑰保密才能保證密文不被攻破優(yōu)點：無需進行初始密鑰的協(xié)商缺點：加密和解密算法的計算量較大,計算成本較高20本講重點內(nèi)容密碼學的構成:密碼學和密碼分析加密加密的基本概念：明文、密文、密鑰典型的密碼攻擊模式安全密碼學應該可以防御的攻擊模式加密系統(tǒng)的安全性分析現(xiàn)代密碼學的分類21思考題(1)什么是明文？什么是密文？從明文轉(zhuǎn)換到密文還需要輸入什么數(shù)據(jù)？需要利用什么過程？(2)通常有幾種破譯密碼的攻擊方式？一個安全的加密系統(tǒng)至少應該防范何種密碼攻擊？最好能夠防范何種密碼攻擊？(3)加密系統(tǒng)的安全性分成哪幾種類型？常用的是哪種安全的加密系統(tǒng)？為什么？22思考題(續(xù))(4)

什么是塊加密算法？什么是流加密算法？實際應用中，是否可以用塊加密算法替代流加密算法？試說明理由。(5)

什么是對稱密鑰加密算法？什么是不對稱密鑰加密算法？實際應用中，是否可以采用不對稱密鑰算法替代對稱密鑰加密算法？試說明理由。(6)

密碼技術主要應該防御哪幾類密碼破譯技術的攻擊？這幾類密碼攻擊技術有何特征？什么類型的密碼系統(tǒng)算是安全密碼系統(tǒng)？23本周課外作業(yè)(1)網(wǎng)絡安全技術主要保護哪兩類對象？試舉例說明。(2)例舉2個網(wǎng)絡安全被破壞的實例，試用網(wǎng)絡安全風險模型分析，是屬于哪種網(wǎng)絡安全威脅？(3)

密碼技術主要應該防御哪幾類密碼破譯技術的攻擊？這幾類密碼攻擊技術有何特征？什么類型的密碼系統(tǒng)算是安全密碼系統(tǒng)？24第2章密碼學導論(2)

傳統(tǒng)密碼學概述沈蘇彬南京郵電大學信息網(wǎng)絡技術研究所25關鍵知識點傳統(tǒng)密碼學的基本原理是“替代”和“換位”傳統(tǒng)密碼學的加密和解密采用同一個密鑰傳統(tǒng)密碼學的安全性很大程度上決定密鑰長度目前常用的傳統(tǒng)密碼學算法是DES算法，56比特的DES算法并不安全。未來擬采用的傳統(tǒng)密碼學算法是AES算法26主要內(nèi)容愷撒加密法傳統(tǒng)密碼學基本原理數(shù)據(jù)加密標準DES算法三重DES算法高級加密標準AES算法RC4算法加密操作模式27傳統(tǒng)密碼學歷史傳統(tǒng)密碼學起源于古代的密碼術。早在古羅馬時代愷撒大帝就采用“替代”方法加密自己發(fā)布的命令，這種“替代”加密方法被稱為“愷撒加密法”。傳統(tǒng)密碼學的基本原理可以歸結為兩條對數(shù)據(jù)處理的方法：替代和換位。美國國家標準局(NBS)于1977年頒布的數(shù)據(jù)加密標準(DES)是目前廣泛應用的傳統(tǒng)加密方法。美國國家標準與技術學會(NIST)在2001年頒布的高級加密標準(AES)將是未來取代DES的一種加密方法。28凱撒密碼愷撒加密法是將明文中的每個字母用該字母對應的后續(xù)第3個字母替代，這里假定字母按照字母表順序循環(huán)排列，即明文中的字母a對應密文中的字母D，明文中的字母x對應密文中字母A。例如明文：attackafterdark密文：DWWDFNDIWHUGDUN29凱撒密碼(續(xù))如果假定每個英文字母對應一個數(shù)值(例如a=1,b=2),并且對于每個明文字母p經(jīng)過凱撒密碼處理后得到密文字母C,則凱撒密碼加密算法可以表示為

C=E(p)=(p+3)mode26凱撒密碼的解密算法可以表示為

p=D(C)=(C-3)mod26明文:abcdefghijklmnopqrstuvwxyz密文:DEFGHIJKLMNOPQRSTUVWXYZABC30通用凱撒密碼算法W.Stallings將凱撒密碼算法中的字母表移位數(shù)從3擴展到任意數(shù)k<26,這樣,就可以得到通用凱撒密碼加密算法:

C=E(p)=(p+k)mode26這樣,通用凱撒密碼解密算法就可以表示為:

p=D(C)=(C-k)mod26這里k就是通用凱撒密碼的密鑰.由于k只有25個可能取值,所以,在已知加密/解密算法下,只要嘗試25種密鑰,就可以破譯通用凱撒密碼.31通用愷撒加密法的啟示從通用愷撒加密法可以得到這樣的啟示，如果某個加密法只依靠密鑰保密，則這種密鑰的選擇應該具有很好的隨機性，并且可以選擇的空間足夠大，使得攻擊者利用現(xiàn)有的計算技術，在可能的時間范圍內(nèi)無法破譯。參照表2.2可知，根據(jù)目前主頻為3.0GHz計算機的處理能力，長度為80的二進制數(shù)密鑰在目前基本上是無法窮舉了。通用愷撒加密法的密鑰相當于長度為5的二進制數(shù)密鑰，當然就很容易被破譯。32為何需要公開加密/解密算法?不公開加密算法，則難以破譯密碼。公開加密算法,僅僅是實際應用的需要。電報的出現(xiàn)才使得加密算法與密鑰的分離。加密算法可以在加密設備中實現(xiàn)，該設備被竊之后，應該不會影響保密電報的傳遞。這就需要將加密算法與密鑰的分離，只有公開加密/解密算法,才能由制造商大規(guī)模生產(chǎn)廉價的加密/解密設備和芯片.才能普及加密算法的應用。33傳統(tǒng)密碼學原理傳統(tǒng)密碼學包括兩條原理:替代和換位替代:將明文中的字母采用其它字母/數(shù)字/符號替代.如果明文采用比特序列表示,則將明文比特模式替代為密文比特模式.凱撒密碼就是采用替代原理設計的加密算法換位:將明文中的元素(字母/比特/字母組/比特組)進行某種形式的重新排列最簡單的一種換位加密算法是圍欄技術,將明文書寫成為上下對角線形式,再按照行順序分別讀出上行和下行的字母序列34傳統(tǒng)密碼學原理(續(xù)1)按照圍欄方法對前面舉例中的明文“attackafterdark”的加密過程如下所示。經(jīng)過加密之后的密文就是一串沒有意義的字符串：“ATCATRAKTAKFEDR”。atcatrak

takfedr35傳統(tǒng)密碼學原理(續(xù)2)圍欄加密算法比較簡單,容易被破譯.更加復雜的換位加密可以將報文逐行寫成一個n×m矩陣,然后按照某個定義的列序列,逐列讀出字母.這種列的先后排序就構成了換位加密的密鑰密鑰:25134明文:attackafterdark密文:TADCEKAKRTFAATR行列36傳統(tǒng)密碼學原理(續(xù)3)矩陣加密方法必須事先確定矩陣的n和m的值。對于矩陣加密方法會提出這樣的問題：如果讀入的待加密字符串裝不下一個n×m的矩陣時，應該如何處理？如果讀入的待加密字符串裝不滿一個n×m的矩陣時，應該如何處理？實際上矩陣加密方法屬于塊加密方法，這兩個問題是塊加密方法必須處理的問題。37傳統(tǒng)密碼學算法大部分常用的傳統(tǒng)加密算法都是塊加密算法,它處理固定長度塊的明文,輸出相同長度的密文塊目前最常用,最重要的傳統(tǒng)加密算法包括:(1)數(shù)據(jù)加密標準DES(2)三重數(shù)據(jù)加密算法3DES或TDEA(3)高級加密標準AES38數(shù)據(jù)加密標準DES數(shù)據(jù)加密標準，英文縮寫DES，是迄今為止應用最為廣泛的標準化加密算法之一。DES是美國國家標準局(NBS，現(xiàn)在更名為美國國家標準與技術學會NIST)于1977年標準化的一種傳統(tǒng)密碼學加密算法。DES是在國際商用機器(IBM)公司于1973年提出的一種加密方法的基礎上，經(jīng)過美國國家安全局(NSA)的驗證和修改后標準化的加密方法。39數(shù)據(jù)加密標準DES(續(xù)1)IBM公司提交的加密算法是一種對稱密鑰的塊加密算法，塊長度為128個比特，密鑰長度為128個比特。該加密算法經(jīng)過NSA安全評估后，將其塊長度更改為64個比特，密鑰長度更改為56個比特，并且修改了原來加密算法中的替代矩陣S-盒。對于NSA對DES算法的更改有以下評論：(1)NSA降低密鑰長度是為了降低DES加密算法的安全性，使得NSA在必要時，有能力破譯DES加密系統(tǒng)。(2)NSA修改原來加密算法中的S-盒，是為自己破譯DES加密系統(tǒng)設置了后門40數(shù)據(jù)加密標準DES(續(xù)2)到了20世紀90年代初期，有兩次不成功的對DES破譯的報告顯示，DES的S-盒具有很強的防范攻擊的能力。這說明更改的S-盒是增強了DES的安全性到了20世紀90年代中期，對于DES成功的破譯報告表明，較短的密鑰長度是DES算法的安全弱點。41DES算法概述DES加密算法總體上是比較容易了解的一種加密算法。雖然其中具體的“替代”和“換位”的處理函數(shù)還是比較復雜，但是，這并不妨礙對DES加密算法的理解。DES算法處理過程沿時間軸縱向可以分成前期處理、16次循環(huán)處理、后期處理部分，橫向可以分成數(shù)據(jù)處理和密鑰處理兩個部分。42DES算法概述(續(xù)1)64比特明文初始排列IP第1輪處理第2輪處理第16輪處理左右32比特換位逆初始排列IP–164比特密文56比特密鑰密鑰排列選擇1左循環(huán)移位密鑰排列選擇2密鑰排列選擇2密鑰排列選擇2左循環(huán)移位左循環(huán)移位K1K2K16圖2.5DES算法結構示意圖43DES算法概述(續(xù)2)DES加密處理分成三個部分:(1)64比特明文塊通過初始排列IP(換位)處理；(2)通過16個輪回的替代和移位處理,左右半換位形成預輸出(3)預輸出的64比特塊進行逆初始排列IP-1處理,產(chǎn)生64比特塊密文DES解密過程與DES加密過程基本一樣,但是需要按照相反順序使用子密鑰,即按照K16,K15,…,K1順序處理每個輪回44DES算法每輪處理過程每輪處理可以表示為:Li=Ri-1,Ri=Li-1

F(Ri-1,Ki)Lj-1(32比特)Rj-1(32比特)8個S-盒排列Rj(32比特)Lj(32比特)Cj-1(28比特)Dj-1(28比特)左移位左移位排列選擇2Cj(28比特)Dj(28比特)待加密64比特數(shù)據(jù)塊56比特密鑰圖2.6DES算法每輪處理過程Kj4848比特擴展排列45DES算法的解密過程(1)DES算法的解密過程采用加密完全相同的過程，只是使用輪回密鑰的順序必須相反。從DES的每輪處理過程可得：Lj=Rj–1 (2.1)Rj=Lj–1

F(Rj–1,Kj) (2.2)假定“||”表示兩個符號串的合并操作，L’0||R’0表示經(jīng)過DES初始排列的待解密數(shù)據(jù)塊，初始排列操作可以表示為IP。L’0||R’0=IP(C) (2.3)46DES算法的解密過程(2)按照DES算法，密文是在第16輪產(chǎn)生的密文塊L16||R16經(jīng)過左右換位和逆初始排列產(chǎn)生的，即C=IP–1(R16||L16) (2.4)將公式(2.4)帶入公式(2.3)可得L’0||R’0=IP(IP–1(R16||L16))=R16||L16 (2.5)由于DES解密過程與DES加密過程相同，只是使用輪回密鑰的次序顛倒，即L’j=R’j–1

(2.6)R’j=L’j–1

F(R’j–1,K16–(j–1))

(2.7)47DES算法的解密過程(3)利用公式(2.6)和(2.7)，公式(2.5)，以及公式(2.1)和(2.2)可以推導出以下公式：L’1=R’0=L16=R15 (2.8)R’1=L’0

F(R’0,K16)=R16

F(R15,K16)=(L15

F(R15,K16))

F(R15,K16)=L15 (2.9)以此類推，可以用歸納法證明存在以下等式：L’j

=R16–j (2.10)R’j=L16–j (2.11)48DES算法的解密過程(4)當DES算法經(jīng)過16次解密處理，可以得到：L’16||R’16=R0||L0

再經(jīng)過DES算法后期左右換位和逆初始排列的處理就可以得到：IP–1(L0||R0)=IP–1(IP(P))=P (2.12)分析：在DES算法的正常求解過程中，通過兩次“異或”運算抵消了復雜的“替代”和“換位”處理函數(shù)F對數(shù)據(jù)塊的處理，無需尋找F的逆函數(shù)。49三重DES算法早在20世紀70年代頒布DES標準的時候，一些密碼學專家就預測到隨著計算技術的發(fā)展，DES將難以滿足安全性的需求，因此，提出了對多重DES算法的研究。多重DES算法基本思路是：通過多次對數(shù)據(jù)塊執(zhí)行DES加密算法，提高密文的安全性。三重DES算法，簡稱為TDES、TDEA或者3DES，在1999年被接納為NIST標準，該算法可以將DES的密鑰擴展為112比特或者168比特長度。

50三重DES算法(續(xù))TDES算法的思路十分簡單：利用密鑰K1對明文P進行一次DES加密，利用密鑰K2對密文C1進行一次DES解密，再利用密鑰K3進行一次DES加密。TDES加密算法的公式表示如下：C=E(K3,D(K2,E(K1,P)))TDES解密過程正好與加密過程相反：

P=D(K1,E(K2,D(K3,C)))

51DES算法分析DES算法最大弱點是密鑰長度太短雖然可以通過3DES算法可以將密鑰擴展到112比特(當K1=K3)或者168比特長度，但是，由于需要執(zhí)行三次DES算法，其加密效率較低，無法滿足NIST關于加密算法高效性的要求。

DES算法的另外一個缺陷是在軟件中運行的效率較低。為此NIST于1997開始在世界范圍征集替代DES的加密算法，稱為高級加密標準(AES)。

52高級加密標準AESNIST征集的AES的基本要求是：AES應該像DES和TDES那樣是一個塊加密方法，并且至少像TDES一樣安全，但是其軟件實現(xiàn)應該比TDES更加有效。NIST在1997年9月發(fā)布征集候選AES的塊加密方法時明確提出要求的指標：（1）不是機密的，可以向公眾公開的加密方法。（2）可以提供128、192和256比特的密鑰長度。（3）具有128比特塊長度(具有更強的安全性)。（4）在世界任何地方都可用，不受任何限制。

53高級加密標準AES(續(xù))對AES候選方案的評審標準有3條：（1）全面的安全性，這是最為重要的指標。（2）性能，特別是軟件實現(xiàn)的處理性能。（3）算法的知識產(chǎn)權等特征。

比利時學者JoanDaemen和VincentRijmen提出的Rijndael加密算法最終被選為AES算法。NIST在2001年12月正式頒布了基于Rijndael算法AES標準。54RC4加密算法與DES和AES加密算法不同，RC4是一種典型的流加密算法，它在1987年由公鑰密碼學中著名的RSA加密算法的發(fā)明人之一R.Rivest提出。由于RC4的簡單性，使得它被廣泛應用于網(wǎng)絡安全中。流加密算法加密過程主要包括兩個步驟：（1）利用密鑰K生成一個偽隨機比特序列（2）用該偽隨機比特序列與明文進行“異或”運算產(chǎn)生密文。

55RC4加密算法(續(xù)1)流加密算法的解密過程也包括兩個步驟：利用同樣的密鑰K生成相同的一個偽隨機比特序列用該偽隨機比特序列與密文進行“異或”運算得到明文。在流加密算法中，由密鑰K生成的偽隨機比特序列稱為“密鑰流”，用KS(K)表示。流加密算法可以用以下兩個公式表示：C=P

KS(K)P=C

KS(K)

為了保證流加密算法的安全性，對于不同的明文，必須采用不同的KS56RC4加密算法(續(xù)2)RC4加密算法分成兩個部分：初始化部分，主要用于產(chǎn)生長度為256個八位位組的偽隨機比特序列；RC4處理部分，利用初始化產(chǎn)生的偽隨機比特序列對明文或者密文進行逐個八位位組的“異或”操作，并且每當對一個八位位組進行一次“異或”操作，就更改偽隨機比特序列。57RC4加密算法(續(xù)3)//Procedure:RC4_Init//Input:key:pointertothekey//keylen:lengthofthekey//Output:s:statearraywith256entriesvoidRC4_Init(byte*key;intkeylen;bytes[256]){unsignedintj,keyIndex=0,stateIndex=0;bytea=0;//Paddings[]with0upto255for(j=0;j<256;j++)s[j]=j;//Computeinitialstatearrayfor(j=0;j<256;j++){stateIndex=stateIndex+key[keyIndex]+a;stateIndex=stateIndex&0xff;//mod256a=s[j];s[j]=s[stateIndex];s[stateIndex]=a;if(++keyIndex>=keylen)keyIndex=0;}}圖2.8RC4初始化部分C語言程序58RC4加密算法(續(xù)4)//Procedure:RC4_Process//Input:in:pointertotheplaintextorciphertextbeingprocessed//len:lengthoftheplaintextorciphertextbeingprocessed//Input/output:s:statearraystoringpseudo-randombitsequence//index1,index2:statearrayindicesmodulo256//Output:out:pointertotheresultingciphertextorplaintextvoidRC4_Process(byte*in;intlen,index1,index2;bytes[256];byte*out){intj;bytea,b;for(j=0;j<len;j++){index1=(index1+1)&0xff;//addwithmodulo256a=s[index1];index2=(index2+a)&0xff;//addwithmodulo256b=s[index2];s[index1]=b;s[index2]=a;//updatestatearrayout[j]=in[j]^s[((a+b)&0xff)];//xoroperation}}圖2.9RC4處理部分C語言程序59RC4加密算法(續(xù)5)經(jīng)過多年的分析和測試，可以證明在密鑰長度足夠大時，并且丟棄到最前面的若干個（例如最前面的256個八位位組）偽隨機比特序列，RC4算法是安全的。需要注意的是，有些使用RC4加密算法的網(wǎng)絡安全標準設定的RC4密鑰長度過短，例如安全套接層(英文縮寫SSL)協(xié)議規(guī)范中規(guī)定了RC4的密鑰長度為40個比特，這就使得RC4成為不安全的加密算法。

60加密操作模式前面介紹的DES和AES加密算法都是塊加密算法，它們只能對64比特或者128比特的數(shù)據(jù)進行加密?，F(xiàn)實網(wǎng)絡中傳遞的數(shù)據(jù)并不一定是64比特或者128比特？問題1：如何在現(xiàn)實網(wǎng)絡環(huán)境下針對不同長度的報文應用塊加密算法？問題2：是否可以在現(xiàn)實網(wǎng)絡安全應用中使用塊加密算法加密/解密數(shù)據(jù)流？

61加密操作模式(續(xù))加密操作模式就是利用塊加密算法對任意長度的數(shù)據(jù)塊或者數(shù)據(jù)流進行加密或者解密處理的方式。

NIST標準化了4種加密操作模式：電子密碼簿(英文縮寫ECB)模式密文塊鏈接(英文縮寫CBC)模式密文反饋(英文縮寫CFB)模式輸出反饋(英文縮寫OFB)模式。

62任意長度報文的處理對于任意長度的報文可以采用分塊和填充的方法，將報文轉(zhuǎn)換成為適合于加密算法的數(shù)據(jù)塊。明文段P1明文段P2…Pn+1明文段Pnbbbab–a初始明文P，長度為l填充后明文P’，長度為(n+1)b圖2.10數(shù)據(jù)報文分段加密示意圖63電子密碼簿(ECB)模式最簡單的處理辦法是電子密碼薄ECB：對于一組長度都為b的數(shù)據(jù)塊，就可以采用相同密鑰K分別執(zhí)行n+1次加密算法E。ECB的問題：對于給定某個密鑰,相同的數(shù)據(jù)塊,產(chǎn)生相同的密文塊DES加密C1

KP1

DES加密C2KP2

…DES加密Cn+1

KPn+1

64密文塊鏈接(CBC)模式CBC模式中,加密算法輸入是前個密文塊與當前明文塊“異或”的結果,每個塊使用相同密鑰CBC模式中加密和解密算法公式

Cj=E(K,Pj

Cj–1),Pj=D(K,Cj)

Cj–1，

C0=IVCBC中與第一個明文塊進行“異或”操作的初始化向量IV無需保密.可以先用明文傳遞DES加密+C1

KP1

IVDES加密+C2KP2

…DES加密+Cn+1

KPn+1

Cn65密文反饋(CFB)模式CFB可以將DES這類塊加密算法轉(zhuǎn)換成為流加密算法.流加密算法不需要填充數(shù)據(jù),無浪費.假定傳輸單元長度j比特(j通常為8),與CBC類似,其上次密文作為本次輸入.64-jjDES加密選擇j位丟棄64-j位+KP16464jjIV64-jjDES加密選擇j位丟棄64-j位+KP26464jj左移j個比特64-jjDES加密選擇j位丟棄64-j位+KPM6464jjC1…C2CM-166密文反饋(CFB)模式(續(xù))與CBC不同,CFB僅僅對初始值與反饋值的合并數(shù)據(jù)加密后.再與明文“異或”得到密文。以上加密/解密過程可以采用公式表示如下：Rj=(Rj–1*2lmod2b)+Cj–1

Cj=S(l,E(K,Rj))

Pj

Pj=S(l,E(K,Rj))

Cj

67傳統(tǒng)密碼學應用傳統(tǒng)密鑰學廣泛應用于計算機安全和網(wǎng)絡安全,例如UNIX系統(tǒng)口令加密網(wǎng)絡數(shù)據(jù)傳輸中,傳統(tǒng)密碼學可以用于鏈路層加密和端到端加密網(wǎng)絡安全系統(tǒng)中,通常采用傳統(tǒng)密碼學加密大容量的數(shù)據(jù).因為目前還是傳統(tǒng)密碼學中的加密/解密算法效率最高.68本章重點內(nèi)容愷撒加密法傳統(tǒng)密鑰學基本原理:替代和移位數(shù)據(jù)加密標準DES高級加密標準AESRC4加密算法加密操作模式69思考題(1)

傳統(tǒng)的愷撒加密算法是否可以公開算法？通用愷撒加密算法是否可以公開算法？從密碼學角度進行分析，愷撒加密算法是否安全？(2)

傳統(tǒng)加密算法的基本原理是什么？DES加密算法如何運用這些基本原理構成一個安全的加密算法？(3)

什么是三重DES算法？從密碼學角度分析，為什么三重DES算法可以改善DES加密算法的安全性？70思考題(續(xù))(4)

AES算法在哪幾個方面對DES算法進行了改進？AES算法與DES算法在哪些方面相同，哪些方面不同？為什么說AES的安全性優(yōu)于DES算法？(5)加密操作模式主要解決數(shù)據(jù)加密中的哪幾類問題？現(xiàn)在常用的有幾類加密操作模式？為什么說ECB模式不安全？(6)

為什么說CBC是一種塊加密操作模式？這種塊加密操作模式不適合于什么樣的網(wǎng)絡安全應用環(huán)境？如何解決這方面的問題？71本周課外作業(yè)(1)分別采用愷撒算法和圍欄算法加密明文“meetyouatsix”。是否可以將以上兩種算法結合，產(chǎn)生一個新的加密算法？如果可以，請用新算法加密以上明文。(2)采用矩陣加密法加密明文“meetyouatsix”，請采用3×4矩陣，密鑰為3142。(3)加密操作模式主要解決數(shù)據(jù)加密中的哪幾類問題？現(xiàn)在常用的有幾類加密操作模式？為什么說ECB模式不安全？72沈蘇彬南京郵電大學信息網(wǎng)絡技術研究所第2章密碼學導論(3)

公鑰密碼學概述73關鍵知識點公鑰密碼學是為了解決電信網(wǎng)環(huán)境下的安全數(shù)據(jù)傳遞而提出的密碼方法。公鑰密碼學可以公開部分密鑰。公鑰加密算法目前采用計算不可逆原理目前廣泛應用的公鑰加密算法是RSA算法Diffie-Hellman密鑰生成算法可以解決在公共電信網(wǎng)環(huán)境下數(shù)據(jù)加密傳遞的問題74主要內(nèi)容公鑰密碼學發(fā)展動因公鑰密碼學基本原理RSA公鑰加密算法Diffie-Hellman密鑰生成算法公鑰密碼體系與密鑰管理75公鑰密碼學歷史Diffie和Hellman于1976年首先提出公鑰密碼學的需求和思路,這是幾千年來密碼學中的真正的一次革命性的進步.這是電信時代產(chǎn)物.美國麻省理工學院的RonRivest,AdiShamir,LenAdleman于1978年首先提出的公共密鑰加密算法RSA,RSA算法的發(fā)明使得公鑰密碼學得到了廣泛的應用2003年5月,發(fā)明公鑰加密算法的RonRivest,AdiShamir和LenAdeman獲得2002度圖靈獎(計算機領域的諾貝爾獎)76公鑰密碼學發(fā)展動因公鑰密碼學發(fā)展動因來源于電信網(wǎng)環(huán)境下安全數(shù)據(jù)傳遞的應用。電信網(wǎng)環(huán)境數(shù)據(jù)傳遞的存在兩類安全威脅：其一是竊取電信網(wǎng)上傳遞的數(shù)據(jù)；其二在電信網(wǎng)傳遞的數(shù)據(jù)中插入非法的數(shù)據(jù)。為了解決這個問題，可以采用密碼學方法對電信網(wǎng)傳遞的數(shù)據(jù)進行加密。

77公鑰密碼學發(fā)展動因(續(xù)1)在通信網(wǎng)環(huán)境下，傳統(tǒng)密碼學無法實現(xiàn)快速的密鑰分發(fā)，所以，傳統(tǒng)的密碼學無法解決電信網(wǎng)環(huán)境的數(shù)據(jù)安全問題。加密方解密方密鑰池明文P明文P=DK(C)破譯方K密文C=EK(P)秘密通道公共通道破譯文P’圖2.15對稱密鑰加密算法原理示意圖K78公鑰密碼學發(fā)展動因(續(xù)2)為了解決在電信網(wǎng)環(huán)境下任意兩個互不相識的用戶之間能夠進行安全傳遞問題，M.Diffie和W.Hellman設計了兩個方案：（1）采用公鑰密碼系統(tǒng)，將傳統(tǒng)密碼學的密鑰分解成加密密鑰PK和解密密鑰VK，從PK無法推導出VK，這樣，就可以公開加密密鑰PK，由接收方保密自己的解密密鑰VK。

（2）采用“公鑰分發(fā)系統(tǒng)”，通過公開交互的信息，可以生成只有通信雙方才知道的密鑰。

79公鑰密碼學發(fā)展動因(續(xù)3)為了解決電信網(wǎng)環(huán)境下數(shù)據(jù)完整傳遞的問題，必須設計一種機制，使得該發(fā)送方傳遞的數(shù)據(jù)，除發(fā)送方之外，任何其他一方都無法修改數(shù)據(jù)。這樣，才能通過電信網(wǎng)傳遞商業(yè)合同。由于傳統(tǒng)密鑰學的加密算法中發(fā)送方和接收方共用同一個密鑰，則接收方接收后可以更改數(shù)據(jù)。這樣，傳統(tǒng)密碼學無法解決電信網(wǎng)環(huán)境下數(shù)據(jù)完整傳遞的問題。

公鑰密碼體系中只有一方掌握私鑰VK，則發(fā)送方采用私鑰加密報文摘要后傳遞，則其他一方無法修改報文而不被發(fā)覺。

80公鑰密碼學原理W.Diffie和M.Hellman于1976年首先給出了公鑰密碼系統(tǒng)的定義：一個公鑰密碼系統(tǒng)由一對加密算法E和解密算法D構成，該公鑰密碼系統(tǒng)采用一個密鑰對集合KS={(PK,VK)}，對于任何一個KS集合中的密鑰對(PK,VK)與任何一個明文P，存在以下特性：

（1）采用密鑰對(PK,VK)中任何一個密鑰對明文P執(zhí)行加密算法E，都可以采用另外一個密鑰對密文進行解密。

81公鑰密碼學原理(續(xù)1)（2）對于掌握了密鑰對(PK,VK)，則加密算法E和解密算法D都是容易計算的。

（3）如果公開密鑰對中的一個密鑰，例如PK，則無法通過計算推導出另外一個密鑰，例如VK。

（4）如果只掌握了密鑰對中的一個密鑰PK，并且利用該密鑰將明文P加密得到密文C，則無法再利用該密鑰將C進行解密得到明文P。

這4個特性較為完整地刻畫了公鑰密碼系統(tǒng)的特征。

82公鑰密碼學原理(續(xù)2)由于公鑰密碼學中的加密算法采用了不同的加密和解密密鑰，所以，也稱為不對稱密鑰加密算法。其原理如下圖所示。加密方解密方公鑰池明文P明文P=DVK(C)破譯方密文C=EPK(P)公共通道破譯文P’圖2.16不對稱密鑰加密算法原理示意圖PK私鑰池VK83RSA公鑰加密算法RSA公鑰加密算法是R.L.Rivest，A.Shamir和L.Adleman在1978年提出一種具體實現(xiàn)公鑰密碼系統(tǒng)的加密算法。該算法隨后以這三位發(fā)明者姓氏的第一個英文字母組合成的縮寫RSA命名，即RSA公鑰加密算法，簡稱為RSA算法。這是迄今為止使用最為廣泛的公鑰加密算法，特別是在數(shù)字簽名方面得到了廣泛的應用。

84RSA公鑰加密算法(續(xù))RSA公鑰加密算法是基于數(shù)論中的歐拉定理和費馬定理設計的一種加密算法，其安全性主要是基于“大數(shù)分解”的不可解特性。

RSA公鑰加密算法可以分成兩個部分：RSA公鑰加密算法的加密和解密過程；RSA公鑰加密算法的“密鑰對”選擇和生成過程。

85RSA算法加密/解密過程為了利用一個公鑰(e,n)對一個報文M進行加密，這里e和n是一對正整數(shù)，可以采用以下過程：（1）將報文M表示成一個0到n–1的整數(shù)。如果M較長，可以將M分解成多個數(shù)據(jù)塊，分別進行多次加密。（2）將M進行e次乘法運算，然后對乘積取n的模，這樣，就得到M的密文C。C=E(M)=Me(modn)86RSA算法加密/解密過程(續(xù))（3）如果需要對密文C進行解密，則只需要對C進行d次乘法運算，然后再對乘積取n的模，這樣，就得到報文M。

M=D(C)=Cd(modn)這里(d,n)就是與公鑰(e,n)對應的私鑰，這是需要該“密鑰對”所有者秘密保存的密鑰。這里的e，d和n是需要用戶在生成“密鑰對”過程中選擇和生成的正整數(shù)。

87RSA算法的密鑰選擇

為了使用RSA加密算法，首先需要按照以下方法選擇并生成RSA公鑰加密算法的“密鑰對”。（1）選擇兩個很大的“隨機”素數(shù)p和q，這兩個素數(shù)的乘積就是RSA密鑰中的正整數(shù)n，即n=p*q

如果p和q足夠大，即使公開n，則根據(jù)目前的計算能力，也無法分解出p和q。88RSA算法的密鑰選擇(續(xù))（2）選擇一個很大的隨機整數(shù)d，使得該整數(shù)與(p–1)*(q–1)的最大公因子為1（3）從p，q和d中計算出e，e是以(p–1)*(q–1)為模的d的倒數(shù)，即e*d=1(mod(p–1)*(q–1))從以上算法過程可以看出，私鑰是根據(jù)一定規(guī)則選擇的，而公鑰是計算得出的。89RSA算法的證明

按照歐拉和費馬的定理可知，對于任何一個整數(shù)M（M相當于轉(zhuǎn)換成為整數(shù)的報文），如果與n互質(zhì)，則

M

(n)=1(modn) (1)這里

(n)表示所有小于n的，與n互質(zhì)的正整數(shù)的個數(shù)。對于任何一個素數(shù)p，

(p)=p–1 (2)

(n)=

(p*q)=

(p)*

(q)=(p–1)*(q–1)(3)90RSA算法的證明(續(xù)1)對于RSA中公鑰(e,n)和私鑰(d,n)中的參數(shù)，存在以下關系：

e*d=1(mod(p–1)*(q–1)),即e*d=1(mod

(n))這樣，取模運算的規(guī)則可知，可以找到某個整數(shù)k，使得e*d=k*

(n)+191RSA算法的證明(續(xù)2)

以下就可以證明RSA算法。RSA算法的加密之后的解密過程可以表示為：D(E(M))=(E(M))d=(Me)d(modn)=Me*d(modn)=Mk*

(n)+1(modn)(5)由于p無法整除M，這樣，按照公式(1)和(2)可以得出：Mp–1=1(modp)

由于(p–1)是

(n)的因子，所以，Mk*

(n)=1(modp) 92RSA算法的證明(續(xù)2)

這樣，就可以得到如下公式：Mk*

(n)+1=M(modp) (6)同理可以得到如下公式：Mk*

(n)+1=M(modq) (7)由于n=p*q，綜合公式(6)和(7)，按照取模運算規(guī)則可以得出：Mk*

(n)+1=M(modn)這樣，就證明了RSA算法的加密和解密過程是正確的。

93RSA算法的實現(xiàn)RSA加密和解密算法。R.L.Rivest等人提出了一個計算Me的算法，它最多執(zhí)行2*log2(e)次乘法和除法，具體如下：（i）設ekek-1…e1e0是e的二進制數(shù)表示形式。（ii）設置變量C的初值為1。（iii）對于j=k,k–1,…,0，重復執(zhí)行(a)和(b)：(a)C=C*C(modn)

(b)如果ej=1，則C=C*M(modn)

（iv）輸出C，C就是M的密文。94RSA算法的實現(xiàn)(續(xù)1)RSA密鑰的選擇要求如下：對于p和q選擇的要求：其十進制位數(shù)應該不小于100，兩個數(shù)的長度僅僅差別幾個十進制數(shù)。另外，(p–1)和(q–1)應該包含很大的素數(shù)因子，而(p–1)和(q–1)之間的公因子應該很小。選擇與(n)互質(zhì)的私鑰d的方法比較簡單，例如任何大于max(p,q)的素數(shù)都可以作為d。為了防范攻擊者猜測到私鑰，d的選擇集合應該足夠大，不一定只局限于素數(shù)。95RSA算法的實現(xiàn)(續(xù)2)可以采用歐幾里德算法，通過計算(n)與d的最大公因子選擇公鑰e。歐幾里德計算(n)和d的最大公因子gcd((n),d)的算法可以表示為如下形式：(i)設x0=(n)，x1=d，j=1(ii)xj+1=xj-1(modxj)(iii)如果xj+10，則j=j+1，轉(zhuǎn)(ii)；如果xj+1=0，則輸出最大公因子xj。96RSA算法的實現(xiàn)(續(xù)3)由于(n)與d互質(zhì)，所以，它們的最大公因子是1。就可以找到參數(shù)e1和e2，使得

e1

*(n)+e2*d=1這里的e2滿足e2*d(mod(n))=1的條件，所以，e2可以作為與d對應的公鑰e。如果得出的e小于log2(n)，則從安全角度考慮，需要重新選擇d，重新計算e。97RSA算法舉例這里選擇p=47，q=59，n=47*59=2773，d=157。

(n)=46*58=2668，e計算如下：2668=157*16+156=157*17–1這樣，可知e=17以下對“ITSALLGREEKTOME”進行加密。首先采用00表示空格、01表示A、26表示Z，對該句子進行編碼，得到以下數(shù)據(jù)：092019000112120007180505110020150013050098RSA算法舉例(續(xù))以下僅對第一個數(shù)據(jù)塊進行加密，由于e二進制數(shù)為“10001”，則第一個數(shù)據(jù)塊加密算式如下：92017=(((((1)2*920)2)2)2)2*920=948(mod2773)以上整個英文句子加密后的密文為：0948234210841444266323900778077402191655對第一個數(shù)據(jù)塊的解密算式可以按照加密算式進行，其結果為：948157=92