《第5章(2) 數(shù)據(jù)加密基礎(chǔ)及其主》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《第5章(2) 數(shù)據(jù)加密基礎(chǔ)及其主（48頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、羅森林羅森林北京理工大學(xué)信息科學(xué)技術(shù)學(xué)院電子工程系1密碼學(xué)(cryptography)是研究加密和解密變換的一門(mén)學(xué)科。明文(plaintext)：通常，人們將可懂的文本稱(chēng)為明文。密文(ciphertext,cryptograph):將明文變換成不可懂的形式的文本加密(encipher,encrypt)把明文變換成密文的過(guò)程.解密(decipher,decrypt)把密文變換成明文的過(guò)程數(shù)據(jù)加密的基本概念2密碼體制(ciphersystem):完成加密和解密的算法。通常，數(shù)據(jù)的加密和解密過(guò)程是通過(guò)密碼體制(ciphersystem)+密鑰(keyword)來(lái)控制的。數(shù)據(jù)加密的基本概念(續(xù))加密解
2、密明文明文密文密文密鑰密鑰加密或解密變換3由以上介紹可知，數(shù)據(jù)加密的兩個(gè)環(huán)節(jié)分別是加密算加密算法法(密碼體制)和密鑰密鑰(密鑰管理)密碼體制必須易于使用，特別是應(yīng)當(dāng)可以在微型計(jì)算機(jī)是使用；對(duì)所允許選擇的密鑰，加密和解密變換都有必須迅速有效；密碼體制的安全性依賴(lài)于密鑰的安全性，現(xiàn)代密碼學(xué)不追求加密算法的保密性，而是追求加密算法的完備，即：使攻擊者在不知道密鑰的情況下，沒(méi)有辦法從算法找到突破口。下面介紹密碼體制的基本概念：數(shù)據(jù)加密的基本概念(續(xù))4通常的密碼體制密碼體制采用移位法、代替法和代數(shù)方法來(lái)進(jìn)行加密和解密的變換，可以采用一種或幾種方法結(jié)合的方式作為數(shù)據(jù)變換的基本模式，下面舉例說(shuō)明：移位法也
3、叫置換法。移位法把明文中的字符重新排列，字符本身不變但其位置改變了。例如最簡(jiǎn)單的例子：把文中的字母和字符倒過(guò)來(lái)寫(xiě)。明文：Datasecurityhasebolvedtapidlysince1975密文：5791ECNISYLDIPATDEVLOBESAHYTIRUCESATAD或?qū)⒚芪囊怨潭ㄩL(zhǎng)度來(lái)發(fā)送5791ECNISYLDIPATDEVLOBESAHYTIRUCESATAD*密碼體制(ciphersystem)5代替法是利用對(duì)照的方式，用一個(gè)字符來(lái)對(duì)應(yīng)另一個(gè)字符。例如：按ASCII碼的向后移位一次明文：ABCDEFGHIJKLMNOPQRSTU23232密文：BCDEFGHIJKLMNOPQ
4、RSTUV34343代數(shù)法加密可以對(duì)下列兩種明文表示法進(jìn)行相關(guān)的變換：1、將明文中的字符按指定的變換方法用數(shù)字來(lái)代替，然后對(duì)這些數(shù)字值進(jìn)行一系列可逆的數(shù)學(xué)運(yùn)算，變成密文。2、按照二-十進(jìn)制，把明文字符的二進(jìn)制等效值當(dāng)作一組邏輯和算術(shù)運(yùn)算的輸入，產(chǎn)生的二進(jìn)制結(jié)果再變回到二-十進(jìn)制作為密文。密碼體制(ciphersystem)(續(xù))6通常情況下，一個(gè)密碼體制由以下五個(gè)部分組成：明文信息空間M；密文信息空間C；密鑰空間K；加密變換Ek:MC，其中kK;解密空間DkM,其中kK;密碼體制(ciphersystem)(續(xù))7密碼體制分為私用密鑰加密技術(shù)(對(duì)稱(chēng)加密)和公開(kāi)密鑰加密技術(shù)(非對(duì)稱(chēng)加密)：私用密
5、鑰加密，利用一個(gè)密鑰對(duì)數(shù)據(jù)進(jìn)行加密，對(duì)方接收到數(shù)據(jù)后，需要用同一密鑰來(lái)進(jìn)行解密。這種加密技術(shù)的特點(diǎn)是數(shù)學(xué)運(yùn)算量小，加密速度快，其主要弱點(diǎn)在于密鑰管理困難，而且一旦密鑰泄露則直接影響到信息的安全性。由于用同一密鑰又叫對(duì)稱(chēng)加密公開(kāi)密鑰加密技術(shù)，l976年，Diffie和Hellman首次提非對(duì)稱(chēng)加密出公開(kāi)密鑰加密體制，即密碼體制(ciphersystem)(續(xù))8每個(gè)人都有一對(duì)密鑰，其中一個(gè)為公開(kāi)的，一個(gè)為私有的。發(fā)送信息時(shí)用對(duì)方的公開(kāi)密鑰加密，收信者用自己的私用密鑰進(jìn)行解密。公開(kāi)密鑰加密算法的核心是運(yùn)用一種特殊的數(shù)學(xué)函數(shù)一單向陷門(mén)函數(shù)，即從一個(gè)方向求值是容易的。但其逆向計(jì)算卻很困難，從而在實(shí)際上
6、成為不可行的。公開(kāi)密鑰加密技術(shù)它不僅保證了安全性又易于管理。其不足是加密和解密的時(shí)間長(zhǎng)。鑒兩者各自的優(yōu)缺點(diǎn)，現(xiàn)在有許多密碼系統(tǒng)采用二者融合的方法，組成混合密碼系統(tǒng)。密碼體制(ciphersystem)(續(xù))9RSA加密標(biāo)準(zhǔn)10公開(kāi)密鑰算法是在1976年由當(dāng)時(shí)在美國(guó)斯坦福大學(xué)的迪菲（Diffie）和赫爾曼(Hellman)兩人首先。1976年，W.diffie和M.hellman在發(fā)表的論文NewDirectioninCryptography首次提出了公開(kāi)密鑰密碼體制的概念，其中最關(guān)鍵的思想是尋找一個(gè)“單向函數(shù)”RSA算法介紹單向函數(shù)11RSA算法介紹單向函數(shù)什么叫“單向函數(shù)”呢？X YY=F(
7、m)Y XX=F-1(y)不能實(shí)現(xiàn)不能實(shí)現(xiàn)12三位數(shù)學(xué)家(RonaldRivest,AdiShamir和LenAdleman)提出了第一個(gè)比較完善的公開(kāi)密鑰密碼體制，即著名的RSA體制。它既能用于加密也能用于數(shù)字簽名。RSA算法介紹13RSA算法研制的最初理念與目標(biāo)是旨在解決DES算法秘密密鑰利用公開(kāi)信道傳輸分發(fā)困難的難題。而實(shí)際結(jié)果不但很好地解決了這個(gè)難題；還可利用RSA來(lái)完成對(duì)電文的數(shù)字簽名以對(duì)抗電文的否認(rèn)與抵賴(lài)；同時(shí)還可以利用數(shù)字簽名較容易地發(fā)現(xiàn)攻擊者對(duì)電文的非法篡改，以保護(hù)數(shù)據(jù)信息的完整性。在介紹RSA公鑰加密算法原理這前，介紹一點(diǎn)相關(guān)的數(shù)論的知識(shí)是必需的。RSA算法介紹14基本的數(shù)論
8、知識(shí)定義定義1：設(shè)：設(shè)a,b,m都是整數(shù)。如果都是整數(shù)。如果m|(a-b)，則稱(chēng)，則稱(chēng)a和和b模模 m同余，記為同余，記為m稱(chēng)為同余式的模。稱(chēng)為同余式的模。15RSA公鑰密碼體制的加密變換步驟：1、隨機(jī)地選擇兩個(gè)素?cái)?shù)p和q（保密）；2、計(jì)算r=p*q(公開(kāi))3、計(jì)算保密的歐拉指示函數(shù)(r)=(p-1)*(q-1);4、隨機(jī)選取正整數(shù)e,1e(r)，滿(mǎn)足gcd(e,(r)=1,e是公開(kāi)的加密密鑰。5、用Euclid計(jì)算d,滿(mǎn)足de1(mod(r).d是保密的解密密鑰。6、加密變換：對(duì)明文mZn，密文為c=mc=me e modmodr r7、加密變換：對(duì)明文mZn，密文為m=m=c cd d m
9、odmodr r下面證明加密變換和解密變換是一對(duì)下面證明加密變換和解密變換是一對(duì)互為逆變換互為逆變換：RSA算法原理下一步16在證明解密變換是加密變換的逆變換之前，介紹一下Euler定理和Fermat定理：Euler定理：設(shè)m和r都是正整數(shù)。如果(1).gcd(m,r)=1(2).r=p*q(3).(r)=(p-1)*(q-1),則m(r)1(mod r)返回返回Fermat定理：設(shè)x和p都是正整數(shù)。如果p是素?cái)?shù)并且gcd(x,p)=1，則xp-1 1(mod p).返回返回RSA算法原理17下面來(lái)證明解密變換是加密變換的逆變換。因?yàn)閐e1(mod(r)所以存在整數(shù)t1使得de=t*(r)+1
10、i對(duì)任意明文1mr，當(dāng)gcd(m,r)=1時(shí)，根據(jù)Euler定理，有：RSA算法原理18ii當(dāng)gcd(m,r)1時(shí)，因?yàn)閞=p*q并且p和q都是素?cái)?shù)，所以gcd(m,r)一定為p或者q,不妨設(shè)gcd(m,r)=p，則m一定是p的倍數(shù)，設(shè)m=cp,1cq.因?yàn)閙q-11(modq),(Fermat定理)所以(mq-1)t(p-1)1(modq),即mt*(r)1(modq),于是存在一個(gè)整數(shù)s,使得mt*(r)=1+sq,用m=cp同乘上式的兩端，有mt*(r)+1=m+msq=m+cpsq=m+csr,RSA算法原理19RSA算法原理因此，mt*(r)+1m(modr)綜上所述，對(duì)任意mZn，
11、都有即解密變換和加密變換是互逆變換。證畢！一個(gè)例子20例：設(shè)p=11,q=23,則r=pq=1123=253(r)=(p-1)*(q-1)=1022=220.選取加密密鑰e=3.顯然，gcd(3,220)=1.利用Euclid算法容易求得解密密鑰d=147.容易驗(yàn)證31471(mod220)明文空間Zn=0,1,2,251,252.對(duì)于明文m=165,有密文c=1653mod253=110.對(duì)密文c=110,有明文m=110147mod253=165.RSA算法的一個(gè)實(shí)例返回21RSA算法原理實(shí)際計(jì)算時(shí)運(yùn)算可以采用重復(fù)平方和乘法的快速指數(shù)算法(Fast Exponentiation Algor
12、ithm)即：c=fastexp(m,e,r)m=fastexp(c,d,r)以一個(gè)例子來(lái)說(shuō)明加密和解密的過(guò)程：先介紹一種有效檢驗(yàn)隨機(jī)選擇的d是否與(r)互素，以及對(duì)求同余式的解e，歐幾里得算法提供了一種有效的方法。22RSA算法原理歐幾里得算法(Euclid Alogorithm)：若則則a與與b的的gcd就等于就等于b與與c的的gcd.如：a=38=2*19,b=26=2*13由于19與13互為素?cái)?shù)，所以2是a和b的最大公約數(shù)。由歐幾里得算法可得同樣的結(jié)果：(1).38=26*1+12用26除38商為1，余數(shù)為12(2).26=12*2+2用12除26商為2，余數(shù)為2(3).12=2*6即
13、：38與26的公約數(shù)就是26與12的公約數(shù)，也是12和2的公約數(shù)。23用 歐 幾 里 得 的 算 法，可 以 證 明 當(dāng) p=47,q=61,(r)=2760時(shí)，d=167是秘密密鑰的候選者：2760=167*16+88(a)167=88*1+79(b)88=79*1+9(c)79=9*8+7(d)9=7*1+2(e)7=2*3+1(f)2=1*2(g)由于2和1互素，所以2760與167互素。RSA算法原理24e公開(kāi)密鑰的計(jì)算：1=7-2*3(a)將2=9-7*1(e)式代入(a)中得到1=7-(9-7*1)*3=7*4-9*3(b)將7=79-9*8(d)式代入(b)中得到1=79*4-9
14、*32-9*3=79*4-9*35(c)將9=88-79*1(c)式代入(c)中得到1=79*4-88*35+79*35=79*39-88*35(d)將79=167-88*1(b)式代入(d)中得到1=(167-88*1)*39-88*35=167*39-88*35(e)最后，將88=2760-167*16(a)式代入(e)中得到1=167*39-2760*74+167*16*741=167*1223-2760*34RSA算法原理25根據(jù)得知e=1223是與秘密密鑰d=167對(duì)應(yīng)的公開(kāi)密鑰。RSA算法原理從上面的過(guò)程中可以得到以下數(shù)據(jù)：p=47(選出的)q=61(選出的)r=p*q=47*61
15、=2867(選出的)(r)=(p-1)*(q-1)=46*60=2760(推導(dǎo)的)d=167(選出的)e=1223(推出的)注：用RSA算法加密的信息，首先要將信息分成一連串的數(shù)據(jù)塊，每個(gè)數(shù)據(jù)塊的值不超出r-1，否則就不可能得到唯一的明文表達(dá)式。26例：對(duì)明文“RSAALGRITHM”的加密：首先將明文轉(zhuǎn)換為數(shù)字，例如將明文的每個(gè)英文字母用十進(jìn)制數(shù)字的兩位數(shù)字表示，例如空白=00，A=01，B=02，Z=26。由些得到明文的數(shù)據(jù)塊為：1819010001120715180920081300利用加密變換公式RSA算法加密實(shí)例可以加密第一個(gè)明文數(shù)據(jù)塊1819，將其自乘到e=1223次冪之后，用r=
16、2867去除，取其余數(shù)2756作為密文：類(lèi)似地加密其它明文數(shù)據(jù)塊，得到密文是：2756200105420669234704081815利用解密變換公式，可以將密文恢復(fù)為原來(lái)的明文。27pRSA的安全性依賴(lài)于大數(shù)分解，但是否等同于大數(shù)分解一直未能得到理論上的證明，因?yàn)闆](méi)有證明破解RSA就一定需要作大數(shù)分解。但是，目前攻擊RSA的一些變種算法已被證明等價(jià)于大數(shù)分解。不管怎樣，分解r是最顯然的攻擊方法?，F(xiàn)在，人們已能分解多個(gè)十進(jìn)制位的大素?cái)?shù)。因此，模數(shù)r必須選得大一些，因具體適用情況而定。p當(dāng)然也可以通過(guò)猜測(cè)(p-1)*(q-1)的值來(lái)攻擊RSA。但這種攻擊沒(méi)有分解r容易。p有些攻擊專(zhuān)門(mén)針對(duì)RSA的
17、實(shí)現(xiàn)。他們不攻擊基本的算法，而是攻擊協(xié)議。僅會(huì)使用RSA而不重視它的實(shí)現(xiàn)是不夠的。實(shí)現(xiàn)細(xì)節(jié)也很重要。這就是對(duì)RSA的選擇選擇密文攻密文攻擊擊。RSA在選擇密文攻擊面前很脆弱。一般攻擊者是將某一信息作一下偽裝(Blind)，讓擁有私鑰的實(shí)體簽署。然后，經(jīng)過(guò)計(jì)算就可得到它所想要的信息。RSA算法的安全性分析算法的安全性分析（一）28p還有一種就是對(duì)RSA的公共模數(shù)攻擊。若系統(tǒng)中共有一個(gè)模數(shù)，只是不同的人擁有不同的e和d，系統(tǒng)將是危險(xiǎn)的。最普遍的情況是同一信息用不同的公鑰加密，這些公鑰共模而且互質(zhì)，那末該信息無(wú)需私鑰就可得到恢復(fù)。設(shè)P為信息明文，兩個(gè)加密密鑰為e1和e2，公共模數(shù)是r，則：C1=Pe
18、1modrC2=Pe2modr密碼分析者知道r、e1、e2、C1和C2，就能得到P。p另外，還有其它幾種利用公共模數(shù)攻擊的方法。總之，如果知道給定模數(shù)的一對(duì)e和d，一是有利于攻擊者分解模數(shù)，一是有利于攻擊者計(jì)算出其它成對(duì)的e和d，而無(wú)需分解模數(shù)。解決辦法只有一個(gè)，那就是不要共享模數(shù)r。RSA算法的安全性分析算法的安全性分析（二）29RSA算法是第一個(gè)能同時(shí)用于加密和數(shù)字簽名的算法，也易于理解和操作。RSA是被研究得最廣泛的公鑰算法，從提出到現(xiàn)在已二十多年，經(jīng)歷了各種攻擊的考驗(yàn)，逐漸為人們接受，普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一。RSA的安全性依賴(lài)于大數(shù)的因子分解，但并沒(méi)有從理論上證明破譯RSA
19、的難度與大數(shù)分解難度等價(jià)。即RSA的重大缺陷是無(wú)法從理論上把握它的保密性能如何。總結(jié)30但RSA也有它的缺點(diǎn)，主要有：A)產(chǎn)生密鑰很麻煩，受到素?cái)?shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密。B)分組長(zhǎng)度太大，為保證安全性，r至少也要600bits以上，使運(yùn)算代價(jià)很高，尤其是速度較慢，較對(duì)稱(chēng)密碼算法慢幾個(gè)數(shù)量級(jí)；且隨著大數(shù)分解技術(shù)的發(fā)展，這個(gè)長(zhǎng)度還在增加，不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化?？偨Y(jié)31a)陳魯生,沈世鎰.現(xiàn)代密碼學(xué),北京.科學(xué)出版社,2002b)劉尊全.劉氏高強(qiáng)度公開(kāi)加密算法設(shè)計(jì)原理與裝置.北京:清華大學(xué)出版社,1996c)盧開(kāi)澄，郭寶安等.計(jì)算機(jī)系統(tǒng)安全(TheSecurityofComputer
20、System).重慶:重慶出版社,1999參考資料32DES算法33數(shù)據(jù)加密標(biāo)準(zhǔn)DES1977年美國(guó)國(guó)家標(biāo)準(zhǔn)局公布了IBM公司研制的一種數(shù)據(jù)加密算法:數(shù)據(jù)加密標(biāo)準(zhǔn)(Data Encryption Standard).原定服役十年,由于在這期間，該加密標(biāo)準(zhǔn)沒(méi)有受到真正的威脅，20多年來(lái)一直活躍在國(guó)際保密通信的舞臺(tái)上。近些年，隨著計(jì)算機(jī)技術(shù)的提高，已經(jīng)有了現(xiàn)實(shí)的威脅。512位的密鑰已經(jīng)能被破解，但是要花很多的時(shí)間，計(jì)算量非常大，34數(shù)據(jù)加密標(biāo)準(zhǔn)DES1024位長(zhǎng)度密鑰至今沒(méi)能被破解。DES作為一種高速對(duì)稱(chēng)加密算法，仍然具有重要意義。特別是DES（密鑰系統(tǒng)）和公鑰系統(tǒng)結(jié)合組成混合密碼系統(tǒng)。使DES和
21、公鑰系統(tǒng)（如RSA）能夠各自揚(yáng)長(zhǎng)避短，提高了加密系統(tǒng)的安全和效率。35DES加密算法DES是一種分組密碼：假定明文m是0和1組成的長(zhǎng)度為64bit的符號(hào)串，密鑰也是64bit的0,1符號(hào)串，設(shè)：m=m1m2m3m64k=k1k2k3k4k5k64必須說(shuō)明的是：k只的56bit 有用，k8,k16,k32,k64這位是奇偶校驗(yàn)位，在算法中不起作用。加密過(guò)程可表達(dá)為：DES(m)=IP-1T16T15T2T1IP(m)36DES加密算法下面逐一介紹各個(gè)組成部分的功能IP是初始置換，IP-1它的逆置換mIP M設(shè)m=m1m2m3m64M=M1M2M3M64置換之后有：M1=m58 ,M2=m50,M
22、64=m737DES加密算法現(xiàn)將的下標(biāo)列表如下585042342618102605244362820124IP:62544638302214664564840322416857494133251791595143352719113615345372921135635547393123157數(shù)字代表原m的下標(biāo)。38DES加密算法IP-1滿(mǎn)足IPIP-1IP-1IPIM m若M=M1M2M3M64則m=M40M8M48M25現(xiàn)將IP-1關(guān)于m的下標(biāo)列表于后：IP-139DES加密算法408481656246432397471555236331IP-1:38646145422623037545145
23、3216129364441352206028353431251195927342421150185826331411049175725數(shù)字代表原M的下標(biāo)。40DES加密算法DES的迭代過(guò)程流程圖：IPL0R0fk1L1=R0R1=L0f(Rf(R0 0k k1 1)fk2L2=R1R2=L1 f(R1k2)R16=L15 f(R15k16)L16=R15IPIP-1-141DES加密算法Li-1(32bit)Ri-1(32bit)fLiRiki第i次迭代過(guò)程，如下圖：i=1,2,圖中：Li-1和Ri-1分別第i-1次迭代結(jié)果的左右兩部分，各32bit.Li=Ri-1 Ri=Li-1f(Ri-1
24、,ki)ki是由是由64位密鑰產(chǎn)生的子密鑰。位密鑰產(chǎn)生的子密鑰。ki是是48bit42DES加密算法DES的關(guān)鍵在于f(Ri-1,ki)的功能。的功能。f 是將是將32bit的的輸入轉(zhuǎn)化為輸入轉(zhuǎn)化為32bit的輸出。如下圖：的輸出。如下圖：s1s2s3s4s5s6s7s8ERi-1(32bit)(48bit)ki(48bit)P32bit32bit43DES解密算法DES的解密過(guò)程和DES的加密過(guò)程完全類(lèi)似，只不過(guò)將16圈的子密鑰序列k1，k2，k3，k4，k5，k16 的順序倒過(guò)來(lái)，即第1圈用第16個(gè)子密鑰k16，第2圈用k15，余此類(lèi)推，即DES-1=IP-1T1T2T15T16IP容易驗(yàn)
25、證：DES-1(DES(m)=mDES(DES-1(m)=m44DES解密算法證明：由于：DES-1=IP-1T1T2T15T16IPIP-1IP=I所以：DES-1(DES(m)=IP-1T1T2T15T16(T16T15T2T1IP(m).我們看看T16(T16T15T2T1IP(m)的結(jié)果T16T15T2T1IP(m)表示DES(m)第16圈迭代45DES解密算法后R16 和和L16的結(jié)果。的結(jié)果。R16=L15 f(R15k16)L16=R15DES(m)R16 結(jié)果結(jié)果R16=L15 f(R15k16)L16=R15fLRk16L=R15 R=L15 f(R15,k16)f(R15,k16)=L15DESDES-1-1(DES(DES(mm)的第一次迭代的第一次迭代46DES解密算法同理：L15=R14 R15=L14f(R14,k15)R15L15fL=R14R=L14k15DESDES-1-1(DES(DES(mm)的第二次迭代的第二次迭代依此類(lèi)推DES-1(DES(m)=m得證得證47謝謝48
第5章(2) 數(shù)據(jù)加密基礎(chǔ)及其主
