網(wǎng)絡(luò)安全原理與應(yīng)用-第2章-密碼學(xué)導(dǎo)論

第2章密碼學(xué)導(dǎo)論(1)

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

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

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

什么是對(duì)稱(chēng)密鑰加密算法？什么是不對(duì)稱(chēng)密鑰加密算法？實(shí)際應(yīng)用中，是否可以采用不對(duì)稱(chēng)密鑰算法替代對(duì)稱(chēng)密鑰加密算法？試說(shuō)明理由。(6)

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

密碼技術(shù)主要應(yīng)該防御哪幾類(lèi)密碼破譯技術(shù)的攻擊？這幾類(lèi)密碼攻擊技術(shù)有何特征？什么類(lèi)型的密碼系統(tǒng)算是安全密碼系統(tǒng)？24第2章密碼學(xué)導(dǎo)論(2)

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

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

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

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

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

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

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

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

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

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

(2.7)47DES算法的解密過(guò)程(3)利用公式(2.6)和(2.7)，公式(2.5)，以及公式(2.1)和(2.2)可以推導(dǎo)出以下公式：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èi)推，可以用歸納法證明存在以下等式：L’j

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

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

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

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

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

DES算法的另外一個(gè)缺陷是在軟件中運(yùn)行的效率較低。為此NIST于1997開(kāi)始在世界范圍征集替代DES的加密算法，稱(chēng)為高級(jí)加密標(biāo)準(zhǔn)(AES)。

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

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

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

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

KS(K)P=C

KS(K)

為了保證流加密算法的安全性，對(duì)于不同的明文，必須采用不同的KS56RC4加密算法(續(xù)2)RC4加密算法分成兩個(gè)部分：初始化部分，主要用于產(chǎn)生長(zhǎng)度為256個(gè)八位位組的偽隨機(jī)比特序列；RC4處理部分，利用初始化產(chǎn)生的偽隨機(jī)比特序列對(duì)明文或者密文進(jìn)行逐個(gè)八位位組的“異或”操作，并且每當(dāng)對(duì)一個(gè)八位位組進(jìn)行一次“異或”操作，就更改偽隨機(jī)比特序列。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語(yǔ)言程序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語(yǔ)言程序59RC4加密算法(續(xù)5)經(jīng)過(guò)多年的分析和測(cè)試，可以證明在密鑰長(zhǎng)度足夠大時(shí)，并且丟棄到最前面的若干個(gè)（例如最前面的256個(gè)八位位組）偽隨機(jī)比特序列，RC4算法是安全的。需要注意的是，有些使用RC4加密算法的網(wǎng)絡(luò)安全標(biāo)準(zhǔn)設(shè)定的RC4密鑰長(zhǎng)度過(guò)短，例如安全套接層(英文縮寫(xiě)SSL)協(xié)議規(guī)范中規(guī)定了RC4的密鑰長(zhǎng)度為40個(gè)比特，這就使得RC4成為不安全的加密算法。

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

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

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

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

KP1

DES加密C2KP2

…DES加密Cn+1

KPn+1

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

Cj=E(K,Pj

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

Cj–1，

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

KP1

IVDES加密+C2KP2

…DES加密+Cn+1

KPn+1

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

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

Pj

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

Cj

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（3）如果公開(kāi)密鑰對(duì)中的一個(gè)密鑰，例如PK，則無(wú)法通過(guò)計(jì)算推導(dǎo)出另外一個(gè)密鑰，例如VK。

（4）如果只掌握了密鑰對(duì)中的一個(gè)密鑰PK，并且利用該密鑰將明文P加密得到密文C，則無(wú)法再利用該密鑰將C進(jìn)行解密得到明文P。

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

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

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

RSA公鑰加密算法可以分成兩個(gè)部分：RSA公鑰加密算法的加密和解密過(guò)程；RSA公鑰加密算法的“密鑰對(duì)”選擇和生成過(guò)程。

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

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

87RSA算法的密鑰選擇

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

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

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

M

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

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

(p)=p–1 (2)

(n)=

(p*q)=

(p)*

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

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

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

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

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

(n)+1(modn)(5)由于p無(wú)法整除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)，按照取模運(yùn)算規(guī)則可以得出：Mk*

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

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

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

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

e1

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

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