第17講--公鑰密碼概述

1、公鑰密碼體制,背景,在擁有大量用戶的通信網(wǎng)絡(luò)，若想讓兩兩用戶都能進(jìn)行保密通信，即要求 (1)任意一對用戶共享一個(gè)會(huì)話密鑰 (2)不同的用戶對共享的會(huì)話密鑰不相同 對于分配中心，N個(gè)用戶則需要分配CN2個(gè)會(huì)話密鑰，大量的數(shù)據(jù)存儲(chǔ)和分配是一件很麻煩的事，在計(jì)算機(jī)網(wǎng)絡(luò)環(huán)境下顯的尤為突出。另外傳統(tǒng)密碼不易實(shí)現(xiàn)數(shù)字簽名，也進(jìn)一步限制了其發(fā)展。,公開密鑰算法的提出,公鑰密碼學(xué)是1976年由Diffie和Hellman在其“密碼學(xué)新方向”一文中提出的，見文獻(xiàn)： W.Diffie and M.E.Hellman, New Directrions in Cryptography， IEEE Transactio

2、n on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654,Diffie生平,Diffie(1944-) 1965年，獲得麻繩理工學(xué)院數(shù)學(xué)學(xué)士學(xué)位 1976年，和Hellman聯(lián)合發(fā)表密碼學(xué)新方向 1991年，任職于Sun公司 1992年，1992年瑞士聯(lián)邦理工學(xué)院授予博士頭銜。,公鑰密碼學(xué)的八卦,公鑰密碼學(xué)據(jù)說是他們最早發(fā)明的,馬爾科姆威廉姆生 1975年和前者合作發(fā)現(xiàn)了DH密鑰交換方法,克利福德.科克思 1973年發(fā)現(xiàn)了RSA算法,詹姆斯.埃利斯 1969年提出公鑰算法模型,公開密鑰算法,公開密鑰算法是非對稱算法，即密鑰分為公鑰和

3、私鑰，因此稱雙密鑰體制 雙鑰體制的公鑰可以公開，因此也稱公鑰算法 公鑰算法的出現(xiàn)，給密碼的發(fā)展開辟了新的方向。公鑰算法雖然已經(jīng)歷了20多年的發(fā)展，但仍具有強(qiáng)勁的發(fā)展勢頭，在鑒別系統(tǒng)和密鑰交換等安全技術(shù)領(lǐng)域起著關(guān)鍵的作用,加密與解密由不同的密鑰完成 加密： 解密： 知道加密算法，從加密密鑰得到解密密鑰在計(jì)算上是不可行的 兩個(gè)密鑰中任何一個(gè)都可以作為加密而另一個(gè)用作解密（不是必須的）,公開密鑰算法的基本要求,基于公開密鑰的加密過程,用公鑰密碼實(shí)現(xiàn)保密,用戶擁有自己的密鑰對(KU,KR) 公鑰 KU公開，私鑰KR保密,基于公開密鑰的鑒別過程,用公鑰密碼實(shí)現(xiàn)鑒別,條件：兩個(gè)密鑰中任何一個(gè)都可以用作加密

4、而另外一個(gè)用作解密 鑒別： 鑒別保密,公開密鑰算法,公鑰算法的種類很多，具有代表性的三種密碼： 基于整數(shù)分解難題（IFP）的算法體制 基于離散對數(shù)難題（DLP）算法體制 基于橢圓曲線離散對數(shù)難題（ECDLP）的算法體制,Diffie-Hellman密鑰交換算法,Diffie-Hellman公鑰技術(shù),Diffie-Hellman公鑰密碼技術(shù)又稱為Diffie-Hellman密碼交換協(xié)議,它是Whitefield Diffie和Martin Hellman在1976年提出的,是至今仍然流行的一種公 鑰技術(shù).(見教材P86),D-H密鑰交換協(xié)議背景密鑰分配,人工手動(dòng)分配密鑰: 問題 效率低 成本高

5、每個(gè)用戶要存儲(chǔ)與所有用戶通信的密鑰 安全性差 機(jī)器自動(dòng)分配密鑰: 要求 任何兩個(gè)用戶能獨(dú)立計(jì)算他們之間的秘密密鑰 傳輸量小 存儲(chǔ)量小 任何一個(gè)(或多個(gè))用戶不能計(jì)算出其他用戶之間的秘密密鑰,單向陷門函數(shù)函數(shù),滿足下列條件的函數(shù)f： (1) 給定x，計(jì)算y=f(x)是容易的 (2) 給定y, 計(jì)算x使y=f(x)是困難的 (3) 存在z，已知z 時(shí), 對給定的任何y，若相應(yīng)的x存在，則計(jì)算x使y=f(x)是容易的 所謂計(jì)算x= f-1(Y)困難是指計(jì)算上相當(dāng)復(fù)雜，已無實(shí)際意義,單向陷門函數(shù)說明,僅滿足(1)、(2)兩條的稱為單向函數(shù)；第(3)條稱為陷門性，z 稱為陷門信息 當(dāng)用陷門函數(shù)f作為加密

6、函數(shù)時(shí)，可將f公開，這相當(dāng)于公開加密密鑰，此時(shí)加密密鑰便稱為公開密鑰，記為Pk f函數(shù)的設(shè)計(jì)者將z保密，用作解密密鑰，此時(shí)z稱為秘密鑰匙，記為Sk。由于設(shè)計(jì)者擁有Sk，他自然可以解出x=f-1(y) 單向陷門函數(shù)的第(2)條性質(zhì)表明竊聽者由截獲的密文y=f(x)推測x是不可行的,Diffie-Hellman密鑰交換算法,Diffie和Hellman在其里程碑意義的文章中，雖然給出了密碼的思想，但是沒有給出真正意義上的公鑰密碼實(shí)例，也既沒能找出一個(gè)真正帶陷門的單向函數(shù) 然而，他們給出單向函數(shù)的實(shí)例，并且基于此提出Diffie-Hellman密鑰交換算法,Diffie-Hellman密鑰交換算法的

7、原理,基于有限域中計(jì)算離散對數(shù)的困難性問題之上：設(shè)F為有限域，gF是F的乘法群 F*=F0=，并且對任意正整數(shù)x，計(jì)算gx是容易的；但是已知g和y求x使y= gx，是計(jì)算上幾乎不可能的,Diffie-Hellman密鑰交換協(xié)議描述,Alice和Bob協(xié)商好一個(gè)大素?cái)?shù)p，和大的整數(shù)g，1 p和g無須保密，可為網(wǎng)絡(luò)上的所有用戶共享,Diffie-Hellman密鑰交換協(xié)議描述,當(dāng)Alice和Bob要進(jìn)行保密通信時(shí)，他們可以按如下步驟來做： (1) Alice選取大的隨機(jī)數(shù)x，并計(jì)算 X = gx (mod P) (2) Bob選取大的隨機(jī)數(shù)y，并計(jì)算 Y = gy (mod P) (3) Alic

8、e將X傳送給Bob；Bob將Y傳送給Alice (4) Alice計(jì)算K= (Y)x(mod P); Bob計(jì)算K =（X) y(mod P), 易見，K = K =g xy (mod P) 由(4)知，Alice和Bob已獲得了相同的秘密值K 雙方以K作為加解密鑰以傳統(tǒng)對稱密鑰算法進(jìn)行保密通信,DH協(xié)議分析,優(yōu)點(diǎn): (1) 任何兩個(gè)人都可協(xié)商出會(huì)話密鑰,不需事先擁有對方的公開或秘密的信息. (2) 每次密鑰交換后不必再保留秘密信息,減少了保密的負(fù)擔(dān). 前提條件: 必須進(jìn)行身份認(rèn)證,確保不是與假冒的用戶進(jìn)行密鑰交換,否則不能抵抗中間人攻擊.,中間人攻擊,-攻擊者W在信道中間,假冒U與V進(jìn)行密鑰交換,同時(shí)假冒V與U進(jìn)行密鑰交換.致使看似U與V交換的密鑰,實(shí)際上都是與攻擊者交換的密鑰.,具體攻擊,具體方法,攻擊者W在信道上截獲 和 后,不將它們送給用戶V和用戶U,而是隨機(jī)選取整數(shù) ,并計(jì)算出 將它明傳給用戶U,同時(shí)暫時(shí)保留 ;同時(shí)隨機(jī)選取整數(shù) ,并計(jì)算出 后,將明傳給用戶V,同時(shí)暫時(shí)保留 .,具體方法,用戶U計(jì)算出 用戶V計(jì)算出 攻擊者W分別計(jì)算出 分別作為解密用戶U發(fā)給用戶V的密鑰和解密用戶V發(fā)給用戶U的密鑰.,具體方法,攻擊者截獲用戶U發(fā)給V的密文后,不傳給用戶V,而是解讀出明文后再將明文用W與V的密鑰加密后傳給V. 備