網(wǎng)絡(luò)安全理論課件 第3章 密碼學基礎(chǔ)與加密技術(shù)

位置：存放位置及文件名通信：通信方式活動：進程隱藏溫故而知新——特洛伊木馬隱蔽性1技術(shù)手段：運行實時監(jiān)控程序：防火墻、防病毒軟件端口掃描查看連接安全意識：不要隨意打開來歷不明的郵件不要隨意下載來歷不明的軟件及時修補漏洞和關(guān)閉可疑的端口盡量少用共享文件夾經(jīng)常升級系統(tǒng)和更新病毒庫溫故而知新——木馬與后門的防范方法2方案：問題解決方法算法架構(gòu)流程題目：1、DDoS防御互聯(lián)網(wǎng)、云計算環(huán)境、微信等新型2、漏洞發(fā)現(xiàn)與檢測3、木馬檢測與防御平時考核3第三章密碼學基礎(chǔ)與加密技術(shù)4密碼學的基本概念密碼學的發(fā)展歷史密碼學的重要算法內(nèi)容提要53.1密碼學中的基本概念6Kryptos（希臘文隱藏）Logos（希臘文信息）什么是密碼學？7KryptoslogosCryptology＋CryptographyCryptanalysis明文(Plaintext)：要保密的消息加密(Encryption)：偽裝消息以隱藏內(nèi)容的過程密文(Ciphertext)：加密后的消息解密(Decryption)：把密文轉(zhuǎn)變?yōu)槊魑牡倪^程加密員或密碼員(Cryptographer).密碼算法(CryptographyAlgorithm)：用于加密和解密的數(shù)學函數(shù)。加密采用的一組規(guī)則稱作加密算法(EncryptionAlgorithm).解密所采用的一組規(guī)則稱為解密算法(DecryptionAlgorithm).基本術(shù)語Copyright?電子科技大學計算機學院8

密碼學的目的：信源和信宿在不安全的信道上進行通信，而密碼分析員（破譯者）不能理解他們通信的內(nèi)容。加密通信的模型

Copyright?電子科技大學計算機學院9信源密鑰源加密器E解密器D明文P密鑰K密文C明文P密碼分析員公開信道秘密信道信宿

密碼體制Copyright?電子科技大學計算機學院10y=f(x)，x=f-1(y)c=E(m)m=D(c)D(c)=E-1(c)=E-1(E(m)=m加解密必要條件：一對一映射（滿的單射）滿射：象集中每個元素都有原象的映射

單射：原象集中不同元素的象不同的映射

密碼學本質(zhì)11

密碼學的目的：信源和信宿在不安全的信道上進行通信，而密碼分析員（破譯者）不能理解他們通信的內(nèi)容。溫故而知新——加密通信的模型Copyright?電子科技大學計算機學院12信源密鑰源加密器E解密器D明文P密鑰K密文C明文P密碼分析員公開信道秘密信道信宿

溫故而知新——密碼體制Copyright?電子科技大學計算機學院13密碼算法分類2023/5/14密碼算法基于密鑰保密性基于算法保密性基于保密的內(nèi)容對稱密碼算法非對稱密碼算法分組密碼算法流密碼算法明文處理方法按照保密的內(nèi)容分:受限制的（restricted)算法：算法的保密性基于保持算法的秘密?；诿荑€（key-based)的算法：算法的保密性基于對密鑰的保密。密碼算法分類-iCopyright?電子科技大學計算機學院15基于密鑰的算法，按照密鑰的特點分類：對稱密碼算法（symmetriccipher)：加密和解密密鑰相同，或從一個易于推出另一個。又稱秘密密鑰算法或單密鑰算法。DES、AES密碼算法分類-iiCopyright?電子科技大學計算機學院16加密解密明文M密文C原始明文M密鑰K密鑰KEK（M）=CDK（C）=M.DK（EK（M））=M.基于密鑰的算法，按照密鑰的特點分類：非對稱密鑰算法（asymmetriccipher)：加密密鑰和解密密鑰不相同，從一個很難推出另一個。又稱公開密鑰算法（public-keycipher)。RSA、ECC密碼算法分類-iiCopyright?電子科技大學計算機學院17加密解密明文M密文C原始明文M加密密鑰K1解密密鑰K2EK1（M）=CDK2（C）=MDK2（EK1（M））=M.按照明文的處理方法：分組密碼（blockcipher)將明文分成固定長度的組，用同一密鑰和算法對每一塊加密，輸出也是固定長度的密文。流密碼（streamcipher)又稱序列密碼.序列密碼每次加密一位或一字節(jié)的明文。密碼算法分類-iiiCopyright?電子科技大學計算機學院18目的：破譯密文或密鑰Kerckhoff原則：假設(shè)破譯者Oscar已知密碼體制，即掌握加解密算法最常見的破解類型如下：唯密文攻擊：Oscar具有密文串y.，主要窮舉攻擊已知明文攻擊：Oscar具有一個或多個明文串x和相應(yīng)的密文y.或特定明文模式（特定文件頭格式，軟件版權(quán)聲明等）選擇明文攻擊：Oscar獲得對加密機的暫時訪問，能選擇明文串x并構(gòu)造出相應(yīng)的密文串y。選擇密文攻擊：Oscar暫時接近解密機,可選擇密文串y，并構(gòu)造出相應(yīng)的明文x。

密碼分析Copyright?電子科技大學計算機學院19無條件安全（Unconditionallysecure）無論破譯者有多少密文，他也無法解出對應(yīng)的明文,即使他解出了,他也無法驗證結(jié)果的正確性.Onetimepad，一次一密計算上安全（Computationallysecure）破譯的代價超出信息本身的價值破譯的時間超出了信息的有效期可證明安全性密碼算法的安全性依賴于復(fù)雜問題大數(shù)分解背包問題密碼算法的安全性Copyright?電子科技大學計算機學院204.1密碼技術(shù)的發(fā)展歷史21Copyright?電子科技大學計算機學院古代加密方法（手工加密）古典密碼（機械階段）近代密碼（計算階段）密碼學的發(fā)展階段22古代密碼23應(yīng)用需求是推動技術(shù)發(fā)明和進步的直接動力。戰(zhàn)爭是科學技術(shù)進步的催化劑。有戰(zhàn)爭，就面臨著通信安全的需求，密碼技術(shù)源遠流長。存于石刻或史書中的記載表明，許多古代文明，包括希臘人、埃及人、希伯來人、亞述人都在實踐中逐步發(fā)明了密碼系統(tǒng)。古代加密方法Copyright?電子科技大學計算機學院24一種早期的希臘變換密碼一張紙條環(huán)繞在一個圓柱上消息沿著圓柱橫寫紙條上的字母看起來是一些隨機字母并不十分安全，密鑰是紙條和圓柱的寬度Scytale密碼25以一種形式寫下消息，以另一種形式讀取消息

幾何圖形密碼26Polybius校驗表（棋牌密碼）公元前2世紀，希臘人Polybius設(shè)計將字母編碼成符號對123451ABCDE2FGHI/JK3LMNOP4QRSTU5VWXYZCopyright?電子科技大學計算機學院27古典密碼28代換（代替Substitution）明文內(nèi)容的表示形式改變，內(nèi)容元素之間相對位置不變明文字母用密文中對應(yīng)字母代替置換（換位Transposition

orPermutation）明文內(nèi)容元素的相對位置改變，內(nèi)容的表示形式不變實現(xiàn)方式：手工或機械變換。典型加密技術(shù)29溫故而知新——密碼算法分類2023/5/14密碼算法基于密鑰保密性基于算法保密性基于保密的內(nèi)容對稱密碼算法非對稱密碼算法分組密碼算法流密碼算法明文處理方法caesar仿射棋盤單表多表代換技術(shù)31又叫循環(huán)移位密碼字母表收尾相連將明文字母替代為右（后）邊第k個字母加密：E(a)=(a+k)modn（%n）a：明文字母序號，k：密鑰，n：字符集中字母個數(shù)(26)。解密：D(a)=(a-k)%nCaesar密碼Copyright?電子科技大學計算機學院32設(shè)k＝3，明文P＝COMPUTERSYSTEMS，加密：E(C)=(2+3)%26=5=FE(O)=(14+3)%26=17=RE(M)=(12+3)%26=15=P……E(S)=(18+3）%26=21=V密文C=FRPSXWHUVBVWHPV，解密：D(F)=(5-3)%26=2=CCaesar密碼實例33凱撒加密法(CaesarCipher)

abcdzyxefabcdzyxefabcdzyxefabcdzyxef凱撒大帝前方軍士meet…phhw…pmwtmeet…明文：meetmeafterthetogaparty密文：phhwphdiwhuwkhwrjdsduwbpmwthh2023/5/1434凱撒加密的破解–暴力破解法phhwphdiwhuwkhwrjdsduwbogguogchvgtvjgvqicrctva-1abcdzyxefabcdzyxefnffunfbgufsuifuphbqbsuzabcdzyxefabcdzyxef-2meetmeafterthetogapartyabcdzyxefabcdzyxef-3Bingo!2023/5/1435凱撒加密的破解–暴力破解法對凱撒加密做暴力破解法

(Brute-forceCryptanalysis)25種的可能，逐一測試測試出來是明文，一看便知2023/5/1436選取參數(shù)k1，k2，k1與26互素加密：c=Ek(m)=(k1m+k2)%26解密：m=Dk(c)=k3(c-k2)%26，（k3×k1）%26=1eg,k1=3,k3=9gcd(k1,26)=1加解密可逆性條件加解密必要條件：滿的單射反例：k1=2,加密m1=1（b），m2=14（o）c1=(2+k2)%26=(28+k2)%26=c2仿射密碼37加法和乘法密碼結(jié)合k1=1，c=(m+k2)%26k2=0，c=k1m%26密鑰空間大小：k1×k2模運算性質(zhì)：結(jié)合律(a+b)%p=(a%p+b%p)%p(a*b)%p=(a%p*b%p)%pc=Ek(m)=(k1*m+k2)%26=(k1*m%26+k2%26)%26k1：φ(n)，序列0，1，2，…，n－1中與n互素的數(shù)的個數(shù)，φ(26)=12k2：26密鑰空間：12×26=312仿射密碼38密碼猜測caesar，k=1，2……25仿射，k1，k2（312）加法和乘法結(jié)合密碼破譯39發(fā)展歷程古代古典近代典型加密技術(shù)代換（代替Substitution）置換（換位Transposition

orPermutation）乘積密碼Caesar、仿射思考：scytale、Caesar、仿射分別采用什么技術(shù)溫故而知新——密碼學40在算法中維護著一個置換表，這個置換表記錄了明文和密文的對照關(guān)系。密鑰詞組：ILOVEMYCOUNTRY（去除重復(fù)Y）單表置換思考與Caesar、仿射的區(qū)別？無簡單加密函數(shù)自然語言存在高冗余，字母出現(xiàn)頻率不同無加密函數(shù)，怎么破？42頻率特征各種語言中，各個字母的使用次數(shù)是不一樣的。連接特征前后字母存在一定關(guān)聯(lián)性。英語中，q后幾乎百分之百連接著ux前幾乎總是i和e，只在極個別情況下是o和ae和e之間，r的出現(xiàn)頻率很高。重復(fù)特征兩個字符以上的字符串重復(fù)出現(xiàn)的現(xiàn)象。英語中th,the,tion,tious等經(jīng)常出現(xiàn)。代換密碼破譯的三大要素43e的頻率最高其次是t,a,o,I,n,s,h,rz,q,x,j頻率近似為0英語字母的頻率統(tǒng)計44步驟：1.統(tǒng)計密文中的字母出現(xiàn)頻率，將統(tǒng)計結(jié)果與自然語言頻率表對比，確定部分密鑰2.結(jié)合連接特征和重復(fù)特征，確定部分密鑰3.從語義上，猜測其它密鑰破譯凱撒密碼：通過識別a-e-i和r-s-t三元組的峰，或jk和xyz的特征，可以獲得密鑰破譯單表替換密碼：需確定每個字母雙、三字母的頻率統(tǒng)計表通常很有幫助字頻統(tǒng)計攻擊45字頻統(tǒng)計攻擊例密文：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ頻率最高的P和Z可能對應(yīng)e和t猜ZW是th（最常用二字組合），ZWP是the（最常用三字組合）{S、U、O、M、H}可能對應(yīng){a、h、i、n、o、r、s}{A、B、G、Y、I、J}可能對應(yīng){b、j、k、q、v、x、z}46aaaaaaaaaaiwsdisclosdysrdysvrlinformlbudircconcsvbnmdwipoliiclrprsnivsofviconginmoscowteetethteetetttheeeethteeettetheet明文字符固定加密（映射）為固定的密文字符密文保留了自然語言的字頻統(tǒng)計規(guī)律單表置換典型多表密碼：一個明文字母可映射為多個密文字母。密鑰k=k1k2……kn明文M=m1m2……mrci=（mi+ki）%26，i=1,2…r。例如：M=datasecurity，k=best：維吉尼亞（法國外交官Vigenere）密碼48datasecuritybestbestbesteelttiunsmlr49例如：

密鑰deceptive明文：wearediscoveredsaveyourself密鑰：deceptivedeceptivedeceptive密文：ZICVTWQNGRZGVTWAVZHCQYGLMGJ不同位置的同一明文字母，會用多個密鑰加密，字母頻率被模糊，但并未完全消失密鑰長d，則第i,i+d,i+2d,…明文（密文）密鑰相同（為ki）例：明文wearediscoveredsaveyourself密鑰：deceptive，d=9密文：ZICVTWQNGRZGVTWAVZHCQYGLMGJ重排列，在每一列上進行字頻攻擊維吉尼亞安全性：50ZICVTWQNGRZGVTWAVZHCQYGLMGJwearediscoveredsaveyourselfdeceptive+=密文中可能出現(xiàn)重復(fù)的字段明文中常存在重復(fù)字段當重復(fù)字段的間隔是d的整數(shù)倍時，將使用相同的密鑰加密，因而密文重復(fù)不同的明文獲得相同密文的巧合很少發(fā)生Kasiski方法在密文中尋找重復(fù)字段計算重復(fù)字段的間距密鑰長度d應(yīng)是這些間距的公約數(shù)缺點查找算法運算量大，耗時長時爾發(fā)生的巧合影響機器判斷Kasiski（普魯士少?？ㄎ魉够┓椒?1Vigenere多表替換，仍然重復(fù)使用密碼一次一密：名稱來源于特工攜帶的密碼本，每用一頁后撕去大、不重復(fù)的真隨機密鑰字母集發(fā)送者、接收者使用相同的一次密碼本發(fā)送者按序用密鑰字母加密明文中每個字符接收者按序用相應(yīng)的密鑰字母解密密文的每個字符。一個密鑰使用一次一次密碼本（onetimepad）Copyright?電子科技大學計算機學院52明文：00101100010....11011100101011密鑰：01110111010....10001011101011（加）密文：01011011000....01010111000000密鑰：01110111010....10001011101011（解）明文：00101100010....11011100101011一次性密碼本加密／解密的例證53俄羅斯亂數(shù)本俄羅斯一次一密密碼本的一頁。數(shù)字的排列具有俄國特色。54優(yōu)點：當隨機密鑰與明文等長時，絕對安全：每次都用新密鑰隨機密鑰產(chǎn)生的密文中完全沒有統(tǒng)計關(guān)系、規(guī)律唯一可理論證明的無條件安全缺點：實現(xiàn)困難難以產(chǎn)生大量真隨機密鑰真隨機數(shù)條件：看起來隨機、不可預(yù)測、不可重現(xiàn)目前一般靠自然物理現(xiàn)象產(chǎn)生，如：電路白噪聲、量子等難以及時、安全地分發(fā)大量密鑰一次性密碼本優(yōu)缺點55置換技術(shù)置換（Transposition

orPermutation）通過重排字母順序隱藏信息不改變字母表示形式不改變字母的統(tǒng)計概率與代換算法的本質(zhì)區(qū)別可藉此辨別密碼算法類型56將明文按對角線方向?qū)懗扇舾尚邪葱休敵黾用芙Y(jié)果例如：明文：meetmeafterthetogaparty書寫為兩行：mematrhtgpryetefeteoaat密文：MEMATRHTGPRYETEFETEOAAT柵欄技術(shù)（RailFenceCipher）57將明文按密鑰的位數(shù)寫為若干列按照密鑰，順序輸出各列例如：attackpostponeduntiltwoam.密鑰：4312567明文：attackpostponeduntiltwoamxyz密文:TTNAAPTMTSUOAODWCOIXKNLYPETZ

縱行換位（RowTranspositionCipher）58通過旋轉(zhuǎn)一個同樣的格子，得到不同的窗口例：明文：attackpostponeduntilseventwenty-fouram密文：ACSODLVTUTKTNTEWYAAOUIETNOMTPPNSNEFR思考：如何生成漏格板？旋轉(zhuǎn)漏格板59attackpostponduntilseventwentyfouramattackpostponduntilseventwentyfouram一維變換－矩陣轉(zhuǎn)置二維變換－圖形轉(zhuǎn)置更多變換60DNATSREDNUUOYNAC明文：canyouunderstand密文：codtaueanurnynsd輸入輸出UUOYNACSREDNNATD密文明文明文：canyouunderstand密文：dnsuaruteodynnac單重置換不夠安全規(guī)則簡單，易被重構(gòu)戰(zhàn)爭中的應(yīng)用都有被破譯的記錄多種/重置換安全性增強規(guī)則迭代后，重構(gòu)的難度大大增加多重置換61其它相關(guān)技術(shù)62嚴格來說，并不是加密技術(shù)。暗號和隱語暗號：通過事物的狀態(tài)或人的行為來傳達事先約定的信息消息樹、口哨、窗臺上的花瓶隱語：把信息變換成與此信息無關(guān)（但有意義）的語言“虎、虎、虎”、“天王蓋地虎”漏格板63大風漸起，寒流攻擊著我們的肌體，雪花從天空中落下，預(yù)示明天5點的活動，開始時會有困難。隱寫術(shù)（Steganography）方案：按一定規(guī)律將信息隱藏在大段消息中隱寫墨水、字符標記、針刺等圖像水印、語音水印、視頻水印缺點：大段消息中只能隱藏少量信息不夠安全。通常是先加密，后隱寫。應(yīng)用：秘密傳送版權(quán)保護數(shù)據(jù)完整性保護646566基于數(shù)學公式基于映射表表破解密鑰嘗試分析語言字頻統(tǒng)計規(guī)律溫故而知新——古代、古典密碼673.2近代密碼68由于自然語言特征，單純的替換或置換都不能保證安全。連續(xù)使用多種加密算法，可以提供更高的安全性多次代換可以構(gòu)造更復(fù)雜的代換多次置換可以構(gòu)造更復(fù)雜的置換代換后置換，可以大大提高安全性這是構(gòu)造現(xiàn)代密碼的基本技術(shù)之一密碼算法迭代69采用n個函數(shù)f1,f2,…,fn的復(fù)合c=f1(f2(…fn(m)))交替使用代換和置換，實現(xiàn)混亂（confusion）和擴散（diffusion），破壞對密碼系統(tǒng)進行的各種統(tǒng)計分析擴散：雪崩效應(yīng)每一位明文的變化盡可能多影響密文的變化每一位密鑰的變化也盡可能影響密文混亂：攪拌機使明文、密鑰和密文之間的統(tǒng)計關(guān)系變得盡可能復(fù)雜乘積密碼70乘積密碼（代換-置換網(wǎng)絡(luò)）71數(shù)據(jù)加密標準譯碼器編碼器典型的迭代密碼：一個輪函數(shù)一個密鑰編排方案特殊的迭代密碼：代換-置換網(wǎng)絡(luò)，輪函數(shù)包括三個變換：代換、置換、密鑰混合常見的乘積密碼——迭代密碼7273迭代密碼明文分組密文分組置換n次迭代代換子密鑰密鑰編排方案輪函數(shù)f1949年ClaudeShannon發(fā)表的“保密系統(tǒng)的通信理論”（TheCommunicationTheoryofSecrecySystems），這篇文章發(fā)表了30年后才顯示出它的價值。近代密碼的理論基礎(chǔ)Copyright?電子科技大學計算機學院741916-20011967年DavidKahn的《TheCodebreakers》1971-73年IBMWatson實驗室的HorstFeistel等的幾篇技術(shù)報告Smith,J.L.,TheDesignofLucifer,ACryptographicDeviceforDataCommunication,1971Smith,J.L.,…,AnExprementalApplicationofCryptogrphytoaremotelyAccessedDataSystem,Aug.1972Feistel,H.,CryptographyandComputerPrivacy,May1973近代密碼的理論基礎(chǔ)Copyright?電子科技大學計算機學院75數(shù)據(jù)的安全基于密鑰而不是算法的保密算法公開，密鑰保密1976年W.Diffie和M.Hellman發(fā)表了“密碼學的新方向”（NewDirectionsinCryptography）一文，提出了適應(yīng)網(wǎng)絡(luò)上保密通信的公鑰密碼思想，掀起了公鑰密碼研究的序幕。近代密碼的理論基礎(chǔ)Copyright?電子科技大學計算機學院76W.DiffieM.Hellman1978年RSA公鑰密碼體制的出現(xiàn)，公鑰密碼杰出代表，事實標準密碼學史上里程碑之一。2002年圖靈獎近代密碼學應(yīng)用的里程碑之一Copyright?電子科技大學計算機學院77RonRivestAdiShamir

LeonardAdleman1978美國國家標準局正式公布實施了美國的數(shù)據(jù)加密標準（DataEncryptionStandard，DES），公開它的加密算法，并被批準用于政府等非機密單位及商業(yè)上的保密通信。近代密碼學應(yīng)用的里程碑之二Copyright?電子科技大學計算機學院78美國計算機協(xié)會（ACM）3.14宣布了2012年度圖靈獎得主：MIT機電工程與計算機科學系教授SilvioMicali。以色列魏茨曼科學研究所算機科學與應(yīng)用數(shù)學教授ShafiGoldwasser、開創(chuàng)了可證明安全性領(lǐng)域的先河，奠定了現(xiàn)代密碼學理論的數(shù)學基礎(chǔ)。他們創(chuàng)造出了將密碼學從藝術(shù)變?yōu)橐婚T科學的數(shù)據(jù)架構(gòu)。2012年度圖靈獎793.3對稱加密算法80Copyright?電子科技大學計算機學院81加密通信的模型加密解密明文M密文C原始明文M密鑰K密鑰KEK（M）=CDK（C）=M.DK（EK（M））=M.DES82美國商業(yè)部國家標準局NBS于1973年5月和1974年8月兩次發(fā)布通告，向社會征求密碼算法。IBM公司研制的分組乘積密碼體制lucifer應(yīng)征美國國家標準局NIST：1977年作為非機要部門使用的數(shù)據(jù)加密標準國際商用保密通信和計算機通信最常用的加密算法，2000年停用56位密鑰來加密64位數(shù)據(jù)的方法DES(DataEncryptionStandard)算法Copyright?電子科技大學計算機學院83適宜硬件實現(xiàn)，處理速度遠超軟件實現(xiàn)。衍生出可抗差分分析攻擊的變形DES以及密鑰長度為128比特的三重DES等。

在POS、ATM、磁卡及智能卡（IC卡）、加油站、高速公路收費站等領(lǐng)域被廣泛應(yīng)用如信用卡持卡人PIN的加密傳輸IC卡與POS間的雙向認證DES(DataEncryptionStandard)算法Copyright?電子科技大學計算機學院84采用n個函數(shù)f1,f2,…,fn的復(fù)合c=f1(f2(…fn(m)))交替使用代換和置換，通過混亂（confusion）和擴散（diffusion），破壞對密碼系統(tǒng)進行的各種統(tǒng)計分析典型的迭代密碼：一個輪函數(shù)一個密鑰編排方案特殊的迭代密碼：代換-置換網(wǎng)絡(luò)，輪函數(shù)包括三個變換：代換、置換、密鑰混合溫故而知新—常見乘積密碼—迭代密碼8586溫故而知新——迭代密碼明文分組密文分組置換n次迭代代換密鑰密鑰編排方案輪函數(shù)f三個入口參數(shù)：Key、Data、%e。Key：8byte共64bit，有效56bit；Data：8byte共64bit；%e：加密或解密。DES算法原理Copyright?電子科技大學計算機學院8788DES算法原理

64位碼64位碼初始變換逆初始變換16次迭代變換明文密文輸入輸出IPIP-189初始變換IP輸入（64位）58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157輸出（64位）L0（32位）R0（32位）矩陣轉(zhuǎn)秩+字節(jié)內(nèi)置換90IP(InitialPermutation)908162432404856816243240485691逆初始變換IP-1輸入（64位）40848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725輸出（64位）92IP-1(FinalPermutation)9281624324048568162432404856IP×IP-1=E不影響DES的安全性，只是為了使得算法更加難以理解。初始變換和逆變換9394DES9464bitplaintextblockIPL0R0L1=R0R1=L0+f(R0,K1)fK1(derivedfrom

56bitkey)L16=R15fK16(derivedfrom

56bitkey)IP-1repeat16times…64bitciphertextblockR16=L15+f(R15,K16)32324895f函數(shù)95LiRiLi+1Ri+148bitsubkeyGeneratorK48=g(i,K56)(Thekeyforeachroundisdeterministicallyfoundfromtheinput56bitkey).ExpansionPermutationS-BoxSubstitutionP-BoxPermutation324848483232323232f函數(shù)f(Ri,Ki)——S-BoxRi(32bits)Ki(48bits)E48bitsB1B2B3B4B5B6B7B8

S1S2S3S4S5S6S7S8C1C2C3C4C5C6C7C8P32bitsB分成8個6位比特串S-BoxSubstitution壓縮代換（6bits->4bits）97擴展置換ER(32bit)321234545678989101112131213141516171617181920212021222324252425262728292829303132148bit98擴展置換E98145891213161720212425282932148ExpansionPermutation324899使用密鑰99148X-ORwith48bitkey148484848100代換壓縮100S-box1S-box2S-box3S-box4S-box5S-box6S-box7S-box8145891213161720212425282932148S-BoxSubstitution4832把6bit數(shù)據(jù)變?yōu)?bit數(shù)據(jù)。S1,S2...S8選擇函數(shù)101數(shù)據(jù)加密標準S1:14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7,

0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8,

4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0,

15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13,S2:15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10,3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5,0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15,13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9,4X16矩陣102數(shù)據(jù)加密標準S6:

12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11,

10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8,

9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6,

4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13,S7:

4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1,

13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6,

1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2,

6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12,S8:

13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7,

1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2,

7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8,

2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11,S3:

10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8,

13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1,

13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7,

1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12,S4:

7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15,

13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9,

10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4,

3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14,S5:

2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9,

14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6,

4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14,

11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3,103HowanS-BoxworksS-box11441312151183106125907015741421311061211953841148136211151297310501512824917511314100613lineselect行列坐標104HowanS-Boxworks數(shù)據(jù)加密標準012345678910111213141501441312151183106125907101574142131106121195382411481362111512973105031512824917511314100613S1101100

1020010輸入6位輸出4位DES最敏感部分，原理至今未公開。人們擔心隱藏陷門，但并沒找到弱點。美國國家安全局透露了幾條設(shè)計準則：1.不是輸入的線性仿射函數(shù)。2.改變1位輸入，輸出至少改變2位。最大程度上增大了擴散量。3.任意一位輸出保持不變時，0和1個數(shù)之差極小。即如果保持一位不變而改變其它五位，那么其輸出0和1的個數(shù)不應(yīng)相差太多。S-box105106P置換P-BoxPermutation3232Theoutputsof8

S-Box（32bits）1672021291228171152326518311028241432273919133062211425P-BoxOutputoffunctionf（32bits）10732bit置換145891213161720212425282932P-BoxPermutation3232145891213161720212425282932108子密鑰的產(chǎn)生64位密鑰置換選擇1C0(28位)D0(28位)循環(huán)左移循環(huán)左移C1(28位)D1(28位)置換選擇2K1(48位)(56位)循環(huán)左移循環(huán)左移Ci(28位)Di(28位)置換選擇2Ki(48位)(56位)16個子密鑰的生成算法循環(huán)左移：119121102321124212252132621427215282161109密鑰置換選擇157494133251791585042342618102595143352719113605244366355473931331576254463830221466153453729211352820124不考慮各字節(jié)第8位密鑰（64位）C0(28位)D0(28位)110InitialKeyPermutation8162432404856816243240485664密鑰置換2去掉第9，18，22，25，35，38，43，54位，56位變成48位111數(shù)據(jù)加密標準Ci(28位)Di(28位)1417112415328156211023191242681672720132415231374755304051453348444939563453464250362932Ki(48位)112KeySplit&Shift&Compress8162432404856ShiftleftbyNiShiftleftbyNi8162432404856Ni={1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1}81624324048ShiftaccumulateseveryroundK48K56113DES完整一輪迭代DES代碼classCShift{public:DWORDLONGmask[16];intstep[16];CShift(){for(inti=0;i<16;i++){step[i]=2;mask[i]=0xc000000;}step[0]=step[1]=step[8]=step[15]=1;mask[0]=mask[1]=mask[8]=mask[15]=0x8000000;}}classCDES{public:CDES(){m_dwlKey=0;m_dwlData=0;ConvertTableToMask(dwlKey_PC_1,64）；//PrintTable(dwlKey_PC_1,7,8）；ConvertTableToMask(dwlKey_PC_2,56）；ConvertTableToMask(dwlData_IP,64）；ConvertTableToMask(dwlData_Expansion,32）；ConvertTableToMask(dwlData_FP,64）；ConvertTableToMask(dwlData_P,32）；Generate_S();}114與DES的加密過程完全類似將16輪子密鑰序列K1，K2……K16的順序倒過來。即第一輪用第16個子密鑰K16，第二輪用K15，其余類推。DES解密算法115強力攻擊：255次嘗試差分密碼分析法（Shamir）：247次嘗試線性密碼分析法：243次嘗試DES算法存在的問題與挑戰(zhàn)116數(shù)據(jù)加密標準117溫故而知新——DES完整一輪迭代1997年DES抗攻擊的統(tǒng)計分析結(jié)果DES算法安全性118數(shù)據(jù)加密標準個人攻擊小組攻擊院校網(wǎng)絡(luò)攻擊大公司軍事情報機構(gòu)40（bits）數(shù)周數(shù)日數(shù)小時數(shù)毫秒數(shù)微秒56數(shù)百年數(shù)十年數(shù)年數(shù)小時數(shù)秒鐘64數(shù)千年數(shù)百年數(shù)十年數(shù)日數(shù)分鐘80不可能不可能不可能數(shù)百年數(shù)百年128不可能不可能不可能不可能數(shù)千年119上表攻擊者的計算資源及攻擊能力數(shù)據(jù)加密標準上表中攻擊者配有如下計算機資源的攻擊能力

攻擊者類型所配有的計算機資源每秒處理的密鑰數(shù)個人攻擊1臺高性能桌式計算機及其軟件217-224小組攻擊16臺高性能桌式計算機及其軟件221-224院、校網(wǎng)絡(luò)攻擊256臺高性能桌式計算機及其軟件225-228大公司配有價值1百萬美元的硬件243

軍事情報機構(gòu)配有價值1百萬美元的硬件及先進的攻擊技術(shù)2551、二重DES（二個密鑰，長度112位）：加密：C=Ek2[Ek1(P)]解密：P=Dk1[Dk2(C)]要防止中途攻擊2、三重DES（二個密鑰）加密：C=Ek1[Dk2[Ek1(P)]]解密：P=Dk1[Ek2[Dk1(C)]]3、IDEA加密算法1992年，瑞士的Lai和Massey128位密鑰，8輪，快速，軟硬件實現(xiàn)。多重DES及IDEA120AES1211997年9月，國家標準技術(shù)研究所NIST征集高級加密標準AES，替代DES。選擇的基本條件：公開；對稱分組密碼；鑰匙長度動態(tài)可變：128、192、256可軟硬件實現(xiàn)。1998年8月首次選出15個候選者，1999年3月遴選出5個，2000年10月確定比利時的Rijndael算法成為AES。高級加密標準(AES)1222023/5/14AES算法概要明文Xir輪迭代密文Y子密鑰K0

（a）AES算法框圖Xi-1字節(jié)代替BS行移位SR列混合MCXiKi-1（b）一輪AES結(jié)構(gòu)AES的設(shè)計原則：能夠抵御已知攻擊、硬件實現(xiàn)容易且速度快、設(shè)計簡單3.4分組密碼加密模式124

大數(shù)加密問題：保持各分組內(nèi)容的完整保持各分組的次序不變加密算法不僅要包括加密算法本身，還需要帶有某種大數(shù)加密機制。根據(jù)加密分組間的關(guān)聯(lián)方式，可以分為五種加密模式。分組密碼加密模式

電子代碼本（ECB-ElectronicCodeBook）模式分組依次獨立加密，產(chǎn)生獨立密文分組，各分組加密結(jié)果互不影響優(yōu)點：簡單利于并行誤差不傳送適合傳輸長度短的報文缺點：不隱藏明文模式：相同明文分組產(chǎn)生相同分組可主動攻擊：密文內(nèi)容若遭剪貼、替換，也不易被發(fā)現(xiàn)

密鑰E密鑰E密鑰E密文分組明文分組密鑰E密鑰E密鑰E密鑰E明文分組密文分組密鑰DDDD電子代碼本ECB不能很好的隱藏數(shù)據(jù)模式同樣明文塊產(chǎn)生相同的密文塊加密工作模式效果127原圖ECB模式加密非ECB模式加密128

第一分組先與初始向量(IV)異或再加密，后續(xù)分組先與前一密文分組異或再加密，每一分組加密結(jié)果均受前面所有分組內(nèi)容的影響優(yōu)點：隱藏了明文模式；不容易主動攻擊，安全性好于ECB適合傳輸長度長的報文是SSL、IPSec的標準。缺點：不利于并行誤差傳遞需IV密碼塊鏈模式（CBC-CipherBlockChaining）

密文分組密鑰IV明文分組區(qū)EEEEIVD密文分組密鑰明文分組DDD加密初始化向量，結(jié)果與第一明文分組異或。前一個密文分組作為輸入向量加密后當前明文分組異或優(yōu)點：隱藏了明文模式；分組密碼轉(zhuǎn)化為流模式可以及時加密傳送小于分組的數(shù)據(jù)缺點：不利于并行誤差傳送唯一IV密文反饋模式（CFB-CiphertextFeedback）

IV密文分組密鑰明文分組EEEEIV密鑰密文分組明文分組EEEE

IV加密后與第一分組異或產(chǎn)生第一密文分組前一加密結(jié)果作為當前加密的輸入向量前一加密結(jié)果與當前明文分組異或產(chǎn)生密文分組優(yōu)點：隱藏明文模式分組轉(zhuǎn)流模式傳送小于分組的數(shù)據(jù)缺點：不利并行可主動攻擊誤差傳送需IV輸出反饋模式（OFB-OutputFeedback）

計數(shù)器模式（Counter(CTR)）計數(shù)器值加密后與明文異或，隨著消息塊的增加，計數(shù)器的值依次遞增1解密使用相同計數(shù)器值序列加密后與密文分組異或適合對實時性和速度要求比較高的場合，具有以下的優(yōu)點。處理效率：下一塊數(shù)據(jù)不需要前一塊數(shù)據(jù)的運算結(jié)果，并行加密(解密)。預(yù)處理：基本加密算法的執(zhí)行不依賴明文或者密文的輸入，可以事先處理。隨機訪問：各密文分組的處理獨立，可隨機對任一密文分組進行解密處理。簡單性：只需實現(xiàn)加密算法，加密階段和解密階段都使用相同的加密算法。分組轉(zhuǎn)流模式，傳送小于分組的數(shù)據(jù)缺點：可主動攻擊：密文內(nèi)容若遭剪貼、替換，也不易被發(fā)現(xiàn)誤差傳送3.5公開密鑰體制（非對稱密碼體制）

密鑰管理困難對稱密碼體制：通信雙方需一對密鑰，n個用戶需要C(n,2)=n(n-1)/2個密鑰。用戶量增大，密鑰量急劇增大。如：n=100，C(100,2)=4,995n=5000，C(5000,2)=12,497,500分配問題：保密通信前，需安全（通道）傳遞密鑰對稱加密算法無法實現(xiàn)抗抵賴的需求數(shù)字簽名問題問題的提出Copyright?電子科技大學計算機學院1341976Stanford大學Diffie和Hellman在“密碼學發(fā)展新動向”一文中首次提出公開密鑰密碼體制思想。解決：加密密鑰分配數(shù)字簽名公開密鑰密碼體制的提出公開密碼體制思想Copyright?電子科技大學計算機學院136CBACB公開密碼體制思想Copyright?電子科技大學計算機學院137AB公開Ku保密Kr公開公開密碼體制Copyright?電子科技大學計算機學院138每個用戶擁有（產(chǎn)生）一對密鑰加密密鑰Ku——公開，公鑰解密密鑰Kr——保密，私鑰公私鑰相互決定，但不能相互推導(dǎo)加解密算法公開加密：Eku(m)=c解密：Dkr(c)=m兩個密鑰中任何一個都可以用作加密，而另一個用作解密用公開密鑰實現(xiàn)加密DKRb(c)=mget(KUb)EKUb(m)=c用公鑰加密的信息，不用能公鑰解密用公鑰密碼實現(xiàn)鑒別（簽名）140公鑰私鑰簽名：sig=DKR(m)驗證：m=EKU(sig)用公開密鑰實現(xiàn)鑒別（簽名）DKRa(m)=sigget(KUa)EKUa(sig)=m用公開密鑰實現(xiàn)保密和鑒別EKUb(DKRa(m))=cEKUa(DKRb(c))=m公鑰密鑰管理PKIabcABC1.Getkb2.Ekb(M)3.Db(M)安全性主要基于數(shù)學中的難解問題最流行的有兩大類基于大整數(shù)因子分解問題，351*79=27729比如RSA體制、Rabin體制等基于離散對數(shù)問題如ElGamal體制、橢圓曲線密碼體制公鑰密碼體制的安全基礎(chǔ)standFord公鑰體制的起源MartinE.Hellman

RalphC.MerkleWhitefieldDiffie公鑰思想＋背包公鑰算法Merke難題2015年圖靈獎mit公鑰體制的起源——RSARonaldL.RivestAdiShamirLeonardM.AdlemanRSA公鑰算法－大整數(shù)因子分解困難性2002年圖靈獎密鑰管理困難數(shù)量龐大難分發(fā)不支持簽名，不能抗抵賴溫故而知新——對稱密碼算法局限147溫故而知新——公開密碼體制思想Copyright?電子科技大學計算機學院148CBACB溫故而知新——公開密碼體制思想Copyright?電子科技大學計算機學院149AB公開Ku保密Kr公開公鑰密碼算法的設(shè)計

涉及到各方：發(fā)送方、接收方、攻擊者涉及到數(shù)據(jù)：公鑰、私鑰、明文、密文公鑰算法的條件：產(chǎn)生一對密鑰是計算可行的已知公鑰和明文，產(chǎn)生密文是計算可行的接收方利用私鑰來解密密文是計算可行的對于攻擊者，利用公鑰來推斷私鑰是計算不可行的已知公鑰和密文，恢復(fù)明文是計算不可行的(可選)加密和解密的順序可交換基本思想和要求設(shè)計公鑰算法的關(guān)鍵陷門單向函數(shù)一函數(shù)f:(AB)若滿足下列二條件，則f稱為單向函數(shù)：對所有xA，易于計算f(x)。對“幾乎所有xA”由f(x)求x極為困難，以至于實際上不可能做到“易于計算”指函數(shù)值能在其輸入長度的多項式時間內(nèi)求出，即若輸入長度為n，計算函數(shù)的時間是na的倍數(shù)(a為一固定的常數(shù))。若計算函數(shù)時間是an的倍數(shù)，則為不可能做到的。單向函數(shù)(One-way)2023/5/14152單向函數(shù)求逆困難，陷門單向函數(shù)求逆容易(Trapdoorone-wayfunction)在不知陷門信息下求逆困難的函數(shù)，當知道陷門信息后，求逆是易于實現(xiàn)的。單向陷門函數(shù)滿足：y=fk(x)易于計算——加密；x=fk-1(y)計算不可行——破譯；存在k’且已知，x=fk’-1(y)易于計算——解密。陷門單向函數(shù)RSA算法154MIT三位年青數(shù)學家R.L.Rivest，A.Shamir和L.Adleman等[1978,1979]發(fā)明。需求：兩個算法：加密，解密兩個密鑰：公鑰，私鑰基本思想：x公鑰，y私鑰，且xy=1（逆元）加密形如：mx=c解密：cy=(mx)y=mxy=m問題：xy=1，x=1/y，即x、y可相互推導(dǎo)RSA的提出2023/5/14155溫故而知新——公開密碼體制Copyright?電子科技大學計算機學院156每個用戶擁有（產(chǎn)生）一對密鑰加密密鑰Ku——公開，公鑰解密密鑰Kr——保密，私鑰公私鑰相互決定，但不能相互推導(dǎo)加解密算法公開加密：Eku(m)=c解密：Dkr(c)=m兩個密鑰中任何一個都可以用作加密，而另一個用作解密溫故而知新——用公開密鑰實現(xiàn)保密和鑒別EKUb(DKRa(m))=zEKUb(DKRb(z))=m尋找一種運算，使得x、y互為逆元，但從x推導(dǎo)y困難冪運算+模運算，利用數(shù)論中大整數(shù)分解的困難性。加密：mx%n=c解密：cy%n=(mx)y%n=m問題：x·y？？=1，即x，y如何互為逆元RSA的提出2023/5/14158x·y%φ(n)=1單向陷門函數(shù)(Trapdoorone-wayfunction)在不知陷門信息下求逆困難的函數(shù)，當知道陷門信息后，求逆是易于實現(xiàn)的。單向陷門函數(shù)滿足：y=fk(x)易于計算——加密；x=fk-1(y)計算不可行——破譯；存在k’且已知，x=fk’-1(y)易于計算——解密。溫故而知新——陷門單向函數(shù)基本思想：x公鑰，y私鑰，且xy=1（逆元），指數(shù)運算加密：mx=c解密：cy=(mx)y=mxy=m問題：xy=1，x=1/y，即x、y可相互推導(dǎo)尋找一種運算，使得x、y互為逆元，但從x推導(dǎo)y困難模運算，利用數(shù)論中大整數(shù)分解的困難性。加密：mx%n=c解密：cy%n=(mx)y%n=m問題：x·y？？=1，即x，y如何互為逆元溫故而知新——RSA的提出2023/5/14160素數(shù)：只能被1和它本身整除的數(shù)，如2、3、5、……19、23

互素：gcd(a,b)=1，如(15,8)，（6,35)。模n逆元：若a，n互素，a?b%n=1a·b=k·n+1；如3·9%26=1Euclid算法求乘法逆元Euler函數(shù)φ(n)：小于n且與n互素的正整數(shù)的個數(shù)，n>1φ(3)=φ(4)=φ(6)=2，φ(5)=4，φ(7)=6若n是素數(shù)，則φ(n)=n-1若n=p*q，p、q是素數(shù)，則φ(n)=(p-1)*(q-1)例：φ(21)=φ(3*7)=2*6=12數(shù)論知識簡介161模運算（同余）性質(zhì)：自反性、對稱性、傳遞性；a≡a%n；若a≡b%n，則b≡a%n；若a≡b%n，b≡c%n，則a≡c%n若a%n≡b%n，則(a-b)%n≡0；分配律(a+b)%n≡[(a%n)+(b%n)]%n；--；**；例：152%12≡(15%12)*(15%12)=9;數(shù)論知識簡介162Euler定理：若a與n互素，aφ(n)%n=1推論：a.aφ(n)-1%n=1，即a與aφ(n)-1互為%n逆元。a換成m，mφ(n)%n=1，m·mφ(n)%n=m，mφ(n)+1%n=mcy%n=(mx)y%n=mx.y%n=mφ(n)+1%n=mx.y%(n)≡1數(shù)論知識簡介163公鑰（非對稱）密碼算法兩個算法加密算法解密算法一對密鑰公鑰——加密私鑰——解密RSA公鑰密碼算法要素164溫故而知新——公開密碼體制Copyright?電子科技大學計算機學院165每個用戶擁有（產(chǎn)生）一對密鑰加密密鑰Ku——公開，公鑰解密密鑰Kr——保密，私鑰公私鑰相互決定，但不能相互推導(dǎo)加解密算法公開加密：Eku(m)=c解密：Dkr(c)=m兩個密鑰中任何一個都可以用作加密，而另一個用作解密溫故而知新——用公開密鑰實現(xiàn)加密DKRb(c)=mget(KUb)EKUb(m)=c溫故而知新——用公開密鑰實現(xiàn)鑒別（簽名）DKRa(m)=cget(KUa)EKUa(c)=m1.獨立隨機選取兩大素數(shù)p和q(100～200位十進制），保密2.計算模數(shù)n=p×q3.計算歐拉函數(shù)(n)=(p－1)(q－1)，保密并銷毀p和q4.隨機選一整數(shù)e，1e<(n)，gcd((n),e)=1，以n、e為公鑰，公開5.計算出