《可信計(jì)算課件資源》第2章密碼學(xué)技術(shù)

第二章密碼學(xué)技術(shù)122安全需求1/31/2023完整性Integrity真實(shí)性authenticity保證數(shù)據(jù)來源的真實(shí)性可追究性accountability確保一個(gè)主體能夠?qū)λ男袨?結(jié)果負(fù)責(zé)隱私性privacy維護(hù)個(gè)人身份信息的機(jī)密性維護(hù)數(shù)據(jù)的有效性及正確性，抵御惡意的或意外的更改機(jī)密性Confidentiality確保信息僅可被授權(quán)的用戶訪問可用性Availability維護(hù)資源/服務(wù)能夠傳遞到有效用戶2基本的安全路徑Identification身份證明Authentication認(rèn)證Authorization授權(quán)你是誰？你來自于什么地方？你所聲稱的你是你；你所聲稱的內(nèi)容是真實(shí)的。允許主體對其所請求資源所執(zhí)行的訪問。3身份證明(Identification)是一個(gè)動(dòng)作或一個(gè)過程，用于向系統(tǒng)表明一個(gè)實(shí)體的身份，這樣系統(tǒng)就可以將其與所有其他的實(shí)體區(qū)分開來。身份證明有兩個(gè)作用：可追查性與訪問控制。4認(rèn)證是一個(gè)過程，通過這個(gè)過程，一個(gè)實(shí)體向另一個(gè)實(shí)體證明其聲稱的屬性。認(rèn)證一般分為三種數(shù)據(jù)源認(rèn)證 驗(yàn)證消息的某個(gè)聲稱屬性，用它驗(yàn)證消息是否來源于所聲稱的消息源實(shí)體認(rèn)證驗(yàn)證消息發(fā)送者的身份認(rèn)證的密鑰建立（密鑰交換、密鑰協(xié)商）產(chǎn)生一條安全通道，用于后繼的應(yīng)用層安全通信會話認(rèn)證5授權(quán)授權(quán)是一個(gè)過程，對于一個(gè)給定的物理或邏輯資源，該過程需要判斷哪種訪問類型允許對資源進(jìn)行訪問。一旦用戶的身份已經(jīng)被授權(quán)了，那么他會允許訪問一個(gè)指定的區(qū)域、系統(tǒng)或服務(wù)。強(qiáng)制性授權(quán)：訪問控制列表細(xì)粒度加密67密碼學(xué)因應(yīng)用需求而產(chǎn)生,因應(yīng)用需求而發(fā)展。Cryptographyisoriginatedanddevelopedfromtherequirementsofapplication.8

2.1安全中的密碼問題2.2對稱加密DES2.3公鑰密碼學(xué)2.4密鑰管理92.1安全中的密碼問題10以數(shù)據(jù)加密、用戶認(rèn)證為基礎(chǔ)的開放型網(wǎng)絡(luò)安全保障技術(shù)，可望成為網(wǎng)絡(luò)安全問題的最終的、一體化解決方案。利用加密技術(shù)來保護(hù)網(wǎng)絡(luò)系統(tǒng)中包括用戶數(shù)據(jù)在內(nèi)的所有數(shù)據(jù)流，在不對網(wǎng)絡(luò)環(huán)境作特殊要求的前提下，從根本上解決網(wǎng)絡(luò)服務(wù)中的可用性和信息的完整性這兩大要求。不需要網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的支持，在數(shù)據(jù)傳輸中不對所經(jīng)的網(wǎng)絡(luò)的安全有要求，實(shí)現(xiàn)網(wǎng)絡(luò)通信過程端到端的安全保障。目前的防火墻系統(tǒng)都支持基于密碼技術(shù)的私有虛擬網(wǎng)（virtualprivatenetwork），可以說密碼是任何安全技術(shù)所不可缺少的部分。（1）密碼是安全技術(shù)核心11舉例：保險(xiǎn)柜保護(hù)珍貴的物品或機(jī)要的信息通常可以借助一個(gè)保險(xiǎn)庫，例如銀行的金庫。保險(xiǎn)柜中的每一件東西是以物理的方式進(jìn)行保護(hù)的，只有授權(quán)者用鑰匙或輸入相應(yīng)的組合密碼才能打開庫房的門。安全要求較高的地方，保險(xiǎn)柜的需要多把門鎖并按“分權(quán)原則”進(jìn)行管理，即由多人分別掌管不同的鑰匙，當(dāng)至少兩個(gè)以上的授權(quán)人同時(shí)在場，才能打開保險(xiǎn)庫。12舉例：紙幣

紙幣的安全問題，則完全屬于不同的類型。此時(shí)，鈔票安全的關(guān)鍵是真實(shí)性的鑒別，而不在于是否保密，因?yàn)殁n票決不允許被任何形式的偽造和更改。防偽：精制的版刻畫面、水印、特制的金屬絲線、隱藏在畫面內(nèi)的微寫以及各種其它標(biāo)記…，可以通過觀察和觸摸來驗(yàn)證。安全性好的貨幣，其防偽檢驗(yàn)措施應(yīng)簡潔而有效，用戶能較容易掌握。

13傳統(tǒng)的安全機(jī)制有兩個(gè)特點(diǎn)：安全性基于不可更改的物理標(biāo)記不論是保險(xiǎn)庫的鑰匙還是紙幣上的水印，它們基本上是保持不變的。正是標(biāo)記的不可更改，才使檢驗(yàn)系統(tǒng)真實(shí)性成為可能。安全性有時(shí)依賴于眾所周知的特征。為了保險(xiǎn)庫的安全，對鑰匙和組合密碼要求保密；但紙幣上標(biāo)識其真?zhèn)蔚母鞣N記號應(yīng)做到盡人皆知，這樣才便于人們檢驗(yàn)鈔票的真?zhèn)?。?）安全機(jī)制的特點(diǎn)14問題：系統(tǒng)的安全取決于物理標(biāo)記的不可復(fù)制及人們對系統(tǒng)的熟悉程度和經(jīng)驗(yàn)。隨著新技術(shù)的發(fā)展，專家所掌握的絕技很快成為大眾技術(shù)，“不可復(fù)制”的東西會一再地被復(fù)制出來。如果一個(gè)系統(tǒng)的安全基本上依賴于經(jīng)驗(yàn)這類人為的因素，這樣的安全是靠不住的，也是很危險(xiǎn)的。密碼學(xué)所追求的安全，是一種客觀的、可以被證明的安全。也就是：安全性不僅僅建立在靜止不變的物理特征上；安全判別不能只憑經(jīng)驗(yàn)，還要能邏輯地證明無限制的安全強(qiáng)度。

（2）安全機(jī)制的特點(diǎn)15密碼學(xué)的目標(biāo)正是要設(shè)計(jì)這樣的安全體系，它將提供可證明的各種強(qiáng)度的安全等級。數(shù)學(xué)相對于其它科學(xué)的優(yōu)勢在于它的邏輯體系，它的每一個(gè)推斷和結(jié)論都來自嚴(yán)格的證明?，F(xiàn)代密碼學(xué)正是一門數(shù)學(xué)背景極強(qiáng)的學(xué)科，它自然帶有數(shù)學(xué)的許多特征。設(shè)想一種貨幣（譬如電子貨幣），如果其安全強(qiáng)度可以借助密碼學(xué)的手段和數(shù)學(xué)方法證明，那樣貨幣發(fā)行銀行就無需因?yàn)榭萍及l(fā)展而擔(dān)驚受怕，因?yàn)樨泿诺陌踩皇墙⒃诮裉斓募夹g(shù)上，而是基于可以證明的、具有超前的安全強(qiáng)度。16密碼學(xué)除了提供在原理上可證明（數(shù)學(xué)上可分析）的安全性，還有“安全強(qiáng)度可加”等優(yōu)點(diǎn)。舉例：身份認(rèn)證的入口控制自動(dòng)取款機(jī)ATM。使用ATM之前，首先要作的是檢驗(yàn)用戶的身份，即用戶向ATM輸入個(gè)人密碼PIN，ATM經(jīng)過與系統(tǒng)的聯(lián)機(jī)查詢來判斷用戶是否合法。這種安全體系實(shí)際是通過靜態(tài)的PIN來鑒別身份，它的弱點(diǎn)是一但攻擊者從線路上截獲到PIN，就可以假冒用戶的身份進(jìn)行欺騙。為了避免靜態(tài)密碼潛在的不安全因素，考慮一種改良的身份認(rèn)證協(xié)議，它的基本特點(diǎn)是認(rèn)證過程不傳遞任何秘密，而是代以交換具有隨機(jī)特征的數(shù)據(jù)來實(shí)現(xiàn)問答，使攻擊者無從下手。這就是所謂的挑戰(zhàn)/應(yīng)答式協(xié)議C&R（ChallengenandResponse）17優(yōu)點(diǎn)：通過簡單的協(xié)議和密碼函數(shù)，可將系統(tǒng)的安全性提高一大步：即僅有卡而不知PIN仍無法通過檢查。缺點(diǎn)：系統(tǒng)同時(shí)也掌握用戶的密鑰k。鑒于這一點(diǎn)，可采用公鑰算法或無任何信息泄漏的零知識證明（Zero-Knowledge）算法。18動(dòng)態(tài)口令（挑戰(zhàn)/應(yīng)答）一個(gè)令牌每分鐘產(chǎn)生一個(gè)不同的口令服務(wù)器也同樣產(chǎn)生這樣的口令通過對比，如果一樣就通過認(rèn)證客戶端服務(wù)器(1)客戶端向服務(wù)器發(fā)送請求(1)服務(wù)器收到請求(1)請求驗(yàn)證(2)服務(wù)器產(chǎn)生隨機(jī)數(shù)(2)隨機(jī)數(shù)(2)收到服務(wù)器發(fā)來的隨機(jī)數(shù)(3)客戶端將隨機(jī)數(shù)通過USB接口傳送給ePass，產(chǎn)生口令(3)產(chǎn)生口令(4)服務(wù)器產(chǎn)生口令，驗(yàn)證S(口令)=C(口令)(4)驗(yàn)證結(jié)果19密碼學(xué)是信息安全的核心，圍繞著密碼理論和應(yīng)用分為幾個(gè)不同的層次，最底層是數(shù)學(xué)、邏輯等基礎(chǔ)；然后是基本的密碼算法，接下來是在此基礎(chǔ)上具有普適性的密碼協(xié)議，最上面是一些針對具體應(yīng)用的協(xié)議。數(shù)學(xué)基礎(chǔ)：數(shù)論、抽象代數(shù)、常用數(shù)學(xué)難題基本密碼學(xué)算法：對稱加密、非對稱加密、Hash基礎(chǔ)協(xié)議：數(shù)字簽名、零知識證明、VSS、盲簽名高級協(xié)議：電子選舉、電子拍賣、門限簽名,SSL20（3）密碼中的困難問題什么是計(jì)算計(jì)算模型可計(jì)算問題計(jì)算復(fù)雜度21隨著計(jì)算機(jī)日益廣泛而深刻的運(yùn)用，計(jì)算這個(gè)原本專門的數(shù)學(xué)概念已經(jīng)泛化到了人類的整個(gè)知識領(lǐng)域，并上升為一種極為普適的科學(xué)概念和哲學(xué)概念，成為人們認(rèn)識事物、研究問題的一種新視角、新觀念和新方法。在大眾的意識里，計(jì)算首先指的就是數(shù)的加減乘除，其次則為方程的求解、函數(shù)的微分積分等；懂的多一點(diǎn)的人知道，計(jì)算在本質(zhì)上還包括定理的證明推導(dǎo)?？梢哉f，“計(jì)算”是一個(gè)無人不知元人不曉的數(shù)學(xué)概念，事實(shí)上，直到1930年代，由于哥德爾K.Godel，1906-1978）、丘奇(A.Church，1903-1995)、圖靈(A.M.TUI-ing，1912-1954)等數(shù)學(xué)家的工作，人們才弄清楚什么是計(jì)算的本質(zhì)，以及什么是可計(jì)算的、什么是不可計(jì)算的等根本性問題。22所謂計(jì)算，就是從一個(gè)符號串f變換成另一個(gè)符號串g。例如:從符號串2+3變換成5就是一個(gè)加法計(jì)算;如果符號串f是x2

，而符號串g是2x,從f到g的計(jì)算就是微分。定理證明也是如此，令f表示一組公理和推導(dǎo)規(guī)則，令g是一個(gè)定理,那么從f到g的一系列變換就是定理g的證明。文字翻譯也是計(jì)算，如f代表一個(gè)英文句子，而g為含意相同的中文句子，那么從f到g就是把英文翻譯成中文。這些變換間有什么共同點(diǎn)？為什么把它們都叫做計(jì)算？因?yàn)樗鼈兌际菑募褐?串)開始，一步一步地改變符號(串)，經(jīng)過有限步驟，最后得到一個(gè)滿足預(yù)先規(guī)定的符號(串)的變換過程。23計(jì)算主要有兩大類：數(shù)值計(jì)算：包括實(shí)數(shù)和函數(shù)的加減乘除、幕運(yùn)算、開方運(yùn)算、方程的求解等。符號推導(dǎo)：包括代數(shù)與各種函數(shù)的恒等式、不等式的證明,幾何命題的證明等。無論是數(shù)值計(jì)算還是符號推導(dǎo),它們在本質(zhì)上是等價(jià)的、一致的，即二者是密切關(guān)聯(lián)的，可以相互轉(zhuǎn)化，具有共同的計(jì)算本質(zhì)。隨著數(shù)學(xué)的不斷發(fā)展,還可能出現(xiàn)新的計(jì)算類型。24計(jì)算的實(shí)質(zhì)：為了回答究竟什么是計(jì)算、什么是可計(jì)算性等問題，人們采取的是建立計(jì)算模型的方法。四種模型：一般遞歸函數(shù)、λ可計(jì)算函數(shù)、圖靈機(jī)和波斯特(E.L.Post，1897-1954)系統(tǒng)。在此基礎(chǔ)上，最終形成了如今著名的丘奇-圖靈論點(diǎn)：凡是可計(jì)算的函數(shù)都是一般遞歸函數(shù)(或是圖靈機(jī)可計(jì)算函數(shù)等)。這就確立了計(jì)算與可計(jì)算性的數(shù)學(xué)含義。25Turing機(jī)用機(jī)器來模擬人們用紙筆進(jìn)行運(yùn)算的過程：在紙上寫上或擦除某個(gè)符號；把注意力從紙的一個(gè)位置移動(dòng)到另一個(gè)位置；在每個(gè)階段，人要決定下一步的動(dòng)作，依賴于(a)此人當(dāng)前所關(guān)注的紙上某個(gè)位置的符號(b)此人當(dāng)前思維的狀態(tài)。圖靈構(gòu)造出一臺假想的機(jī)器，由以下幾個(gè)部分：一條無限長的紙帶一個(gè)讀寫頭一個(gè)狀態(tài)寄存器一套控制規(guī)則26可計(jì)算問題若某問題，若存在一個(gè)Turing機(jī)，對于相應(yīng)的初始狀態(tài)，Turing機(jī)經(jīng)過有限步最終停機(jī)。稱該問題是（Turing）可計(jì)算的。對于可計(jì)算的問題，計(jì)算復(fù)雜性的定義：計(jì)算所需的步數(shù)或指令條數(shù)(這叫時(shí)間復(fù)雜度)。計(jì)算所需的存儲單元數(shù)量(這叫空間復(fù)雜度)。27密碼的強(qiáng)度依賴于構(gòu)造密碼算法問題的計(jì)算復(fù)雜度。但計(jì)算上困難的問題不一定就意味著密碼算法的強(qiáng)度是足夠安全的（復(fù)雜度和安全的不平衡）密碼算法需要的是在不知道密鑰的情況下解密是困難的問題，但是在知道密鑰的情況下，解密應(yīng)該是容易的。（依賴陷門信息的困難）(4)密碼學(xué)28密碼學(xué)發(fā)展:大體分三個(gè)階段歷史時(shí)期的古典密碼學(xué)加密手段愷撒密碼二戰(zhàn)尤其是計(jì)算機(jī)出現(xiàn)以來的現(xiàn)代階段

-Shannon公鑰體系階段

Diffie/Hellman、RSA2920世紀(jì)早期密碼機(jī)30密碼學(xué)發(fā)展在密碼學(xué)的發(fā)展中，有一條原則就是秘而不宣。雖然歷史上早就有密碼學(xué)應(yīng)用的痕跡，但是是一戰(zhàn)刺激了其需求，而在二戰(zhàn)中得到了充分發(fā)展和應(yīng)用，并極大的影響了戰(zhàn)爭進(jìn)程。1949年，Shannon關(guān)于保密系統(tǒng)通信理論的發(fā)表，奠定了密碼學(xué)在公開領(lǐng)域研究的基礎(chǔ)。然后是廣泛商業(yè)應(yīng)用的DES標(biāo)準(zhǔn)。1975年，Hellman和Diffie提出了公鑰算法，這是現(xiàn)代密碼學(xué)的里程碑。隨后響應(yīng)這一號召而提出的RSA算法，至今仍是當(dāng)今網(wǎng)絡(luò)安全的基石。此后，隨著互聯(lián)網(wǎng)絡(luò)的發(fā)展，開創(chuàng)了密碼學(xué)應(yīng)用的新領(lǐng)域。31

Alice加密

E（P，K）＝C Bob解密

D（C，K）＝P

（1）函數(shù)公開，且一般D＝E

（2）K只有A、B知道（3）P明文，C為密文加密與解密32安全的問題1、D＝E＝XOR2、K是真隨機(jī)的，且和P等長

One-timePad（一次一密）這個(gè)算法也是理論上安全的唯一的算法理論安全性只有當(dāng)密鑰和明文一樣長時(shí)才能完全保密 即onetimepad計(jì)算安全性理論上并不完美，但在實(shí)踐中難以攻破33密碼學(xué)中兩個(gè)加密方法（申農(nóng)）Confusion混亂（替代）所謂混亂，是指在加密變換過程中是明文、密鑰以及密文之間的關(guān)系盡可能地復(fù)雜化，以防密碼破譯者采用統(tǒng)計(jì)分析法進(jìn)行破譯攻擊?；靵y可以用“攪拌機(jī)”來形象地解釋，將一組明文和一組密文輸入到算法中，經(jīng)過充分混合，最后變成密文。同時(shí)要求，執(zhí)行這種“混亂”作業(yè)的每一步都必須是可逆的，即明文混亂以后能得到密文，反之，密文經(jīng)過逆向的混亂操作以后能恢復(fù)出明文。Substitution替代密碼 以掩蓋明文和密文的關(guān)系34密碼學(xué)中兩個(gè)加密方法（申農(nóng)）Diffusion擴(kuò)散

所謂擴(kuò)散，是指要將算法設(shè)計(jì)得使每一比特明文的變化盡可能多地影響到輸出密文序列的變化，以便隱蔽明文的統(tǒng)計(jì)特性；擴(kuò)散的另一層意思是將每一位密鑰的影響也盡可能迅速地?cái)U(kuò)展到較多的輸出密文比特中去。即擴(kuò)散的目的是希望密文中的任一比特都要盡可能與明文、密文相關(guān)聯(lián)，或者說，明文和密鑰中任何一比特值得改變，都會在某種程度上影響到密文值的變化，以防止統(tǒng)計(jì)分析攻擊。無擴(kuò)散技術(shù)的加密

p1:00000000c1:00000010p2:00000001c2:00000011有擴(kuò)散技術(shù)的加密

p1:00000000c1:01011010p2:00000001c2:1110101135如果把一封信鎖在保險(xiǎn)柜中，把保險(xiǎn)柜藏在紐約的某個(gè)地方…，然后告訴你去看這封信。這并不是安全，而是隱藏。相反，如果把一封信鎖在保險(xiǎn)柜中，然后把保險(xiǎn)柜及其設(shè)計(jì)規(guī)范和許多同樣的保險(xiǎn)柜給你，以便你和世界上最好的開保險(xiǎn)柜的專家能夠研究鎖的裝置。而你還是無法打開保險(xiǎn)柜去讀這封信，這樣才是安全的。

36(5)基本概念和術(shù)語常規(guī)加密簡化模型37(5)基本概念和術(shù)語Shannon保密通信模型38

基本概念

?密碼學(xué)-研究加密技術(shù)的原理/方法（如何創(chuàng)建的秘密代碼）?密碼分析/密碼破譯-研究如何破譯密文的原則/解密的方法。

-目的：評估此加密系統(tǒng)是脆弱?Kerkhoffs‘的原則-密碼分析，假設(shè)敵手知道：加密/解密算法，但不知道密鑰KEY。39破譯是試圖恢復(fù)明文或找出密鑰的嘗試唯密文攻擊攻擊者只有一些密文(目的：找明文，可能找密鑰)已知明文攻擊知道一些過去的(明文及其密文所用過的密鑰)作參考和啟發(fā)選擇明文攻擊特定明文進(jìn)行加密，可得到密文（明密文的加密密鑰）選擇密文攻擊有一臺解密機(jī)（能使用解密密鑰）密碼分析的攻擊類型40兩個(gè)用戶A,B,攻擊者C[假設(shè)D(x1x2)=D(x1)D(x2)]41C隨機(jī)選擇rEB(r)EB(x)DB(EB(r)EB(x))rxC隨機(jī)選擇

rrxDB(EB(r)EB(x))EB(r)EB(x)41五元組（P，C，K，E，D）明文空間P 可能的明文的有限集密文空間C 可能的密文的有限集密鑰空間K 可能的密鑰的有限集對k∈K，決定一個(gè)加密規(guī)則ek∈E：P→C

和解密規(guī)則dk∈D：C→P，滿足對明文x∈P

dk（ek（x））＝x密碼體制42一個(gè)密碼系統(tǒng)的特點(diǎn)是：

使用的加密類型

-替代/置換

密鑰的使用

-單密鑰（或?qū)ΨQ）/雙密鑰（或公鑰）

對明文的處理方式

-塊（分組）/流43基本原則算法公開假設(shè)使用的算法和體制是公開的標(biāo)準(zhǔn)化：商用領(lǐng)域的互通性商用密碼體制的安全依賴于密鑰，而非算法密鑰的隨機(jī)性生成字典攻擊dictionaryattack沒有規(guī)律，不好猜蠻力攻擊bruteforceattack密鑰空間要大存儲、傳輸、使用軟件、硬件44密碼算法分類：按照密鑰的特點(diǎn)分類對稱密碼算法（symmetriccipher)：又稱傳統(tǒng)密碼算法（conventionalcipher)，就是加密密鑰和解密密鑰相同，或?qū)嵸|(zhì)上等同，即從一個(gè)易于推出另一個(gè)。又稱秘密密鑰算法或單密鑰算法。非對稱密鑰算法（asymmetriccipher):加密密鑰和解密密鑰不相同，從一個(gè)很難推出另一個(gè)。又稱公開密鑰算法（public-keycipher)

。公開密鑰算法用一個(gè)密鑰進(jìn)行加密,而用另一個(gè)進(jìn)行解密.其中的加密密鑰可以公開,又稱公開密鑰（publickey)，簡稱公鑰.解密密鑰必須保密,又稱私人密鑰（privatekey)私鑰.簡稱私鑰。45單密鑰加密技術(shù)密鑰原文ABCD原文ABCD密文%#%￥密鑰生成與分發(fā)密鑰互連網(wǎng)絡(luò)密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥原文ABCD原文ABCD密文%#%￥密文%#%￥原文ABCD密文%#%￥一個(gè)箱子一把鎖，箱子運(yùn)輸鎖上鎖，關(guān)鎖與開鎖用一把鑰匙，交換鑰匙是關(guān)鍵，如何讓鑰匙不被竊??？雙鑰匙加密技術(shù)公鑰（m,n=pq)私鑰(r,p,q)原文ABCD原文ABCD密文%#%￥公鑰(m,n=pq)亂文;~@‘互連網(wǎng)絡(luò)密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥密文%#%￥亂文;~@‘亂文;~@‘亂文;~@‘亂文;~@‘亂文;~@‘亂文;~@‘亂文;~@‘亂文;~@‘亂文;~@‘亂文;~@‘亂文;~@‘亂文;~@‘亂文;~@‘亂文;~@‘亂文;~@‘亂文;~@‘亂文;~@‘亂文;~@‘亂文;~@‘亂文;~@‘密文%#%￥亂文;~@‘原文ABCD原文ABCD密文%#%￥密文%#%￥原文ABCD密文%#%￥一個(gè)箱子一把鎖，兩把鑰匙對付鎖，一把關(guān)鎖一把開鎖，關(guān)鎖的不能開鎖，開鎖的不能關(guān)鎖，接收者提供鑰匙，把關(guān)鎖鑰匙交給對方，開鎖鑰匙留給自己。密碼算法分類：按照明文的處理方法分組密碼（blockcipher):將明文分成固定長度的組，用同一密鑰和算法對每一塊加密，輸出也是固定長度的密文。流密碼（streamcipher):又稱序列密碼.序列密碼每次加密一位或一字節(jié)的明文，也可以稱為流密碼。序列密碼是手工和機(jī)械密碼時(shí)代的主流48安全性分類理論安全性one-timepad [P=?NP]P?NP?PSPACE?EXPTIME?EXPSPACE實(shí)際安全性計(jì)算安全性 成本大于解密所得利益(機(jī)時(shí)和耗電)

周期長于所需保密時(shí)間可證明安全性

RSA算法的安全性等價(jià)于大數(shù)分解?49無條件安全（Unconditionallysecure）無論破譯者有多少密文,他也無法解出對應(yīng)的明文,即使他解出了,他也無法驗(yàn)證結(jié)果的正確性.如：Onetimepad可證明安全性（provablesecurity）如果能證明挫敗一個(gè)密碼學(xué)方法跟某個(gè)著名的困難問題（如整數(shù)素因子分解、計(jì)算機(jī)離散對數(shù)）的困難程度相同，則稱這個(gè)密碼學(xué)方法是可證明安全的；計(jì)算上安全（Computationallysecure）破譯的代價(jià)超出信息本身的價(jià)值破譯的時(shí)間超出了信息的有效期.密碼體制評價(jià)50蠻力攻擊bruteforceattack密鑰空間 Mkey/s Gkey/s2^32 35.8分2^56 10^3年2^128 10^24年 10^18年計(jì)算安全性51（1）常用對稱加密算法52DES和三重DES數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)是加密方案中最廣泛的應(yīng)用使用64位明文塊和56位密鑰產(chǎn)生64位密文塊關(guān)注算法及56位密鑰的使用

三重DES將基本的DES算法重復(fù)三次使用兩個(gè)或三個(gè)獨(dú)立的密鑰更加安全的同時(shí)速度變慢53高級加密標(biāo)準(zhǔn)(AES)DES的替代品1997年NIST公開征集的高級加密標(biāo)準(zhǔn)2001年被選為美國聯(lián)邦信息處理標(biāo)準(zhǔn)作為FIPS197頒布——對稱分組密碼使用128位分組數(shù)據(jù)&128/192/256位密鑰目前廣泛的應(yīng)用于商業(yè)54（2）消息認(rèn)證防止主動(dòng)攻擊證明接收的消息是可信的內(nèi)容未被篡改可靠的消息來源以正確的順序及時(shí)發(fā)送利用對稱加密的認(rèn)證（共享密鑰）只有發(fā)送方和接收方有共享密鑰獨(dú)立的認(rèn)證機(jī)制（數(shù)字簽名）附加信息來驗(yàn)證消息55消息認(rèn)證碼56消息認(rèn)證57（3）公鑰——加密58公鑰——認(rèn)證59公鑰算法RSA(Rivest,Shamir,Adleman)產(chǎn)生于1977年被認(rèn)為是使用最廣泛的且被實(shí)現(xiàn)的公鑰加密算法大概需要1024密鑰長度Diffie-Hellman密鑰交換算法用于共享密鑰的交換數(shù)字簽名標(biāo)準(zhǔn)(DSS)使用SHA-1提供了數(shù)字簽名功能橢圓曲線密碼(ECC)和RSA相比，使用更短的密鑰長度得到相同的安全性60公鑰證書612.2對稱加密DES62古典密碼思想替代和置換其技術(shù)、思想以及破譯方法雖然很簡單，但是反映了密碼設(shè)計(jì)和破譯的思想，是學(xué)習(xí)密碼學(xué)的基本入口。替代substitution 把明文的比特模式替換成密文的比特模式置換transpostion（換位）打亂明文的順序排列方式，即置亂63愷撒密碼（替代）破譯以下密文：wuhdwb

lpsrvvleohTREATYIMPOSSIBLECi=E(Pi)=Pi+3加密算法：字母表：(密碼本）

ABCDEFGHIJKLMNOPQRSTUVWXYZ

defghijklmnopqrstuvwxyzabc64通過執(zhí)行對明文字母的置換，取得一種類型完全不同的映射，即置換密碼。若該明文被視為一個(gè)比特序列，則置換涉及到用密文比特模式代替明文比特模式置換652413×3421a 1213A a1213 Ab 2424B 即 b2424 Bc 3132C c3132 Cd 4341D d4341 D

a 1213 1224 1232 A 1241b 2424 2432 2441 B 2413c 3132 3141 3113 C 3124d 4341 4313 4324 D 4332（a－A） （b－B） （c－A） （d－A）abcd－ABAAa 2413 2424 2432 A 2441b 3124 3132 3141 B 3113c 4332 4341 4313 4324d 1241 1213 1224 1232（a－B） （b－A） （c－C） （d－A）abcd－BACAa 3113 3124 3132 3141b 4324 4332 4341 4313c 1232 1241 1213 1224d 2441 2413 2424 2432（b－B） （b－C） （a－D） （b－B）bbab－BCDBa 4313 4324 4332 4341b 1224 1232 1241 1213c 2432 2441 2413 2424d 3141 3113 3124 3132（a－A） （a－A） （c－D） （d－A）aacd－AADAa 1213 1224 1232 1241b 2424 2432 2441 2413c 3132 3141 3113 3124d 4341 4313 4324 4332（a－A） （b－B） （c－A） （d－A）abcd－ABAA 明文abcd

abcd

bbab

aacd

abcd

密文ABAABACABCDBAADAABAA4個(gè)字母的例子66DES及后來的許多分組密碼設(shè)計(jì)中都充分體現(xiàn)了Shannon在1949年的論文中所提出的設(shè)計(jì)強(qiáng)密碼的思想。

由簡易實(shí)現(xiàn)的密碼系統(tǒng)進(jìn)行組合，構(gòu)造復(fù)雜的、密鑰量大的密碼系統(tǒng)。Shannon曾給出兩種組合方式，即概率加權(quán)法（分段）和乘積法（多次迭代）。

擴(kuò)散（Diffusion）概念：將每一位明文及密鑰盡可能迅速地散布到較多個(gè)密文數(shù)字中去，以便隱蔽明文的統(tǒng)計(jì)特性。

混淆（Confusion）概念：使明文和密文、密鑰和密文之間的統(tǒng)計(jì)相關(guān)性極小化。使統(tǒng)計(jì)分析更為困難?，F(xiàn)代密碼與Shannon密碼思想67對稱加密算法分類分組密碼算法（blockcipher）明文被分為固定長度的塊(即分組)，對每個(gè)分組用相同的算法和密鑰加解密分組一般為n＝64比特，或更長(Padding)密文分組和明文分組同樣長對某個(gè)密鑰可以構(gòu)造一個(gè)明密文對照表Codebook(SubstitutionTable)所以分組的長，至少64比特才好密鑰空間2^k<<可逆映射個(gè)數(shù)(2^n)!68對稱加密算法分類流加密算法streamcipher每次可以加密一個(gè)比特適合：如遠(yuǎn)程終端輸入等應(yīng)用流密碼的一類可用偽隨機(jī)數(shù)發(fā)生器實(shí)現(xiàn)密鑰做為隨機(jī)數(shù)種子，產(chǎn)生密鑰流keystream(不重復(fù),或極大周期)

XOR(plaintext，keystream)One-timePad69流密碼例：明文m=m1,m2,…….mk

偽隨機(jī)序列k=k1,k2,…….kk

密文ci=miki,i=1,2,…….k解密過程與加密過程一致序列密碼的安全性完全依賴于偽隨機(jī)數(shù)的強(qiáng)度移位寄存器是產(chǎn)生序列密碼的有效方法RC4、SEAL（SoftwareOptimizedEncryptionAlgorithm，軟件優(yōu)化加密算法）70分組加密與流加密比較基本區(qū)別粒度8字節(jié)分組vs.1比特或1字節(jié)各自適應(yīng)不同的應(yīng)用數(shù)據(jù)格式Padding（填充）對相同的明文分組，總是輸出相同的密文分組； 而流密碼卻輸出不同的密文比特流密碼一般快很多分組密碼多些，是主流分組密碼也可以用作流模式7172（1）Feistel/DES加密框架明文分組的長n＝2w分左右兩半L0R0密鑰K產(chǎn)生子鑰：K→k1，k2，…，kr

r是輪數(shù)，比如16輪⊕是異或函數(shù)XORp⊕x⊕x=p函數(shù)F是散列混亂函數(shù)可以是手工精心構(gòu)造的查表函數(shù)73FeistelNetwork74Feistel–‘for’Loop加密計(jì)算序列

L0＝左半 R0＝右半

L1＝R0 R1＝L0⊕F(k1,R0) L2＝R1 R2＝L1⊕F(k2,R1) L3＝R3

R3＝L2⊕F(k3,R2) … Li＝Ri-1

Ri＝Li-1⊕F(ki,Ri-1) …

Ln＝Rn-1

Rn＝Ln-1⊕F(kn,Rn-1)

密文即（Ln，Rn）解密計(jì)算75Feistel

加密/解密續(xù)下頁76接上頁772輪加解密舉例假設(shè)n＝2輪，C＝（L2，R2） 加密 明文＝半＋半＝L0+R0 L1＝R0 R1＝L0⊕F(k1,R0) L2＝R1 R2＝L1⊕F(k2,R1)解密 密文＝半＋半＝L2＋R2 R1＝L2 L1＝R2⊕F(k2,R1) R0＝L1 L0＝R1⊕F(k1,R0)

明文＝L0＋R0L1＝R2⊕F(k2,R1)＝L1⊕F(k2,R1)⊕F(k2,R1)＝L1L0＝R1⊕F(k1,R0)＝L0⊕F(k1,R0)⊕F(k1,R0)＝L078Feistel–特征分組大小密鑰大小循環(huán)次數(shù)一般僅幾輪是不夠的，得十幾輪才好，如16輪子鑰產(chǎn)生算法越復(fù)雜越好輪函數(shù)Round關(guān)鍵其他考慮速度（尤其是軟件實(shí)現(xiàn)的速度）便于分析（使用簡潔的結(jié)構(gòu)）79Feistel類算法舉例DES、CAST、Blowfish/(Twofish?)、RC6(/5)不是Feistel結(jié)構(gòu)的AES、IDEA*絕大數(shù)分組密碼屬于或類似Feistel結(jié)構(gòu)多輪每輪有XOR（或能恢復(fù)的操作）輪函數(shù)80DES加密算法的背景發(fā)明人：美國IBM公司W(wǎng).Tuchman和C.Meyer1971-1972年研制成功?；A(chǔ)：1967年美國HorstFeistel提出的理論產(chǎn)生：美國國家標(biāo)準(zhǔn)局（NBS)1973年5月到1974年8月兩次發(fā)布通告，公開征求用于電子計(jì)算機(jī)的加密算法。經(jīng)評選從一大批算法中采納了IBM的LUCIFER方案。標(biāo)準(zhǔn)化：DES算法1975年3月公開發(fā)表，1977年1月15日由美國國家標(biāo)準(zhǔn)局頒布為數(shù)據(jù)加密標(biāo)準(zhǔn)（DataEncryptionStandard），于1977年7月15日生效。（2）數(shù)據(jù)加密標(biāo)準(zhǔn)DES81DES特點(diǎn)分組大小SIZE=64bits密鑰大小SIZE=56bits輪數(shù)=16輪16個(gè)子密鑰=48bits82DES的描述DES是一種分組對稱加密算法，輸入的明文為64位，密鑰64位（實(shí)際可用密鑰長度為56位），生成的密文為64位；83DataEncryptionStandard（DES）DES同時(shí)用到了換位（置換）和替代參數(shù)Feistel體制分組密碼分組大小64bit，密鑰大小56bit，輪數(shù)16輪S-Boxes 84DESEncryption

OverviewPC-1PC-2連接PC-1連接PC－2連接初始置換Round1/31/202385Key:PermutedChoiceOne(PC-1)574941332517981585042342618161025951433527241911360524436326355473931231540762544638302248146615345372956211352820124647×8K的56比特重新排列，成為C0D0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263641/31/202386Key:PermutedChoiceTwo(PC-2)14171124153281562110231912426816727201324152313747553040514533484449395634534642503629328×6未入選的：9、18、22等每輪從56比特中選取48比特即為Ki，并同時(shí)左移Roundnumber12345678910111213141516Bitsrotated11222222122222211/31/202387Keyi48bit28×21/31/20238858504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157IP&IP-18×81在第40比特位置40848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725初始明文按照IP重排；16輪后的密文按照IP-1重排即為最后密文oddeven1/31/202389Li-1（32比特）Ri-1（32比特）Li（32比特）48比特寄存器選擇擴(kuò)展運(yùn)算E48比特寄存器子密鑰Ki（48比特）32比特寄存器選擇壓縮運(yùn)算S置換運(yùn)算PRi（32比特）Li=Ri-1DES的一輪迭代1/31/202390RoundKi48bit1/31/202391ExpansionPermutation3212345456789891011121312131415161716171819202120212223242524252627282928293031321Ri的32bit→48bit兩邊的是重復(fù)選中的6×81/31/202392RoundFunction6×84×81/31/202393S-Boxes：1-4兩邊2比特選擇行號中間4比特選擇列號1/31/202394S-Boxes：5-81/31/202395PermutationFunctionP16720212912281711523265183110282414322739191330622114258×4從S盒出來后重排1/31/202396DESEncryption

Review置換……1/31/202397OneSamplep=0123456789ABCDEFk=133457799BBCDFF1

……

c=85E813540F0AB4051/31/202398DES（64位）已經(jīng)破譯DES算法仍值得信賴但是關(guān)鍵場合不要用DES對一般個(gè)人用戶仍是安全的RSAchallenge反而給了信心DES還是AES，或者其他DES模塊仍廣泛存在，AES還沒有普及如果軟件實(shí)現(xiàn)，任何一個(gè)經(jīng)過考驗(yàn)的算法都好DES/3DES、AES、RC4、RC5、IDEA、BlowfishFree/Open99DES總結(jié)DES算法本身沒有大的缺陷對DES攻擊方法復(fù)雜度為2^47DES使用的2^56密鑰空間不夠大蠻力攻擊目前已能夠奏效(DESChanllengeIII)DES已經(jīng)不再是推薦標(biāo)準(zhǔn)AESDES模塊仍廣泛存在保護(hù)和延續(xù)投資對DES的改造使用現(xiàn)存的軟件硬件在強(qiáng)度上提高100DESModesofOperation

-FIPS81

DESbasicfunction:

DES(IN,Key,Enc/Dec)=OUTKey56bits(randombits!)Enc -IN64bitsplaintextblock -OUT64bitsciphertextblockDec -IN64bitsciphertextblock -OUT64bitsplaintextblock101

ApplyDEStwiceusingtwokeys,K1andK2.C=EK2[EK1[P]]P=DK2[DK1[C]]雙重DES可以是密鑰空間增大，Thisleadstoa2x56=112bitkey,soitismoresecurethanDES.Isit?Goal:giventhepair(P,C)findkeysK1andK2?中間人攻擊102分組密碼的工作模式：（1）電碼本（ECB）（2）密碼分組鏈接（CBC）（3）密碼反饋（CFB）（4）輸出反饋（OFB）（5）計(jì)數(shù)器（CTR）103104分組密碼的工作模式（1）電碼本模式（ECB）：用相同的密鑰分別對64位明文組加密，報(bào)文被順序分割分成8字節(jié)分組各個(gè)分組獨(dú)立加密，解密時(shí)需等齊整個(gè)分組填充典型應(yīng)用：單個(gè)數(shù)據(jù)安全傳輸105（1）FigureECB106（2）CBC:CipherBlockChaining

密碼分組鏈接方式

當(dāng)前明文分組先和前一個(gè)密文異或，再加密初始向量IV－initializationvector IV不必保密，但必須一致*優(yōu)點(diǎn)避免明密對應(yīng)還可以用做鑒別authentication*缺點(diǎn)等待緩沖區(qū)湊足8字節(jié)分組，否則需padding不能并行加密、隨機(jī)存取107108CFB:CipherFeedback

密碼反饋方式IV64bit，IV用Key加密得到RIV不必保密，但是必須相同明文s比特，與R的高位s比特XOR，得密文s比特s比特的密文同時(shí)從R的低位進(jìn)入，擠掉R的高位的s比特*優(yōu)點(diǎn)流密碼streamcipher也有校驗(yàn)的效果109110CTR:CounterMode 計(jì)數(shù)方式（也是一種流方式應(yīng)用）重復(fù)加密初始counter＋＋，得密鑰流明文與之XOR優(yōu)點(diǎn)適合隨機(jī)存取*注意：Counter的初值須不能預(yù)測111112使用常規(guī)加密進(jìn)行保密通信易受攻擊的位置113鏈路加密和端到端加密114鏈路加密在一段同質(zhì)線路的兩端鏈路兩端分別設(shè)置加密設(shè)備(硬件)要求所有線路段上都加密才行可以加密整個(gè)包【目的地址＋源地址＋控制＋數(shù)據(jù)＋校驗(yàn)】但是在路由器中可解密成明文*位于第一二層即物理層和數(shù)據(jù)鏈路層*對于在兩個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)間的某一次通信鏈路,鏈路加密能為網(wǎng)上傳輸?shù)臄?shù)據(jù)提供安全保證所有消息在被傳輸之前進(jìn)行加密,在每一個(gè)節(jié)點(diǎn)對接收到的消息進(jìn)行解密,然后先使用下一個(gè)鏈路的密鑰對消息進(jìn)行加密,再進(jìn)行傳輸115端到端加密端到端加密存在于兩個(gè)程序進(jìn)程之間只是在源和目的兩端架設(shè)保密設(shè)備只能加密有效[數(shù)據(jù)]載荷部分適合公共商用網(wǎng)*因此不能避免流量分析*位于在3＋層網(wǎng)絡(luò)層VPN、傳輸層SSL、應(yīng)用層PGP*適合分散用戶如一般的個(gè)人、公眾、商業(yè)應(yīng)用等116端到端加密端到端加密允許數(shù)據(jù)在從源點(diǎn)到終點(diǎn)的傳輸過程中始終以密文形式存在采用端到端加密(又稱脫線加密或包加密),消息在被傳輸時(shí)到達(dá)終點(diǎn)之前不進(jìn)行解密,因?yàn)橄⒃谡麄€(gè)傳輸過程中均受到保護(hù),所以即使有節(jié)點(diǎn)被損壞也不會使消息泄露117Linkvs.End-to-end118Applayervs.Linklayer1192.3公鑰密碼學(xué)120密碼學(xué)重要進(jìn)步從Rotor到DES

在對稱密鑰體制中，加密與解密使用同一密鑰，因此在公網(wǎng)上傳送和管理密鑰是一個(gè)嚴(yán)峻問題。NewDirectionsinCryptography

WhitfieldDiffie，Hellman1976提出了公鑰密碼算法的概念和思路提出了鑒別和簽名問題提出了D-H密鑰協(xié)商協(xié)議121公鑰密碼算法的思路對稱算法的缺陷為事先協(xié)商密鑰，需另外的安全信道或KDC不能滿足簽名的需求非對稱算法密鑰K＝（Kd，Ke），Kd即私鑰Ke即公鑰加密：E（P，Ke）＝C解密：D（C，Kd）＝P要求從Ke

Kd理論上能夠 實(shí)際上需要計(jì)算量太大因而很難122公鑰密碼算法的實(shí)現(xiàn)基于某些數(shù)學(xué)特性從公鑰推導(dǎo)私鑰理論可能，但計(jì)算困難

(從私鑰到公鑰容易)單向函數(shù)(one-wayfunction)123One-wayFunction單向性單向函數(shù)函數(shù)函數(shù)值計(jì)算很容易：已知x，很容易計(jì)算y=f(x)逆計(jì)算是不可行的：已知y，很困難計(jì)算x=f-1(y)困難程度舉例打碎/拼接、平方/開方、乘法/分解*單向函數(shù)存在否尚無嚴(yán)格的數(shù)學(xué)證明124TrapdoorOne-wayFunction單向陷門函數(shù)如果知道某個(gè)陷門(秘訣)，即能容易恢復(fù)x（陷門即為私鑰）舉例魔方的置亂/恢復(fù)如果有那個(gè)口訣，就能很快恢復(fù)加密/解密125公鑰算法參數(shù)建立及加解密每個(gè)用戶生成密鑰對(Ke、Kd)Ke或Kd是一個(gè)或幾個(gè)數(shù)(大數(shù))Ke需要公開Kd得自己秘密保留(公鑰publickey私鑰privatekey密鑰secretkey)公鑰的發(fā)布從Ke推導(dǎo)Kd的困難性使Ke不怕被公開公開的目錄服務(wù)公鑰Ke要在專門機(jī)構(gòu)（CA）登記126加密系統(tǒng)解密系統(tǒng)明文(P)乙方公鑰乙方密鑰密文(C)明文(P)甲方乙方加密（如果有人要給該用戶發(fā)送消息P）先獲得該用戶的公開鑰Ke加密C=E（P，Ke）傳輸解密D（C，Kd）＝P除非擁有Kd，否則不能解開*一般用于傳輸會話密鑰（和簽名及鑒別）127公鑰算法用來加密圖示128消息來源認(rèn)證和數(shù)字簽名公鑰不僅可用于加密，還能提供數(shù)據(jù)和消息來源的認(rèn)證（RSA）對消息H簽名：

S=Sig（H，Kd）驗(yàn)證

Ver（C，Ke）＝？H

消息H必然是Kd的持有人簽署的129公鑰算法用來認(rèn)證圖示130具有機(jī)密性與認(rèn)證性的公鑰體制131RSA算法由MIT的Rivest,Shamir&Adleman

在1977提出，R,S,ARonRivest

http:///~rivest/AdiShamir http://www.wisdom.weizmann.ac.il/~shamir/LenAdleman

http:///dept/molecular-science/基本參數(shù)分組密碼算法基于整數(shù)乘法明/密文分組以及公/私鑰被看作小于n的整數(shù)加/解密是模乘運(yùn)算132RSA參數(shù)建立選擇素?cái)?shù)選取兩個(gè)512bit的隨機(jī)素?cái)?shù)p,q計(jì)算模n和Euler函數(shù)φ(n)n＝pq

φ(n)=(p-1)(q-1)選取一個(gè)與φ(n)互素的整數(shù)e<n找ed≡1modφ(n)用擴(kuò)展Euclid算法求數(shù)d發(fā)布發(fā)布(e,n)，這是公鑰ked保密，(d,n)是私鑰kd133RSA加密解密加密明文分組m做為整數(shù)須小于n c=memodn解密

m=cdmodn134RSA實(shí)例選p＝7，q＝17則n＝pq＝119且φ(n)＝(p-1)(q-1)＝6×16＝96取e＝5則d＝77(5×77＝385＝4×96＋1≡1mod96)公鑰（5，119），私鑰（77，119）加密m＝19則c＝memodn=195mod119=66mod119解密c＝66m＝cdmodn=6677mod119＝19mod119135RSA考慮必須做到確定兩個(gè)大素?cái)?shù)：

p,q

選擇e或者d，并計(jì)算d或者e素?cái)?shù)測試是重要的算法必須夠大，否則對手可能很快分解n判定，試除法不可行判定，采用Miller-Rabin概率測試方法強(qiáng)素?cái)?shù)：(p-1)/2和(q-1)/2應(yīng)是素?cái)?shù)由e求d要使用到擴(kuò)展Euclid算法選取較小的e（較大的d）：e：3、65537快速計(jì)算X^Y%Z136RSA考慮必須做到確定兩個(gè)大素?cái)?shù)：

p,q

選擇e或者d，并計(jì)算d或者e素?cái)?shù)測試是重要的算法必須夠大，否則對手可能很快分解n判定，試除法不可行判定，采用Miller-Rabin概率測試方法強(qiáng)素?cái)?shù)：(p-1)/2和(q-1)/2應(yīng)是素?cái)?shù)由e求d要使用到擴(kuò)展Euclid算法選取較小的e（較大的d）：e：3、65537快速計(jì)算X^Y%Z137RSA中基本計(jì)算的復(fù)雜度大數(shù)的加、減計(jì)算復(fù)雜度O(k),O(k) {字加法}K是大數(shù)的字寬度大數(shù)的乘、除(逆元)計(jì)算復(fù)雜度O(k2),O(k2logk) {字乘法}大數(shù)指數(shù)運(yùn)算xcmodnO(k2logc) {字乘法}注：都是在modn下138攻擊RSA枚舉枚舉所有可能明文m，用e加密和c比較枚舉所有可能的私鑰d（已知明文）數(shù)學(xué)方法分解n=pq，就可以計(jì)算φ(n)，就可從e求得d不分解n，而直接求φ(n)，再求d不求φ(n)，直接求d大家相信：由n確定?(n)等價(jià)于因子分解139Diffie-HellmanD-H方案提供兩個(gè)用戶生成共享密鑰，是基于離散對數(shù)問題。步驟：選取大素?cái)?shù)q和它的一個(gè)公共的生成元g，這些參數(shù)公開A選擇隨機(jī)數(shù)Xa，B選擇隨機(jī)數(shù)Xb

A計(jì)算Ya＝g^Xamodq，B計(jì)算Yb＝g^Xbmodq交換Ya，YbA計(jì)算K＝Y(jié)b^Xamodq，B計(jì)算K'＝Y(jié)a^Xbmodq事實(shí)上，K＝K'140分析（別人怎么計(jì)算K?）：別人看到了Ya和Yb，但需要計(jì)算Xa或Xb，即要算離散對數(shù)

Ya＝g^Xamodq，或Yb＝g^Xbmodq

從公鑰計(jì)算出對應(yīng)私鑰也是計(jì)算上不可行的。141Diffie-Hellman的例子A，B一起選擇了q=53,g=17步驟：A，B分別選擇秘密密鑰XA=5,Xb=7

A計(jì)算公鑰Ya＝gXamodq=40，B計(jì)算公鑰Yb＝gXbmodq=6交換Ya，YbA計(jì)算共享密鑰K＝Y(jié)b^Xamodq=38，B計(jì)算共享密鑰K'＝Y(jié)a^Xbmodq=38K＝K'142對稱算法vs.公鑰算法安全性（下屏）速度典型相差1000倍密鑰管理對稱算法需要額外安全信道公鑰：證書中心CA混合密碼體制公鑰算法用于簽名和認(rèn)證用公鑰算法傳輸會話密鑰用會話密鑰/對稱算法加密批量數(shù)據(jù)143

對稱密碼vs.

公鑰密碼一般要求：1、加密解密用相同的密鑰2、收發(fā)雙方必須共享密鑰安全性要求：1、密鑰必須保密2、沒有密鑰，解密不可行3、知道算法和若干密文不足以確定密鑰一般要求：1、加密解密算法相同，但使用不同的密鑰2、發(fā)送方擁有加密或解密密鑰，而接收方擁有另一個(gè)密鑰安全性要求：1、兩個(gè)密鑰之一必須保密2、無解密密鑰，解密不可行3、知道算法和其中一個(gè)密鑰以及若干密文不能確定另一個(gè)密鑰1442.4密鑰管理145密鑰產(chǎn)生與分配一方產(chǎn)生，傳遞到另一方另外的安全信道，如面對面、電話、信函、信使等如果從前有一舊密鑰，可以借以傳遞新密鑰有中心的可通過第三方中心轉(zhuǎn)交(或中心產(chǎn)生,分發(fā)給雙方)中心可能和用戶有各自的通信密鑰分布式秘密計(jì)算使用不安全信道協(xié)商計(jì)算密鑰(DH密鑰協(xié)商協(xié)議)146交換密鑰：是與某個(gè)通信參與者相關(guān)聯(lián)的密鑰（與身份相關(guān)）。會話密鑰（sessionkey

）：是與通信本身相關(guān)聯(lián)的密鑰（與實(shí)體身份無關(guān)）。密鑰僅用于加密傳輸數(shù)據(jù)。1471、對稱密鑰的管理148密鑰傳遞問題密鑰的管理：主要手段是密鑰傳遞，是通過秘密信道進(jìn)行。秘密信道：（1）派遣專遞人員將密鑰送到對方。（2）數(shù)據(jù)的機(jī)密性不是很高，可通過郵遞系統(tǒng)傳送密鑰（銀行和信用卡中心在給客戶傳送口令時(shí)就是通過這種方式）。（3）秘密專用電纜用作秘密信道。問題：既然存在用于傳遞密鑰的秘密信道，為什么不直接通過該秘密信道傳遞數(shù)據(jù)呢？只有（3）

秘密信道并不保證信息的機(jī)密性149傳遞密鑰的秘密信道一般不適合用于直接傳遞機(jī)密信息。內(nèi)容需要保護(hù)的數(shù)據(jù)量遠(yuǎn)遠(yuǎn)大于密鑰量，而秘密信道傳送數(shù)據(jù)的代價(jià)要比公開信道高很多。密鑰的傳遞一般在秘密通信開始前進(jìn)行，可以容忍較長時(shí)間的延遲，而對保密數(shù)據(jù)的傳輸，一般不能容忍長時(shí)間延遲。密鑰傳遞實(shí)際問題：假定有n個(gè)用戶需要在兩兩之間建立一個(gè)共同密鑰，由于保密的原因，這些密鑰應(yīng)該互不相同，那么需要建立n(n+1)/2個(gè)不同的密鑰（不包括更新）。如何利用公開信道傳遞密鑰：Diffie-Hellman

1502、Diffie-Hellman密鑰協(xié)商交換協(xié)議通信相互傳遞部分信息，再分別根據(jù)對方的部分信息計(jì)算出秘密信息，使得雙方計(jì)算結(jié)果相同，而攻擊者卻不能根據(jù)所截獲的信息計(jì)算出這個(gè)秘密信息，于是就達(dá)到了密鑰傳遞的目的。這種方法不是密鑰傳遞，而是密鑰協(xié)商，最終得到的密鑰不是某一方選取的，而是根據(jù)雙方選取的隨機(jī)數(shù)產(chǎn)生的。151DH76，Diffie-Hellman步驟選取大素?cái)?shù)q和它的一個(gè)生成元g，這些參數(shù)公開A選擇隨機(jī)數(shù)Xa，B選擇隨機(jī)數(shù)Xb

A計(jì)算Ya＝g^Xamodq，B計(jì)算Yb＝g^Xbmodq交換Ya，YbA計(jì)算K＝Y(jié)b^Xamodq，B計(jì)算K'＝Y(jié)a^Xbmodq事實(shí)上，K＝K‘其困難程度被認(rèn)為等同于求解有限域上的離散對數(shù)問題。152證明、分析和例子證明K＝K’ K＝Y(jié)b^Xamodq K’＝Y(jié)a^Xb modq

＝(g^Xb)^Xamodq ＝(g^Xa)^Xbmodq

＝g^(XbXa)modq ＝g^(XaXb)modq舉例q＝97，g＝5 A選Xa＝36，B選Xb＝58，則

Ya＝5^36％97＝50，Yb＝5^58％97＝44