密码学理论基础.pptVIP

密碼學理論基礎Foundations of Cryptography 呂學一 (中央研究院 資訊科學所) .tw/~hil/ Today What is cryptography? Two approaches Three basic tools P, NP and BPP Part I : What is cryptography? Historically Before 1970 : Cryptography = design analysis of secure encryption scheme Goal : How to provide secret communication over insecure Illustration Alice要送一封信給Bob,但是Carol想要偷看,如何防止被偷看或偷聽則是1970年代之前,密碼學的重要課題. Historically After 1970 : (多加入下面兩個主題討論) Unforgeable signatures Fault-tolerant protocol Goal : design and analysis of a system that needs to withstand any malicious attempts in abusing it. Unforgeable signatures Unforgeable signatures包含兩個部分 Signature system (防內神) Message authentication (防外鬼) Signature system 的能力比Message authentication 還要強 Fault-tolerant protocol Fault-tolerant protocol有三個問題可以討論 Coin toss over phone (兩人在電話中,如何丟一公正錢幣) Simultaneous exchange of secrets (兩人如何能同時交換所持有的秘密,當一方反悔時,雙方皆無法成功取得對方的資料) Voting (如何可以秘密投票,讓別人都無法得知自己所投的內容,並能公正的開出正確的結果) Part II : Two approaches Security? How do we measure the “security” of a crypto system ? Two approaches Classic : information theory based Modern : complexity theory based Classic Classic : information theory based 目標 : perfect security, 使竊聽者絕對無法猜到plain text, 其描述為 : eavesdropper所能猜到的最好情況, 使 eavesdropper竊聽到 ciphertext之前和之後皆是相同情況. 若 key是random, 且長度和 plain text 等長或更長,且eavesdropper不知道key,則一定可以保證eavesdropper無法猜出原來的plain text. Question : key distribution problem Modern Modern : complexity theory based (退一步海闊天空) Impossible relax infeasible (on average) 描述 : 若eavesdropper要猜出來需要花極大的代價 Complexity based cryptography Putting computational limit on any REAL-LIFE adversaries. Example : RSA, base on 因數分解是很難的 Part III : Three basic tools Basic tools Three basic tools : One way function (OWF) –chapter 2 Pseudorandom generator (PRG) –chapter 3 Zero knowledge proof –chapter 4 One way function 由x到f(x)很容易,由f(x)回到x很難. Open problem : OWF exists? Pseudorandom generator 將seed 送進PRG,其所產生的結果和任意產生的數值無法區分. Open problem : PRG exists? Zero knowledge proof 當立法院質詢國防部(