1、公鑰密碼體制量子密碼研究室王 濱2005.4.12上課安排公鑰密碼體制的概念、思想和工作方式Diffie-Hellman密鑰交換算法RSA 算法EIgamal公鑰算法ECC算法背景 在擁有大量用戶的通信網(wǎng)絡(luò)，若想讓兩兩用戶都能進(jìn)行保密通信，即要求(1)任意一對用戶共享一個(gè)會話密鑰(2)不同的用戶對共享的會話密鑰不相同 對于分配中心，N個(gè)用戶則需要分配CN2個(gè)會話密鑰，大量的數(shù)據(jù)存儲和分配是一件很麻煩的事，在計(jì)算機(jī)網(wǎng)絡(luò)環(huán)境下顯的尤為突出。另外傳統(tǒng)密碼不易實(shí)現(xiàn)數(shù)字簽名，也進(jìn)一步限制了其發(fā)展。公開密鑰算法的提出公鑰密碼學(xué)是1976年由Diffie和Hellman在其“密碼學(xué)新方向”一文中提出的，見文

2、獻(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加密與解密由不同的密鑰完成 加密： 解密：知道加密算法，從加密密鑰得到解密密鑰在計(jì)算上是不可行的兩個(gè)密鑰中任何一個(gè)都可以作為加密而另一個(gè)用作解密（不是必須的）公開密鑰算法的基本要求基于公開密鑰的加密過程基于公開密鑰的鑒別過程用公鑰密碼實(shí)現(xiàn)鑒別 條件：兩個(gè)密鑰中任何一個(gè)都可以用作加密而另外一個(gè)用作解密鑒別： 鑒別保密 公開密鑰算

3、法公鑰算法的種類很多，具有代表性的三種密碼： 基于整數(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é)議背景密鑰分配人工手動分配密鑰: 問題 效率低成本高每個(gè)用戶要存儲與所有用戶通信的密鑰安全性差機(jī)器自動分配密鑰: 要

4、求任何兩個(gè)用戶能獨(dú)立計(jì)算他們之間的秘密密鑰傳輸量小存儲量小任何一個(gè)(或多個(gè))用戶不能計(jì)算出其他用戶之間的秘密密鑰單向陷門函數(shù)說明僅滿足(1)、(2)兩條的稱為單向函數(shù)；第(3)條稱為陷門性，z 稱為陷門信息當(dāng)用陷門函數(shù)f作為加密函數(shù)時(shí)，可將f公開，這相當(dāng)于公開加密密鑰，此時(shí)加密密鑰便稱為公開密鑰，記為Pkf函數(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在其里程碑意義的文章中，雖然給

5、出了密碼的思想，但是沒有給出真正意義上的公鑰密碼實(shí)例，也既沒能找出一個(gè)真正帶陷門的單向函數(shù)然而，他們給出單向函數(shù)的實(shí)例，并且基于此提出Diffie-Hellman密鑰交換算法Diffie-Hellman密鑰交換協(xié)議描述Alice和Bob協(xié)商好一個(gè)大素?cái)?shù)p，和大的整數(shù)g，1gp，g最好是FP中的本原元，即FP*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)

6、 (3) Alice將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é)商出會話密鑰,不需事先擁有對方的公開或秘密的信息.(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發(fā)給V的密文后,不傳給用戶V,而是解讀出明文后再將明文用W與V的密鑰加密后傳給V