《公鑰密碼概述》PPT課件.ppt

公鑰密碼體制,量子密碼研究室 王 濱 2005.4.12,上課安排,公鑰密碼體制的概念、思想和工作方式 Diffie-Hellman密鑰交換算法 RSA 算法 EIgamal公鑰算法 ECC算法,背景,在擁有大量用戶的通信網(wǎng)絡，若想讓兩兩用戶都能進行保密通信，即要求 (1)任意一對用戶共享一個會話密鑰 (2)不同的用戶對共享的會話密鑰不相同 對于分配中心，N個用戶則需要分配CN2個會話密鑰，大量的數(shù)據(jù)存儲和分配是一件很麻煩的事，在計算機網(wǎng)絡環(huán)境下顯的尤為突出。另外傳統(tǒng)密碼不易實現(xiàn)數(shù)字簽名，也進一步限制了其發(fā)展。,公開密鑰算法的提出,公鑰密碼學是1976年由Diffie和Hellman在其“密碼學新方向”一文中提出的，見文獻： 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,公開密鑰算法,公開密鑰算法是非對稱算法，即密鑰分為公鑰和私鑰，因此稱雙密鑰體制 雙鑰體制的公鑰可以公開，因此也稱公鑰算法 公鑰算法的出現(xiàn)，給密碼的發(fā)展開辟了新的方向。公鑰算法雖然已經(jīng)歷了20多年的發(fā)展，但仍具有強勁的發(fā)展勢頭，在鑒別系統(tǒng)和密鑰交換等安全技術(shù)領域起著關鍵的作用,加密與解密由不同的密鑰完成 加密： 解密： 知道加密算法，從加密密鑰得到解密密鑰在計算上是不可行的 兩個密鑰中任何一個都可以作為加密而另一個用作解密（不是必須的）,公開密鑰算法的基本要求,基于公開密鑰的加密過程,用公鑰密碼實現(xiàn)保密,用戶擁有自己的密鑰對(KU,KR) 公鑰 KU公開，私鑰KR保密,基于公開密鑰的鑒別過程,用公鑰密碼實現(xiàn)鑒別,條件：兩個密鑰中任何一個都可以用作加密而另外一個用作解密 鑒別： 鑒別保密,公開密鑰算法,公鑰算法的種類很多，具有代表性的三種密碼： 基于整數(shù)分解難題（IFP）的算法體制 基于離散對數(shù)難題（DLP）算法體制 基于橢圓曲線離散對數(shù)難題（ECDLP）的算法體制,Diffie-Hellman密鑰交換算法,Diffie-Hellman公鑰技術(shù),Diffie-Hellman公鑰密碼技術(shù)又稱為Diffie-Hellman密碼交換協(xié)議,它是Whitefield Diffie和Martin Hellman在1976年提出的,是至今仍然流行的一種公 鑰技術(shù).(見教材P143),D-H密鑰交換協(xié)議背景密鑰分配,人工手動分配密鑰: 問題 效率低 成本高 每個用戶要存儲與所有用戶通信的密鑰 安全性差 機器自動分配密鑰: 要求 任何兩個用戶能獨立計算他們之間的秘密密鑰 傳輸量小 存儲量小 任何一個(或多個)用戶不能計算出其他用戶之間的秘密密鑰,單向陷門函數(shù)函數(shù),滿足下列條件的函數(shù)f： (1) 給定x，計算y=f(x)是容易的 (2) 給定y, 計算x使y=f(x)是困難的 (3) 存在z，已知z 時, 對給定的任何y，若相應的x存在，則計算x使y=f(x)是容易的 所謂計算x= f-1(Y)困難是指計算上相當復雜，已無實際意義,單向陷門函數(shù)說明,僅滿足(1)、(2)兩條的稱為單向函數(shù)；第(3)條稱為陷門性，z 稱為陷門信息 當用陷門函數(shù)f作為加密函數(shù)時，可將f公開，這相當于公開加密密鑰，此時加密密鑰便稱為公開密鑰，記為Pk f函數(shù)的設計者將z保密，用作解密密鑰，此時z稱為秘密鑰匙，記為Sk。由于設計者擁有Sk，他自然可以解出x=f-1(y) 單向陷門函數(shù)的第(2)條性質(zhì)表明竊聽者由截獲的密文y=f(x)推測x是不可行的,Diffie-Hellman密鑰交換算法,Diffie和Hellman在其里程碑意義的文章中，雖然給出了密碼的思想，但是沒有給出真正意義上的公鑰密碼實例，也既沒能找出一個真正帶陷門的單向函數(shù) 然而，他們給出單向函數(shù)的實例，并且基于此提出Diffie-Hellman密鑰交換算法,Diffie-Hellman密鑰交換算法的原理,基于有限域中計算離散對數(shù)的困難性問題之上：設F為有限域，gF是F的乘法群 F*=F0=，并且對任意正整數(shù)x，計算gx是容易的；但是已知g和y求x使y= gx，是計算上幾乎不可能的,Diffie-Hellman密鑰交換協(xié)議描述,Alice和Bob協(xié)商好一個大素數(shù)p，和大的整數(shù)g，1 p和g無須保密，可為網(wǎng)絡上的所有用戶共享,Diffie-Hellman密鑰交換協(xié)議描述,當Alice和Bob要進行保密通信時，他們可以按如下步驟來做： (1) Alice選取大的隨機數(shù)x，并計算 X = gx (mod P) (2) Bob選取大的隨機數(shù)y，并計算 Y = gy (mod P) (3) Alice將X傳送給Bob；Bob將Y傳送給Alice (4) Alice計算K= (Y)x(mod P); Bob計算K =（X) y(mod P), 易見，K = K =g xy (mod P) 由(4)知，Alice和Bob已獲得了相同的秘密值K 雙方以K作為加解密鑰以傳統(tǒng)對稱密鑰算法進行保密通信,DH協(xié)議分析,優(yōu)點: (1) 任何兩個人都可協(xié)商出會話密鑰,不需事先擁有對方的公開或秘密的信息. (2) 每次密鑰交換后不必再保留秘密信息,減少了保密的負擔. 前提條件: 必須進行身份認證,確保不是與假冒的用戶進行密鑰交換,否則不能抵抗中間人攻擊.,中間人攻擊,-攻擊者W在信道中間,假冒U與V進行密鑰交換,同時假冒V與U進行密鑰交換.致使看似U與V交換的密鑰,實際上都是與攻擊者交換的密鑰.,具體攻擊,具體方法,攻擊者W在信道上截獲 和 后,不將它們送給用戶V和用戶U,而是隨機選取整數(shù) ,并計算出 將它明傳給用戶U,同時暫時保留 ;同時隨機選取整數(shù) ,并計算出 后,將明傳給用戶V,同時暫時保留 .,具體方法,用戶U計算出 用戶V計算出 攻擊者W分別計算出 分別作為解密用戶U發(fā)給用戶V的密鑰和解密用戶V發(fā)給用戶U的密鑰.,具體方法,攻擊者截獲用戶U發(fā)給V的密文后,不傳給用戶V,而是解讀出明文后再將明文用W與V的密鑰加密后傳給V. 備注: 中間人