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

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

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

Copyright?電子科技大學(xué)計(jì)算機(jī)學(xué)院9信源密鑰源加密器E解密器D明文P密鑰K密文C明文P密碼分析員公開(kāi)信道秘密信道信宿

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

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

密碼學(xué)本質(zhì)11

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

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

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

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

orPermutation）明文內(nèi)容元素的相對(duì)位置改變，內(nèi)容的表示形式不變實(shí)現(xiàn)方式：手工或機(jī)械變換。典型加密技術(shù)29溫故而知新——密碼算法分類2023/5/14密碼算法基于密鑰保密性基于算法保密性基于保密的內(nèi)容對(duì)稱密碼算法非對(duì)稱密碼算法分組密碼算法流密碼算法明文處理方法caesar仿射棋盤單表多表代換技術(shù)31又叫循環(huán)移位密碼字母表收尾相連將明文字母替代為右（后）邊第k個(gè)字母加密：E(a)=(a+k)modn（%n）a：明文字母序號(hào)，k：密鑰，n：字符集中字母?jìng)€(gè)數(shù)(26)。解密：D(a)=(a-k)%nCaesar密碼Copyright?電子科技大學(xué)計(jì)算機(jī)學(xué)院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密碼實(shí)例33凱撒加密法(CaesarCipher)

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

(Brute-forceCryptanalysis)25種的可能，逐一測(cè)試測(cè)試出來(lái)是明文，一看便知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模運(yùn)算性質(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ù)的個(gè)數(shù)，φ(26)=12k2：26密鑰空間：12×26=312仿射密碼38密碼猜測(cè)caesar，k=1，2……25仿射，k1，k2（312）加法和乘法結(jié)合密碼破譯39發(fā)展歷程古代古典近代典型加密技術(shù)代換（代替Substitution）置換（換位Transposition

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

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

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

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

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

在POS、ATM、磁卡及智能卡（IC卡）、加油站、高速公路收費(fèi)站等領(lǐng)域被廣泛應(yīng)用如信用卡持卡人PIN的加密傳輸IC卡與POS間的雙向認(rèn)證DES(DataEncryptionStandard)算法Copyright?電子科技大學(xué)計(jì)算機(jī)學(xué)院84采用n個(gè)函數(shù)f1,f2,…,fn的復(fù)合c=f1(f2(…fn(m)))交替使用代換和置換，通過(guò)混亂（confusion）和擴(kuò)散（diffusion），破壞對(duì)密碼系統(tǒng)進(jìn)行的各種統(tǒng)計(jì)分析典型的迭代密碼：一個(gè)輪函數(shù)一個(gè)密鑰編排方案特殊的迭代密碼：代換-置換網(wǎng)絡(luò)，輪函數(shù)包括三個(gè)變換：代換、置換、密鑰混合溫故而知新—常見(jiàn)乘積密碼—迭代密碼8586溫故而知新——迭代密碼明文分組密文分組置換n次迭代代換密鑰密鑰編排方案輪函數(shù)f三個(gè)入口參數(shù)：Key、Data、%e。Key：8byte共64bit，有效56bit；Data：8byte共64bit；%e：加密或解密。DES算法原理Copyright?電子科技大學(xué)計(jì)算機(jī)學(xué)院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個(gè)6位比特串S-BoxSubstitution壓縮代換（6bits->4bits）97擴(kuò)展置換ER(32bit)321234545678989101112131213141516171617181920212021222324252425262728292829303132148bit98擴(kuò)展置換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ù)加密標(biāo)準(zhǔn)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ù)加密標(biāo)準(zhǔn)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行列坐標(biāo)104HowanS-Boxworks數(shù)據(jù)加密標(biāo)準(zhǔn)012345678910111213141501441312151183106125907101574142131106121195382411481362111512973105031512824917511314100613S1101100

1020010輸入6位輸出4位DES最敏感部分，原理至今未公開(kāi)。人們擔(dān)心隱藏陷門，但并沒(méi)找到弱點(diǎn)。美國(guó)國(guó)家安全局透露了幾條設(shè)計(jì)準(zhǔn)則：1.不是輸入的線性仿射函數(shù)。2.改變1位輸入，輸出至少改變2位。最大程度上增大了擴(kuò)散量。3.任意一位輸出保持不變時(shí)，0和1個(gè)數(shù)之差極小。即如果保持一位不變而改變其它五位，那么其輸出0和1的個(gè)數(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個(gè)子密鑰的生成算法循環(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ù)加密標(biāo)準(zhǔn)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的加密過(guò)程完全類似將16輪子密鑰序列K1，K2……K16的順序倒過(guò)來(lái)。即第一輪用第16個(gè)子密鑰K16，第二輪用K15，其余類推。DES解密算法115強(qiáng)力攻擊：255次嘗試差分密碼分析法（Shamir）：247次嘗試線性密碼分析法：243次嘗試DES算法存在的問(wèn)題與挑戰(zhàn)116數(shù)據(jù)加密標(biāo)準(zhǔn)117溫故而知新——DES完整一輪迭代1997年DES抗攻擊的統(tǒng)計(jì)分析結(jié)果DES算法安全性118數(shù)據(jù)加密標(biāo)準(zhǔn)個(gè)人攻擊小組攻擊院校網(wǎng)絡(luò)攻擊大公司軍事情報(bào)機(jī)構(gòu)40（bits）數(shù)周數(shù)日數(shù)小時(shí)數(shù)毫秒數(shù)微秒56數(shù)百年數(shù)十年數(shù)年數(shù)小時(shí)數(shù)秒鐘64數(shù)千年數(shù)百年數(shù)十年數(shù)日數(shù)分鐘80不可能不可能不可能數(shù)百年數(shù)百年128不可能不可能不可能不可能數(shù)千年119上表攻擊者的計(jì)算資源及攻擊能力數(shù)據(jù)加密標(biāo)準(zhǔn)上表中攻擊者配有如下計(jì)算機(jī)資源的攻擊能力

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

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

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

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

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

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

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

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

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

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

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

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

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

涉及到各方：發(fā)送方、接收方、攻擊者涉及到數(shù)據(jù)：公鑰、私鑰、明文、密文公鑰算法的條件：產(chǎn)生一對(duì)密鑰是計(jì)算可行的已知公鑰和明文，產(chǎn)生密文是計(jì)算可行的接收方利用私鑰來(lái)解密密文是計(jì)算可行的對(duì)于攻擊者，利用公鑰來(lái)推斷私鑰是計(jì)算不可行的已知公鑰和密文，恢復(fù)明文是計(jì)算不可行的(可選)加密和解密的順序可交換基本思想和要求設(shè)計(jì)公鑰算法的關(guān)鍵陷門單向函數(shù)一函數(shù)f:(AB)若滿足下列二條件，則f稱為單向函數(shù)：對(duì)所有xA，易于計(jì)算f(x)。對(duì)“幾乎所有xA”由f(x)求x極為困難，以至于實(shí)際上不可能做到“易于計(jì)算”指函數(shù)值能在其輸入長(zhǎng)度的多項(xiàng)式時(shí)間內(nèi)求出，即若輸入長(zhǎng)度為n，計(jì)算函數(shù)的時(shí)間是na的倍數(shù)(a為一固定的常數(shù))。若計(jì)算函數(shù)時(shí)間是an的倍數(shù)，則為不可能做到的。單向函數(shù)(One-way)2023/5/14152單向函數(shù)求逆困難，陷門單向函數(shù)求逆容易(Trapdoorone-wayfunction)在不知陷門信息下求逆困難的函數(shù)，當(dāng)知道陷門信息后，求逆是易于實(shí)現(xiàn)的。單向陷門函數(shù)滿足：y=fk(x)易于計(jì)算——加密；x=fk-1(y)計(jì)算不可行——破譯；存在k’且已知，x=fk’-1(y)易于計(jì)算——解密。陷門單向函數(shù)RSA算法154MIT三位年青數(shù)學(xué)家R.L.Rivest，A.Shamir和L.Adleman等[1978,1979]發(fā)明。需求：兩個(gè)算法：加密，解密兩個(gè)密鑰：公鑰，私鑰基本思想：x公鑰，y私鑰，且xy=1（逆元）加密形如：mx=c解密：cy=(mx)y=mxy=m問(wèn)題：xy=1，x=1/y，即x、y可相互推導(dǎo)RSA的提出2023/5/14155溫故而知新——公開(kāi)密碼體制Copyright?電子科技大學(xué)計(jì)算機(jī)學(xué)院156每個(gè)用戶擁有（產(chǎn)生）一對(duì)密鑰加密密鑰Ku——公開(kāi)，公鑰解密密鑰Kr——保密，私鑰公私鑰相互決定，但不能相互推導(dǎo)加解密算法公開(kāi)加密：Eku(m)=c解密：Dkr(c)=m兩個(gè)密鑰中任何一個(gè)都可以用作加密，而另一個(gè)用作解密溫故而知新——用公開(kāi)密鑰實(shí)現(xiàn)保密和鑒別EKUb(DKRa(m))=zEKUb(DKRb(z))=m尋找一種運(yùn)算，使得x、y互為逆元，但從x推導(dǎo)y困難冪運(yùn)算+模運(yùn)算，利用數(shù)論中大整數(shù)分解的困難性。加密：mx%n=c解密：cy%n=(mx)y%n=m問(wèn)題：x·y？？=1，即x，y如何互為逆元RSA的提出2023/5/14158x·y%φ(n)=1單向陷門函數(shù)(Trapdoorone-wayfunction)在不知陷門信息下求逆困難的函數(shù)，當(dāng)知道陷門信息后，求逆是易于實(shí)現(xiàn)的。單向陷門函數(shù)滿足：y=fk(x)易于計(jì)算——加密；x=fk-1(y)計(jì)算不可行——破譯；存在k’且已知，x=fk’-1(y)易于計(jì)算——解密。溫故而知新——陷門單向函數(shù)基本思想：x公鑰，y私鑰，且xy=1（逆元），指數(shù)運(yùn)算加密：mx=c解密：cy=(mx)y=mxy=m問(wèn)題：xy=1，x=1/y，即x、y可相互推導(dǎo)尋找一種運(yùn)算，使得x、y互為逆元，但從x推導(dǎo)y困難模運(yùn)算，利用數(shù)論中大整數(shù)分解的困難性。加密：mx%n=c解密：cy%n=(mx)y%n=m問(wèn)題：x·y？？=1，即x，y如何互為逆元溫故而知新——RSA的提出2023/5/14160素?cái)?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ù)的個(gè)數(shù)，n>1φ(3)=φ(4)=φ(6)=2，φ(5)=4，φ(7)=6若n是素?cái)?shù)，則φ(n)=n-1若n=p*q，p、q是素?cái)?shù)，則φ(n)=(p-1)*(q-1)例：φ(21)=φ(3*7)=2*6=12數(shù)論知識(shí)簡(jiǎn)介161模運(yùn)算（同余）性質(zhì)：自反性、對(duì)稱性、傳遞性；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ù)論知識(shí)簡(jiǎn)介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ù)論知識(shí)簡(jiǎn)介163公鑰（非對(duì)稱）密碼算法兩個(gè)算法加密算法解密算法一對(duì)密鑰公鑰——加密私鑰——解密RSA公鑰密碼算法要素164溫故而知新——公開(kāi)密碼體制Copyright?電子科技大學(xué)計(jì)算機(jī)學(xué)院165每個(gè)用戶擁有（產(chǎn)生）一對(duì)密鑰加密密鑰Ku——公開(kāi)，公鑰解密密鑰Kr——保密，私鑰公私鑰相互決定，但不能相互推導(dǎo)加解密算法公開(kāi)加密：Eku(m)=c解密：Dkr(c)=m兩個(gè)密鑰中任何一個(gè)都可以用作加密，而另一個(gè)用作解密溫故而知新——用公開(kāi)密鑰實(shí)現(xiàn)加密DKRb(c)=mget(KUb)EKUb(m)=c溫故而知新——用公開(kāi)密鑰實(shí)現(xiàn)鑒別（簽名）DKRa(m)=cget(KUa)EKUa(c)=m1.獨(dú)立隨機(jī)選取兩大素?cái)?shù)p和q(100～200位十進(jìn)制），保密2.計(jì)算模數(shù)n=p×q3.計(jì)算歐拉函數(shù)(n)=(p－1)(q－1)，保密并銷毀p和q4.隨機(jī)選一整數(shù)e，1e<(n)，gcd((n),e)=1，以n、e為公鑰，公開(kāi)5.計(jì)算出