第8章-pki.

1、問(wèn)題的提出,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,1,Alice,Bob,加密的消息,Hecker (Attacker，Eve),我是黑客，看你怎么把密鑰傳遞給Bob。哈哈！,,快把密鑰傳給我?。〖敝?！,加密密鑰如何傳遞給Bob哪？,以前模型的缺陷,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,2,,,,Problem 1：如何實(shí)現(xiàn)密鑰的安全傳輸？Problem 2：有沒(méi)有不需要安全信道的密碼技術(shù)？,2024/3/19,計(jì)算機(jī)科學(xué)

2、與技術(shù)學(xué)院,3,公鑰密碼學(xué)（Public Key Cryptography, PKC）,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,4,主要內(nèi)容,,公鑰密碼學(xué)基本概念,1,,RSA密碼體制,2,,Elgamal密碼體制,3,,橢圓曲線密碼體制ECC,4,,基于身份的加密體制,5,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,5,公鑰加密體系,Problem：如何安全的傳遞秘密文件？要求：Alice 和 Bob沒(méi)有共享密鑰,Alice,Bo

3、b,如何將包裹安全的傳遞給Bob哪???,Messenger,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,6,,,Alice,,Bob,Messenger,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,7,,,Alice,Bob,Messenger,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,8,,,Alice,Bob,Messenger,,,結(jié)論：現(xiàn)實(shí)生活中可以實(shí)現(xiàn)沒(méi)有共享密鑰的信息的安全傳輸?shù)侍土耍ㄠ]差需要來(lái)回3次）問(wèn)

4、題： 密碼學(xué)中有沒(méi)有辦法實(shí)現(xiàn)沒(méi)有共享密鑰的加解密？ 一定要以損失效率為代價(jià)嗎？,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,9,對(duì)稱加密體制的不足—密鑰分配和管理,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,10,,,,,,,,,,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,11,對(duì)稱加密體制的不足—簽名和認(rèn)證問(wèn)題,對(duì)稱密碼體制中，通信雙方共享密鑰，因此接收方可以偽造原文—不能實(shí)現(xiàn)鑒別認(rèn)證發(fā)送方也可以否認(rèn)—不能實(shí)現(xiàn)

5、不可否認(rèn)性尤其在電子商務(wù)等網(wǎng)絡(luò)應(yīng)用中，互不認(rèn)識(shí)的網(wǎng)絡(luò)用戶之間進(jìn)行安全交易時(shí)，不能解決陌生人之間的身份認(rèn)證和交易信息認(rèn)證問(wèn)題,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,12,解決方法—公鑰密碼體制,公鑰密碼（非對(duì)稱密碼）：每個(gè)用戶都分別擁有兩個(gè)密鑰：加密密鑰(公鑰)與解密密鑰(私鑰) ，兩者并不相同，且由加密密鑰得到解密密鑰在計(jì)算上不可行。加密密鑰是公開(kāi),2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,13,類比：任何人只需按一下就可以把鎖

6、關(guān)上，但只有有鑰匙的人才能把鎖打開(kāi)。關(guān)鎖(加密)是容易的，人人都可以做到，但開(kāi)鎖(解密)只能由有鑰匙的人來(lái)做。知道關(guān)鎖的知識(shí)無(wú)助于開(kāi)鎖,1976年，美國(guó)學(xué)者Diffie和Hellman在美國(guó)國(guó)家計(jì)算機(jī)會(huì)議上提出了公鑰密碼體制的概念，并將該開(kāi)創(chuàng)性的論文《密碼學(xué)的新方向》（“New Directions in Cryptography”）發(fā)表在IEEE雜志信息論卷上，成為近代密碼學(xué)的又一里程碑同時(shí)，以色列的Merkle也獨(dú)立的提出了該思

7、想，但是論文發(fā)表稍晚（1978年，論文出版的原因）,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,14,解決方法—公鑰密碼體制,Diffie-Hellman-Merkle,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,15,Whitfield Diffie,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,16,世界著名的密碼技術(shù)與安全技術(shù)專家，1991年加盟Sun公司，在Sun實(shí)驗(yàn)室工作此前，他曾在北方電訊任安全系統(tǒng)經(jīng)理達(dá)20年之久“公鑰加密”概

8、念的發(fā)明人，被業(yè)界公認(rèn)為信息技術(shù)安全事物的權(quán)威人士20 世紀(jì) 90 年代，主要研究密碼技術(shù)的公用策略方面，并多次在美國(guó)參議院和眾議院作證Diffie是馬可尼基金會(huì) (Marconi Foundation) 成員，并且從許多機(jī)構(gòu) -- 美國(guó)電氣及電子工程師學(xué)會(huì)(IEEE)、電子前沿基金會(huì) (Electronic Frontiers Foundation)、美國(guó)標(biāo)準(zhǔn)技術(shù)研究所(NIST)、美國(guó)國(guó)家安全局 (NSA)、富蘭克林研究所 (F

9、ranklin Institute) 和 美國(guó)計(jì)算機(jī)協(xié)會(huì) (ACM) --獲得多種獎(jiǎng)項(xiàng),Martin E. Hellman,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,17,1966年獲得紐約大學(xué)學(xué)士學(xué)位1967和1969分別獲得斯坦福大學(xué)的碩士和博士學(xué)位1968-69年IBM在華盛頓的研究中心1969-1971年MIT1971年斯坦福大學(xué)公鑰密碼學(xué)的創(chuàng)始人之一,公鑰密碼體制示意圖,發(fā)送方A查找接收方B的公鑰A采用公

10、鑰加密算法以B的公鑰加密明文消息A通過(guò)不安全信道將密文發(fā)送給BB收到密文后用自己的私鑰解密獲取明文,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,18,發(fā)送方A,接收方B,加密算法,解密算法,,不安全信道,,B的公鑰,B的私鑰,,密文,明文,,明文,,,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,19,,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,20,重要公鑰密碼體制,設(shè)計(jì)公鑰密碼體制 尋找單向陷門函數(shù)

11、 數(shù)學(xué)困難問(wèn)題大整數(shù)因子分解問(wèn)題(如公鑰密碼體制RSA)給定兩個(gè)素?cái)?shù)p,q,計(jì)算乘積n=pq很容易，但給定整數(shù)n，求n的素因子p,q使得n=pq是困難的有限域上的離散對(duì)數(shù)問(wèn)題(如公鑰密碼體制ElGamal)已知有限循環(huán)群G=={gk|k=0,1,2,…}及其生成元g和階|G|=n.給定整數(shù)a，求h=ga很容易；但是給定元素h，計(jì)算整數(shù)x，使得h=gx非常困難橢圓曲線上的離散對(duì)數(shù)問(wèn)題(

12、如公鑰密碼體制ECC)背包問(wèn)題（背包算法）基于身份的密碼體制（IBE）,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,21,,,1. 費(fèi)爾瑪定理定理 (Fermat)若p是素?cái)?shù)，a是正整數(shù)且gcd(a, p)=1，則ap-1≡1 mod p。,費(fèi)爾瑪定理和歐拉定理,Fermat定理也可寫成如下形式： 設(shè)p是素?cái)?shù)，a是任一正整數(shù)，則ap≡a mod p。2. 歐拉函數(shù)設(shè)n是一正整數(shù)，小于n且與n互素的正整數(shù)的個(gè)數(shù)稱為n的歐拉函數(shù)，

13、記為φ(n)。例如： φ(6)=2 ，φ(7)=6 ，φ(8)=4。若n是素?cái)?shù)，則顯然有φ(n)=n-1。3. 歐拉定理定理（Euler） 若a和n互素，則aφ(n)≡1 mod n,公鑰密碼體制RSA,RSA公鑰算法由 MIT 的Rivest, Shamir和Adleman在I978年提出來(lái)的是被最廣泛接受并實(shí)現(xiàn)的通用公鑰密碼算法，已成為公鑰密碼的國(guó)際標(biāo)準(zhǔn)該算法的數(shù)學(xué)基礎(chǔ)是初等數(shù)論中的歐拉定理，其安全性基于大整數(shù)因子分

14、解的困難性,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,24,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,25,Len Adleman,Ron Rivest,Adi Shamir,,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,26,RSA算法描述,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,27,,算法描述l     密鑰的產(chǎn)生1）選大素?cái)?shù)p和q (各100～200位十進(jìn)制數(shù)字)，計(jì)算

15、 n=p×q , ?(n)=(p－1)(q－1) 隨機(jī)選一整數(shù)e， 1?e<?(n)，(?(n), e)=1。因而在模?(n)下，e有逆元. 計(jì)算 d=e -1 (mod ?(n)) 取公鑰為{e ， n}。秘密鑰為d (p, q不再需要，可以銷毀),l   加密加密時(shí)首先將明文比特串分組，使得每個(gè)分組對(duì)應(yīng)的十進(jìn)制數(shù)小于n，

16、即分組長(zhǎng)度小于log2n。然后對(duì)每個(gè)明文分組m，作加密運(yùn)算 c=me mod n l   解密對(duì)密文分組c的解密運(yùn)算為 m=cd mod n,下面證明RSA算法中解密過(guò)程的正確性。證明： 由加密過(guò)程知c≡me mod n，所以cd mod n≡med mod n≡mkφ(n)+1 mod n下面分兩

17、種情況： ① m與n互素，則由Euler定理得mφ(n)≡1 mod n,mkφ(n)≡1 mod n,mkφ(n)+1≡m mod n即cd mod n≡m。② gcd(m,n)≠1，先看gcd(m,n)=1的含義，由于n=pq，所以gcd(m,n)=1意味著m不是p的倍數(shù)也不是q的倍數(shù)。因此gcd(m,n)≠1意味著m是p的倍數(shù)或q的倍數(shù)，不妨設(shè)m=tp，其中t為一正整數(shù)。此時(shí)必有g(shù)cd(m,q)=1，否則m也是q的倍

18、數(shù)，從而是pq的倍數(shù)，與m<n=pq矛盾。,由gcd(m,q)=1及Euler定理得mφ(q)≡1 mod q，所以mkφ(q)≡1 mod q,［mkφ(q)］φ(p)≡1 mod q, mkφ(n)≡1 mod q因此存在一整數(shù)r，使得mkφ(n)=1+rq，兩邊同乘以m=tp得mkφ(n)+1=m+rtpq=m+rtn即mkφ(n)+1≡m mod n，所以cd mod n≡m。(證畢),例,,2024/3/19

19、,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,32,一些疑問(wèn),2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,33,,素?cái)?shù)的生成,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,34,,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,35,RSA的實(shí)現(xiàn),,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,36,RSA的安全性,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,37,對(duì)RSA的攻擊,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,38,,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)

20、學(xué)院,39,循環(huán)攻擊,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,40,,循環(huán)攻擊實(shí)例,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,41,,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,42,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,43,,,,,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,44,回到例子,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,45,,同模攻擊,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,46,,,,2024/3/19,

21、計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,47,選擇密文攻擊,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,48,,,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,49,低加密指數(shù)攻擊,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,50,時(shí)間攻擊,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,51,,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,52,,RSA-OAEP：最佳非對(duì)稱加密填充,RSA-OAEP：對(duì)消息編碼的一種方法，由M. Bellare 和 P. Rog

22、away提出首先對(duì)消息進(jìn)行填充，然后用RSA進(jìn)行加密該方法是可證明安全的加密操作由3步組成：長(zhǎng)度檢查EME-OAEP編碼RSA加密,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,53,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,54,,公鑰密碼體制ElGamal,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,55,算法描述,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,56,,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,57,,,

23、2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,58,,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,59,ElGamal的安全性,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,60,,離散對(duì)數(shù)問(wèn)題的求解,目前已經(jīng)存在一些計(jì)算離散對(duì)數(shù)的算法，但都不足以用來(lái)破解ElGamal公鑰密碼算法著名的有：大步-小步法（Giant-step Baby-step）指數(shù)積分法（Index Calculus） —更有效,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)

24、學(xué)院,61,設(shè)A=(a1,a2,…,an)是由n個(gè)不同的正整數(shù)構(gòu)成的n元組，s是另一已知的正整數(shù)。背包問(wèn)題就是從A中求出所有的ai，使其和等于s。其中A稱為背包向量，s是背包的容積。例如,A=（43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523），s=3231。由于3231=129+473+903+561+1165所以從A中找出的滿足要求的數(shù)有129、473、903、561、1165

25、。,4.4 背包密碼體制,原則上講，通過(guò)檢查A的所有子集，總可找出問(wèn)題的解（如果有解的話）。本例A的子集共有210=1024個(gè)（包括空集）。然而如果A中元素個(gè)數(shù)n很大，子集個(gè)數(shù)2n將非常大。如A中有300個(gè)元素，A的子集有2300。尋找滿足要求的A的子集沒(méi)有比窮搜索更好的算法，因此背包問(wèn)題是NPC問(wèn)題。,由背包問(wèn)題構(gòu)造公鑰密碼體制同樣是要構(gòu)造一個(gè)單向函數(shù)f，將x(1≤x≤2n-1)寫成長(zhǎng)為n的二元表示0…001,0…010，0…011

26、,…,1…111, f(x)定義為A中所有ai的和，其中x的二元表示的第i位為1，即f(1)=f(0…001)=anf(2)=f(0…010)=an-1f(3)=f(0…011)=an-1+an…f(2n-1)=f(1…111)=a1+a2+…+an使用向量乘，有f(x)=A·Bx，其中Bx是將x的二元表示寫成的列向量。,上例中f(364) = f(0101101100) = 129+47

27、3+903+561+1165 = 3231，類似地可求出:f(609)=2942, f(686)=3584, f(32)=903, f(46)=3326,f(128)=215, f(261)=2817, f(44)=2629, f(648)=819。由f的定義可見(jiàn)，已知x很容易求f(x)，但已知f(x)求x就是要解背包問(wèn)題。當(dāng)然在實(shí)際應(yīng)用中，n不能太小，比如說(shuō)，至少為200。,用f對(duì)明文消息m加密時(shí)，首先將m寫成二元表

28、示，再將其分成長(zhǎng)為n的分組（最后一個(gè)分組不夠長(zhǎng)的話，可在后面填充一些0），然后求每一分組的函數(shù)值，以函數(shù)值作為密文分組。例如，明文消息是英文文本，則可將每個(gè)字母用其在字母表中的序號(hào)表示，再將該序號(hào)轉(zhuǎn)換為二進(jìn)制形式（5位即可），如表4.5所示，其中符號(hào)‘ ’表示空格。,背包向量仍取上例中的A，設(shè)待加密的明文是SAUNA AND HEALTH。因?yàn)锳長(zhǎng)為10，所以應(yīng)將明文分成長(zhǎng)為10比特（即兩個(gè)明文字母）的分組SA，UN，A‘ ’，AN

29、，D‘ ’，HE，AL，TH相應(yīng)的二元序列為1001100001，1010101110，0000100000，0000101110，0010000000，0100000101，0000101100，1010001000。,分別對(duì)以上二元序列作用于函數(shù)f，得密文為（2942，3584，903，3326，215，2817，2629，819）。解密運(yùn)算分別以每一密文分組做為背包容積，求背包問(wèn)題的解。為使接收方能夠解密，就需找出單向函

30、數(shù)的陷門。為此需引入一種特殊類型的背包向量。定義背包向量A=(a1,a2,…,an)稱為超遞增的，如果,超遞增背包向量對(duì)應(yīng)的背包問(wèn)題很容易通過(guò)以下算法（稱為貪婪算法）求解。已知s為背包容積，對(duì)A從右向左檢查每一元素，以確定是否在解中。若s≥an，則an在解中，令xn=1；若s<an，則an不在解中，令xn=0。下面令對(duì)an-1重復(fù)上述過(guò)程，一直下去，直到檢查出a1是否在解中。檢查結(jié)束后得 x=(x1x2…xn)，Bx=(

31、x1x2…xn)T。,然而，敵手如果也知道超遞增背包向量，同樣也很容易解密。為此可用模乘對(duì)A進(jìn)行偽裝，模乘的模數(shù)k和乘數(shù)t皆取為常量，滿足k>∑ai，gcd(t,k)=1，即t在模k下有乘法逆元。設(shè)bi ≡t·ai mod k, i=1,2,…,n得一新的背包向量B=(b1,b2,…,bn)，記為B≡t·A mod k，用戶以B作為自己的公開(kāi)鑰。,例4.10 A=(1, 3, 5, 11, 21, 44,

32、87, 175, 349, 701)是一超遞增背包向量，取k=1590，t=43， gcd(43, 1590)=1，得 B=(43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523)。在得到B后，對(duì)明文分組x=(x1x2…xn)的加密運(yùn)算為c=f(x)=B·Bx≡t·A·Bx mod k對(duì)單向函數(shù)f(x)，t、t-1和k可作為其秘密的陷門信息，即解密密鑰。解

33、密時(shí)首先由s≡t-1 c mod k，求出s作為超遞增背包向量A的容積，再解背包問(wèn)題即得x=(x1x2…xn)。這是因?yàn)閠-1 c mod k≡t-1tABx mod k≡ABx mod k，而由k>∑ai，知ABx<k，所以t-1c mod k=ABx，是惟一的。,例4.11 接例4.10，A=(1, 3, 5, 11, 21, 44, 87, 175, 349, 701)是一超遞增背包向量，k=1590，t=43，得t-

34、1 ≡37 mod 1590，設(shè)用戶收到的密文是(2942, 3584, 903, 3326, 215, 2817, 2629, 819) ，由37×2942≡734 mod 1590, 37×3584≡638 mod 1590, 37×903≡21 mod 1590, 37×3326≡632 mod 1590, 37×215 ≡5 mod 1590, 37×2817≡879

35、 mod 1590, 37×2629≡283 mod 1590, 37×819≡93 mod 1590, 得(734, 638, 21, 632, 5, 879, 283, 93)。,取s=734，由734>701，得x10=1；令s=734-701=33，由33<349，得x9=0；重復(fù)該過(guò)程得第一個(gè)明文分組是1001100001，它對(duì)應(yīng)的英文文本是SA；類似地得其他明文分組，解密結(jié)果為SAUNA A

36、ND HEALTH。,背包密碼體制是Diffie和Hellman 1976年提出公鑰密碼體制的設(shè)想后的第一個(gè)公鑰密碼體制，由Merkle和Hellman 1978年提出。然而又過(guò)了兩年該體制即被破譯，破譯的基本思想是不必找出正確的模數(shù)k和乘數(shù)t（即陷門信息），只須找出任意模數(shù)k′和乘數(shù)t′，使得用k′和t′去乘公開(kāi)的背包向量B時(shí)，能夠產(chǎn)生超遞增的背包向量即可。,公鑰密碼體制ECC,橢圓曲線在代數(shù)學(xué)和幾何學(xué)上已經(jīng)廣泛研究了150多年，有豐

37、富而深厚的理論積累1985年，H. Koblitz和V. Miller分別提出了橢圓曲線密碼體制（Elliptic Curve Cryptosystem，ECC）安全性基于橢圓曲線離散對(duì)數(shù)問(wèn)題可用短得多的密鑰獲得同RSA一樣的安全性，現(xiàn)在許多標(biāo)準(zhǔn)化組織已經(jīng)將其作為新的信息安全標(biāo)準(zhǔn),2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,76,橢圓曲線的定義,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,77,橢圓曲線,2024/3/19,計(jì)算機(jī)

38、科學(xué)與技術(shù)學(xué)院,78,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,79,,橢圓曲線上的運(yùn)算,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,80,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,81,有限域上橢圓曲線加法,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,82,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,83,,,,橢圓曲線密碼算法,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,84,,,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,85,,

39、,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,86,橢圓曲線上的離散對(duì)數(shù)問(wèn)題,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,87,ECC小結(jié),安全性能更高（160位等同RSA的1024位）計(jì)算量小，處理速度快存儲(chǔ)空間占用小帶寬要求低應(yīng)用前景非常好，特別在移動(dòng)通信,無(wú)線設(shè)備上的應(yīng)用(WAPI、WPKI、WNS),2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,88,公鑰體制的問(wèn)題：,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,89,A

40、lice,Bob,Hecker (Attacker，Eve),,,,,缺少身份認(rèn)證機(jī)制,基于身份的加密體制IBE,1984年，Shamir提出基于身份加密(IBE, Identity-based Encryption) ，以簡(jiǎn)化Email系統(tǒng)中的證書管理。當(dāng)Alice給地址“Bob@abc.com”的Bob發(fā)郵件時(shí)，只需用公鑰“Bob@abc.com”加密消息；Bob收到加密消息之后向一個(gè)可信第三方證實(shí)自己的身份，可信第三方將Bob的私

41、鑰送給Bob， Bob用該私鑰解密消息公鑰可以是任意的關(guān)于用戶身份的字符串；用戶向可信第三方認(rèn)證自己的身份并獲得私鑰，該過(guò)程可在收到加密消息之前也可在之后完成,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,90,,在實(shí)際應(yīng)用中，用戶的身份ID可以是姓名、電話號(hào)碼、身份證號(hào)碼、IP地址、電子郵件地址。用戶私鑰由被稱作私鑰生成器PKG(Private Key Generator)的可信第三方計(jì)算得到用戶的公鑰是一些公開(kāi)的身份信息，其他用戶

42、不需要在數(shù)據(jù)庫(kù)中查找用戶的公鑰，也不需要對(duì)公鑰的真實(shí)性進(jìn)行檢驗(yàn),2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,91,IBE的組成,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,92,,BF-IBE方案,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,93,,BF-IBE基礎(chǔ)方案,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,94,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,95,,,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,96,BF-IBE完全方案

43、,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,97,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,98,,IBE的優(yōu)缺點(diǎn),優(yōu)點(diǎn)：不需要對(duì)證書進(jìn)行管理不足：身份確認(rèn)本來(lái)就是一件復(fù)雜的事情，尤其用戶數(shù)量很大。也就是說(shuō)，IBE適合應(yīng)用于用戶群小得場(chǎng)合可信第三方如何安全地將用戶的私鑰送到用戶的手中密鑰托管,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,99,公鑰密碼體制的安全性,,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,100,公鑰密碼

44、分析,蠻力攻擊。防范措施：長(zhǎng)密鑰。但從實(shí)用性角度，要考慮折衷找到根據(jù)公鑰計(jì)算私鑰的方法。目前為止，對(duì)于一個(gè)特定的公鑰算法，尚未從數(shù)學(xué)上證明這種攻擊不可能公鑰系統(tǒng)特有的攻擊方法。假設(shè)發(fā)送的報(bào)文僅僅含有一個(gè)56比特的DES密鑰。敵對(duì)方可以用公鑰加密所有的可能密鑰，然后匹配。因而無(wú)論密鑰方案的密鑰大小是多少，攻擊都?xì)w結(jié)為對(duì)56bit密鑰的蠻力攻擊,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,101,公鑰密碼的優(yōu)點(diǎn)（與對(duì)稱密碼相比）,密鑰分發(fā)

45、簡(jiǎn)單需秘密保存的密鑰量少可以滿足互不認(rèn)識(shí)的人之間私人談話的保密性可以實(shí)現(xiàn)數(shù)字簽名和認(rèn)證的功能,2024/3/19,計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,102,公鑰密碼的不足（與對(duì)稱密碼相比）,公鑰密碼算法比對(duì)稱密碼算法慢公鑰密碼算法提供更多的信息對(duì)算法進(jìn)行攻擊，如公鑰密碼算法對(duì)選擇明文攻擊是脆弱的，尤其明文集比較小時(shí)數(shù)據(jù)擴(kuò)展公鑰密碼算法一般是建立在特定的數(shù)學(xué)難題之上，往往這種困難性只是一種設(shè)想,2024/3/19,計(jì)算機(jī)科學(xué)與