公鑰密碼體制精講ppt課件

1、1,第6章,非對(duì)稱密碼體制,2,學(xué)習(xí)要點(diǎn)： 了解非對(duì)稱密碼體制的提出背景、基本思想 了解非對(duì)稱密碼體制的基本應(yīng)用方向 了解三種典型的公鑰密碼體制 DH密鑰交換算法 RSA,3,61概述,問(wèn)題的提出： 密鑰管理困難 傳統(tǒng)密鑰管理兩兩分別用一對(duì)密鑰時(shí)，則n 個(gè)用戶需要C( n, 2)= n( n- 1)/ 2 個(gè)密鑰，當(dāng)用戶量增大時(shí)密鑰空間急劇增大。如: n= 100 時(shí)C( 100,2)= 4,995 n= 5000 時(shí)C( 5000,2)= 12,497,500 陌生人間的保密通信問(wèn)題 數(shù)字簽名的問(wèn)題 傳統(tǒng)加密算法無(wú)法實(shí)現(xiàn)抗抵賴的需求,4,5,6.1.1 公鑰密碼體制,公鑰密碼又稱為雙鑰密碼、

2、非對(duì)稱密碼 公鑰密碼體制提出的標(biāo)志性文獻(xiàn)： W.Diffie and M.E.Hellman, New Directions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654,6,7,6.1.2 對(duì)公鑰密碼體制的要求,（1）參與方B容易通過(guò)計(jì)算產(chǎn)生一對(duì)密鑰（公開密鑰KUb和私有密鑰KRb）。 （2）在知道公開密鑰和待加密報(bào)文M的情況下，對(duì)于發(fā)送方A，很容易通過(guò)計(jì)算產(chǎn)生對(duì)應(yīng)的密文：CEKUb（M） （3）接收方B使用私有密鑰容易通過(guò)計(jì)算解密所得的密文以便恢復(fù)原來(lái)的

3、報(bào)文：MDKRb（C）DKRb（EKUb（M）,8,（4）敵對(duì)方即使知道公開密鑰KUb，要確定私有密鑰KRb在計(jì)算上是不可行的。 （5）敵對(duì)方即使知道公開密鑰KUb和密文C，要想恢復(fù)原來(lái)的報(bào)文M在計(jì)算上也是不可行的。 （6）加密和解密函數(shù)可以以兩個(gè)次序中的任何一個(gè)來(lái)使用: (這條不是所有公開密鑰體系都適用，如DSA只用于數(shù)字簽名) M = DKRb（EKUb（M） M = EKUb（DKRb （M）,9,6.1.3 單向陷門函數(shù),滿足公鑰密碼體制，要設(shè)計(jì)一單向陷門函數(shù) 單向陷門函數(shù)是滿足下列條件的函數(shù)f： (1)給定x，計(jì)算y=fpk(x)是容易的 (2)給定y, 計(jì)算x使x=f-1sk（y）

4、是困難的 (3)知道密鑰Sk的情況下，反向計(jì)算是容易的 x=f-1sk（y）,注：1 僅滿足(1)、(2)兩條的稱為單向函數(shù)；第(3)條稱為陷門性，Sk稱為陷門信息。 2 當(dāng)用陷門函數(shù)f作為加密函數(shù)時(shí)，可將加密密鑰pk公開。f函數(shù)的設(shè)計(jì)者將Sk保密，用作解密密鑰。由于加密函數(shù)是公開的，任何人都可以將信息X加密成y=fpk(x) ，然后送給函數(shù)的設(shè)計(jì)者（當(dāng)然可以通過(guò)不安全信道傳送）；由于設(shè)計(jì)者擁有Sk，他自然可以解出x=f-1sk（y） 。 3 單向陷門函數(shù)的第(2)條性質(zhì)表明竊聽(tīng)者由截獲的密文y=fpk(x)推測(cè)x是不可行的。,11,12,生活中的例子 將擠出的牙膏弄回管子里比把牙膏擠出來(lái)困難

5、得多； 燃燒一張紙要比使它從灰燼中再生容易得多 把盤子打碎成數(shù)千片碎片很容易，把所有這些碎片再拼成為一個(gè)完整的盤子則很難。,13,數(shù)學(xué)上 (有很多函數(shù)看起來(lái)和感覺(jué)像單向函數(shù)，能夠有效地計(jì)算它們，但我們至今未找到有效的求逆算法。) 將許多大素?cái)?shù)相乘要比將其乘積因式分解容易得多。 我們把離散對(duì)數(shù)函數(shù)、RSA函數(shù)作為單向函數(shù)來(lái)使用，但是，目前還沒(méi)有嚴(yán)格的數(shù)學(xué)證明表明所謂這些單向函數(shù)真正難以求逆，即單向函數(shù)是否存在還是未知的,14,單向函數(shù)不能用作加密。因?yàn)橛脝蜗蚝瘮?shù)加密的信息是無(wú)人能解開它的。但我們可以利用具有陷門信息的單向函數(shù)構(gòu)造公開密鑰密碼。,15,6.1.4 公開密鑰密碼系統(tǒng)的分析方法,強(qiáng)行攻

6、擊(對(duì)密鑰)。 公開密鑰算法本身可能被攻破。 可能報(bào)文攻擊(對(duì)報(bào)文本身的強(qiáng)行攻擊)。,16,6.1.5 公鑰密碼系統(tǒng)的應(yīng)用,加密/解密 數(shù)字簽名 會(huì)話密鑰交換,17,18,19,6-2 Diffie-Hellman密鑰交換算法,Diffie-Hellman密鑰交換算法的有效性依賴于計(jì)算有限域中離散對(duì)數(shù)的困難性。 本原元 離散對(duì)數(shù),20,本原元（原根）,對(duì)于一個(gè)素?cái)?shù)q，如果數(shù)值： ， ，是各不相同的整數(shù)，并且以某種排列方式組成了從1到q-1的所有整數(shù) 則稱整數(shù)a是素?cái)?shù)q的一個(gè)本原元,21,離散對(duì)數(shù),對(duì)于一個(gè)整數(shù)b和素?cái)?shù)q的一個(gè)本原元a， 可以找到一個(gè)唯一的指數(shù)i，使得： b=ai mod q (

7、0 i q-1) 成立，則指數(shù)i稱為b的以a為底數(shù)的模q的離散對(duì)數(shù)。,22,23,一個(gè)素?cái)?shù)q和一個(gè)整數(shù)a（均公開），a是q的一個(gè)原根 用戶A選擇一個(gè)隨機(jī)數(shù)XAq，計(jì)算 用戶B選擇一個(gè)隨機(jī)數(shù)XBq，計(jì)算 每一方都對(duì)X的值保密存放而使得Y的值對(duì)于另一方可以公開得到 用戶A計(jì)算密鑰： 用戶B計(jì)算密鑰： 雙方以K作為加、解密密鑰，以對(duì)稱密鑰算法進(jìn)行保密通信,Diffie-Hellman密鑰交換算法,24,DH例子,素?cái)?shù)q=97,它的一個(gè)本原元a=5 A和B分別選擇隨機(jī)數(shù)Xa=36和Xb=58 A計(jì)算公開密鑰：Ya=536 mod 97=50 mod 97 B計(jì)算公開密鑰：Yb=558 mod 97=4

8、4 mod 97 A計(jì)算會(huì)話密鑰：K= 4436 mod 97=75 mod 97 B計(jì)算會(huì)話密鑰：K= 5058 mod 97=75 mod 97,25,63RSA,由Rivest,Shamir和Adleman在1978年提出來(lái)的 數(shù)學(xué)基礎(chǔ):Euler定理，并建立在大整數(shù)因子分解的困難性之上,26,明文空間P 密文空間C = Zn (剩余類集合) 密鑰的生成 為了產(chǎn)生兩個(gè)密鑰，選取兩個(gè)大素?cái)?shù)，p和q。為了獲得最大程度的安全性，兩數(shù)的長(zhǎng)度一樣。計(jì)算乘積： n = pq,RSA密碼體制描述,27,然后隨機(jī)選取加密密鑰e，使e和(p-1)(q-1)互素。最后用歐幾里德擴(kuò)展算法計(jì)算解密密鑰d，以滿足

9、： ed1 mod (p-1)(q-1) 則 d= e-1 mod ( (p-1)(q-1) ) 注意： e和n是公開的，公鑰KU=e,n p和q不再需要，但不可泄露 私鑰KR=d,n,28,加密 (用e,n) 明文：Mn 密文：C=Me (mod n) 解密 (用d,n) 密文：C 明文：M=Cd (mod n),29,RSA加密/解密,30,算法分析,密鑰生成時(shí)，要求n很大，攻擊者要將其成功的分解為p*q是困難的。(大因子分解困難性) RSA的加密函數(shù) C=Me mod n 是一個(gè)單向函數(shù) 接收方，擁有私鑰，解密容易,證明：M=Cd mod n=(Me mod n)d mod n=M 在e

10、d=1 mod (n) 條件下成立 M = Cd mod n = (Me mod n)d mod n=Med mod n = M1+k (n) mod n = M (M(n)k mod n = M (M(n) mod n) k mod n (根據(jù)歐拉定理注5) = M 1k mod n = M ( Mn),ed=1 mod (n),k為整數(shù) ed-1=k (n) ed=k (n)+1,31,若Bob選擇了p=7和q17 則n=119, (n)=61696253，一個(gè)正整數(shù)e能用作加密指數(shù)，當(dāng)且僅當(dāng)e不能被2，3所整除 假設(shè)Bob選擇e=5，那么用輾轉(zhuǎn)相除法將求得： d=e -1 77(mod

11、96) Bob的解密密鑰d=77,119，公開5,119 現(xiàn)假設(shè)Alice想發(fā)送明文19給Bob,RSA的例子,32,Alice能否直接發(fā)送 1234給Bob?,例2：p=47, q=61, (n)=(47-1)(61-1)=2760時(shí)，SK=167是否為秘密密鑰的候選者？ 用歐氏算法計(jì)算：gcd(2760,167)=1即可證明。,用RSA算法加密與解密的過(guò)程： 例：明文=“RSA ALGORITHM” (1) 明文用數(shù)字表示 空白=00， A=01, B=02, , Z=26 (兩位十進(jìn)制數(shù)表示) 1819 0100 0112 0715 1809 2008 1300 (2) 利用加密變換公式

12、 C=mPK mod r, 即C = 18191223 mod 2867=2756 PK=1223=10011000111 =210+27+26+22+21+20 =1024+128+64+4+2+1 C=18191223 (mod 2867) =18191024 1819128 181964 18194 18192 18191(mod 2867) =2756,2756 2001 0542 0669 2347 0408 1815,35,步驟：Bob為實(shí)現(xiàn)者 Bob尋找出兩個(gè)大素?cái)?shù)p和q Bob計(jì)算出n=pq和 (n)=(p-1)(q-1). Bob選擇一個(gè)隨機(jī)數(shù)e(0e (n)，滿足 （e，

13、(n)）1 Bob使用輾轉(zhuǎn)相除法計(jì)算d=e-1(mod (n) Bob在目錄中公開n和e作為她的公開密鑰,RSA密碼體制描述,36,密碼分析者攻擊RSA體制的關(guān)鍵點(diǎn)在于如何分解n。若分解成功使n=pq，則可以算出 (n)（p-1)(q-1)，然后由公開的e，解出秘密的d。,37,要求：若使RSA安全，p與q必為足夠大的素?cái)?shù)，使分析者沒(méi)有辦法在有效時(shí)間內(nèi)將n分解出來(lái)。建議選擇p和q大約是100位的十進(jìn)制素?cái)?shù)。 模n的長(zhǎng)度要求至少是512比特。,38,為了抵抗現(xiàn)有的整數(shù)分解算法，對(duì)RSA模n的素因子p和q還有如下要求： (1)|p-q|很大，通常 p和q的長(zhǎng)度相同； (2)p-1 和q-1分別含有

14、大素因子p1和q1 (3)gcd(p1-1,q1-1)應(yīng)該很小。 為了提高加密速度，通常取e為特定的小整數(shù)，如EDI國(guó)際標(biāo)準(zhǔn)中規(guī)定 e2161，ISO/IEC9796中甚至允許取e3。這時(shí)加密速度一般比解密速度快10倍以上。,39,40,選擇兩個(gè)大素?cái)?shù)p和q，通常要求每個(gè)均大于10100。 計(jì)算npq和(n)(p1)(q1)。 選擇一與(n)互素的數(shù)、令其為d 。 找到一個(gè)e滿足ed1 (mod (n)。 選好這些參數(shù)后，將明文劃分成塊，使得每個(gè)明文報(bào)文P長(zhǎng)度m滿足0mn。加密P時(shí)，計(jì)算CPe(mod n)，解密C時(shí)計(jì)算PCd(mod n)。由于模運(yùn)算的對(duì)稱性，可以證明， 在確定的范圍內(nèi)，加密

15、和解密函數(shù)是互逆的。 為實(shí)現(xiàn)加密，需要公開(e, n)，為實(shí)現(xiàn)解密需要(d, n)。,RSA算法歸納,41,RSA的速度,硬件實(shí)現(xiàn)時(shí)，RSA比DES慢大約1000倍。 軟件實(shí)現(xiàn)時(shí)， DES 比RSA快大約100倍。 聰明地選擇一個(gè)e值，RSA加密速度將快得多,42,如何計(jì)算ab mod n？ 如何判定一個(gè)給定的整數(shù)是素?cái)?shù)？ 如何找到足夠大的素?cái)?shù)p和q ?,問(wèn)題,43,要點(diǎn)1： (a b) mod n = (a mod n) (b mod n) mod n 執(zhí)行乘法操作之前先用模的方法降階,要點(diǎn)2：m的二進(jìn)制表示為bkbk-1b0, 則,計(jì)算am mod n,am mod n = a(2i) m

16、od n = a(2i) mod n,bi0,bi0,如何計(jì)算ab mod n？,44,快速取模指數(shù)算法計(jì)算ab mod n,c 0;d 1 for i k downto 0 do c 2c d (d d)mod n if bi=1 then c c+1 d (d a)mod n return d,45,快速取模指數(shù)算法：例子,7 560mod 561=1,a=7,n=561, m=560=(1000110000)2,Miller and Rabin, WITNESS算法 WITNESS(a,n) 判定n 是否為素?cái)?shù)，a是某個(gè)小于n的整數(shù),1. 令bkbk-1b0 為(n-1)的二進(jìn)制表示，

17、2. d 1 3. for i k downto 0 4.do x d 5.d (d d) mod n 6.if d = 1 and x 1 and x n-1 7. then return TRUE 8.if bi = 1 9. then d (d a) mod n 10. if d 1 11. then return TRUE 12. return FALSE,返回值： TRUE: n一定不是素?cái)?shù) FALSE: n可能是素?cái)?shù),應(yīng)用： 隨機(jī)選擇a n, 計(jì)算s次， 如果每次都返回FALSE， 則這時(shí)n是素?cái)?shù)的概率為 (1 - 1/2s),如何判定一個(gè)給定的整數(shù)是素?cái)?shù)？,47,1. 隨機(jī)選一個(gè)

18、奇數(shù)n (偽隨機(jī)數(shù)發(fā)生器) 2. 隨機(jī)選擇一個(gè)整數(shù)a n 3. 執(zhí)行概率素?cái)?shù)判定測(cè)試,如果n 未測(cè)試通過(guò),則 拒絕數(shù)值n, 轉(zhuǎn)向步驟1 4. 如果n已通過(guò)足夠的測(cè)試, 則接受n, 否則轉(zhuǎn)向步驟2; 說(shuō)明： 隨機(jī)選取大約用 ln(N)/2的次數(shù)，如ln(2200)/2=70 好在生成密鑰對(duì)時(shí)才用到，慢一點(diǎn)還可忍受。 確定素?cái)?shù)p和q以后，只需選取e, 滿足gcd(e,(n)=1, 計(jì)算d = e-1 mod (n) （擴(kuò)展的歐拉算法）,如何找到足夠大的素?cái)?shù)p和q ?,48,p和q在長(zhǎng)度上應(yīng)僅差幾個(gè)數(shù)位，即p和q應(yīng)是1075 到10100 （p-1）和（q-1）都應(yīng)包含一個(gè)較大的素?cái)?shù)因子 gcd(p

19、-1, q-1)應(yīng)比較小 如果en 且 dn1/4,則d可以很容易確定,建議 ,49,DES和RSA性能比較（同等強(qiáng)度）,50,RSA的數(shù)字簽名應(yīng)用將在第八章介紹！,51,52,53,54,55,64橢圓曲線密碼體制ECC,橢圓曲線密碼體制以高效性著稱 由Neal Koblitz和Victor Miller在1985年分別提出 ECC的安全性基于橢圓曲線離散對(duì)數(shù)問(wèn)題的難解性 密鑰長(zhǎng)度大大地減小 是目前已知公鑰密碼體制中每位提供加密強(qiáng)度最高的一種體制,56,ECC和RSA性能比較,57,橢圓曲線的概念和分類,定義：橢圓曲線是一個(gè)具有兩個(gè)變?cè)獂和y的三次方程，它是滿足： Y2+aXY+bY=X3+

20、cX2+dX+e 的所有點(diǎn)(X,Y)的集合，外加一個(gè)零點(diǎn)或無(wú)窮遠(yuǎn)點(diǎn)O,58,1、實(shí)數(shù)域上的橢圓曲線,實(shí)數(shù)域上的橢圓曲線是對(duì)于固定的a、b值，滿足形如方程： Y2=X3+aX+b 的所有點(diǎn)的集合，外加一個(gè)零點(diǎn)或無(wú)窮遠(yuǎn)點(diǎn) 其中a、b是實(shí)數(shù)，X和Y在實(shí)數(shù)域上取值,59,2、有限域GF(p)上的橢圓曲線,GF(p)域上的橢圓曲線是對(duì)于固定的a、b值，滿足形如方程： Y2=X3+aX+b mod(p) 的所有點(diǎn)的集合，外加一個(gè)零點(diǎn)或無(wú)窮遠(yuǎn)點(diǎn) 其中a、b，X和Y在GF(p)域上取值,60,Hasse定理,如果E是定義在GF(p)域上的橢圓曲線，N是E上的點(diǎn)的個(gè)數(shù)，則：,61,例子,62,3、有限域GF(2

21、m)上的橢圓曲線,是對(duì)于固定的a、b值，滿足形如方程： Y2+XY=X3+aX2+b 的所有點(diǎn)的集合，外加一個(gè)零點(diǎn)或無(wú)窮遠(yuǎn)點(diǎn) 其中a、b，X和Y在GF(2m)域上取值 GF(2m)域上的元素是m位的串,63,例子,由多項(xiàng)式 定義的域GF（24） 基元為g=(0010)，g的各冪分別是,64,例子（續(xù)）,考慮橢圓曲線： 點(diǎn)(g5, g3)滿足該方程 (g3)2 + g5 g3 = (g5) 3 + g4 (g5) 2 + 1 g6 + g8 = g15 +g14 + 1 (1100) + (0101) = (0001) + (1001) + (0001) (1001) = (1001),65,滿足該方程的點(diǎn)集,66,橢圓曲線的加法規(guī)則,Abel群 ： 加法規(guī)則1： 加法規(guī)則2： 加法規(guī)則3：互逆點(diǎn) 加法規(guī)則4：加法交換律 加法規(guī)則5：加