公鑰密碼體制量子密碼研究室王濱2005.4.121上課安排公鑰密碼體制的概念、思想和工作方式Diffie-Hellman密鑰交換算法RSA算法EIgamal公鑰算法ECC算法2背景

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

W.DiffieandM.E.Hellman,NewDirectrionsinCryptography，

IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-6544公開密鑰算法公開密鑰算法是非對稱算法，即密鑰分為公鑰和私鑰，因此稱雙密鑰體制雙鑰體制的公鑰可以公開，因此也稱公鑰算法公鑰算法的出現(xiàn)，給密碼的發(fā)展開辟了新的方向。公鑰算法雖然已經(jīng)歷了20多年的發(fā)展，但仍具有強勁的發(fā)展勢頭，在鑒別系統(tǒng)和密鑰交換等安全技術領域起著關鍵的作用5加密與解密由不同的密鑰完成加密：

解密：知道加密算法，從加密密鑰得到解密密鑰在計算上是不可行的兩個密鑰中任何一個都可以作為加密而另一個用作解密（不是必須的）公開密鑰算法的基本要求6基于公開密鑰的加密過程7用公鑰密碼實現(xiàn)保密

用戶擁有自己的密鑰對(KU,KR)

公鑰KU公開，私鑰KR保密8基于公開密鑰的鑒別過程9用公鑰密碼實現(xiàn)鑒別條件：兩個密鑰中任何一個都可以用作加密而另外一個用作解密鑒別：

鑒別＋保密

10公開密鑰算法公鑰算法的種類很多，具有代表性的三種密碼：基于整數(shù)分解難題（IFP）的算法體制基于離散對數(shù)難題（DLP）算法體制基于橢圓曲線離散對數(shù)難題（ECDLP）的算法體制11Diffie-Hellman密鑰交換算法12Diffie-Hellman公鑰技術Diffie-Hellman公鑰密碼技術又稱為Diffie-Hellman密碼交換協(xié)議,它是WhitefieldDiffie和MartinHellman在1976年提出的,是至今仍然流行的一種公鑰技術.(見教材P143)13D-H密鑰交換協(xié)議背景密鑰分配人工手動分配密鑰:問題效率低成本高每個用戶要存儲與所有用戶通信的密鑰安全性差機器自動分配密鑰:要求任何兩個用戶能獨立計算他們之間的秘密密鑰傳輸量小存儲量小任何一個(或多個)用戶不能計算出其他用戶之間的秘密密鑰14單向陷門函數(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)困難是指計算上相當復雜，已無實際意義15單向陷門函數(shù)說明僅滿足(1)、(2)兩條的稱為單向函數(shù)；第(3)條稱為陷門性，z稱為陷門信息當用陷門函數(shù)f作為加密函數(shù)時，可將f公開，這相當于公開加密密鑰，此時加密密鑰便稱為公開密鑰，記為Pkf函數(shù)的設計者將z保密，用作解密密鑰，此時z稱為秘密鑰匙，記為Sk。由于設計者擁有Sk，他自然可以解出x=f-1(y)單向陷門函數(shù)的第(2)條性質(zhì)表明竊聽者由截獲的密文y=f(x)推測x是不可行的16Diffie-Hellman密鑰交換算法Diffie和Hellman在其里程碑意義的文章中，雖然給出了密碼的思想，但是沒有給出真正意義上的公鑰密碼實例，也既沒能找出一個真正帶陷門的單向函數(shù)然而，他們給出單向函數(shù)的實例，并且基于此提出Diffie-Hellman密鑰交換算法17Diffie-Hellman密鑰交換算法的原理基于有限域中計算離散對數(shù)的困難性問題之上：設F為有限域，g∈F是F的乘法群F*=F\{0}=<g>，并且對任意正整數(shù)x，計算gx是容易的；但是已知g和y求x使y=gx，是計算上幾乎不可能的18Diffie-Hellman密鑰交換協(xié)議描述Alice和Bob協(xié)商好一個大素數(shù)p，和大的整數(shù)g，1<g<p，g最好是FP中的本原元，即FP*＝<g>p和g無須保密，可為網(wǎng)絡上的所有用戶共享19Diffie-Hellman密鑰交換協(xié)議描述當Alice和Bob要進行保密通信時，他們可以按如下步驟來做：

(1)Alice選取大的隨機數(shù)x，并計算X=gx

(modP)(2)Bob選取大的隨機數(shù)y，并計算Y=gy

(modP)(3)Alice將X傳送給Bob；Bob將Y傳送給Alice(4)Alice計算K=(Y)x(modP);Bob計算K=（X)y(mod

P),易見，K=K=gxy

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