第七章公开金钥密码系统

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

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

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

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

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

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

7、三的公開金鑰 加密法加密法為 C = Me mod N (注意：0 M N-1 )5. 即為張三的解密金鑰(亦稱私有金鑰或祕密金鑰) 解密法解密法為 M = Cd mod N公開金鑰密碼系統國立嘉義大學 資訊管理學系資訊安全概論2007101. 張三選 p=3 ， q=11 ; 此時 N = p q = 3 x 11 = 332. 張三選出 1 個與 ( p-1 ) x ( q-1 ) = ( 3-1 )( 11-1 ) = 2 x 10 = 20互質數 e=33. ( e, N) = (3,33) 即為張三的公開金鑰4. 張三選 1 個數 d=7 當作解密金鑰，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 演算法- 例子公開金鑰密碼系統國立嘉義大學 資訊管理學系資訊安全概論200711Eulers TheorempEuler通用定理通用定理: If gcd(a,N)=1, thenwhere ( ) called Euler phi function. n(N) ：與 N 互質的正整數個數 1mod)(NaN定理: (P) = P-1 若P為質數 (N) = (PQ) =

9、 (P)(Q) = (P-1)(Q-1) 公開金鑰密碼系統國立嘉義大學 資訊管理學系資訊安全概論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 公開金鑰密碼系統國立嘉義大學 資訊管理學系資訊安全概論200713RSA 之安全特性pRSA 具有

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

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

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

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

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

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

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

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

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

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

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