第七章公開金鑰密碼系統(tǒng)

1、資訊與網(wǎng)路安全概論黃明祥、林詠章 著 The McGraw-Hill Companies, Inc., 2007國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論2007第 七 章公開金鑰密碼系統(tǒng)Public-Key Cryptosystems公開金鑰密碼系統(tǒng)國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論20072目錄7.1 公開金鑰基本概念7.2 RSA公開金鑰密碼機(jī)制7.3 ElGamal的公開金鑰密碼系統(tǒng)7.4 橢圓曲線密碼系統(tǒng)7.5 混合式的加密機(jī)制7.6 量子密碼學(xué)7.7 密碼系統(tǒng)的評估公開金鑰密碼系統(tǒng)國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論200737.1 公開金鑰基本概念p對稱式密碼系統(tǒng)有金鑰的管理問

2、題，例如要與 N 個(gè)人做秘密通訊，那麼就必須握有 N 把秘密金鑰nN 個(gè)人要互相通訊，共須 _ 把金鑰p為了改善對稱式密碼系統(tǒng)問題，於是便有公開金鑰密碼系統(tǒng) (Public-Key Cryptosystems) 的產(chǎn)生n1976年，史丹佛的 Diffie 及 Hellman 提出概念n1978年， MIT 的 Rivest, Shamir 及 Adleman 提出第一套安全的公開金鑰密碼系統(tǒng) RSA 公開金鑰密碼系統(tǒng)國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論20074Secret-Key Cryptosystemp祕密金鑰密碼系統(tǒng)(Secret-Key Cryptosystems) 單金鑰密碼系統(tǒng)

3、(One-Key Cryptosystems)對稱式密碼系統(tǒng)(Symmetric Cryptosystems)n優(yōu)點(diǎn)：加解密速度快n缺點(diǎn)：有金鑰管理的問題 每位使用者需儲(chǔ)存 n-1 把Keys 公開金鑰密碼系統(tǒng)國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論20075Public-Key Cryptosystemp公開金鑰密碼系統(tǒng)(Public-Key Cryptosystems) 雙金鑰密碼系統(tǒng)(Two-Key Cryptosystems)非對稱式密碼系統(tǒng)(Asymmetric Cryptosystems)n優(yōu)點(diǎn) 沒有金鑰管理的問題 只是不需要共享很多金鑰，還是有管理問題 高安全性 不能直接相比 有數(shù)

4、位簽章功能n缺點(diǎn) 加解密速度慢p著名之公開金鑰密碼系統(tǒng)：nRSA密碼系統(tǒng)nElGamal密碼系統(tǒng)公開金鑰密碼系統(tǒng)國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論20076CA明文加密解密明文密文密文明文解密加密明文密文密文張三張三s 私有金鑰李四李四s 私有金鑰李四李四s 公開金鑰張三張三s 公開金鑰SendSend金鑰公開金鑰密碼系統(tǒng) 加解密Private keyPublic key公開金鑰密碼系統(tǒng)國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論20077公開金鑰密碼系統(tǒng) 數(shù)位簽章p一般數(shù)位簽章 (Digital Signature) 具有下列功能：n鑑別性(Authentication)：可確認(rèn)文件來源的合法

5、性，而非經(jīng)他人偽造n完整性(Integrity)：可確保文件內(nèi)容不會(huì)被新增或刪除。n不可否認(rèn)性(Non-repudiation)：簽章者事後無法否認(rèn)曾簽署過此文件公開金鑰密碼系統(tǒng)國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論200787.2 RSA公開金鑰密碼機(jī)制p非對稱式密碼系統(tǒng)的一種。p1978年美國麻省理工學(xué)院三位教授Rivest、Shamir、 Adleman (RSA) 所發(fā)展出來的p利用公開金鑰密碼系統(tǒng)作為資料加密的方式，可達(dá)到資料加密及數(shù)位簽章的功能nEncryption : 明文加密使用區(qū)塊為每次加密的範(fàn)圍，使用密文接收者的公開金鑰 (Public Key) 將明文加密 將某長度以下的

6、二進(jìn)位碼當(dāng)作一個(gè)整數(shù)，進(jìn)行加密計(jì)算nDecryption : 必須使用密文接收者自己的私有金鑰 (Private Key) 才能將密文解出 (密文是以接收者的 Public Key 加密)公開金鑰密碼系統(tǒng)國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論200797.2.1 RSA 的加解密機(jī)制pRSA之安全性取決於質(zhì)因數(shù)分解之困難度要將很大的N因數(shù)分解成P跟Q之相乘，是很困難的1. 張三選 2 個(gè)大質(zhì)數(shù) p 和 q (至少至少100位數(shù)位數(shù))，令 N = p q2. 計(jì)算 (N)=(p-1)(q-1)，並任選 1 個(gè)與 (N) 的互質(zhì)數(shù) e3.計(jì)算 d，滿足 e d mod (N) = 1 4. 即為張

7、三的公開金鑰 加密法加密法為 C = Me mod N (注意：0 M N-1 )5. 即為張三的解密金鑰(亦稱私有金鑰或祕密金鑰) 解密法解密法為 M = Cd mod N公開金鑰密碼系統(tǒng)國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論2007101. 張三選 p=3 ， q=11 ; 此時(shí) N = p q = 3 x 11 = 332. 張三選出 1 個(gè)與 ( p-1 ) x ( q-1 ) = ( 3-1 )( 11-1 ) = 2 x 10 = 20互質(zhì)數(shù) e=33. ( e, N) = (3,33) 即為張三的公開金鑰4. 張三選 1 個(gè)數(shù) d=7 當(dāng)作解密金鑰，d 必須滿足 e d 1 mo

8、d 20 ( 7 x 3 1 mod 20 )令明文令明文 M = 19加密加密 : C = Me mod N = 193 mod 33 = 28解密解密 : M = Cd mod N = 287 mod 33 = 19RSA 演算法- 例子公開金鑰密碼系統(tǒng)國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論200711Eulers TheorempEuler通用定理通用定理: If gcd(a,N)=1, thenwhere ( ) called Euler phi function. n(N) ：與 N 互質(zhì)的正整數(shù)個(gè)數(shù) 1mod)(NaN定理: (P) = P-1 若P為質(zhì)數(shù) (N) = (PQ) =

9、 (P)(Q) = (P-1)(Q-1) 公開金鑰密碼系統(tǒng)國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論200712Why RSA is Correct?C = E(M) = Me mod N M = D(C) = Cd mod NCd=(Me)d=Med mod N since ed= 1 mod (p-1)(q-1)so Med = Ma(p-1)(q-1)+1 =MMa(p-1)(q-1) =MMa(N) mod NAccording to Eulers Theorem, we get M*1=M 公開金鑰密碼系統(tǒng)國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論200713RSA 之安全特性pRSA 具有

10、以下四個(gè)特性D(d, E(e, M) = M，可還原性d 和 e很容易求得若公開(e, N)，別人很難從(e, N)求得d，即只有自己知道如何解密(以e加密)E(e, D(d, M) = Mp13項(xiàng)為public-key cryptosystems之要求1.若同時(shí)滿足第4項(xiàng)要求，則該保密法可用來製作數(shù)位簽章公開金鑰密碼系統(tǒng)國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論200714S = Md張張mod N張張 M =? Se張張mod N張張張三使用自己的祕密金鑰對文件 M 做數(shù)位簽章S張三張三李四李四李四使用張三的公開金鑰確認(rèn)數(shù)位簽章及文件傳送M及S一般使用時(shí)會(huì)先將文件M作HASH函數(shù)處理，使得HA

11、SH(M)比N小7.2.2 RSA數(shù)位簽章公開金鑰密碼系統(tǒng)國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論200715數(shù)位簽章法(Digital Signature)SKa : User a 的 private keyPKa : User a 的 public key比較是否相等為M之簽章公開金鑰密碼系統(tǒng)國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論200716C = ( Md張張mod N張張 )e李李mod N李李M = ( Cd李李mod N李李)e張張mod N張張 張三對文件 M 做數(shù)位簽章後用李四的公用金鑰將簽章加密張三張三李四李四李四使用私有金鑰解開密文 C 再用張三的公開金鑰確認(rèn)數(shù)位簽章傳送密文

12、 CRSA 數(shù)位簽章+加密公開金鑰密碼系統(tǒng)國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論2007177.3 ElGamal 的公開金鑰密碼系統(tǒng)p非對稱式密碼系統(tǒng)的一種p1985年由 ElGamal 所發(fā)展出來的p安全性導(dǎo)因於離散對數(shù)(Discrete Logarithm)之困難度p相同明文可得到不相同的密文nRSA密碼系統(tǒng)則是相同明文得到相同密文pElGamal有訊息擴(kuò)充的問題，RSA機(jī)制則沒有此問題離散對數(shù)(Discrete Logarithm)的問題：若p為很大之質(zhì)數(shù)；g為p之原根 (primitive root) y = gx mod p雖已知y, g, p ，但要導(dǎo)出x值是很困難的 公開金鑰密

13、碼系統(tǒng)國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論200718張三將明文M以李四之公開金鑰加密：1. 張三選一個(gè)亂數(shù) r2. 計(jì)算 b = gr mod P c = M yr mod P3. 張三送(b,c)給李四李四之金鑰產(chǎn)生： y = gx mod Py為李四之公開金鑰x為李四之秘密金鑰P為很大之質(zhì)數(shù)g為與P互質(zhì)之原根4. 李四收到(b,c)後計(jì)算 c (bx)-1 mod P = M7.3.1 ElGamal 的加解密機(jī)制公開金鑰密碼系統(tǒng)國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論2007197.4 橢圓曲線密碼系統(tǒng)pRSA 或 ElGamal 密碼系統(tǒng)需要龐大的運(yùn)算量p為了改善其效率（較少之運(yùn)算量

14、），因此提出橢圓曲線的密碼系統(tǒng) (Elliptic Curve Cryptosystem, ECC)，它的安全性必須相當(dāng)於RSA或ElGamal的密碼系統(tǒng)n1024-bit RSA 安全性 = 160-bit ECC 安全性pECCn任取橢圓曲線上兩點(diǎn)，無論作加法、減法或乘法，其結(jié)果永遠(yuǎn)為有限座標(biāo)點(diǎn)中的一點(diǎn)n橢圓曲線中的離散對數(shù)難題： 給定一參數(shù)K及一點(diǎn)A，要求得另一點(diǎn) B 使得B=KA是很容易的。 但若給定A及B要求得K則很困難 y2=x3+ax+b公開金鑰密碼系統(tǒng)國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論2007207.5 混合式的加密機(jī)制p混合式加密機(jī)制顧名思義就是同時(shí)採用對稱式密碼機(jī)制及公

15、開金鑰密碼機(jī)制的加密系統(tǒng)，截長補(bǔ)短，使得它可以同時(shí)擁有這兩種密碼機(jī)制的優(yōu)點(diǎn)n對稱式：快速、大量資料的加密n非對稱式：安全、簡單的金鑰管理 公開金鑰密碼系統(tǒng)國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論200721Sender : AliceReceiver : BobC = ESK(M)密文密文V = EPU(SK)信封信封SK: Session Key(交談金鑰交談金鑰)ESK :秘密金鑰密碼系統(tǒng)秘密金鑰密碼系統(tǒng)(Key: SK) PU: Bob之公開金鑰之公開金鑰EPU :公開金鑰密碼系統(tǒng)公開金鑰密碼系統(tǒng)(Key: PU) PR: Bob之秘密金鑰之秘密金鑰M = DSK(C)明文明文SK = D

16、PR(V)交談金鑰交談金鑰密文及信封(C, V)7.5.1 數(shù)位信封(Digital Envelope)公開金鑰密碼系統(tǒng)國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論200722Diffie-Hellman 的金鑰協(xié)議方法p其安全性與 ElGamal 一樣植基於解離散對數(shù)的問題上p產(chǎn)生一樣的 session key (SK可作為後續(xù)DES加密用的金鑰) 已知對方的公開金鑰 擁有一樣的 p 與 g p 為很大之質(zhì)數(shù) g 為與 p 互質(zhì)之原根公開金鑰密碼系統(tǒng)國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論200723Diffie-Hellman 的金鑰交換方法pDiffie-Hellman Key Exchange

17、 Protocoln前提：如果對方的公開金鑰事先不知道n大量使用在現(xiàn)今各種安全協(xié)定上，例 SSL公開金鑰密碼系統(tǒng)國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論2007247.6 量子密碼學(xué)p前使用的密碼系統(tǒng)中，如DES、RSA、ElGamal或橢圓曲線密碼系統(tǒng)，其安全程度都僅屬於計(jì)算安全 (Computational Secure) 。p量子電腦的出現(xiàn)，使得現(xiàn)存的密碼系統(tǒng)都將不再安全n量子電腦 (Quantum Computer)是利用量子物理的法則所設(shè)計(jì)的一種電腦。n與傳統(tǒng)電腦最大的差別在於量子電腦可以同步地處理同一件工作，因此可大幅縮減在運(yùn)算上所需花費(fèi)的時(shí)間。n量子電腦的基本元素稱之為量子位元 (

18、Quantum Bits)，簡稱為qubits。p有機(jī)會(huì)利用量子電腦來發(fā)展出無條件安全的密碼系統(tǒng)公開金鑰密碼系統(tǒng)國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論200725量子密碼學(xué)p概念是利用光子的偏振方向來代表0或1。p偏震方向的定義有兩種，分別是直線方案 (Rectilinear)與斜線方案(Diagonal)。p直線方案中偏振方向|代表1，偏振方向代表0。p斜線方案中偏振方向代表1，偏振方向/代表0。p而用來測量偏振方向的偵測器也可分為兩種，分別為直線型，與斜線型， 型偵測器可用來判定|及偏振的光子；同理， 型偵測器可用來判定及/偏振的光子。n光子一經(jīng)測量，其偏振狀態(tài)即可能改變n因此光子無法被第

19、三者從中攔截複製 要複製須先測量，一測量，偏振就改變，接收端就會(huì)收到錯(cuò)誤資訊n可藉上述特性，使雙方在未受保護(hù)下協(xié)議出一次性密碼系統(tǒng)(One-Time Pad)的金鑰公開金鑰密碼系統(tǒng)國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論200726利用量子密碼進(jìn)行秘密通訊p春嬌隨意用直線或斜線方案來傳送一連串可代表0或1位元的光子給志明。p由於志明不知道春嬌依序用了哪些方案來傳送這些光子，故志明也隨意選用直線或斜線偵測器來測定光子的偏振方向。若志明所選的偵測器恰好與春嬌發(fā)送時(shí)所選用的方案一樣時(shí)，則志明可正確地測量出該光子是代表0或是1位元；反之，若選用的偵測器與春嬌發(fā)送時(shí)所選用的不一樣時(shí)，則有一半的機(jī)率可以正確

20、地猜出所要表示的位元。p春嬌與志明公開各自所使用的傳送方案順序。確認(rèn)哪些位元是判定正確的位元、哪些可能是誤判的位元(志明使用錯(cuò)誤方案的偵測器)公開金鑰密碼系統(tǒng)國立嘉義大學(xué) 資訊管理學(xué)系資訊安全概論200727p春嬌與志明核對完之後，他們捨去掉那些使用錯(cuò)誤偵測器所得到的位元，而保留用正確的偵測器所判定的位元。因此雙方可共同得到一段由正確判定位元所組成的加密金鑰。 p不過春嬌與志明所持有的這個(gè)加密金鑰也可能會(huì)有錯(cuò)誤，原因是在傳遞的過程中攻擊者還是有可能會(huì)進(jìn)行竊聽。春嬌與志明可以執(zhí)行一個(gè)簡單的錯(cuò)誤檢查協(xié)定，例如雙方所協(xié)議出來的金鑰長度共有1064個(gè)位元，春嬌就從中選取64個(gè)位元與志明做比對，若比對的結(jié)果有誤，就表示在傳送的過程中遭到監(jiān)聽，金鑰的協(xié)議需要重新來過；若無誤，則春嬌與志明大可相信他們手中的金鑰是一致的。p金鑰協(xié)議無誤後