第8講 公鑰密碼學(xué).ppt

1、1,第8講 公鑰密碼學(xué),2,公鑰密碼學(xué),公鑰密碼學(xué)思想 RSA算法 公鑰的應(yīng)用,3,公鑰密碼學(xué)的發(fā)展是整個(gè)密碼學(xué)發(fā) 展歷史中最偉大的一次革命。,公鑰密碼體制,公鑰算法基于數(shù)學(xué)函數(shù)而不是基于替換和置換,它使用兩個(gè)獨(dú)立的密鑰，在消息的保密性、 密鑰分配和認(rèn)證領(lǐng)域有重要意義。,4,公鑰密碼比傳統(tǒng)密碼更安全,兩個(gè)誤解,公鑰密碼是一種通用的方法，所以 傳統(tǒng)密碼已經(jīng)過(guò)時(shí)。,5,密鑰分配問(wèn)題：如果密鑰被偷，設(shè)計(jì)再好的 密碼體制都沒(méi)有用,傳統(tǒng)密碼中的兩個(gè)問(wèn)題,數(shù)字簽名問(wèn)題：能否設(shè)計(jì)一種方法確保數(shù)字 簽名出自某個(gè)特定的人，并且各方無(wú)異議？,6,1976年 Diffie和Hellman針對(duì)上述問(wèn)題提出 了一種方法

2、，它是密碼學(xué)的一次革命,密碼學(xué)革命,7,公鑰密碼體制介紹,8,僅根據(jù)密碼算法和加密密鑰來(lái)確定解密密鑰在 計(jì)算上是不可行的。,公鑰密碼體制特點(diǎn),兩個(gè)密鑰中的任何一個(gè)可以用來(lái)加密，另一個(gè) 用來(lái)解密。,有6個(gè)組成部分：明文、加密算法、公鑰、 私鑰、密文、解密算法,9,用公鑰進(jìn)行加密,2 Alice產(chǎn)生一對(duì)密鑰，用于加密和解密,3 Alice將一個(gè)密鑰公開(kāi)，另一個(gè)密鑰私有,Bob,Alice,1 Bob要發(fā)送消息給Alice,4 Bob用Alice的公鑰對(duì)消息加密，發(fā)送給Alice。只有Alice能解密,10,公鑰進(jìn)行加密,B的公鑰KUb,B的私鑰KRb,待發(fā)送的明文X,A要發(fā)消息給B,Y=EKUb(

3、X),X=DKRb(Y),破譯者,11,用公鑰進(jìn)行認(rèn)證,Bob,Alice,12,用公鑰進(jìn)行認(rèn)證,A用自己的私鑰進(jìn)行加密Y=EKRa(X),B用A的公鑰鑰進(jìn)行解密認(rèn)證X=DKUa(Y),13,用公鑰進(jìn)行認(rèn)證:問(wèn)題？,問(wèn)題1 需要對(duì)整條消息加密，占用大量存儲(chǔ)空間,解決的方法：僅對(duì)消息的認(rèn)證符加密,問(wèn)題2 不能提供保密性,如何解決？,14,公鑰體制：保密和認(rèn)證,15,公鑰密碼體制的應(yīng)用,1 加密/解密,2 數(shù)字簽名,3 密鑰交換,算法 RSA 橢圓曲線 Diffie-Hellman DSS,是 是 是,是 是 是,否 否 是,否 是 否,16,對(duì)公鑰密碼體制的要求：,1 B產(chǎn)生一對(duì)密鑰（KUb，K

4、Rb）在計(jì)算上是容易的,2 發(fā)送方A加密消息 C=EKUb(M) 在計(jì)算上是容易的,3 接收方B對(duì)密文解密 M=DKRb(C) 在計(jì)算上是容易的,4 攻擊者從KUb計(jì)算出KRb在計(jì)算上不可行的,5 攻擊者從KUb和C計(jì)算出M在計(jì)算上不可行的,6 附加條件（并非所有都滿足）：加密解密順序可 交換： M=EKUb(DKRb(M) ) =DKUb(EKRb(M) ),17,公鑰密碼學(xué)的研究情況,與計(jì)算復(fù)雜性理論密切相關(guān) 計(jì)算復(fù)雜性理論可以提供指導(dǎo) 但是需求不盡相同 計(jì)算復(fù)雜性通常針對(duì)一個(gè)孤立的問(wèn)題進(jìn)行研究 而公鑰密碼學(xué)往往需要考慮一些相關(guān)的問(wèn)題比如，密碼分析還需要考慮已知明文、選擇明文等相關(guān)的情形

5、討論的情形不同 計(jì)算復(fù)雜性考慮最壞的情形 而對(duì)于公鑰密碼學(xué)則是不夠的 一個(gè)困難問(wèn)題必然會(huì)導(dǎo)致一個(gè)保密性很好的密碼系統(tǒng)嗎？ 不一定，還需要有好的構(gòu)造,18,背包(knapsack)問(wèn)題,0-1背包問(wèn)題： 給定一個(gè)正整數(shù)S和一個(gè)背包向量A=(a1,an)，其中ai是正整數(shù)，求滿足方程S = aixi 的二進(jìn)制向量X=(x1,xn)。 這是一個(gè)NP完全問(wèn)題，解決這個(gè)問(wèn)題所需要的時(shí)間與n呈指數(shù)增長(zhǎng) 背包問(wèn)題用于公鑰密碼學(xué) 做法方法：明文為X，S為密文 奧妙在于有兩類(lèi)背包，一類(lèi)可以在線性時(shí)間內(nèi)求解，另一類(lèi)則不能 把易解的背包問(wèn)題修改成難解的背包問(wèn)題 公開(kāi)密鑰使用難解的背包問(wèn)題 私鑰使用易解的背包問(wèn)題,1

6、9,易解的背包問(wèn)題超遞增背包,滿足下列條件的背包 ai aj (j = 1,i-1) 這樣的背包也被稱(chēng)為簡(jiǎn)單背包 求解 從最大的ai開(kāi)始，如果S大于這個(gè)數(shù)，則減去ai, 記xi為1，否則記xi為0 如此下去，直到最小的ai 例如背包序列2, 3, 6, 13, 27, 52 求解70的背包 結(jié)果為2, 3, 13, 52 所以，密文70對(duì)應(yīng)的明文為110101,20,轉(zhuǎn)換背包,簡(jiǎn)單背包用作私鑰 如何產(chǎn)生相應(yīng)的公鑰轉(zhuǎn)換 做法： 選擇一個(gè)整數(shù) m ai (i = 1,n) 然后選擇一個(gè)與m互素的整數(shù)w，然后ai = wai (mod m) (i = 1,n) 這里的ai是偽隨機(jī)分布的 這樣得到的背

7、包是非超遞增背包,21,基于背包問(wèn)題的公鑰密碼系統(tǒng)MH公鑰算法,加密 將明文分為長(zhǎng)度為n的塊X=(x1,xn) 然后用公鑰A = (a1, , an)，將明文變?yōu)槊芪腟S = E(X) = aixi 解密 先計(jì)算S = w-1S mod m 再求解簡(jiǎn)單背包問(wèn)題 S = aixi,22,背包密碼系統(tǒng)的意義,是第一個(gè)公鑰密碼系統(tǒng) 有較好的理論價(jià)值 在實(shí)踐過(guò)程中，大多數(shù)的背包方案都已被破解，或者證明存在缺陷,23,只有兩個(gè)算法被普遍接受,1 RSA,2 橢圓曲線,就是要找一個(gè)單向陷門(mén)函數(shù)：不太容易,24,單向陷門(mén)函數(shù)（1）,Y=fk(X) 容易(k 和X已知),X=f-1k (Y) 計(jì)算上不可行（k

8、未知，Y已知）,X=f-1k (Y) 容易（k已知，Y已知）,尋找合適的單向陷門(mén)函數(shù)是公鑰密碼 體制應(yīng)用關(guān)鍵！,25,單向陷門(mén)函數(shù)（2）,困難程度 舉例 打碎/拼接、平方/開(kāi)方、乘法/分解 * 單向函數(shù)存在否 尚無(wú)嚴(yán)格的數(shù)學(xué)證明,26,單向陷門(mén)函數(shù)（3）,單向陷門(mén)函數(shù) 如果知道某個(gè)陷門(mén)(秘訣)，即能容易恢復(fù)x （陷門(mén)即為私鑰） 舉例 魔方的置亂/恢復(fù) 如果有那個(gè)口訣，就能很快恢復(fù) 加密/解密,27,RSA 算法,先從一個(gè)簡(jiǎn)單例子開(kāi)始 給出算法 證明,28,簡(jiǎn)單例子,選中兩個(gè)素?cái)?shù) p7，q17,npq (n)請(qǐng)練習(xí),任務(wù)：對(duì)明文 M=19 加密,npq119 (n)(p-1)(q-1)61696

9、,選取整數(shù)1e (n)與(n) 互素：e5,求e的逆元d：ed1 mod (n) 請(qǐng)練習(xí),計(jì)算 C=Me(mod n)=? 其中M=19 請(qǐng)練習(xí),計(jì)算 M1=Cd(mod n)=? 請(qǐng)練習(xí),d=77,c=66,29,Exponentiation (c為輔助,求ab),c = 0; f = 1 for i = k downto 0 do c = 2 c f = (f f) mod n if bi = 1 then c = c + 1 f = (f a) mod n return f 這里b可以先看成2的整數(shù)冪,便于理解,30,RSA 示例總結(jié),選p7，q17 則npq119 且(n)(p-1)(

10、q-1)61696 取e5 則d77 (57738549611 mod 96) 公鑰（5，119），私鑰（77，119） 加密m19 則cme mod n= 195 mod 119 = 66 mod 119 解密c66 mcd mod n = 6677mod 11919 mod 119,31,設(shè)置參數(shù)p,q,d,e,bool rsa:set_pqde( int m_in, int e_in ) e=e_in; m=m_in; p=depart(m_in); q=m_in/p; if(p=1 | p=2 | !prime(q) ) return false; /2 n=(p-1)*(q-1);

11、d=n/e;/這里要注意e與n要互素？ while( ( (e*d)%n )!=1 ) d+; /3 max=m_in; while( maxmaxint ) max+=m_in; max=max-m_in; return true; ,32,分解整數(shù)x,int rsa:depart( int x ) int i; if(prime(x) return 1; /X是素?cái)?shù) if(!(x%2) return 2;/X是偶數(shù) i=3; while(x%i) i+; return i; ,33,素?cái)?shù)測(cè)試,bool rsa:prime( int x ) int i; if (x=1)return fal

12、se; /合數(shù) if (x=2)return true; /素?cái)?shù) if ( !(x%2) ) return false; for(i=3;i=sqrt(x);i+=2) if(!(x%i) return false; return true; ,34,加密算法,int rsa:rsaencry(int x,int y,int m ) int yy,li; double l; if( y=1 ) return x%m; yy=y%2;/分幾偶數(shù) if( yy=0 ) l=rsaencry(x,y/2,m); l=l*l; while( lmaxint ) l=l-max; li=(int)l;

13、return li%m; else l=rsaencry(x,y-1,m); l=l*x; while( lmaxint ) l=l-max; li=(int)l; return li%m; ,35,解密算法,int rsa:rsadecode(int x,int y,int m) int x1=x,y1=y,f1=1; while(y1!=0) while(y1%2=0) y1=y1/2; x1=ff(x1,x1,m); y1=y1-1; f1=ff(f1,x1,m); return f1; ,36,37,RSA算法,作者 1977年，R, S, A Ron Rivesthttp:/theo

14、/rivest/ Adi Shamirhttp:/www.wisdom.weizmann.ac.il/shamir/ Len Adleman /dept/molecular-science/ 基本參數(shù) 分組密碼算法 基于整數(shù)乘法 明/密文分組以及公/私鑰被看作小于n的整數(shù) 加/解密是模乘運(yùn)算,38,RSA算法總結(jié)：密鑰產(chǎn)生,找素?cái)?shù) 選取兩個(gè)大的隨機(jī)的素?cái)?shù)p，q 計(jì)算模n和Euler函數(shù)(n) npq (n)=(p-1)(q-1) 找ed1 mod (n) 隨機(jī)取一個(gè)數(shù)e(與(n)互素)，用擴(kuò)展Euclid算法求d即可 發(fā)布 d保密，

15、(d, n)是私鑰 KU 發(fā)布(e,n)，這是公鑰KR 銷(xiāo)毀p、q,39,RSA的正確性,加密 明文分組m做為整數(shù)須小于n c=me mod n 解密 m=cd mod n 證明 依據(jù)Euler定理，在mod n的含義下有： cd(me)dmed mk(n)+1 (m(n)k mm,40,RSA考慮,素?cái)?shù) 必須夠大，否則對(duì)手可能很快分解n 判定，采用Miller-Rabin概率測(cè)試方法 假素?cái)?shù)意味著加解密不能正確進(jìn)行，故可放棄之 強(qiáng)素?cái)?shù) (p-1)/2和(q-1)/2應(yīng)是素?cái)?shù) 選取較小的e和較大的d e：3、65537 快速計(jì)算xy%z 發(fā)布公鑰 證書(shū)中心 CA,41,攻擊RSA,數(shù)學(xué)方法 分解n 得到p和q，就可以知道(n)，就可從e求得d 直接求(n) 不分解n，而直接求(n)，再求d 直接求d 不求(n)，直接求d,42,43,閱讀：RSA挑戰(zhàn)賽,44,使用公鑰傳遞會(huì)話密鑰,直接使用公鑰算法太慢 對(duì)稱(chēng)算法一般幾十兆字節(jié)/秒 1024位RSA解密約100多次/秒(加密快10倍以上) 只用來(lái)傳遞會(huì)話密鑰 (假設(shè)A已經(jīng)有B的公鑰KeB) A發(fā)起和B的通信 A產(chǎn)生會(huì)話密鑰Ks，并用