1、1,公鑰密碼概述 Diffie-Hellman密鑰交換協(xié)議 背包體制簡(jiǎn)介 RSA密碼體制,第四章 公鑰密碼技術(shù),2,RSA公鑰密碼算法,主要內(nèi)容：RSA公鑰密碼算法，RSA公鑰密碼的實(shí)現(xiàn)。 重點(diǎn)： RSA算法，脫密的快速實(shí)現(xiàn)，素?cái)?shù)生成算法。 難點(diǎn)：素?cái)?shù)生成算法。,3,RSA體制,由Rivest、Shamir、Adleman于1978年首次發(fā)表； 最容易理解和實(shí)現(xiàn)的公鑰算法; 經(jīng)受住了多年深入的攻擊; 其理論基礎(chǔ)是一種特殊的可逆模冪運(yùn)算，其安全性基于分解大整數(shù)的困難性； RSA既可用于加密，又可用于數(shù)字簽名，已得到廣泛采用； RSA已被許多標(biāo)準(zhǔn)化組織(如ISO、ITU、IETF和SWIFT等)接

2、納； 目前許多國(guó)家標(biāo)準(zhǔn)仍采用RSA或它的變型,4,假設(shè)m為要傳送的報(bào)文。 1、任產(chǎn)生兩個(gè)素?cái)?shù)p與q，使得n=pqm 2、隨機(jī)選擇數(shù)e：e與(p-1)(q-1) 互素 3、用輾轉(zhuǎn)相除法求d：ed=1 mod(p-1)(q-1) 4、公開：（e，n），保密：d 加密過程：c=me mod n 解密過程：m=cd mod n,一、RSA算法,1、RSA算法描述,5,定義：任給一個(gè)正整數(shù)m，如果用m去除任意兩個(gè)整數(shù)a、b所得的余數(shù)相同，稱a、b對(duì)模m同余。記為： ，若余數(shù)不同，則a、b對(duì)模m不同余。記為： 。,定理： ，當(dāng)且僅當(dāng)m|(a-b)。,定理：歐拉定理，對(duì)任意 有,推論:費(fèi)爾馬定理，若p為素?cái)?shù)

3、，則,其中,2、工作原理,6,RSA算法論證, E和D的可逆性,要證明：D(E(M)=M,MCd (Me)dMed mod n,因?yàn)閑d1 mod(n)，這說明edt(n)+1,其中 t為某整數(shù)。所以,Med Mt(n)+1 mod n 。,因此要證明Med M mod n ，只需證明 M t(n)+1 M mod n 。,7,RSA算法論證,在（M，n）1的情況下，根據(jù)數(shù)論(Euler定理)， M t(n) 1 mod n ，,于是有， M t(n)+1 M mod n 。,8,RSA算法論證,在（M，n）1的情況下，分兩種情況：,第一種情況：M1,2,3,n-1,因?yàn)閚=pq，p和q為素?cái)?shù)

4、， M1,2,3,n-1，且（M，n）1 。,這說明M必含p或q之一為其因子，而且不能同 時(shí)包含兩者， 否則將有Mn ， 與 M1,2,3,n-1矛盾。,9,RSA算法論證,10,RSA算法論證,不妨設(shè)Map 。 又因q為素?cái)?shù)，且M不包含q，故有（M，q）1， 于是有，M (q) 1 mod q 。 進(jìn)一步有，M t(p-1)(q) 1 mod q。 因?yàn)閝是素?cái)?shù)，(q)（q-1），所以t(p-1)(q) t(n)， 所以有 M t(n) 1 mod q。,11,于是，M t(n) bq+1，其中b為某整數(shù)。 兩邊同乘M， M t(n)+1 bqM+M 。 因?yàn)镸ap，故 M t(n)+1 b

5、qap+M =abn+M 。 取模n得， M (n)+1 M mod n 。,RSA算法論證,12,第二種情況：M0 當(dāng)M0時(shí)，直接驗(yàn)證，可知命題成立。,RSA算法論證,13,RSA算法論證,加密和解密運(yùn)算的可交換性,D(E(M)=(Me)d =Med =(Md)e =E(D(M) mod n,所以，RSA密碼可同時(shí)確保數(shù)據(jù)的秘密性和數(shù)據(jù)的 真實(shí)性。,14,RSA算法論證,加解密算法的有效性,RSA密碼的加解密運(yùn)算是模冪運(yùn)算，有比較有效 的算法。,15,RSA算法論證,在計(jì)算上由公開密鑰不能求出解密鑰,小合數(shù)的因子分解是容易的，然而大合數(shù)的因子分 解卻是十分困難的。關(guān)于大合數(shù)的因子分解的時(shí)間

6、復(fù)雜度下限目前尚沒有一般的結(jié)果，迄今為止的各 種因子分解算法提示人們這一時(shí)間下限將不低于 O（EXP（lnNlnlnN）1/2）。 根據(jù)這一結(jié)論，只要合數(shù)足夠大，進(jìn)行因子分解是 相當(dāng)困難的。,16,RSA算法論證,假設(shè)截獲密文C，從中求出明文M。他知道,MCd mod n ， 因?yàn)閚是公開的，要從C中求出明文M，必須先求 出d，而d是保密的。但他知道， ed1 mod (n)， e是公開的，要從中求出d，必須先求出(n)，而 (n)是保密的。但他又知道， (n)=(p-1)(q-1)，,17,要從中求出(n)，必須先求出p和q，而p和q是保密的。 但他知道， n=pq， 要從n求出p和q，只有

7、對(duì)n進(jìn)行因子分解。而當(dāng)n足夠大時(shí)， 這是很困難的。,RSA算法論證,只要能對(duì)n進(jìn)行因子分解，便可攻破RSA密碼。由此可以 得出，破譯RSA密碼的困難性對(duì)n因子分解的困難性。目 前尚不能證明兩者是否能確切相等，因?yàn)椴荒艽_知除了對(duì) n進(jìn)行因子分解的方法外，是否還有別的更簡(jiǎn)捷的破譯方 法。,18,3、例子： 假設(shè)RSA體制中p=3,q=11,取加密密鑰e=7. (1) 求脫密密鑰d; (2) 寫出相應(yīng)的加密算法和脫密算法; (3) 對(duì)明文m=8加密。,7d mod20=1,因e=7與 互素, 故可解模方程 ，即,解: 此時(shí)npq33，且,得到d3。,19,故RSA體制明、密文空間: Z/(33) 加

8、密密鑰：(e, n) =(7, 33) 脫密密鑰：(d, p, q) =(3, 3,11),加密算法: cm7mod33 脫密算法: mc3mod33,對(duì)明文m8加密，得: c87mod33=2,20,二、RSA算法的參數(shù)選擇,為了確保RSA密碼的安全，必須認(rèn)真選擇密碼參數(shù)： p和q要足夠大； 一般應(yīng)用：p和q應(yīng)512 bits 重要應(yīng)用：p和q應(yīng)1024 bits p和q應(yīng)為強(qiáng)素?cái)?shù) 文獻(xiàn)指出，只要(p-1)、(p+1)、(q-1)、(q+1)四 個(gè)數(shù)之一只有小的素因子，n就容易分解。 p和q的差要大；,21,（p-1）和（q-1）的最大公因子要小。 如果（ p-1）和（q-1）的最大公因子太

9、大，則易受迭代加密 攻擊。 e的選擇 隨機(jī)且含1多就安全，但加密速度慢。于是，有的學(xué)者建議取 e216+165537 d的選擇 d不能太小，要足夠大 不要許多用戶共用一個(gè)模n；易受共模攻擊,22,1989年Lenstra, Manasse利用二次篩法使用數(shù)百臺(tái)工作站分解了106位十進(jìn)制數(shù)； 1990年Lenstra, Manasse, Pollar利用數(shù)域篩法使用700臺(tái)工作站花費(fèi)個(gè)月時(shí)間將155位十進(jìn)制數(shù)分解成三個(gè)素?cái)?shù)之積； 1994年Atkins, Graff, Lenstra, Lerland利用多重二次篩法的雙重大素?cái)?shù)算法動(dòng)用1600臺(tái)計(jì)算機(jī)聯(lián)網(wǎng)，600名志愿者花費(fèi)個(gè)月時(shí)間分解了129

10、位十進(jìn)制數(shù)； 2002年成功分解158位的十進(jìn)制數(shù)。 結(jié)論：154位十進(jìn)制數(shù)（512bit）的模長(zhǎng)已經(jīng)不安全，應(yīng)使用308位十進(jìn)制數(shù)（1024bit）模長(zhǎng)。,23,三、RSA算法中大素?cái)?shù)生成,RSA的安全性基礎(chǔ)是基于大合數(shù)分解的困難性，在RSA算法中要求模數(shù)N是兩個(gè)大素?cái)?shù)p和q的乘積。 用戶選擇模數(shù)N的方法是先找到兩個(gè)素?cái)?shù)，然后生成相應(yīng)的模數(shù)N。 素?cái)?shù)判定是要解決的首要問題。,24,1、產(chǎn)生大素?cái)?shù)的算法（Rabin素性檢測(cè)算法）,由歐拉定理知，若n為素?cái)?shù)：,則n可能為素?cái)?shù)，也可能為合數(shù)。 Rabin由此設(shè)計(jì)了一個(gè)判定n是否為素?cái)?shù)的算法。,反過來若： ，則n必為合數(shù)。,若,25,1、產(chǎn)生大素?cái)?shù)的

11、算法Rabin素性檢測(cè)算法,Rabin素性檢測(cè)法是一種概率素?cái)?shù)測(cè)試法。 其輸入為一奇數(shù)，輸出為兩種狀態(tài)Yes或No。若輸入一奇數(shù)N，而輸出為No，即表示N必定為合數(shù)。若輸出為Yes，則表示N為素?cái)?shù)的概率為1-，其中為此素?cái)?shù)測(cè)試法中可控制的任意小數(shù)，但不能為0。（ 是在N是合數(shù)的條件下誤判為素?cái)?shù)的條件概率。）,26,Rabin素性檢測(cè)算法： （1）任取一個(gè)大奇數(shù)n （2）任取 且(a,n)=1 （3）如果, 則判n是素?cái)?shù)； 否則判n是合數(shù)，重新選取n重復(fù)上過程。,Rabin證明了由上述算法所產(chǎn)生的素?cái)?shù)的誤判概率:,由此,我們將算法中的第(2)和(3)步驟重復(fù)k次, 這樣判定n為素?cái)?shù)的誤判概率小于

12、等于(1/4)k。,計(jì)算復(fù)雜度為：O(log2n)3),27,Miller-Rabin算法,隨機(jī)選擇一個(gè)奇整數(shù)n(如利用偽隨機(jī)數(shù)產(chǎn)生器)； 隨機(jī)選擇一個(gè)整數(shù)an； 執(zhí)行諸如Miller-Rabin等概率素?cái)?shù)測(cè)試。若n未通過測(cè)試，則轉(zhuǎn)到第一步； 若n通過足夠多次的測(cè)試，則接受n；否則轉(zhuǎn)向第2步。,28,在實(shí)際使用中,通過首先檢驗(yàn)待檢測(cè)的隨機(jī)數(shù)是否是小素?cái)?shù)(例如所有小于1000的素?cái)?shù))的倍數(shù)，待檢測(cè)通過后再執(zhí)行Rabin檢測(cè)。 Miller-Rabin素?cái)?shù)檢測(cè)算法，已經(jīng)作為標(biāo)準(zhǔn)的檢測(cè)算法列入IEEE P1363的附錄和NIST的數(shù)字簽名標(biāo)準(zhǔn)的附錄，作為密碼學(xué)標(biāo)準(zhǔn)使用。,29,RSA的加脫密計(jì)算都是

13、在模N運(yùn)算下進(jìn)行的，盡管這兩個(gè)加脫密計(jì)算公式形式上比較簡(jiǎn)單，但由于其加、脫密的兩個(gè)主要運(yùn)算，即指數(shù)運(yùn)算與模大整數(shù)運(yùn)算均涉及到很大的數(shù)，故RSA的實(shí)現(xiàn)還是有較大的難度。,快速乘方算法,30,指數(shù)運(yùn)算 最簡(jiǎn)單而直接的計(jì)算方法，就是將m連續(xù)乘e-1次，如此就可以獲得的值了。 當(dāng)m或e很大時(shí)，其計(jì)算復(fù)雜度將是非常高的。,在指數(shù)運(yùn)算中，比較有名的是二元法（也稱為平方乘法）,31,設(shè)e為k位二進(jìn)制數(shù)，w(e)為e的二進(jìn)制系數(shù)中為1的個(gè) 數(shù)，則最多只需要計(jì)算w(e) -1次平方和w(e)次數(shù)的模 乘。從而大大簡(jiǎn)化了計(jì)算。,32,以512比特加密指數(shù)為例，整數(shù)e的二進(jìn)制表示為:,一般的加密過程為:,33,當(dāng)要

14、對(duì)明文進(jìn)行加密時(shí)，可先進(jìn)行預(yù)處理，計(jì)算出m2、m3等，這種方法我們稱之為窗口法。,34,例：,計(jì)算:,35,第一步首先計(jì)算,第二步計(jì)算,第三步計(jì)算,第四步計(jì)算,最后一步計(jì)算,結(jié)論：,36,快速模乘算法,反復(fù)平方乘算法解決了快速乘方取模的問題， 仍未解決快速模乘的問題； Montgomery算法是一種快速模乘的好算法；,將以上兩種算法結(jié)合成為實(shí)現(xiàn)RSA密碼的 有效方法。,37,Montgomery算法的思路： 要計(jì)算Y=AB mod n ,因?yàn)閚很大，取模運(yùn)算困難，采取一 個(gè)小的模R，回避大模數(shù)的計(jì)算。 利用空間換時(shí)間，多用存儲(chǔ)空間換取快速。 缺點(diǎn)：不能直接計(jì)算出Y=AB mod n ，只能計(jì)算

15、出中間 值A(chǔ)BR-1 mod n ，因此還需要預(yù)處理和調(diào)整運(yùn)算。一次性 計(jì)算Y=AB mod n并不劃算。 適合：RSA等密碼中多次的模乘計(jì)算。,38,對(duì)稱密鑰密碼學(xué)與公鑰密碼學(xué),1、對(duì)稱密鑰密碼學(xué)的優(yōu)點(diǎn),（1）能夠設(shè)計(jì)為具有很高的數(shù)據(jù)吞吐率。硬件實(shí)現(xiàn)可以達(dá)到每秒加密幾百兆字節(jié)，而軟件實(shí)現(xiàn)的吞吐率也達(dá)到了每秒兆字節(jié)的數(shù)量級(jí)。,（2）對(duì)稱密碼的密鑰相對(duì)較短。,（3）對(duì)稱密鑰密碼可以作為要素來構(gòu)造各種密碼機(jī)制。比如偽隨機(jī)數(shù)生成器、雜湊函數(shù)、快速數(shù)字簽名方案等,（4）對(duì)稱密鑰密碼能合成強(qiáng)密碼。簡(jiǎn)單變換容易被分拆，但是研究其弱點(diǎn)后，可用來構(gòu)造強(qiáng)的乘積密碼。,39,2、對(duì)稱密鑰密碼學(xué)的缺點(diǎn),（1）在一個(gè)

16、雙方的通信中，密鑰必須在兩端都保密。 （2）在大型網(wǎng)絡(luò)中，要管理許多密鑰對(duì)。其結(jié)果是，有效的密鑰管理需要一個(gè)無條件可信的TTP。（稱一個(gè)TTP是無條件可信的，如果它在所有事情上都可信。例如它也許可以訪問用戶的秘密密鑰和私鑰，還承擔(dān)著公鑰和標(biāo)識(shí)符的聯(lián)系） （3）對(duì)實(shí)體A與B之間的一個(gè)雙方通信，使用密鑰的良好習(xí)慣是：經(jīng)常更換密鑰，通常是會(huì)話密鑰一次一換。 （4）源自對(duì)稱密鑰加密的數(shù)字簽名機(jī)制通常需要關(guān)于公開驗(yàn)證函數(shù)的大密鑰，或者使用TTP。,40,3、公鑰密碼學(xué)的優(yōu)點(diǎn),（1）只有私鑰必須保密。（但必須保證公鑰的真實(shí)性） （2）與無條件可信的TTP相反，公鑰密碼管理需要的只是一個(gè)功能上可信的TTP（

17、稱一個(gè)TTP是功能上可信的，如果它是誠(chéng)實(shí)且公正的，但是不可以訪問用戶的秘密密鑰和私鑰）。關(guān)于使用方式，和實(shí)時(shí)的需要使用相反，這個(gè)TTP也許只需以離線方式使用。 （3）依賴于使用方式的差別，一個(gè)私鑰/公鑰對(duì)可以在一段相當(dāng)長(zhǎng)的時(shí)期內(nèi)保持不變，甚至數(shù)年。比如多次會(huì)話使用相同密鑰。,41,（4）許多公鑰方案產(chǎn)生了相對(duì)有效的數(shù)字簽名機(jī)制。用于刻畫公開驗(yàn)證函數(shù)的密鑰通常比對(duì)稱密鑰小很多。 （5）在大型網(wǎng)絡(luò)中，所需密鑰的數(shù)量要比對(duì)稱密鑰情形下少很多。,42,4、公鑰密碼學(xué)的缺點(diǎn),（1）在吞吐率方面，大多流行的公鑰加密方法要比已知最好的對(duì)稱密鑰加密方案慢幾個(gè)數(shù)量級(jí)。 （2）密鑰長(zhǎng)度（如RSA的1024比特）明

18、顯要比對(duì)稱密鑰（如64比特或128比特）加密所需大得多（10倍或更多）。這是因?yàn)獒槍?duì)對(duì)稱密鑰系統(tǒng)的最有效的攻擊是密鑰窮搜（這一般是設(shè)計(jì)要求），而對(duì)公鑰系統(tǒng)來說，快捷攻擊（如因子分解）比窮搜有效得多。,43,（3）沒有公鑰方案被證明是安全的（對(duì)分組秘密也一樣）。至今發(fā)現(xiàn)的最有效的公鑰加密方案都把安全性建立在一小批數(shù)論問題的困難性假定之上。 （4）公鑰密碼學(xué)沒有對(duì)稱密鑰加密那樣長(zhǎng)久的歷史，它在20世紀(jì)70年代中期才被發(fā)現(xiàn)。,44,5、比較總結(jié),對(duì)稱密鑰加密和公鑰加密有許多互補(bǔ)的優(yōu)點(diǎn)。目前的密碼系統(tǒng)融合了兩者的優(yōu)勢(shì)。 憑借公鑰加密技術(shù)來建立密鑰，然后用于實(shí)體A和B進(jìn)行通信的對(duì)稱密鑰密碼系統(tǒng)。A和B就可綜合利用公鑰方案的公鑰與私鑰對(duì)長(zhǎng)期性，以及對(duì)稱密鑰方案的