公鑰密碼概述ppt課件

1、量子密碼研討室量子密碼研討室王王 濱濱2005.4.122005.4.12 在擁有大量用戶的通訊網(wǎng)絡(luò)，假想象讓兩兩用戶都能進(jìn)展嚴(yán)密通訊，即要求(1)恣意一對(duì)用戶共享一個(gè)會(huì)話密鑰(2)不同的用戶對(duì)共享的會(huì)話密鑰不一樣 對(duì)于分配中心，N個(gè)用戶那么需求分配CN2個(gè)會(huì)話密鑰，大量的數(shù)據(jù)存儲(chǔ)和分配是一件很費(fèi)事的事，在計(jì)算機(jī)網(wǎng)絡(luò)環(huán)境下顯的尤為突出。另外傳統(tǒng)密碼不易實(shí)現(xiàn)數(shù)字簽名，也進(jìn)一步限制了其開(kāi)展。公開(kāi)密鑰算法的提出公開(kāi)密鑰算法的提出公鑰密碼學(xué)是公鑰密碼學(xué)是1976年由年由Diffie和和Hellman在其在其“密碼學(xué)密碼學(xué)新方向一文中提出的，見(jiàn)文獻(xiàn)：新方向一文中提出的，見(jiàn)文獻(xiàn)： W.Diffie and

2、 M.E.Hellman, New Directrions in Cryptography， IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654公開(kāi)密鑰算法公開(kāi)密鑰算法 公開(kāi)密鑰算法是非對(duì)稱算法，即密鑰分為公鑰和私公開(kāi)密鑰算法是非對(duì)稱算法，即密鑰分為公鑰和私鑰，因此稱雙密鑰體制鑰，因此稱雙密鑰體制 雙鑰體制的公鑰可以公開(kāi)，因此也稱公鑰算法雙鑰體制的公鑰可以公開(kāi)，因此也稱公鑰算法 公鑰算法的出現(xiàn)，給密碼的開(kāi)展開(kāi)辟了新的方向。公鑰算法的出現(xiàn)，給密碼的開(kāi)展開(kāi)辟了新的方向。公鑰算法雖然曾閱歷了公鑰算法雖然

3、曾閱歷了20多年的開(kāi)展，但仍具有強(qiáng)勁多年的開(kāi)展，但仍具有強(qiáng)勁的開(kāi)展勢(shì)頭，在鑒別系統(tǒng)和密鑰交換等平安技術(shù)領(lǐng)域的開(kāi)展勢(shì)頭，在鑒別系統(tǒng)和密鑰交換等平安技術(shù)領(lǐng)域起著關(guān)鍵的作用起著關(guān)鍵的作用加密與解密由不同的密鑰完成加密與解密由不同的密鑰完成 加密：加密： 解密：解密：知道加密算法，從加密密鑰得到解密密鑰在計(jì)算上是知道加密算法，從加密密鑰得到解密密鑰在計(jì)算上是不可行的不可行的兩個(gè)密鑰中任何一個(gè)都可以作為加密而另一個(gè)用作解兩個(gè)密鑰中任何一個(gè)都可以作為加密而另一個(gè)用作解密不是必需的密不是必需的公開(kāi)密鑰算法的根本要求公開(kāi)密鑰算法的根本要求:( )KUXY Y EX:( )( )KRKRKUYX XDYDEX基

4、于公開(kāi)密鑰的加密過(guò)程基于公開(kāi)密鑰的加密過(guò)程用公鑰密碼實(shí)現(xiàn)嚴(yán)密用公鑰密碼實(shí)現(xiàn)嚴(yán)密 用戶擁有本人的密鑰對(duì)用戶擁有本人的密鑰對(duì)(KU,KR) 公鑰公鑰 KU公開(kāi)，私鑰公開(kāi)，私鑰KR嚴(yán)密嚴(yán)密:( )bKUAB YEX:( )( )bbbKRKRKUB DYDEXX基于公開(kāi)密鑰的鑒別過(guò)程基于公開(kāi)密鑰的鑒別過(guò)程用公鑰密碼實(shí)現(xiàn)鑒別用公鑰密碼實(shí)現(xiàn)鑒別 條件：兩個(gè)密鑰中任何一個(gè)都可以用作加密而另外條件：兩個(gè)密鑰中任何一個(gè)都可以用作加密而另外一個(gè)用作解密一個(gè)用作解密鑒別：鑒別： 鑒別嚴(yán)密鑒別嚴(yán)密 :( ):( )( )aabaKRKUKUKRAALL YEXALL DYDEXX:():( )baabKUKRKUK

5、RAB ZEDXB EDZX公開(kāi)密鑰算法公開(kāi)密鑰算法公鑰算法的種類很多，具有代表性的三種密碼：公鑰算法的種類很多，具有代表性的三種密碼： 基于整數(shù)分解難題基于整數(shù)分解難題IFP的算法體制的算法體制 基于離散對(duì)數(shù)難題基于離散對(duì)數(shù)難題DLP算法體制算法體制基于橢圓曲線離散對(duì)數(shù)難題基于橢圓曲線離散對(duì)數(shù)難題ECDLP的算法體制的算法體制Diffie-Hellman密鑰交換算法密鑰交換算法Diffie-Hellman公鑰技術(shù)公鑰技術(shù)人工手動(dòng)分配密鑰人工手動(dòng)分配密鑰: 問(wèn)題問(wèn)題 效率低效率低本錢(qián)高本錢(qián)高每個(gè)用戶要存儲(chǔ)與一切用戶通訊的密鑰每個(gè)用戶要存儲(chǔ)與一切用戶通訊的密鑰平安性差平安性差機(jī)器自動(dòng)分配密鑰機(jī)器

6、自動(dòng)分配密鑰: 要求要求任何兩個(gè)用戶能獨(dú)立計(jì)算他們之間的密鑰任何兩個(gè)用戶能獨(dú)立計(jì)算他們之間的密鑰傳輸量小傳輸量小存儲(chǔ)量小存儲(chǔ)量小任何一個(gè)任何一個(gè)(或多個(gè)或多個(gè))用戶不能計(jì)算出其他用戶之間的密用戶不能計(jì)算出其他用戶之間的密鑰鑰單向陷門(mén)函數(shù)函數(shù)單向陷門(mén)函數(shù)函數(shù) 滿足以下條件的函數(shù)滿足以下條件的函數(shù)f： (1) 給定給定x，計(jì)算，計(jì)算y=f(x)是容易的是容易的 (2) 給定給定y, 計(jì)算計(jì)算x使使y=f(x)是困難的是困難的 (3) 存在存在z，知，知z 時(shí)時(shí), 對(duì)給定的任何對(duì)給定的任何y，假設(shè)相應(yīng)的，假設(shè)相應(yīng)的x存在，那么計(jì)算存在，那么計(jì)算x使使y=f(x)是容易的是容易的所謂計(jì)算所謂計(jì)算x=

7、f-1(Y)困難是指計(jì)算上相當(dāng)復(fù)雜，已無(wú)實(shí)踐困難是指計(jì)算上相當(dāng)復(fù)雜，已無(wú)實(shí)踐意義意義單向陷門(mén)函數(shù)闡明單向陷門(mén)函數(shù)闡明僅滿足僅滿足(1)、(2)兩條的稱為單向函數(shù)；第兩條的稱為單向函數(shù)；第(3)條稱為陷門(mén)性，條稱為陷門(mén)性，z 稱為陷門(mén)信息稱為陷門(mén)信息當(dāng)用陷門(mén)函數(shù)當(dāng)用陷門(mén)函數(shù)f作為加密函數(shù)時(shí)，可將作為加密函數(shù)時(shí)，可將f公開(kāi)，這相當(dāng)于公公開(kāi)，這相當(dāng)于公開(kāi)加密密鑰，此時(shí)加密密鑰便稱為公開(kāi)密鑰，記為開(kāi)加密密鑰，此時(shí)加密密鑰便稱為公開(kāi)密鑰，記為Pkf函數(shù)的設(shè)計(jì)者將函數(shù)的設(shè)計(jì)者將z嚴(yán)密，用作解密密鑰，此時(shí)嚴(yán)密，用作解密密鑰，此時(shí)z稱為鑰匙，稱為鑰匙，記為記為Sk。由于設(shè)計(jì)者擁有。由于設(shè)計(jì)者擁有Sk，他自然可

8、以解出，他自然可以解出x=f-1(y)單向陷門(mén)函數(shù)的第單向陷門(mén)函數(shù)的第(2)條性質(zhì)闡明竊聽(tīng)者由截獲的密文條性質(zhì)闡明竊聽(tīng)者由截獲的密文y=f(x)推測(cè)推測(cè)x是不可行的是不可行的Diffie-Hellman密鑰交換算法密鑰交換算法Diffie和和Hellman在其里程碑意義的文章中，雖然給出了在其里程碑意義的文章中，雖然給出了密碼的思想，但是沒(méi)有給出真正意義上的公鑰密碼實(shí)密碼的思想，但是沒(méi)有給出真正意義上的公鑰密碼實(shí)例，也既沒(méi)能找出一個(gè)真正帶陷門(mén)的單向函數(shù)例，也既沒(méi)能找出一個(gè)真正帶陷門(mén)的單向函數(shù)然而，他們給出單向函數(shù)的實(shí)例，并且基于此提出然而，他們給出單向函數(shù)的實(shí)例，并且基于此提出Diffie-H

9、ellman密鑰交換算法密鑰交換算法Diffie-Hellman密鑰交換算法的原理密鑰交換算法的原理基于有限域中計(jì)算離散對(duì)數(shù)的困難性問(wèn)題之上：設(shè)基于有限域中計(jì)算離散對(duì)數(shù)的困難性問(wèn)題之上：設(shè)F為為有限域，有限域，gF是是F的乘法群的乘法群 F*=F0=，并且對(duì)恣，并且對(duì)恣意正整數(shù)意正整數(shù)x，計(jì)算，計(jì)算gx是容易的；但是知是容易的；但是知g和和y求求x使使y= gx，是計(jì)算上幾乎不能夠的是計(jì)算上幾乎不能夠的Diffie-Hellman密鑰交換協(xié)議描畫(huà)密鑰交換協(xié)議描畫(huà)Alice和和Bob協(xié)商好一個(gè)大素?cái)?shù)協(xié)商好一個(gè)大素?cái)?shù)p，和大的整數(shù)，和大的整數(shù)g，1gp，g最好是最好是FP中的本原元，即中的本原元，

10、即FP*p和和g無(wú)須嚴(yán)密，可為網(wǎng)絡(luò)上的一切用戶共享無(wú)須嚴(yán)密，可為網(wǎng)絡(luò)上的一切用戶共享Diffie-Hellman密鑰交換協(xié)議描畫(huà)密鑰交換協(xié)議描畫(huà)當(dāng)當(dāng)Alice和和Bob要進(jìn)展嚴(yán)密通訊時(shí)，他們可以按如下步驟來(lái)要進(jìn)展嚴(yán)密通訊時(shí)，他們可以按如下步驟來(lái)做：做： (1) Alice選取大的隨機(jī)數(shù)選取大的隨機(jī)數(shù)x，并計(jì)算，并計(jì)算 X = gx (mod P) (2) Bob選取大的隨機(jī)數(shù)選取大的隨機(jī)數(shù)y，并計(jì)算，并計(jì)算 Y = gy (mod P) (3) Alice將將X傳送給傳送給Bob；Bob將將Y傳送給傳送給Alice (4) Alice計(jì)算計(jì)算K= (Y)x(mod P); Bob計(jì)算計(jì)算K =

11、X) y(mod P), 易見(jiàn)，易見(jiàn)，K = K =g xy (mod P)由由(4)知，知，Alice和和Bob已獲得了一樣的值已獲得了一樣的值K雙方以雙方以K作為加解密鑰以傳統(tǒng)對(duì)稱密鑰算法進(jìn)展嚴(yán)密通訊作為加解密鑰以傳統(tǒng)對(duì)稱密鑰算法進(jìn)展嚴(yán)密通訊DH協(xié)議分析協(xié)議分析o優(yōu)點(diǎn)優(yōu)點(diǎn):o(1) 任何兩個(gè)人都可協(xié)商出會(huì)話密鑰任何兩個(gè)人都可協(xié)商出會(huì)話密鑰,不需事先擁不需事先擁有對(duì)方的公開(kāi)或的信息有對(duì)方的公開(kāi)或的信息.o(2) 每次密鑰交換后不用再保管信息每次密鑰交換后不用再保管信息,減少了嚴(yán)密減少了嚴(yán)密的負(fù)擔(dān)的負(fù)擔(dān).o前提條件前提條件:o必需進(jìn)展身份認(rèn)證必需進(jìn)展身份認(rèn)證,確保不是與冒充的用戶進(jìn)展確保不是與

12、冒充的用戶進(jìn)展密鑰交換密鑰交換,否那么不能抵抗中間人攻擊否那么不能抵抗中間人攻擊.中間人攻擊中間人攻擊o-攻擊者W在信道中間,冒充U與V進(jìn)展密鑰交換,同時(shí)冒充V與U進(jìn)展密鑰交換.致使看似U與V交換的密鑰,實(shí)踐上都是與攻擊者交換的密鑰.詳細(xì)攻擊詳細(xì)攻擊詳細(xì)方法詳細(xì)方法o攻擊者W在信道上截獲 和 后,不將它們送給用戶V和用戶U,而是隨機(jī)選取整數(shù) ,并計(jì)算出o 將它明傳給用戶U,同時(shí)暫時(shí)保管;同時(shí)隨機(jī)選取整數(shù) ,并計(jì)算出o 后,將明傳給用戶V,同時(shí)暫時(shí)保管 .puxmodpvxmod21:11pxxwwpwxmod11wx21:22pxxwwpwxmod22wx詳細(xì)方法詳細(xì)方法o用戶用戶U計(jì)算出計(jì)算出o用戶用戶V計(jì)算出計(jì)算出o攻擊者攻擊者W分別計(jì)算出分別計(jì)算出o分別作為解密用戶分別作為解密用戶U發(fā)給用戶發(fā)給用戶V的密鑰和的密鑰和解密用戶解密用戶V發(fā)給用戶發(fā)給用戶U的密鑰的密鑰.ppkuwxxmod)mod(11ppkvwxxmod)mod(22ppkwuxxumod)mod(1ppkwvxxvmod)mod(2詳細(xì)方法詳細(xì)方法o攻擊者截獲用戶攻擊者截獲用戶U發(fā)給發(fā)給V的密文后的密文后,不傳給用戶不傳給用戶V,而是解讀出明文后再將明文用而是解讀出明文后再將明文用W與與V的密鑰加