密碼學(xué)與信息加密課件

第三單元密碼學(xué)與信息加密內(nèi)容提要信息加密的意義介紹密碼學(xué)的歷史及基本概念。介紹加密領(lǐng)域中兩種主流的加密技術(shù)：DES加密（DataEncryptionStandard）RSA加密（Rivest-Shamir-Adleman）并用程序?qū)崿F(xiàn)這兩種加密技術(shù)的算法。最后介紹目前常用的加密工具PGP（PrettyGoodPrivacy），使用PGP產(chǎn)生密鑰，加密文件和郵件。一、信息加密的意義-----為什么要加密（1）

信息傳遞的一般問(wèn)題信源、信道、信宿攻擊的種類(lèi)：中斷（Interruption)（干擾）截?。↖nterception)(偵聽(tīng)）修改（Modification）偽造（Fabrication)角色：通信雙方、可信第三方、不可信第三方介質(zhì)：軟件、硬件、數(shù)據(jù)為什么要加密（2）信息的存儲(chǔ)：在公開(kāi)的地方信息的交換：使用非隱秘介質(zhì)信息的傳輸：通過(guò)不安全信道

獲取消息內(nèi)容被動(dòng)攻擊竊聽(tīng)流量分析破壞完整性中斷破壞可用性主動(dòng)攻擊修改偽造破壞真實(shí)性攻擊類(lèi)型二、密碼學(xué)發(fā)展階段

三個(gè)階段：1949年之前密碼學(xué)是一門(mén)藝術(shù)1949～1975年密碼學(xué)成為科學(xué)1976年以后密碼學(xué)的新方向——公鑰密碼學(xué)第1階段－古典密碼

1949年之前:古典密碼（classicalcryptography)密碼學(xué)還不是科學(xué),而是藝術(shù)出現(xiàn)一些密碼算法和加密設(shè)備密碼算法的基本手段出現(xiàn)，針對(duì)的是字符簡(jiǎn)單的密碼分析手段出現(xiàn)主要特點(diǎn)：數(shù)據(jù)的安全基于算法的保密密碼學(xué)的起源隱寫(xiě)術(shù)(steganography):通過(guò)隱藏消息的存在來(lái)保護(hù)消息.a.隱形墨水b.字符格式的變化c.圖象圖像例1（象形文字的修改）ModifiedHieroglyphics,c.1900B.C.密碼學(xué)的第一個(gè)例子是對(duì)標(biāo)準(zhǔn)書(shū)寫(xiě)符號(hào)的修改例如:古埃及法老墳?zāi)股系奈淖?。思?代替(substitution)左方是密文，右方是相應(yīng)的明文第2階段1949~1975

1949～1975年:計(jì)算機(jī)使得基于復(fù)雜計(jì)算的密碼成為可能相關(guān)技術(shù)的發(fā)展1949年Shannon的“TheCommunicationTheoryofSecretSystems”1967年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主要特點(diǎn)：數(shù)據(jù)的安全基于密鑰而不是算法的保密

第3階段1976~不對(duì)稱(chēng)密鑰的發(fā)展1976年Diffie&Hellman的“NewDirectionsinCryptography”提出了不對(duì)稱(chēng)密鑰密碼1977年Rivest,Shamir&Adleman提出了RSA公鑰算法90年代逐步出現(xiàn)橢圓曲線(xiàn)等其他公鑰算法公鑰密碼使得發(fā)送端和接收端無(wú)密鑰傳輸?shù)谋Ｃ芡ㄐ懦蔀榭赡埽〉?階段1976~對(duì)稱(chēng)密鑰密碼算法進(jìn)一步發(fā)展1977年DES正式成為標(biāo)準(zhǔn)80年代出現(xiàn)“過(guò)渡性”的“postDES”算法,如

IDEA,RCx,CAST等90年代對(duì)稱(chēng)密鑰密碼進(jìn)一步成熟Rijndael,RC6,MARS,Twofish,Serpent等出現(xiàn)2001年Rijndael成為DES的替代者12

三、密碼學(xué)的基本概念（1）密碼學(xué)基本模型發(fā)送方接收方EncryptionDecryption加密：c=

EK

(m)解密：m=

DK

(c)不安全信道密碼分析（Cryptanalysis）plaintextciphertextplaintextKeyKey密碼學(xué)概述密碼學(xué)是一門(mén)古老而深?yuàn)W的學(xué)科，對(duì)一般人來(lái)說(shuō)是非常陌生的。長(zhǎng)期以來(lái)，只在很小的范圍內(nèi)使用，如軍事、外交、情報(bào)等部門(mén)。計(jì)算機(jī)密碼學(xué)是研究計(jì)算機(jī)信息加密、解密及其變換的科學(xué)，是數(shù)學(xué)和計(jì)算機(jī)的交叉學(xué)科，也是一門(mén)新興的學(xué)科。隨著計(jì)算機(jī)網(wǎng)絡(luò)和計(jì)算機(jī)通訊技術(shù)的發(fā)展，計(jì)算機(jī)密碼學(xué)得到前所未有的重視并迅速普及和發(fā)展起來(lái)。在國(guó)外，它已成為計(jì)算機(jī)安全主要的研究方向。密碼學(xué)的基本概念（2）密碼學(xué)(Cryptology)：是研究信息系統(tǒng)安全保密的科學(xué)。

密碼編碼學(xué)(Cryptography)：主要研究對(duì)信息進(jìn)行編碼，實(shí)現(xiàn)對(duì)信息的隱蔽。

密碼分析學(xué)(Cryptanalytics)：主要研究加密消息的破譯或消息的偽造。

應(yīng)該說(shuō)：密碼學(xué)=密碼編碼學(xué)+密碼分析學(xué)密碼學(xué)的基本概念（3）基本術(shù)語(yǔ)明文(plaintext)，密文(ciphertext)加密(encrypt),解密(decrypt,decryption)密碼算法（Algorithm），密碼（Cipher）:用來(lái)加密和解密的數(shù)學(xué)函數(shù)

c=E(m),m=D(c),D(E(m))=m密鑰（Key）:算法中的一個(gè)變量

c=EKe(m),m=DKd(c),DKd(EKe(m))=m鑒別、完整性和抗抵賴(lài)性除了提供機(jī)密性外，密碼學(xué)需要提供三方面的功能：鑒別、完整性和抗抵賴(lài)性。這些功能是通過(guò)計(jì)算機(jī)進(jìn)行社會(huì)交流，至關(guān)重要的需求。鑒別：消息的接收者應(yīng)該能夠確認(rèn)消息的來(lái)源；入侵者不可能偽裝成他人。完整性：消息的接收者應(yīng)該能夠驗(yàn)證在傳送過(guò)程中消息沒(méi)有被修改；入侵者不可能用假消息代替合法消息。抗抵賴(lài)性：發(fā)送消息者事后不可能虛假地否認(rèn)他發(fā)送的消息。算法和密鑰現(xiàn)代密碼學(xué)用密鑰解決了這個(gè)問(wèn)題，密鑰用K表示。K可以是很多數(shù)值里的任意值，密鑰K的可能值的范圍叫做密鑰空間。加密和解密運(yùn)算都使用這個(gè)密鑰，即運(yùn)算都依賴(lài)于密鑰，并用K作為下標(biāo)表示，加解密函數(shù)表達(dá)為：EK（M）=CDK（C）=MDK（EK（M））=M，如圖8-2所示。有些算法使用不同的加密密鑰和解密密鑰，也就是說(shuō)加密密鑰K1與相應(yīng)的解密密鑰K2不同，在這種情況下，加密和解密的函數(shù)表達(dá)式為：EK1（M）=CDK2（C）=M函數(shù)必須具有的特性是，DK2（EK1（M））=M，如圖8-3所示。對(duì)稱(chēng)算法基于密鑰的算法通常有兩類(lèi)：對(duì)稱(chēng)算法和公開(kāi)密鑰算法（非對(duì)稱(chēng)算法）。對(duì)稱(chēng)算法有時(shí)又叫傳統(tǒng)密碼算法，加密密鑰能夠從解密密鑰中推算出來(lái)，反過(guò)來(lái)也成立。在大多數(shù)對(duì)稱(chēng)算法中，加解密的密鑰是相同的。對(duì)稱(chēng)算法要求發(fā)送者和接收者在安全通信之前，協(xié)商一個(gè)密鑰。對(duì)稱(chēng)算法的安全性依賴(lài)于密鑰，泄漏密鑰就意味著任何人都能對(duì)消息進(jìn)行加解密。對(duì)稱(chēng)算法的加密和解密表示為：EK（M）=CDK（C）=M公開(kāi)密鑰算法公開(kāi)密鑰算法（非對(duì)稱(chēng)算法）的加密的密鑰和解密的密鑰不同，而且解密密鑰不能根據(jù)加密密鑰計(jì)算出來(lái)，或者至少在可以計(jì)算的時(shí)間內(nèi)不能計(jì)算出來(lái)。之所以叫做公開(kāi)密鑰算法，是因?yàn)榧用苊荑€能夠公開(kāi)，即陌生者能用加密密鑰加密信息，但只有用相應(yīng)的解密密鑰才能解密信息。加密密鑰叫做公開(kāi)密鑰（簡(jiǎn)稱(chēng)公鑰），解密密鑰叫做私人密鑰（簡(jiǎn)稱(chēng)私鑰）。公開(kāi)密鑰K1加密表示為：EK1（M）=C。公開(kāi)密鑰和私人密鑰是不同的，用相應(yīng)的私人密鑰K2解密可表示為：DK2（C）=M。DES對(duì)稱(chēng)加密技術(shù)DES(DataEncryptionStandard)算法，于1977年得到美國(guó)政府的正式許可，是一種用56位密鑰來(lái)加密64位數(shù)據(jù)的方法。DES算法的歷史美國(guó)國(guó)家標(biāo)準(zhǔn)局1973年開(kāi)始研究除國(guó)防部外的其它部門(mén)的計(jì)算機(jī)系統(tǒng)的數(shù)據(jù)加密標(biāo)準(zhǔn)，于1973年5月15日和1974年8月27日先后兩次向公眾發(fā)出了征求加密算法的公告。加密算法要達(dá)到的目的有四點(diǎn)。提供高質(zhì)量的數(shù)據(jù)保護(hù)，防止數(shù)據(jù)未經(jīng)授權(quán)的泄露和未被察覺(jué)的修改；具有相當(dāng)高的復(fù)雜性，使得破譯的開(kāi)銷(xiāo)超過(guò)可能獲得的利益，同時(shí)又要便于理解和掌握；DES密碼體制的安全性應(yīng)該不依賴(lài)于算法的保密，其安全性?xún)H以加密密鑰的保密為基礎(chǔ)；實(shí)現(xiàn)經(jīng)濟(jì)，運(yùn)行有效，并且適用于多種完全不同的應(yīng)用。DES算法的安全性DES算法正式公開(kāi)發(fā)表以后，引起了一場(chǎng)激烈的爭(zhēng)論。1977年Diffie和Hellman提出了制造一個(gè)每秒能測(cè)試106個(gè)密鑰的大規(guī)模芯片，這種芯片的機(jī)器大約一天就可以搜索DES算法的整個(gè)密鑰空間，制造這樣的機(jī)器需要兩千萬(wàn)美元。1993年R.Session和M.Wiener給出了一個(gè)非常詳細(xì)的密鑰搜索機(jī)器的設(shè)計(jì)方案，它基于并行的密鑰搜索芯片，此芯片每秒測(cè)試5×107個(gè)密鑰，當(dāng)時(shí)這種芯片的造價(jià)是10.5美元，5760個(gè)這樣的芯片組成的系統(tǒng)需要10萬(wàn)美元，這一系統(tǒng)平均1.5天即可找到密鑰，如果利用10個(gè)這樣的系統(tǒng)，費(fèi)用是100萬(wàn)美元，但搜索時(shí)間可以降到2.5小時(shí)?？梢?jiàn)這種機(jī)制是不安全的。

DES算法的安全性1997年1月28日，美國(guó)的RSA數(shù)據(jù)安全公司在互聯(lián)網(wǎng)上開(kāi)展了一項(xiàng)名為“密鑰挑戰(zhàn)”的競(jìng)賽，懸賞一萬(wàn)美元，破解一段用56比特密鑰加密的DES密文。計(jì)劃公布后引起了網(wǎng)絡(luò)用戶(hù)的強(qiáng)力響應(yīng)。一位名叫Rocke

Verser的程序員設(shè)計(jì)了一個(gè)可以通過(guò)互聯(lián)網(wǎng)分段運(yùn)行的密鑰窮舉搜索程序，組織實(shí)施了一個(gè)稱(chēng)為DESHALL的搜索行動(dòng)，成千上萬(wàn)的志愿者加入到計(jì)劃中，在計(jì)劃實(shí)施的第96天，即挑戰(zhàn)賽計(jì)劃公布的第140天，1997年6月17日晚上10點(diǎn)39分，美國(guó)鹽湖城Inetz公司的職員MichaelSanders成功地找到了密鑰，在計(jì)算機(jī)上顯示了明文：“Theunknownmessageis:Strongcryptographymakestheworldasaferplace”。DES算法的原理DES算法的入口參數(shù)有三個(gè)：Key、Data、Mode。其中Key為8個(gè)字節(jié)共64位，是DES算法的工作密鑰；Data也為8個(gè)字節(jié)64位，是要被加密或被解密的數(shù)據(jù)；Mode為DES的工作方式有兩種：加密或解密。DES算法是這樣工作的：如Mode為加密，則用Key去把數(shù)據(jù)Data進(jìn)行加密，生成Data的密碼形式（64位）作為DES的輸出結(jié)果；如Mode為解密，則用Key去把密碼形式的數(shù)據(jù)Data解密，還原為Data的明碼形式（64位）作為DES的輸出結(jié)果。DES算法的實(shí)現(xiàn)步驟DES算法實(shí)現(xiàn)加密需要三個(gè)步驟：第一步：變換明文。對(duì)給定的64位比特的明文x，首先通過(guò)一個(gè)置換IP表來(lái)重新排列x，從而構(gòu)造出64位比特的x0，x0=IP(x)=L0R0，其中L0表示x0的前32比特，R0表示x0的后32位。第二步：按照規(guī)則迭代。規(guī)則為L(zhǎng)i=Ri-1Ri=Li⊕f(Ri-1,Ki)（i=1,2,3…16）經(jīng)過(guò)第一步變換已經(jīng)得到L0和R0的值，其中符號(hào)⊕表示的數(shù)學(xué)運(yùn)算是異或，f表示一種置換，由S盒置換構(gòu)成，Ki是一些由密鑰編排函數(shù)產(chǎn)生的比特塊。f和Ki將在后面介紹。第三步：對(duì)L16R16利用IP-1作逆置換，就得到了密文y。加密過(guò)程如圖8-4所示。從圖中可以看出，DES加密需要四個(gè)關(guān)鍵點(diǎn)：1、IP置換表和IP-1逆置換表。2、函數(shù)f。3、子密鑰Ki。4、S盒的工作原理。（1）IP置換表和IP-1逆置換表輸入的64位數(shù)據(jù)按置換IP表進(jìn)行重新組合，并把輸出分為L(zhǎng)0、R0兩部分，每部分各長(zhǎng)32位，其置換IP表如表8-1所示。58501234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157將輸入64位比特的第58位換到第一位，第50位換到第二位，依此類(lèi)推，最后一位是原來(lái)的第7位。L0、R0則是換位輸出后的兩部分，L0是輸出的左32位，R0是右32位。比如：置換前的輸入值為D1D2D3…D64，則經(jīng)過(guò)初始置換后的結(jié)果為：L0=D58D50...D8，R0=D57D49...D7。經(jīng)過(guò)16次迭代運(yùn)算后。得到L16、R16，將此作為輸入，進(jìn)行逆置換，即得到密文輸出。逆置換正好是初始置的逆運(yùn)算，例如，第1位經(jīng)過(guò)初始置換后，處于第40位，而通過(guò)逆置換IP-1，又將第40位換回到第1位，其逆置換IP-1規(guī)則表8-2所示。逆置換表IP-140848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725（2）函數(shù)f函數(shù)f有兩個(gè)輸入：32位的Ri-1和48位Ki，f函數(shù)的處理流程如圖8-5所示。E變換的算法是從Ri-1的32位中選取某些位，構(gòu)成48位。即E將32比特?cái)U(kuò)展變換為48位，變換規(guī)則根據(jù)E位選擇表，如表8-3所示。3212345456789891011121312131415161716171819202120212223242524252627282928293031321Ki是由密鑰產(chǎn)生的48位比特串，具體的算法下面介紹。將E的選位結(jié)果與Ki作異或操作，得到一個(gè)48位輸出。分成8組，每組6位，作為8個(gè)S盒的輸入。每個(gè)S盒輸出4位，共32位，S盒的工作原理將在第第四步介紹。S盒的輸出作為P變換的輸入，P的功能是對(duì)輸入進(jìn)行置換，P換位表如表8-4所示。1672021291228171152326518311028241432273919133062211425（3）子密鑰ki假設(shè)密鑰為K，長(zhǎng)度為64位，但是其中第8、16、24、32、40、48、64用作奇偶校驗(yàn)位，實(shí)際上密鑰長(zhǎng)度為56位。K的下標(biāo)i的取值范圍是1到16，用16輪來(lái)構(gòu)造。構(gòu)造過(guò)程如圖8-6所示。首先，對(duì)于給定的密鑰K，應(yīng)用PC1變換進(jìn)行選位，選定后的結(jié)果是56位，設(shè)其前28位為C0，后28位為D0。PC1選位如表8-5所示。57494133251791585042342618102595143352719113605244366355473931231576254463830221466153453729211352820124第一輪：對(duì)C0作左移LS1得到C1，對(duì)D0作左移LS1得到D1，對(duì)C1D1應(yīng)用PC2進(jìn)行選位，得到K1。其中LS1是左移的位數(shù)，如表8-6所示。1122222212222221表8-6中的第一列是LS1，第二列是LS2，以此類(lèi)推。左移的原理是所有二進(jìn)位向左移動(dòng)，原來(lái)最右邊的比特位移動(dòng)到最左邊。其中PC2如表8-7所示。14171124153281562110231912,42681672720132415231374755304051453348444939563453464250362932第二輪：對(duì)C1，D1作左移LS2得到C2和D2，進(jìn)一步對(duì)C2D2應(yīng)用PC2進(jìn)行選位，得到K2。如此繼續(xù)，分別得到K3，K4…K16。（4）S盒的工作原理S盒以6位作為輸入，而以4位作為輸出，現(xiàn)在以S1為例說(shuō)明其過(guò)程。假設(shè)輸入為A=a1a2a3a4a5a6，則a2a3a4a5所代表的數(shù)是0到15之間的一個(gè)數(shù)，記為：k=a2a3a4a5；由a1a6所代表的數(shù)是0到3間的一個(gè)數(shù)，記為h=a1a6。在S1的h行，k列找到一個(gè)數(shù)B，B在0到15之間，它可以用4位二進(jìn)制表示，為B=b1b2b3b4，這就是S1的輸出。DES算法的解密過(guò)程是一樣的，區(qū)別僅僅在于第一次迭代時(shí)用子密鑰K15，第二次K14、最后一次用K0，算法本身并沒(méi)有任何變化。DES的算法是對(duì)稱(chēng)的，既可用于加密又可用于解密。DES算法的應(yīng)用誤區(qū)DES算法具有比較高安全性，到目前為止，除了用窮舉搜索法對(duì)DES算法進(jìn)行攻擊外，還沒(méi)有發(fā)現(xiàn)更有效的辦法。而56位長(zhǎng)的密鑰的窮舉空間為256，這意味著如果一臺(tái)計(jì)算機(jī)的速度是每一秒種檢測(cè)一百萬(wàn)個(gè)密鑰，則它搜索完全部密鑰就需要將近2285年的時(shí)間，可見(jiàn)，這是難以實(shí)現(xiàn)的，當(dāng)然，隨著科學(xué)技術(shù)的發(fā)展，當(dāng)出現(xiàn)超高速計(jì)算機(jī)后，我們可考慮把DES密鑰的長(zhǎng)度再增長(zhǎng)一些，以此來(lái)達(dá)到更高的保密程度。DES算法的程序?qū)崿F(xiàn)根據(jù)DES算法的原理，可以方便的利用C語(yǔ)言實(shí)現(xiàn)其加密和解密算法。程序在VC++6.0環(huán)境下測(cè)試通過(guò)在VC++6.0中新建基于控制臺(tái)的Win32應(yīng)用程序，算法如程序proj8_1.cpp所示。設(shè)置一個(gè)密鑰匙為數(shù)組charkey[8]={1,9,8,0,9,1,7,2}，要加密的字符串?dāng)?shù)組是str[]="Hello"，利用Des_SetKey(key)設(shè)置加密的密鑰，調(diào)用Des_Run(str,str,ENCRYPT)對(duì)輸入的明文進(jìn)行加密，其中第一個(gè)參數(shù)str是輸出的密文，第二個(gè)參數(shù)str是輸入的明文，枚舉值ENCRYPT設(shè)置進(jìn)行加密運(yùn)算。程序執(zhí)行的結(jié)果如圖8-7所示。RSA算法的原理

1976年，Diffie和Hellman在文章“密碼學(xué)新方向（NewDirectioninCryptography）”中首次提出了公開(kāi)密鑰密碼體制的思想，1977年，Rivest、Shamir和Adleman三個(gè)人實(shí)現(xiàn)了公開(kāi)密鑰密碼體制，現(xiàn)在稱(chēng)為RSA公開(kāi)密鑰體制，它是第一個(gè)既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法。這種算法易于理解和操作，算法的名字以發(fā)明者的名字命名：RonRivest，Adi

Shamir和LeonardAdleman。但RSA的安全性一直未能得到理論上的證明。它經(jīng)歷了各種攻擊，至今未被完全攻破。RSA體制RSA體制可以簡(jiǎn)單描述如下：（1）、生成兩個(gè)大素?cái)?shù)p和q。（2）、計(jì)算這兩個(gè)素?cái)?shù)的乘積n=p×q。（3）、計(jì)算小于n并且與n互質(zhì)的整數(shù)的個(gè)數(shù)，即歐拉函數(shù)φ(n)=(p-1)(q-1)。（4）、選擇一個(gè)隨機(jī)數(shù)b滿(mǎn)足1<b<φ(n)，并且b和φ(n)互質(zhì)，即gcd(b,φ(n))=1。（5）、計(jì)算ab=1modφ(n)。（6）、保密a，p和q，公開(kāi)n和b。利用RSA加密時(shí)，明文以分組的方式加密：每一個(gè)分組的比特?cái)?shù)應(yīng)該小于log2n比特。加密明文x時(shí)，利用公鑰(b,n)來(lái)計(jì)算c=xbmodn就可以得到相應(yīng)的密文c。解密的時(shí)候，通過(guò)計(jì)算camodn就可以恢復(fù)出明文x。選取的素?cái)?shù)p和q要足夠大，從而乘積n足夠大，在事先不知道p和q的情況下分解n是計(jì)算上不可行的。常用的公鑰加密算法包括：RSA密碼體制、ElGamal密碼體制和散列函數(shù)密碼體制（MD4、MD5等）。RSA算法的安全性RSA的安全性依賴(lài)于大數(shù)分解，但是否等同于大數(shù)分解一直未能得到理論上的證明，因?yàn)闆](méi)有證明破解RSA就一定需要作大數(shù)分解。假設(shè)存在一種無(wú)須分解大數(shù)的算法，那它肯定可以修改成為大數(shù)分解算法。目前，RS