第19講--公鑰密碼概述

1、量子密碼研究室量子密碼研究室王王 濱濱2005.4.12 公開(kāi)密鑰算法的提出公開(kāi)密鑰算法的提出公鑰密碼學(xué)是公鑰密碼學(xué)是1976年由年由Diffie和和Hellman在其在其“密碼學(xué)密碼學(xué)新方向新方向”一文中提出的，見(jiàn)文獻(xiàn)：一文中提出的，見(jiàn)文獻(xiàn)： W.Diffie and 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ì)稱(chēng)算法，即密鑰分為公鑰和私公開(kāi)密鑰算法是非對(duì)

2、稱(chēng)算法，即密鑰分為公鑰和私鑰，因此稱(chēng)雙密鑰體制鑰，因此稱(chēng)雙密鑰體制 雙鑰體制的公鑰可以公開(kāi)，因此也稱(chēng)公鑰算法雙鑰體制的公鑰可以公開(kāi)，因此也稱(chēng)公鑰算法 公鑰算法的出現(xiàn)，給密碼的發(fā)展開(kāi)辟了新的方向。公鑰算法的出現(xiàn)，給密碼的發(fā)展開(kāi)辟了新的方向。公鑰算法雖然已經(jīng)歷了公鑰算法雖然已經(jīng)歷了2020多年的發(fā)展，但仍具有強(qiáng)勁多年的發(fā)展，但仍具有強(qiáng)勁的發(fā)展勢(shì)頭，在鑒別系統(tǒng)和密鑰交換等安全技術(shù)領(lǐng)域的發(fā)展勢(shì)頭，在鑒別系統(tǒng)和密鑰交換等安全技術(shù)領(lǐng)域起著關(guān)鍵的作用起著關(guān)鍵的作用加密與解密由不同的密鑰完成加密與解密由不同的密鑰完成 加密：加密： 解密：解密：知道加密算法，從加密密鑰得到解密密鑰在計(jì)算上是知道加密算法，從加密

3、密鑰得到解密密鑰在計(jì)算上是不可行的不可行的兩個(gè)密鑰中任何一個(gè)都可以作為加密而另一個(gè)用作解兩個(gè)密鑰中任何一個(gè)都可以作為加密而另一個(gè)用作解密（不是必須的）密（不是必須的）公開(kāi)密鑰算法的基本要求公開(kāi)密鑰算法的基本要求:( )KUXY Y EX:( )( )KRKRKUYX XDYDEX基于公開(kāi)密鑰的加密過(guò)程基于公開(kāi)密鑰的加密過(guò)程用公鑰密碼實(shí)現(xiàn)保密用公鑰密碼實(shí)現(xiàn)保密 用戶擁有自己的密鑰對(duì)用戶擁有自己的密鑰對(duì)(KU,KR) 公鑰公鑰 KU公開(kāi)，私鑰公開(kāi)，私鑰KR保密保密:( )bKUAB YEX:( )( )bbbKRKRKUB DYDEXX基于公開(kāi)密鑰的鑒別過(guò)程基于公開(kāi)密鑰的鑒別過(guò)程用公鑰密碼實(shí)現(xiàn)鑒別

4、用公鑰密碼實(shí)現(xiàn)鑒別 條件：兩個(gè)密鑰中任何一個(gè)都可以用作加密而另外條件：兩個(gè)密鑰中任何一個(gè)都可以用作加密而另外一個(gè)用作解密一個(gè)用作解密鑒別：鑒別： 鑒別保密鑒別保密 :( ):( )( )aabaKRKUKUKRAALL YEXALL DYDEXX:():( )baabKUKRKUKRAB ZEDXB EDZX公開(kāi)密鑰算法公開(kāi)密鑰算法公鑰算法的種類(lèi)很多，具有代表性的三種密碼：公鑰算法的種類(lèi)很多，具有代表性的三種密碼： 基于整數(shù)分解難題（基于整數(shù)分解難題（IFPIFP）的算法體制）的算法體制 基于離散對(duì)數(shù)難題（基于離散對(duì)數(shù)難題（DLPDLP）算法體制）算法體制基于橢圓曲線離散對(duì)數(shù)難題（基于橢圓曲線

5、離散對(duì)數(shù)難題（ECDLPECDLP）的算法體制）的算法體制Diffie-Hellman密鑰交換算法密鑰交換算法Diffie-Hellman公鑰技術(shù)公鑰技術(shù)人工手動(dòng)分配密鑰人工手動(dòng)分配密鑰: 問(wèn)題問(wèn)題 效率低效率低成本高成本高每個(gè)用戶要存儲(chǔ)與所有用戶通信的密鑰每個(gè)用戶要存儲(chǔ)與所有用戶通信的密鑰安全性差安全性差機(jī)器自動(dòng)分配密鑰機(jī)器自動(dòng)分配密鑰: 要求要求任何兩個(gè)用戶能獨(dú)立計(jì)算他們之間的秘密密鑰任何兩個(gè)用戶能獨(dú)立計(jì)算他們之間的秘密密鑰傳輸量小傳輸量小存儲(chǔ)量小存儲(chǔ)量小任何一個(gè)任何一個(gè)(或多個(gè)或多個(gè))用戶不能計(jì)算出其他用戶之間用戶不能計(jì)算出其他用戶之間的秘密密鑰的秘密密鑰單向陷門(mén)函數(shù)函數(shù)單向陷門(mén)函數(shù)函數(shù)

6、 滿足下列條件的函數(shù)滿足下列條件的函數(shù)f f： (1) 給定給定x，計(jì)算，計(jì)算y=f(x)是容易的是容易的 (2) 給定給定y, 計(jì)算計(jì)算x使使y=f(x)是困難的是困難的 (3) 存在存在z，已知，已知z 時(shí)時(shí), 對(duì)給定的任何對(duì)給定的任何y，若相應(yīng)的，若相應(yīng)的x存在，則計(jì)算存在，則計(jì)算x使使y=f(x)是容易的是容易的所謂計(jì)算所謂計(jì)算x= x= f-1(Y)(Y)困難是指計(jì)算上相當(dāng)復(fù)雜，已無(wú)困難是指計(jì)算上相當(dāng)復(fù)雜，已無(wú)實(shí)際意義實(shí)際意義單向陷門(mén)函數(shù)說(shuō)明單向陷門(mén)函數(shù)說(shuō)明僅滿足僅滿足(1)、(2)兩條的稱(chēng)為單向函數(shù)；第兩條的稱(chēng)為單向函數(shù)；第(3)條稱(chēng)為陷門(mén)性，條稱(chēng)為陷門(mén)性，z 稱(chēng)為陷門(mén)信息稱(chēng)為陷門(mén)

7、信息當(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í)加密密鑰便稱(chēng)為公開(kāi)密鑰，記為開(kāi)加密密鑰，此時(shí)加密密鑰便稱(chēng)為公開(kāi)密鑰，記為Pkf函數(shù)的設(shè)計(jì)者將函數(shù)的設(shè)計(jì)者將z保密，用作解密密鑰，此時(shí)保密，用作解密密鑰，此時(shí)z稱(chēng)為秘密稱(chēng)為秘密鑰匙，記為鑰匙，記為Sk。由于設(shè)計(jì)者擁有。由于設(shè)計(jì)者擁有Sk，他自然可以解出，他自然可以解出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密鑰交換算法密鑰交換算法Diffi

8、e和和Hellman在其里程碑意義的文章中，雖然給出在其里程碑意義的文章中，雖然給出了密碼的思想，但是沒(méi)有給出真正意義上的公鑰密碼了密碼的思想，但是沒(méi)有給出真正意義上的公鑰密碼實(shí)例，也既沒(méi)能找出一個(gè)真正帶實(shí)例，也既沒(méi)能找出一個(gè)真正帶陷門(mén)陷門(mén)的單向函數(shù)的單向函數(shù)然而，他們給出單向函數(shù)的實(shí)例，并且基于此提出然而，他們給出單向函數(shù)的實(shí)例，并且基于此提出Diffie-Hellman密鑰交換算法密鑰交換算法Diffie-Hellman密鑰交換算法的原理密鑰交換算法的原理基于有限域中計(jì)算離散對(duì)數(shù)的困難性問(wèn)題之上：設(shè)基于有限域中計(jì)算離散對(duì)數(shù)的困難性問(wèn)題之上：設(shè)F為有限域，為有限域，gF是是F的乘法群的乘法群

9、 F*=F0=，并且對(duì)，并且對(duì)任意正整數(shù)任意正整數(shù)x，計(jì)算，計(jì)算gx是容易的；但是已知是容易的；但是已知g和和y求求x使使y= gx，是計(jì)算上幾乎不可能的，是計(jì)算上幾乎不可能的Diffie-Hellman密鑰交換協(xié)議描述密鑰交換協(xié)議描述Alice和和Bob協(xié)商好一個(gè)大素?cái)?shù)協(xié)商好一個(gè)大素?cái)?shù)p，和大的整數(shù)，和大的整數(shù)g，1gp，g最好是最好是FP中的本原元，即中的本原元，即FP*p和和g無(wú)須保密，可為網(wǎng)絡(luò)上的所有用戶共享無(wú)須保密，可為網(wǎng)絡(luò)上的所有用戶共享Diffie-Hellman密鑰交換協(xié)議描述密鑰交換協(xié)議描述當(dāng)當(dāng)Alice和和Bob要進(jìn)行保密通信時(shí)，他們可以按如下步驟來(lái)要進(jìn)行保密通信時(shí)，他們可

10、以按如下步驟來(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 =（X) y(mod P), 易見(jiàn)，易見(jiàn)，K = K =g xy (mod P)由由(4)知，知，Alice和和Bob已獲得了相同的秘密值已獲得了相同的秘密值K雙方以雙方以K作為加解密鑰以傳統(tǒng)對(duì)稱(chēng)密鑰算法進(jìn)行保密通信作為加解密鑰以傳

11、統(tǒng)對(duì)稱(chēng)密鑰算法進(jì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) 每次密鑰交換后不必再保留秘密信息每次密鑰交換后不必再保留秘密信息,減少了減少了保密的負(fù)擔(dān)保密的負(fù)擔(dān).o前提條件前提條件:o必須進(jìn)行身份認(rèn)證必須進(jìn)行身份認(rèn)證,確保不是與假冒的用戶進(jìn)行確保不是與假冒的用戶進(jìn)行密鑰交換密鑰交換,否則不能抵抗中間人攻擊否則不能抵抗中間人攻擊.中間人攻擊中間人攻擊o-攻擊者攻擊者W在信道中間在信道中間,假冒假冒U與與V進(jìn)行密進(jìn)行密鑰交換鑰交換,同時(shí)假冒同時(shí)假冒V與與U

12、進(jìn)行密鑰交換進(jìn)行密鑰交換.致使致使看似看似U與與V交換的密鑰交換的密鑰,實(shí)際上都是與攻擊實(shí)際上都是與攻擊者交換的密鑰者交換的密鑰.具體攻擊具體攻擊具體方法具體方法o攻擊者W在信道上截獲 和 后,不將它們送給用戶V和用戶U,而是隨機(jī)選取整數(shù) ,并計(jì)算出 將它明傳給用戶U,同時(shí)暫時(shí)保留;同時(shí)隨機(jī)選取整數(shù) ,并計(jì)算出 后,將明傳給用戶V,同時(shí)暫時(shí)保留 .puxmodpvxmod21:11pxxwwpwxmod11wx21:22pxxwwpwxmod22wx具體方法具體方法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具體方法具體方法o攻擊者截獲用戶攻擊者截獲用戶U發(fā)給發(fā)給V的密文后的密文后,不傳給用戶不傳給用戶V,而是解讀出明文后再將明文用而是解讀出明文后再將明文用W與與V的密鑰加的密鑰