信息系統(tǒng)安全與課件公鑰密碼學(xué)chap

1、 問題的提出問題的提出 問題的提出問題的提出4問題的提出問題的提出9.1.1 公鑰密碼機(jī)制公鑰密碼機(jī)制 公開密鑰算法是公開密鑰算法是非對稱算法非對稱算法，即密鑰分為公鑰和私鑰，因，即密鑰分為公鑰和私鑰，因此稱此稱雙密鑰體制雙密鑰體制 雙鑰體制的公鑰可以公開，因此也稱雙鑰體制的公鑰可以公開，因此也稱公鑰算法公鑰算法基于數(shù)學(xué)函數(shù)而不是代替和換位，基于數(shù)學(xué)函數(shù)而不是代替和換位，密碼學(xué)歷史上唯一的一密碼學(xué)歷史上唯一的一次真正的革命次真正的革命公鑰密碼學(xué)是公鑰密碼學(xué)是1976年由年由Diffie和和Hellman在其在其“密碼學(xué)新方密碼學(xué)新方向向”一文中提出的公鑰算法的出現(xiàn)，給密碼的發(fā)展開辟了一文中提出

2、的公鑰算法的出現(xiàn)，給密碼的發(fā)展開辟了新的方向。公鑰算法雖然已經(jīng)歷了新的方向。公鑰算法雖然已經(jīng)歷了2020多年的發(fā)展，但仍具多年的發(fā)展，但仍具有強(qiáng)勁的發(fā)展勢頭，在有強(qiáng)勁的發(fā)展勢頭，在鑒別系統(tǒng)和密鑰交換鑒別系統(tǒng)和密鑰交換等安全技術(shù)領(lǐng)等安全技術(shù)領(lǐng)域起著關(guān)鍵的作用域起著關(guān)鍵的作用9.1 公鑰密碼學(xué)及公鑰密碼體制基本原理公鑰密碼學(xué)及公鑰密碼體制基本原理從最初一直到現(xiàn)代，幾乎所有密碼系統(tǒng)都建立在基從最初一直到現(xiàn)代，幾乎所有密碼系統(tǒng)都建立在基本的本的替代和置換替代和置換工具的基礎(chǔ)上。工具的基礎(chǔ)上。在用了數(shù)千年的本質(zhì)上可以手算完成的算法之后，在用了數(shù)千年的本質(zhì)上可以手算完成的算法之后，常規(guī)的密碼學(xué)隨著常規(guī)的密

3、碼學(xué)隨著轉(zhuǎn)輪加密轉(zhuǎn)輪加密/解密機(jī)解密機(jī)的發(fā)展才出現(xiàn)的發(fā)展才出現(xiàn)了一個(gè)重大進(jìn)步。了一個(gè)重大進(jìn)步。機(jī)電式變碼旋轉(zhuǎn)軟件使得極其復(fù)雜的密碼系統(tǒng)被研機(jī)電式變碼旋轉(zhuǎn)軟件使得極其復(fù)雜的密碼系統(tǒng)被研制出來。有了計(jì)算機(jī)后，更加復(fù)雜的系統(tǒng)被設(shè)計(jì)出制出來。有了計(jì)算機(jī)后，更加復(fù)雜的系統(tǒng)被設(shè)計(jì)出來。來。但是不管是轉(zhuǎn)輪機(jī)還是后來的但是不管是轉(zhuǎn)輪機(jī)還是后來的DES（數(shù)據(jù)加密標(biāo)（數(shù)據(jù)加密標(biāo)準(zhǔn)），雖然代表了重要的進(jìn)展，卻仍然依賴于替代準(zhǔn)），雖然代表了重要的進(jìn)展，卻仍然依賴于替代和置換這樣的基本工具。和置換這樣的基本工具。密碼學(xué)歷史上唯一的一次真正的革命密碼學(xué)歷史上唯一的一次真正的革命7 公鑰密碼系統(tǒng)可用于以下三個(gè)方面：公鑰密碼

4、系統(tǒng)可用于以下三個(gè)方面： (1) 通信保密：此時(shí)將公鑰作為加密密鑰，私鑰作通信保密：此時(shí)將公鑰作為加密密鑰，私鑰作為解密密鑰，通信雙方不需要交換密鑰就可以實(shí)為解密密鑰，通信雙方不需要交換密鑰就可以實(shí)現(xiàn)保密通信。現(xiàn)保密通信。 Alice的公鑰Joy明文輸入 加密算法，如RSA傳輸密文解密算法明文輸出Alice的私鑰Bob的公鑰環(huán)TedAliceMike任何人向Alice發(fā)送信息都可以使用同一個(gè)密鑰(Alice的公鑰)加密沒有其他人可以得到Alice 的私鑰，所以只有Alice可以解密公鑰密碼體制的加密功能公鑰密碼體制的加密功能公鑰密碼體制的加密功能公鑰密碼體制的加密功能 Bob向向AliceAl

5、ice發(fā)消息發(fā)消息X， AliceAlice的公鑰為的公鑰為KUa,私鑰為私鑰為KRa 加密加密 Y = EKUa(X) 解密解密 X = DKRa(Y) 因?yàn)橹挥幸驗(yàn)橹挥蠥lice知道知道私鑰，所以其，所以其他人都無法解密。他人都無法解密。2022-2-24910(2) (2) 數(shù)字簽名：將私鑰作為加密密鑰，公鑰作為解數(shù)字簽名：將私鑰作為加密密鑰，公鑰作為解 密密鑰，可實(shí)現(xiàn)由一個(gè)用戶對數(shù)據(jù)加密而使多個(gè)密密鑰，可實(shí)現(xiàn)由一個(gè)用戶對數(shù)據(jù)加密而使多個(gè)用戶解讀。用戶解讀。Bob的公鑰Joy明文輸入 加密算法，如RSA傳輸密文解密算法明文輸出Bob的私鑰Alice的公鑰環(huán)TedBobMike公鑰密碼系統(tǒng)

6、的簽名公鑰密碼系統(tǒng)的簽名/認(rèn)證原理認(rèn)證原理Bob向向Alice 發(fā)送消息發(fā)送消息，用，用A的私鑰加密（的私鑰加密（簽名）簽名）Alice收到密文后，用收到密文后，用Bob的公鑰解密（驗(yàn)的公鑰解密（驗(yàn)證）證）公鑰密碼體制的認(rèn)證公鑰密碼體制的認(rèn)證 Bob向向Alice發(fā)送消息發(fā)送消息X Bob的公鑰為的公鑰為KUb，私鑰為，私鑰為KRb “加密加密”： Y = EKRb(X) （數(shù)字簽名）（數(shù)字簽名） “解密解密”： X = DKUb(Y) 因?yàn)榻?jīng)過因?yàn)榻?jīng)過Bob的秘密鑰加密，只有的秘密鑰加密，只有Bob才能才能做到。因此做到。因此Y可當(dāng)做可當(dāng)做Bob對消息對消息X的數(shù)字簽的數(shù)字簽名。名。另一方面

7、，任何人只要得不到另一方面，任何人只要得不到Bob的秘密鑰的秘密鑰就不能篡改就不能篡改Y，所以以上過程獲得了對消息，所以以上過程獲得了對消息來源和消息完整性的認(rèn)證。來源和消息完整性的認(rèn)證。2022-2-2412圖圖4-2 公鑰密碼體制認(rèn)證框圖公鑰密碼體制認(rèn)證框圖 加密算法解密算法發(fā)送者A接收者B密碼分析員(竊聽者)mAKScAPKASKm密鑰源2022-2-2413 在實(shí)際應(yīng)用中，特別是用戶數(shù)目很多時(shí)，以上在實(shí)際應(yīng)用中，特別是用戶數(shù)目很多時(shí)，以上認(rèn)證方法需要認(rèn)證方法需要很大的存儲空間很大的存儲空間，因?yàn)槊總€(gè)文件，因?yàn)槊總€(gè)文件都必須以明文形式存儲以方便實(shí)際使用，同時(shí)都必須以明文形式存儲以方便實(shí)際

8、使用，同時(shí)還必須存儲每個(gè)文件被加密后的密文形式即數(shù)還必須存儲每個(gè)文件被加密后的密文形式即數(shù)字簽字，以便在有爭議時(shí)用來認(rèn)證文件的來源字簽字，以便在有爭議時(shí)用來認(rèn)證文件的來源和內(nèi)容。和內(nèi)容。 改進(jìn)的方法是減小文件的數(shù)字簽字的大小，即改進(jìn)的方法是減小文件的數(shù)字簽字的大小，即先將文件經(jīng)過一個(gè)函數(shù)壓縮成長度較小的比特先將文件經(jīng)過一個(gè)函數(shù)壓縮成長度較小的比特串，得到的比特串稱為串，得到的比特串稱為認(rèn)證符認(rèn)證符。 認(rèn)證符具有這樣一個(gè)性質(zhì)：認(rèn)證符具有這樣一個(gè)性質(zhì)： 如果保持認(rèn)證符如果保持認(rèn)證符的值不變而修改文件這在計(jì)算上是不可行的。的值不變而修改文件這在計(jì)算上是不可行的。 用發(fā)送者的秘密鑰對認(rèn)證符加密，加密后

9、的結(jié)用發(fā)送者的秘密鑰對認(rèn)證符加密，加密后的結(jié)果為原文件的數(shù)字簽字。果為原文件的數(shù)字簽字。2022-2-2414 以上認(rèn)證過程中，由于消息是由用戶自己的秘以上認(rèn)證過程中，由于消息是由用戶自己的秘密鑰加密的，所以消息不能被他人篡改，但卻密鑰加密的，所以消息不能被他人篡改，但卻能被他人竊聽。這是因?yàn)槿魏稳硕寄苡糜脩舻哪鼙凰烁`聽。這是因?yàn)槿魏稳硕寄苡糜脩舻墓_鑰對消息解密。為了同時(shí)提供認(rèn)證功能和公開鑰對消息解密。為了同時(shí)提供認(rèn)證功能和保密性，可使用雙重加、解密。保密性，可使用雙重加、解密。2022-2-2415圖圖4.3 公鑰密碼體制的認(rèn)證、保密框圖公鑰密碼體制的認(rèn)證、保密框圖2022-2-2416

10、 發(fā)方首先用自己的發(fā)方首先用自己的私鑰私鑰SKA對消息對消息m加密，用加密，用于提供于提供數(shù)字簽名數(shù)字簽名。再用收方的。再用收方的公鑰公鑰PKB第第2次次加加密密，表示為，表示為c=EPKBESKAm 解密過程為解密過程為m=DPKADSKBc 即收方先用自己的即收方先用自己的私鑰私鑰,再用發(fā)方的再用發(fā)方的公鑰公鑰對收到對收到的密文兩次解密。的密文兩次解密。 鑒別保密鑒別保密 :():( )baabKUKRKUKRAB ZEEXB EEZX9.1.2 公鑰密碼的應(yīng)用公鑰密碼的應(yīng)用加密加密/解密解密數(shù)字簽名數(shù)字簽名密碼交換密碼交換 公鑰密鑰的應(yīng)用范圍公鑰密鑰的應(yīng)用范圍加密加密/解密：解密：數(shù)字簽

11、名數(shù)字簽名(身份鑒別身份鑒別)密鑰交換密鑰交換公鑰密鑰遭受窮舉攻擊，密碼越長越好；但為了加解密，公鑰密鑰遭受窮舉攻擊，密碼越長越好；但為了加解密，密鑰又要足夠短；因此公鑰密碼僅限于密鑰管理和簽名中密鑰又要足夠短；因此公鑰密碼僅限于密鑰管理和簽名中算法算法加加/解密解密 數(shù)字簽名數(shù)字簽名密鑰交換密鑰交換RSA是是是是是是Diffie-Hellman否否否否是是DSS否否是是否否對公鑰密碼算法的誤解對公鑰密碼算法的誤解 公開密鑰算法比對稱密鑰密碼算法更安全？公開密鑰算法比對稱密鑰密碼算法更安全？ 任何一種算法都依賴于密鑰長度、破譯密碼的工任何一種算法都依賴于密鑰長度、破譯密碼的工作量，從抗分析角度

12、，沒有一方更優(yōu)越作量，從抗分析角度，沒有一方更優(yōu)越 公開密鑰算法使對稱密鑰成為過時(shí)了的技術(shù)？公開密鑰算法使對稱密鑰成為過時(shí)了的技術(shù)？ 公開密鑰很慢，只能用在密鑰管理和數(shù)字簽名，公開密鑰很慢，只能用在密鑰管理和數(shù)字簽名，對稱密鑰密碼算法將長期存在對稱密鑰密碼算法將長期存在 使用公開密鑰加密，密鑰分配變得非常簡單？使用公開密鑰加密，密鑰分配變得非常簡單？ 事實(shí)上的密鑰分配既不簡單，也不有效事實(shí)上的密鑰分配既不簡單，也不有效5.1.3 公鑰密碼的要求公鑰密碼的要求 涉及到各方：發(fā)送方、接收方、攻擊者涉及到各方：發(fā)送方、接收方、攻擊者 涉及到數(shù)據(jù)：公鑰、私鑰、明文、密文涉及到數(shù)據(jù)：公鑰、私鑰、明文、密

13、文 公鑰算法的條件：公鑰算法的條件： 產(chǎn)生一對密鑰是產(chǎn)生一對密鑰是計(jì)算可行的計(jì)算可行的 已知公鑰和明文，產(chǎn)生密文是已知公鑰和明文，產(chǎn)生密文是計(jì)算可行的計(jì)算可行的 接收方利用私鑰來解密密文是接收方利用私鑰來解密密文是計(jì)算可行的計(jì)算可行的 對于攻擊者，利用公鑰來推斷私鑰是對于攻擊者，利用公鑰來推斷私鑰是計(jì)算不可行的計(jì)算不可行的 已知公鑰和密文，恢復(fù)明文是已知公鑰和密文，恢復(fù)明文是計(jì)算不可行的計(jì)算不可行的 (可選可選)加密和解密的順序可交換加密和解密的順序可交換Company Logo22 陷門單向函數(shù)陷門單向函數(shù)公鑰密碼系統(tǒng)是基于陷門單向函數(shù)的概公鑰密碼系統(tǒng)是基于陷門單向函數(shù)的概念。念。 單向函數(shù)

14、單向函數(shù)是是易于計(jì)算但求逆困難易于計(jì)算但求逆困難的函數(shù)的函數(shù)，而，而陷門單向函數(shù)陷門單向函數(shù)是在不知道陷門信息是在不知道陷門信息情況下求逆困難，而在知道陷門信息時(shí)情況下求逆困難，而在知道陷門信息時(shí)易于求逆的函數(shù)。易于求逆的函數(shù)。滿足上述條件找到單向陷門函數(shù)函數(shù)滿足上述條件找到單向陷門函數(shù)函數(shù) 滿足下列條件的函數(shù)滿足下列條件的函數(shù)f f： (1) 給定給定x，計(jì)算，計(jì)算y=f(x)是容易的是容易的 (2) 給定給定y, 計(jì)算計(jì)算x使使y=f(x)是困難的是困難的 (3) 存在存在z，已知，已知z 時(shí)時(shí), 對給定的任何對給定的任何y，若相應(yīng)的，若相應(yīng)的x存存 在，則計(jì)算在，則計(jì)算x使使y=f(x)

15、是容易的是容易的所謂計(jì)算所謂計(jì)算x= x= f-1(Y)(Y)困難是指計(jì)算上相當(dāng)復(fù)雜，已無困難是指計(jì)算上相當(dāng)復(fù)雜，已無實(shí)際意義實(shí)際意義尋找合適的單向陷門函數(shù)是公鑰密碼體制應(yīng)用的關(guān)鍵單向陷門函數(shù)舉例：單向陷門函數(shù)舉例：離散對數(shù)離散對數(shù)大整數(shù)分解大整數(shù)分解背包問題背包問題單向陷門函數(shù)說明單向陷門函數(shù)說明僅滿足僅滿足(1)、(2)兩條的稱為兩條的稱為單向函數(shù)單向函數(shù)；第；第(3)條稱為陷門性，條稱為陷門性，z 稱為稱為陷門信息陷門信息當(dāng)用陷門函數(shù)當(dāng)用陷門函數(shù)f作為加密函數(shù)時(shí)，可將作為加密函數(shù)時(shí)，可將f公開，這相當(dāng)于公開公開，這相當(dāng)于公開加密密鑰，此時(shí)加密密鑰便稱為公鑰，記為加密密鑰，此時(shí)加密密鑰便稱

16、為公鑰，記為Pkf函數(shù)的設(shè)計(jì)者將函數(shù)的設(shè)計(jì)者將陷門信息陷門信息z保密，用作解密密鑰，此時(shí)保密，用作解密密鑰，此時(shí)z稱為稱為秘密鑰匙，記為秘密鑰匙，記為Sk。由于設(shè)計(jì)者擁有。由于設(shè)計(jì)者擁有Sk，他自然可以解出，他自然可以解出x=f-1(y)單向陷門函數(shù)的第單向陷門函數(shù)的第(2)條性質(zhì)表明竊聽者由截獲的密文條性質(zhì)表明竊聽者由截獲的密文y=f(x)推測推測x是不可行的是不可行的對稱密碼對稱密碼 公鑰密碼公鑰密碼一般要求：1、加密解密用相同的密鑰和算法、加密解密用相同的密鑰和算法2、收發(fā)雙方必須共享密鑰、收發(fā)雙方必須共享密鑰安全性要求：1、密鑰必須保密、密鑰必須保密2、沒有密鑰，解密不可行、沒有密鑰，

17、解密不可行3、知道算法和若干密文不足以確定、知道算法和若干密文不足以確定密鑰密鑰一般要求：1、加密解密算法相同，但使用不同、加密解密算法相同，但使用不同的密鑰的密鑰2、發(fā)送方擁有加密或解密密鑰，而、發(fā)送方擁有加密或解密密鑰，而接收方擁有另一個(gè)密鑰接收方擁有另一個(gè)密鑰安全性要求：1、兩個(gè)密鑰之一必須保密、兩個(gè)密鑰之一必須保密2、無解密密鑰，解密不可行、無解密密鑰，解密不可行3、知道算法和其中一個(gè)密鑰以及若、知道算法和其中一個(gè)密鑰以及若干密文不能確定另一個(gè)密鑰干密文不能確定另一個(gè)密鑰9.2 RSA算法算法 RSA算法是算法是1978年由年由R.Rivest, A.Shamir和和L.Adleman

18、提出的一提出的一種用數(shù)論構(gòu)造的公鑰密碼體制，該體制已得到廣泛的應(yīng)用。種用數(shù)論構(gòu)造的公鑰密碼體制，該體制已得到廣泛的應(yīng)用。RivestShamirAdleman2002 Turing Award (June03)28RSARSA體制體制 最容易理解和實(shí)現(xiàn)的公鑰算法最容易理解和實(shí)現(xiàn)的公鑰算法; ; 經(jīng)受住了多年深入的攻擊經(jīng)受住了多年深入的攻擊; ; 其理論基礎(chǔ)是一種特殊的可逆模冪運(yùn)算，其其理論基礎(chǔ)是一種特殊的可逆模冪運(yùn)算，其安全性基于分解大整數(shù)的困難性；安全性基于分解大整數(shù)的困難性； RSARSA既可用于加密，又可用于數(shù)字簽名，已既可用于加密，又可用于數(shù)字簽名，已得到廣泛采用；得到廣泛采用； RS

19、ARSA已被許多標(biāo)準(zhǔn)化組織已被許多標(biāo)準(zhǔn)化組織( (如如ISOISO、ITUITU、IETFIETF和和SWIFTSWIFT等等) )接納；接納； 目前許多國家標(biāo)準(zhǔn)仍采用目前許多國家標(biāo)準(zhǔn)仍采用RSARSA或它的變型或它的變型 迄今為止理論上最為成熟完善的公鑰密碼體迄今為止理論上最為成熟完善的公鑰密碼體制，該體制已得到廣泛的應(yīng)用。制，該體制已得到廣泛的應(yīng)用。 大整數(shù)分解問題大整數(shù)分解問題：將兩個(gè)整數(shù)乘起來是簡單的，但：將兩個(gè)整數(shù)乘起來是簡單的，但是將一個(gè)整數(shù)分解為幾個(gè)整數(shù)的乘積是困難的，尤是將一個(gè)整數(shù)分解為幾個(gè)整數(shù)的乘積是困難的，尤其是當(dāng)這個(gè)數(shù)比較大的時(shí)候。迄今為止沒有有效的其是當(dāng)這個(gè)數(shù)比較大的時(shí)

20、候。迄今為止沒有有效的算法來解決這個(gè)問題，甚至我們連這個(gè)問題的計(jì)算算法來解決這個(gè)問題，甚至我們連這個(gè)問題的計(jì)算復(fù)雜度量級是多少都不知道。復(fù)雜度量級是多少都不知道。數(shù)論基礎(chǔ)數(shù)論基礎(chǔ) 同余同余 給定一個(gè)正整數(shù)m，如果兩個(gè)整數(shù)a和b滿足（a-b）能夠整除m，即（a-b）/m得到一個(gè)整數(shù)，那么就稱整數(shù)a與b對模m同余，記作ab(mod m)。對模m同余是整數(shù)的一個(gè)等價(jià)關(guān)系。數(shù)論基礎(chǔ)數(shù)論基礎(chǔ) 每個(gè)合數(shù)都可以唯一地分解出素?cái)?shù)因子每個(gè)合數(shù)都可以唯一地分解出素?cái)?shù)因子6 = 2 3999999 = 333711133727641 = 131121從從2 開始試驗(yàn)每一個(gè)小于等于開始試驗(yàn)每一個(gè)小于等于27641 的

21、素?cái)?shù)。的素?cái)?shù)。素?cái)?shù)：只能被素?cái)?shù)：只能被1和它本身整除的自然數(shù)；否則為合數(shù)。和它本身整除的自然數(shù)；否則為合數(shù)。整數(shù)整數(shù)n的十進(jìn)制位數(shù)的十進(jìn)制位數(shù) 因子分解的運(yùn)算次數(shù)因子分解的運(yùn)算次數(shù) 所需計(jì)算時(shí)間（每微秒一次）所需計(jì)算時(shí)間（每微秒一次）501.4x10103.9小時(shí)小時(shí)759.0 x1012104天天1002.3x101574年年2001.2x10233.8x109年年3001.5x10294.0 x1015年年5001.3x10394.2x1025年年數(shù)論基礎(chǔ)數(shù)論基礎(chǔ)數(shù)論基礎(chǔ)數(shù)論基礎(chǔ)mmmEuler 函數(shù)函數(shù)當(dāng)當(dāng)m是素?cái)?shù)時(shí)，小于是素?cái)?shù)時(shí)，小于m的所有整數(shù)均與的所有整數(shù)均與m互素，因此互素，因此

22、(m)=m-1對對m=pq, p和和q 是素?cái)?shù)，是素?cái)?shù)，(m)=(p)(q)=(p-1)(q-1)Euler 函數(shù)函數(shù)舉例舉例 設(shè)設(shè)p=3, q=5, 那么那么 （15）= （3）* * ( (5）=（3-1）* * （5-1） = =8 這這8個(gè)模個(gè)模15的剩余類是的剩余類是： 8個(gè)整數(shù)與個(gè)整數(shù)與15是互素的是互素的 1，2，4，7，8，11，13，14 對對 m = p q , p 和和 q 是 素 數(shù) ，是 素 數(shù) ，(m)=(p)(q)=(p-1)(q-1)例如：例如：20=225，有兩個(gè)素?cái)?shù)，有兩個(gè)素?cái)?shù)2和和5，這樣，這樣， (20) =20(1-1/2)(1-1/5)=8即即20中

23、有中有8個(gè)整數(shù)與個(gè)整數(shù)與20是互素的，即它們沒有是互素的，即它們沒有2或或5為因子：為因子：1, 3, 7, 9, 11, 13, 17, 19數(shù)論基礎(chǔ)數(shù)論基礎(chǔ)數(shù)論基礎(chǔ)數(shù)論基礎(chǔ)數(shù)論基礎(chǔ)數(shù)論基礎(chǔ)數(shù)論基礎(chǔ)數(shù)論基礎(chǔ)擴(kuò)展的歐幾里得算法求逆元擴(kuò)展的歐幾里得算法求逆元79*d mod 3220 = 1 （1）；或者79*d 1mod3220；或者d=79-1(mod3220)這里就要用到歐幾里得算法（又稱輾轉(zhuǎn)相除法），解法如下：（a）式子（1）可以表示成79*d-3220*k=1（其中k為正整數(shù)）；（b）將3220對79取模得到的余數(shù)60代替3220，則變?yōu)?9*d-60*k=1；（c）同理，將79對60

24、取模得到的余數(shù)19代替79，則變?yōu)?9*d-60*k=1；（d）同理，將60對19取模得到的余數(shù)3代替60，則變?yōu)?9*d-3*k=1；（e）同理，將19對3取模得到的余數(shù)1代替19，則變?yōu)閐-3*k=1；當(dāng)d的系數(shù)最后化為1時(shí)，令k=0，代入（e）式中，得d=1；將d=1代入（d）式，得k=6；將k=6代入（c）式，得d=19；將d=19代入（b）式，得k=25；將k=25代入（a）式，得d=1019，這個(gè)值即我們要求的私鑰d的最終值。此時(shí)，我們即可得到公鑰PK=（e，n）=79，3337，私鑰SK=1019，3337，后面的加密和解密直接套相應(yīng)公式即可。RSA算法的實(shí)現(xiàn)算法的實(shí)現(xiàn) 實(shí)現(xiàn)的步

25、驟如下：秘鑰產(chǎn)生實(shí)現(xiàn)的步驟如下：秘鑰產(chǎn)生 (1) Bob尋找出兩個(gè)大素?cái)?shù)尋找出兩個(gè)大素?cái)?shù)p和和q (2) Bob計(jì)算出計(jì)算出n=pq 和和(n)=(p-1)(q-1) (3) Bob選擇一個(gè)隨機(jī)數(shù)選擇一個(gè)隨機(jī)數(shù)e (0e (n)，滿足，滿足gcd(e,(n)=1 (4) Bob使用輾轉(zhuǎn)相除法計(jì)算使用輾轉(zhuǎn)相除法計(jì)算d=e-1(mod(n)，即，即ed 1(mod(p-1)(q-1) (5) Bob在目錄中（在目錄中（e,n)作為公鑰作為公鑰. （6）(d,n)或者或者d作為私鑰作為私鑰.密碼分析者攻擊密碼分析者攻擊RSA體制的關(guān)鍵點(diǎn)在于體制的關(guān)鍵點(diǎn)在于如何分解如何分解n。若分。若分解成功使解成功

26、使n=pq，則可以算出，則可以算出(n)（p-1)(q-1)，然后由公，然后由公開的開的e，解出秘密的，解出秘密的dRSA算法編制算法編制 參數(shù)參數(shù)T=NT=N；私鑰私鑰SK=SK= (d,n) ；公鑰公鑰PK=PK=（e,n) ； 設(shè)：明文設(shè)：明文M M，密文，密文C C，那么：，那么： 用公鑰作業(yè)：用公鑰作業(yè)：M Me e mod N = C mod N = C 用私鑰作業(yè)：用私鑰作業(yè)：C Cd d mod N = M mod N = MRSA Example1.Select primes: p=17 & q=112.Compute n = pq =1711=1873.Comput

27、e (n)=(p1)(q-1)=1610=1604.Select e : gcd(e,160)=1; choose e=75.Determine d: de=1 mod 160 and d 160 Value is d=23 since 237=161= 1160+16.Publish public key Kp=7,1877.Keep secret private key Ks=23,187RSA Example cont sample RSA encryption/decryption is: given message M = 88 (nb. 88187) encryption:C =

28、887 mod 187 = 11 decryption:M = 1123 mod 187 = 88 2022-2-24469.2.2 RSA算法中的計(jì)算問題算法中的計(jì)算問題1. RSA的加密與解密過程的加密與解密過程-求冪運(yùn)算求冪運(yùn)算RSA的加密、解密過程都為求一個(gè)整數(shù)的的加密、解密過程都為求一個(gè)整數(shù)的整數(shù)次冪，再取模。如果按其含義直接計(jì)算，整數(shù)次冪，再取模。如果按其含義直接計(jì)算，則中間結(jié)果非常大，有可能超出計(jì)算機(jī)所允許則中間結(jié)果非常大，有可能超出計(jì)算機(jī)所允許的整數(shù)取值范圍。如上例中解密運(yùn)算的整數(shù)取值范圍。如上例中解密運(yùn)算6677 mod 119，先求，先求6677再取模，則中間結(jié)果就已遠(yuǎn)遠(yuǎn)超

29、再取模，則中間結(jié)果就已遠(yuǎn)遠(yuǎn)超出了計(jì)算機(jī)允許的整數(shù)取值范圍。而用模運(yùn)算出了計(jì)算機(jī)允許的整數(shù)取值范圍。而用模運(yùn)算的性質(zhì)：的性質(zhì)：(ab) mod n=(a mod n)(b mod n) mod n 就可減小中間結(jié)果。就可減小中間結(jié)果。M Me e mod N = C mod N = C. 75 = 74.71 = 3.7 = 10 mod 112022-2-2447再者，考慮如何提高加、解密運(yùn)算中指數(shù)運(yùn)再者，考慮如何提高加、解密運(yùn)算中指數(shù)運(yùn)算的有效性。例如求算的有效性。例如求x16，直接計(jì)算的話需做，直接計(jì)算的話需做15次乘法。然而如果重復(fù)對每個(gè)部分結(jié)果做次乘法。然而如果重復(fù)對每個(gè)部分結(jié)果做平方

30、運(yùn)算即求平方運(yùn)算即求x，x2，x4，x8，x16則只需則只需4次乘次乘法。法。求求am可如下進(jìn)行，其中可如下進(jìn)行，其中a，m是正整數(shù)：是正整數(shù)： 將將m表示為二進(jìn)制形式表示為二進(jìn)制形式bk bk-1b0，即，即 m=bk2k+bk-12k-1+b12+b0 因此因此12012222kkkbbbbbmaaaaaa 2022-2-2448例如：例如：19=124+023+022+121+120，所以，所以a19=(a1)2a0)2a0)2a1)2a1從而可得以下快速指數(shù)算法：從而可得以下快速指數(shù)算法：c=0; d=1；For i=k downto 0 do c=2c;d=(dd) mod n;if

31、 bi =1 then c=c+1;d=(da) mod nreturn d.2022-2-24492. RSA密鑰的產(chǎn)生密鑰的產(chǎn)生 產(chǎn)生密鑰時(shí)，需要考慮產(chǎn)生密鑰時(shí)，需要考慮兩個(gè)大素?cái)?shù)兩個(gè)大素?cái)?shù)p、q的選取的選取，以及，以及e的選取和的選取和d的計(jì)算。的計(jì)算。 因?yàn)橐驗(yàn)閚=pq在體制中是公開的，因此為了防止敵在體制中是公開的，因此為了防止敵手通過窮搜索發(fā)現(xiàn)手通過窮搜索發(fā)現(xiàn)p、q，這，這兩個(gè)素?cái)?shù)兩個(gè)素?cái)?shù)應(yīng)是在一應(yīng)是在一個(gè)個(gè)足夠大足夠大的整數(shù)集合中選取的大數(shù)。如果選取的整數(shù)集合中選取的大數(shù)。如果選取p和和q為為10100左右的大素?cái)?shù)，那么左右的大素?cái)?shù)，那么n的階為的階為10200，每個(gè)明文分組可以

32、含有每個(gè)明文分組可以含有664位（位（102002664），），即即83個(gè)個(gè)8比特字節(jié)，這比比特字節(jié)，這比DES的數(shù)據(jù)分組（的數(shù)據(jù)分組（8個(gè)個(gè)8比比特字節(jié)）大得多，這時(shí)就能看出特字節(jié)）大得多，這時(shí)就能看出RSA算法的優(yōu)算法的優(yōu)越性了。因此越性了。因此如何有效地尋找大素?cái)?shù)是第一個(gè)如何有效地尋找大素?cái)?shù)是第一個(gè)需要解決的問題。需要解決的問題。2022-2-2450 尋找大素?cái)?shù)時(shí)一般是先尋找大素?cái)?shù)時(shí)一般是先隨機(jī)選取一個(gè)大的奇數(shù)隨機(jī)選取一個(gè)大的奇數(shù)（例如用偽隨機(jī)數(shù)產(chǎn)生器），然后用例如用偽隨機(jī)數(shù)產(chǎn)生器），然后用素性檢驗(yàn)算法素性檢驗(yàn)算法檢驗(yàn)這一奇數(shù)是否為素?cái)?shù)，如果不是則選取另一檢驗(yàn)這一奇數(shù)是否為素?cái)?shù)，如果不

33、是則選取另一大奇數(shù)，重復(fù)這一過程，直到找到素?cái)?shù)為止。大奇數(shù)，重復(fù)這一過程，直到找到素?cái)?shù)為止。 素性檢驗(yàn)算法通常都是概率性的，但如果算法被素性檢驗(yàn)算法通常都是概率性的，但如果算法被多次重復(fù)執(zhí)行，每次執(zhí)行時(shí)輸入不同的參數(shù)，算多次重復(fù)執(zhí)行，每次執(zhí)行時(shí)輸入不同的參數(shù)，算法的檢驗(yàn)結(jié)果都認(rèn)為被檢驗(yàn)的數(shù)是素?cái)?shù)，那么就法的檢驗(yàn)結(jié)果都認(rèn)為被檢驗(yàn)的數(shù)是素?cái)?shù)，那么就可以比較有把握地認(rèn)為被檢驗(yàn)的數(shù)是素?cái)?shù)?？梢员容^有把握地認(rèn)為被檢驗(yàn)的數(shù)是素?cái)?shù)。 可見尋找大素?cái)?shù)是一個(gè)比較繁瑣的工作。然而在可見尋找大素?cái)?shù)是一個(gè)比較繁瑣的工作。然而在RSA體制中，只有在產(chǎn)生新密鑰時(shí)才需執(zhí)行這一體制中，只有在產(chǎn)生新密鑰時(shí)才需執(zhí)行這一工作。工作

34、。 p和和q決定出后，下一個(gè)需要解決的問題是如何決定出后，下一個(gè)需要解決的問題是如何選取滿足選取滿足1e(n)和和gcd(n),e)=1的的e，并計(jì)算，并計(jì)算滿足滿足de1 mod (n)的的d。這一問題可由推廣的。這一問題可由推廣的Euclid算法完成。算法完成。RSA 的安全性的安全性 三種三種攻擊攻擊 RSA的方法的方法: 1，強(qiáng)力窮舉密鑰，強(qiáng)力窮舉密鑰:嘗試所有可能的密鑰。因此，嘗試所有可能的密鑰。因此，e 和和d 的位數(shù)越大，算法就越安全的位數(shù)越大，算法就越安全。然而，在密鑰。然而，在密鑰產(chǎn)生和加密解密中使用的計(jì)算都非常復(fù)雜，所以產(chǎn)生和加密解密中使用的計(jì)算都非常復(fù)雜，所以密鑰越大，系

35、統(tǒng)運(yùn)行越慢。密鑰越大，系統(tǒng)運(yùn)行越慢。 2，時(shí)間攻擊：依賴，時(shí)間攻擊：依賴解密算法的運(yùn)行時(shí)間解密算法的運(yùn)行時(shí)間，利用，利用CPU處理某些特殊的模乘比較慢的規(guī)律來確定每處理某些特殊的模乘比較慢的規(guī)律來確定每一位指數(shù)一位指數(shù)RSA 的安全性的安全性 3，數(shù)學(xué)攻擊數(shù)學(xué)攻擊 ：實(shí)質(zhì)上是對兩個(gè)素?cái)?shù)乘積的分：實(shí)質(zhì)上是對兩個(gè)素?cái)?shù)乘積的分解解. RSA的安全性是基于大整數(shù)素因子分解的困的安全性是基于大整數(shù)素因子分解的困難性，難性，而大整數(shù)因子分解問題是數(shù)學(xué)上的著名而大整數(shù)因子分解問題是數(shù)學(xué)上的著名難題，至今沒有有效的方法予以解決，因此可難題，至今沒有有效的方法予以解決，因此可以確保以確保RSA算法的安全性?，F(xiàn)在

36、，人們已能分算法的安全性?，F(xiàn)在，人們已能分解多個(gè)十進(jìn)制位的大素?cái)?shù)。因此，解多個(gè)十進(jìn)制位的大素?cái)?shù)。因此，模數(shù)模數(shù)n 必須必須選大一些選大一些，因具體適用情況而定。目前，人們，因具體適用情況而定。目前，人們已能分解已能分解140多個(gè)十進(jìn)制位的大素?cái)?shù)，這就要多個(gè)十進(jìn)制位的大素?cái)?shù)，這就要求使用更長的密鑰，速度更慢。求使用更長的密鑰，速度更慢。 RSA算法的安全性分析算法的安全性分析密碼分析者攻擊密碼分析者攻擊RSA體制的關(guān)鍵點(diǎn)在于體制的關(guān)鍵點(diǎn)在于如何分解如何分解n若分解成功使若分解成功使n=pq，則可以算出，則可以算出(n)（p-1)(q-1)，然后由公開的然后由公開的e，解出秘密的，解出秘密的d若使

37、若使RSA安全，安全，p與與q必為足夠大的素?cái)?shù)，使分析者必為足夠大的素?cái)?shù)，使分析者沒有辦法在多項(xiàng)式時(shí)間內(nèi)將沒有辦法在多項(xiàng)式時(shí)間內(nèi)將n分解出來分解出來RSA算法的安全性分析算法的安全性分析建議選擇建議選擇p和和q大約是大約是100位的十進(jìn)制素?cái)?shù)位的十進(jìn)制素?cái)?shù)模模n的長度要求至少是的長度要求至少是512比特比特，EDI攻擊標(biāo)準(zhǔn)使用的攻擊標(biāo)準(zhǔn)使用的RSA算法中規(guī)定算法中規(guī)定n的長度為的長度為512至至1024比特位之間，但比特位之間，但必須是必須是128的倍數(shù)的倍數(shù)國際數(shù)字簽名標(biāo)準(zhǔn)國際數(shù)字簽名標(biāo)準(zhǔn)ISO/IEC 9796中規(guī)定中規(guī)定n的長度位的長度位512比比特位特位RSA算法的安全性分析算法的安全

38、性分析 為了抵抗現(xiàn)有的整數(shù)分解算法，對為了抵抗現(xiàn)有的整數(shù)分解算法，對RSA模模n的素因子的素因子p和和q還有如下要求：還有如下要求： (1) |p-q|很大，通常很大，通常 p和和q的長度相同；的長度相同； (2) p-1 和和q-1分別含有大素因子分別含有大素因子p1和和q1 (3) P1-1和和q1-1分別含有大素因子分別含有大素因子p2和和q2 (4) p+1和和q+1分別含有大素因子分別含有大素因子p3和和q3RSA算法的安全性分析算法的安全性分析為了提高加密速度，通常取為了提高加密速度，通常取e為特定的小整數(shù)為特定的小整數(shù)如如EDI國際標(biāo)準(zhǔn)中規(guī)定國際標(biāo)準(zhǔn)中規(guī)定 e 2161ISO/I

39、EC9796中甚至允許取中甚至允許取e3這時(shí)加密速度一般比解密速度快這時(shí)加密速度一般比解密速度快10倍以上倍以上RSA的速度的速度由于進(jìn)行的都是大數(shù)計(jì)算，使得RSA最快的情況也比DES慢上100倍，無論是軟件還是硬件實(shí)現(xiàn)。速度一直是RSA的缺陷。一般來說只用于少量數(shù)據(jù)加密。RSA的缺點(diǎn)的缺點(diǎn)A)產(chǎn)生密鑰很麻煩，受到素?cái)?shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密。B)分組長度太大。C)為保證安全性，n 至少也要 600 bits以上，使運(yùn)算代價(jià)很高，尤其是速度較慢，較對稱密碼算法慢幾個(gè)數(shù)量級；且隨著大數(shù)分解技術(shù)的發(fā)展，這個(gè)長度還在增加，不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化。D)目前，SET(Secure Elect

40、ronic Transaction)協(xié)議中要求CA采用2048比特長的密鑰，其他實(shí)體使用1024比特的密鑰。大素?cái)?shù)產(chǎn)生大素?cái)?shù)產(chǎn)生 素?cái)?shù)生成過程素?cái)?shù)生成過程: 隨機(jī)選擇一個(gè)奇數(shù)隨機(jī)選擇一個(gè)奇數(shù)n(如通過偽隨機(jī)數(shù)發(fā)生器如通過偽隨機(jī)數(shù)發(fā)生器) 隨機(jī)選擇隨機(jī)選擇a, 使使an 進(jìn)行素性測試進(jìn)行素性測試(例如用例如用Miller-Rabin算法算法),若若n沒有通過沒有通過測試測試,拋棄拋棄n,轉(zhuǎn)到轉(zhuǎn)到 如果通過了足夠次數(shù)的測試如果通過了足夠次數(shù)的測試,認(rèn)為認(rèn)為n是素?cái)?shù)。是素?cái)?shù)。 素?cái)?shù)理論素?cái)?shù)理論: 在在N附近，每附近，每ln(N)個(gè)整數(shù)中有一個(gè)素?cái)?shù)個(gè)整數(shù)中有一個(gè)素?cái)?shù)補(bǔ)充補(bǔ)充 反復(fù)平方乘反復(fù)平方乘例如：

41、例如：5*20=95，367，431，640，625=25 mod35；原理：如原理：如20=10100（0，1，10，101，1010，10100）=（0，1，2，5，10，20）1=0*2+1；2=1*2；5=2*2+1；10=5*2；20=10*2；10 2121 2252 212105 222010 225(5 )55mod355(5)525mod355(5 )5255 3125 10mod355(5 )10100 30mod355(5 )30900 25mod35 人物說明 Euler Leonhard (1707-1783) 歐拉，萊奧哈爾德：歐拉，萊奧哈爾德：(1707-1783

42、) 瑞士數(shù)學(xué)家，尤其他對瑞士數(shù)學(xué)家，尤其他對微積分的開創(chuàng)性貢獻(xiàn)，以及他的復(fù)數(shù)、對數(shù)、三角函數(shù)和微積分的開創(chuàng)性貢獻(xiàn)，以及他的復(fù)數(shù)、對數(shù)、三角函數(shù)和月球運(yùn)動(dòng)等理論而聞名于世月球運(yùn)動(dòng)等理論而聞名于世物理學(xué)家物理學(xué)家. Fer.mat Pierre de (1601-1665) 費(fèi)馬，皮爾費(fèi)馬，皮爾德：德：(1601-1665) 法國數(shù)學(xué)家，他有系統(tǒng)地闡法國數(shù)學(xué)家，他有系統(tǒng)地闡述了現(xiàn)代數(shù)理論和概率論述了現(xiàn)代數(shù)理論和概率論. Euclid歐幾里得歐幾里得(約公元前約公元前3世紀(jì)的古希臘數(shù)學(xué)家世紀(jì)的古希臘數(shù)學(xué)家) 他把邏輯學(xué)中他把邏輯學(xué)中的演繹原理應(yīng)用到幾何學(xué)中，籍以由定義明確的公理導(dǎo)出的演繹原理應(yīng)用到幾

43、何學(xué)中，籍以由定義明確的公理導(dǎo)出語句語句.離散對數(shù)公鑰加密算法：離散對數(shù)公鑰加密算法：自閱自閱是目前最為熱門的公鑰加密算法是目前最為熱門的公鑰加密算法，其安全性要遠(yuǎn)遠(yuǎn)，其安全性要遠(yuǎn)遠(yuǎn)高于基于大數(shù)分解的高于基于大數(shù)分解的RSA算法。安全性依賴于離散算法。安全性依賴于離散對數(shù)難解問題：對數(shù)難解問題：離散對數(shù)問題可以描述為：給定一個(gè)質(zhì)數(shù)p，和有限域Zp上的一個(gè)本原元a，對Zp上整數(shù)b，尋找唯一的整數(shù)c，使得acb(mod p)。一般的，如果仔細(xì)選擇p，則認(rèn)為該問題是難解的，且目前還沒有找到計(jì)算離散對數(shù)問題的多項(xiàng)式時(shí)間算法。為了抵抗已知的攻擊，p至少應(yīng)該是150位的十進(jìn)制整數(shù)，且p-1至少有一個(gè)大的素

44、數(shù)因子。下面是一個(gè)使用離散對數(shù)的例子：Alice和Bob首先商議好p的值，本例假設(shè)為p=2579，則本原元為a=2。假設(shè)Alice要發(fā)送消息x =1299給Bob，則1）Bob選擇隨機(jī)數(shù)r=765作為自己的私鑰，計(jì)算q=2r mod p=2756 mod 2579=949，作為公鑰給Alice；2）Alice選擇隨機(jī)數(shù)k =853，計(jì)算y=2k mod p=2853 mod 2579=435，作為公鑰給Bob；3）Alice計(jì)算密文e =x*qk mod p=1299*949853 mod 2579=2396，并傳遞給Bob；4）Bob接收到密文后，計(jì)算x =e*(yr)(-1) mod p=

45、2396*(435765)(-1) mod 2579=1299，從而得到原文。5.4 Diffie-Hellman密鑰交換算法密鑰交換算法Diffie和和Hellman在其里程碑意義的文章中，雖然給出在其里程碑意義的文章中，雖然給出了密碼的思想，但是沒有給出真正意義上的公鑰密碼了密碼的思想，但是沒有給出真正意義上的公鑰密碼實(shí)例，也既沒能找出一個(gè)真正帶實(shí)例，也既沒能找出一個(gè)真正帶陷門陷門的單向函數(shù)的單向函數(shù)然而，他們給出單向函數(shù)的實(shí)例，并且基于此提出然而，他們給出單向函數(shù)的實(shí)例，并且基于此提出Diffie-Hellman密鑰交換算法密鑰交換算法 Diffie-Hellman密鑰交換密鑰交換 允許

46、兩個(gè)用戶可以安全地交換一個(gè)秘密信息，用于后續(xù)的允許兩個(gè)用戶可以安全地交換一個(gè)秘密信息，用于后續(xù)的通訊過程通訊過程 算法的安全性依賴于計(jì)算離散對數(shù)的難度算法的安全性依賴于計(jì)算離散對數(shù)的難度素?cái)?shù)素?cái)?shù)p的原始根定義：如果的原始根定義：如果a是素?cái)?shù)是素?cái)?shù)p的原始根，則數(shù)的原始根，則數(shù)a mod p, a2 mod p, , ap-1 mod p是不同的并且包含是不同的并且包含1到到p-1的整數(shù)的某種排列。的整數(shù)的某種排列。對任意的整數(shù)對任意的整數(shù)b，我們可以找到唯一的冪，我們可以找到唯一的冪i滿足滿足b=ai mod p 0=i=(p-1)指數(shù)指數(shù)i 稱為稱為b的以的以a為底為底 (或基或基)的模的模

47、p離散對數(shù)離散對數(shù) 。記為。記為dloga,p(b)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ǎng)絡(luò)上的所有用戶共享無須保密，可為網(wǎng)絡(luò)上的所有用戶共享 。Diffie-Hellman密鑰交換協(xié)議描述密鑰交換協(xié)議描述當(dāng)當(dāng)Alice和和Bob要進(jìn)行保密通信時(shí)，他們可以按如下步驟來要進(jìn)行保密通信時(shí)，他們可以按如下步驟來做：做： (1) Alice選取大的隨機(jī)數(shù)選取大的隨機(jī)數(shù)x，并計(jì)算，并計(jì)算 X = g

48、x(mod P) (2) Bob選取大的隨機(jī)數(shù)選取大的隨機(jī)數(shù)x ，并計(jì)算，并計(jì)算 X = gx (mod P) (3) Alice將將X傳送給傳送給Bob；Bob將將X 傳送給傳送給Alice (4) Alice計(jì)算計(jì)算K= (X )X(mod P); Bob計(jì)算計(jì)算K =（X) X (mod P), 易見，易見，K = K =g xx (mod P)由由(4)知，知，Alice和和Bob已獲得了相同的秘密值已獲得了相同的秘密值K雙方以雙方以K作為加解密鑰以傳統(tǒng)對稱密鑰算法進(jìn)行保密通信作為加解密鑰以傳統(tǒng)對稱密鑰算法進(jìn)行保密通信 Generate randomXa pCalculateYa=aX

49、a mod pGenerate randomXb pCalculateYb=aXb mod pUser AUser BYaYbCalculateK=(Yb)Xa mod pCalculateK=(Ya)Xb mod pDiffie-Hellman Key ExchangeDiffie-Hellman安全性安全性離散對數(shù)的計(jì)算離散對數(shù)的計(jì)算:y gx mod p 已知已知g,x,p,計(jì)算計(jì)算y是容易的是容易的 已知已知y,g,p,計(jì)算計(jì)算x是困難的是困難的 Diffie-Hellman密鑰交換的攻擊密鑰交換的攻擊 replay攻擊攻擊中間人攻擊圖示中間人攻擊圖示ABK = aXaXbOABK =

50、 aXaXoOK = aXbXo Diffie-Hellman密鑰交換的攻擊密鑰交換的攻擊中間人攻擊中間人攻擊1 雙方選擇素?cái)?shù)雙方選擇素?cái)?shù)p以及以及p的一個(gè)原根的一個(gè)原根a(假定假定O知道知道)2 A選擇選擇Xap,計(jì)算計(jì)算Ya=aXa mod p, AB: Ya3 O截獲截獲Ya,選選Xo,計(jì)算計(jì)算Yo=aXo mod p,冒充冒充AB:Yo4 B選擇選擇Xbp,計(jì)算計(jì)算Yb=aXb mod p, BA: Yb5 O截獲截獲Yb,冒充冒充BA:Yo6 A計(jì)算計(jì)算: (Xo)Xa (aXo)Xa aXoXa mod p7 B計(jì)算計(jì)算: (Xo)Xb (aXo)XXb aXoXb mod p8

51、O計(jì)算計(jì)算: (Ya)Xo aXaXo mod p, (Yb)Xo aXbXo mod pO無法計(jì)算出無法計(jì)算出aXaXb mod pO永遠(yuǎn)必須實(shí)時(shí)截獲并冒充轉(zhuǎn)發(fā)永遠(yuǎn)必須實(shí)時(shí)截獲并冒充轉(zhuǎn)發(fā),否則會被發(fā)現(xiàn)否則會被發(fā)現(xiàn) 防范措施防范措施 1，使用共享的對稱密鑰加密，使用共享的對稱密鑰加密DH交換；交換； 2，使用公鑰加密，使用公鑰加密DH交換；交換； 3，使用私鑰簽名，使用私鑰簽名DH交換；交換； 經(jīng)典例子經(jīng)典例子 Diffie-Hellman密鑰交換算法密鑰交換算法 背包算法背包算法 RSA算法算法 橢圓曲線密碼算法橢圓曲線密碼算法ECC5.5 橢圓曲線密碼介紹橢圓曲線密碼介紹 在在2005年年

52、2月月16日，日，NSA宣布決定采用橢圓曲線密宣布決定采用橢圓曲線密碼的戰(zhàn)略作為美國政府標(biāo)準(zhǔn)的一部分，用來保護(hù)碼的戰(zhàn)略作為美國政府標(biāo)準(zhǔn)的一部分，用來保護(hù)敏感但不保密的信息。敏感但不保密的信息。NSA推薦了一組被稱為推薦了一組被稱為Suit B的算法，包括用來密鑰交換的的算法，包括用來密鑰交換的Menezes-Qu-Vanstone橢圓曲線和橢圓曲線和Diffie-Hellman橢圓曲線，用橢圓曲線，用來數(shù)字簽名的橢圓曲線數(shù)字簽名算法。這一組中來數(shù)字簽名的橢圓曲線數(shù)字簽名算法。這一組中也包括也包括AES和和SHA。 5.5 橢圓曲線密碼介紹橢圓曲線密碼介紹 1985年年Miller,Koblit

53、z 獨(dú)立提出獨(dú)立提出y2+axy+by=x3+cx2+dx+e 曲線上的點(diǎn)連同曲線上的點(diǎn)連同無窮遠(yuǎn)點(diǎn)無窮遠(yuǎn)點(diǎn)O的集合的集合(定義見下頁）定義見下頁） 運(yùn)算定義：運(yùn)算定義： 若曲線三點(diǎn)在一條直線上若曲線三點(diǎn)在一條直線上,則其和為則其和為O O用作加法的單位：用作加法的單位：O = -O; P+O = P 一條豎直線交一條豎直線交X軸兩點(diǎn)軸兩點(diǎn)P1、P2，則，則P1+P2+O=O，于是，于是P1 = -P2 如果兩個(gè)點(diǎn)如果兩個(gè)點(diǎn)Q和和R的的X軸不同，則畫一連線，得到第三點(diǎn)軸不同，則畫一連線，得到第三點(diǎn)P1，則，則Q+R+P1=O，即，即Q+R=-P1 2倍，一個(gè)點(diǎn)倍，一個(gè)點(diǎn)Q的兩倍是，找到它的切線

54、與曲線的另一個(gè)的兩倍是，找到它的切線與曲線的另一個(gè)交點(diǎn)交點(diǎn)S，于是，于是Q+Q=2Q=-S (1) 無窮遠(yuǎn)元素（無窮遠(yuǎn)點(diǎn)，無窮遠(yuǎn)直線）無窮遠(yuǎn)元素（無窮遠(yuǎn)點(diǎn)，無窮遠(yuǎn)直線） 平面上任意兩相異直線的位置關(guān)系有相交和平行兩種平面上任意兩相異直線的位置關(guān)系有相交和平行兩種。引入無窮遠(yuǎn)點(diǎn)，是兩種不同關(guān)系統(tǒng)一。引入無窮遠(yuǎn)點(diǎn)，是兩種不同關(guān)系統(tǒng)一。 ABL1， L2L1，直線直線AP由由AB起繞起繞A點(diǎn)依逆時(shí)針方向轉(zhuǎn)點(diǎn)依逆時(shí)針方向轉(zhuǎn)動(dòng)，動(dòng)，P為為AP與與L1的交點(diǎn)。的交點(diǎn)。L2L1PBAPQQ=BAP /2 AP L2可設(shè)想可設(shè)想L1上有一點(diǎn)上有一點(diǎn)P，它為，它為L2和和L1的交點(diǎn)，稱之為的交點(diǎn)，稱之為。直線直

55、線L1上的無窮遠(yuǎn)點(diǎn)只能有一個(gè)。上的無窮遠(yuǎn)點(diǎn)只能有一個(gè)。（因?yàn)檫^（因?yàn)檫^A點(diǎn)只能有一條平行于點(diǎn)只能有一條平行于L1的直線的直線L2，而兩直線的交點(diǎn)，而兩直線的交點(diǎn)只能有一個(gè)。）只能有一個(gè)。）結(jié)論：結(jié)論：1*. 平面上一組相互平行的直線，有公共的無窮遠(yuǎn)點(diǎn)。平面上一組相互平行的直線，有公共的無窮遠(yuǎn)點(diǎn)。（為與無窮遠(yuǎn)點(diǎn)相區(qū)別，把原來平面上的點(diǎn)叫做（為與無窮遠(yuǎn)點(diǎn)相區(qū)別，把原來平面上的點(diǎn)叫做）2* .平面上任何相交的兩直線平面上任何相交的兩直線L1,L2有不同的無窮遠(yuǎn)點(diǎn)。有不同的無窮遠(yuǎn)點(diǎn)。原因：若否，則原因：若否，則L1和和L2有公共的無窮遠(yuǎn)點(diǎn)有公共的無窮遠(yuǎn)點(diǎn)P，則過兩相異點(diǎn)，則過兩相異點(diǎn)A和和P 有相異兩直線，與公理相矛盾。有相異兩直線，與公理相矛盾。 橢圓曲線密碼示意圖橢圓曲線密碼示意圖 有限域上橢圓曲線有限域上橢圓曲線有限域上橢圓曲線有限域上橢圓曲線y2 x3+ax+b mod p p是奇素?cái)?shù)是奇素?cái)?shù),且且4a3+27b2 0 mod p針對所有的針對所有的0= x p