密碼學 黃胤誠

OUTLINE 對稱與非對稱加密系統 應用最廣泛的加密系統 ── RSA 日常生活應用實例 SSL 電子投票 量子密碼學

對稱式系統 一對私密金鑰 通常是函數與反函數（雙向函數） 容易破解 Private key Private key A B

非對稱加密系統 兩把不同的鑰匙 單向函數的概念 私密金鑰 公開金鑰 知道公開金鑰無法在合理時間內求出私密金鑰

加密系統 ？ 使用對方的公開金鑰加密，只有對應的私密金鑰才能解密。 A B Public key B Private key B

數位簽章 並不是為了隱藏訊息 反相操作： A B 傳送者用secret key加密送出，接收者用public key解開。 Private key A Public key A A B

數位簽章能達到鑑定性、完整性和不可否認性 非對稱加密系統能達到秘密性和完整性 只有指定的接收者才能解開密文 經過加密解密的過程後，不會改變原文 每個人都能傳送密文，不知道是誰傳的 數位簽章能達到鑑定性、完整性和不可否認性 知道是什麼人傳的 每個人都能用傳送者的公開金鑰解開密文 同時達到秘密性、鑑定性、完整性和不可否認性？

混合式加密系統 Private Key A Public Key B A Private Key B Public Key A B

目前最常見的非對稱加密演算法 RSA

RSA 由 Rivest, Shamir, Adleman 三位MIT學者公開演算法，並取得專利權 應用：電子商務交易 軟體及硬體認證 智慧卡（smart card）

RSA － 原理 取兩個大質數 p, q N = pq Φ=(p-1)(q-1) 算出 N 和Φ就能把 p 和 q 丟棄 隨機產生 e 找出 e 的乘法反元素 d， 也就是 ed = 1 mod Φ

RSA － 原理 (con’d) Public key – (e, N) Secret key – (d, N) P是明文，C是密文 加密：C = Pe mod N 解密：P = Cd mod N = Ped mod N = P1 mod N 即使有e仍然無法在合理時間解出P！

RSA 原理 (con’d) 大質因數分解相當困難 只要p、q不差太多也不差太少 在合理的時間內無法解出 RSA 目前還是相當安全

知道了原理之後… 來賺錢吧！

RSA數 RSA security 公司懸賞的大數分解問題 N = pq 目前最大的數為RSA-2048 懸賞金額 US$200,000

RSA – 640 (193 decimal digits) (3107418240490043721350750035888567930037346022842727545 7201619488232064405180815045563468296717232867824379162 7283803341547107310850191954852900733772482278352574238 6454014691736602477652346609) = (1634733645809253848443133883865090859841783670033092312 181110852389333100104508151212118167511579) * (1900871281664822113126851573935413975471896789968515493 666638539088027103802104498957191261465571)

生活中看得到的實例

https (HTTP with SSL)

網路資料保密－SSL SSL ( Security Socket Layer ) 由 Netscape 提出的資料保密協定 可動態選擇加密的演算法（例如RSA） 提供保密和認證功能

SSL (con’d) 左圖為一般的 TCP/IP 架構，右圖則加入了一層SSL。 由應用層送出的資訊經SSL加密後，再送到傳輸層傳送。

SSL (con’d) A B 可選擇的演算法 得到演算法清單 確認演算法 決定演算法 得到公開金鑰 (B) 送出公開金鑰 (B) 隨機做出私密金鑰 以B的公開金鑰加密 收到私密金鑰 以A的公開金鑰加密 送出確認訊息 以私密金鑰進行安全的傳輸

另一個實例

身處電機系… 走在科技的尖端 系學會長選舉電子化 !! 在網路上就能投票？ 公正？安全？

電 子 投 票 傳 統 需滿足以下特性 合法性 隱私性 不可重複性 公正性 完整性 正確性 可驗證性 強固性

電子投票 (con’d) 機制相當複雜 目前研究出有許多理論都能達到上述要求 遲早會來的

現今相當熱門的研究主題 量子密碼學

量子電腦 量子物理被引入計算理論 未來可能發展出的量子電腦，擁有超強平行運算能力，效率大躍進 能夠輕易求解困難的數學問題 使用數學作為加密金鑰的方法不再安全

量子密碼學 因應對策－量子密碼學 不使用數學函式作為金鑰 使用量子物理的原理加密 比現在的密碼系碼更安全 問題的難度更困難

量子密碼學 (con’d) 利用光子偏振方向原理 一旦竊聽就會改變偏振方向 合法的接收者能發現是否被竊聽

參考資料 張真誠，韓亮，賴溪松，近代密碼學及其應用，松崗出版社，1998 http://www.rsasecurity.com/rsalabs/node.asp?id=2093 http://www.cs.nctu.edu.tw/~rjchen/crypto/chap5.ppt http://www.sciam.com.tw/read/readshow.asp?FDocNo=621&DocNo=997