密码学(Cryptography)

所需积分/C币:8 2018-10-14 12:11:36 834KB PDF

分析哈希,对称、非对称加密,零知识证明等密码学算法的理论安全保证。斯坦福大学课程讲义(154页)。
i Contents Foreword 1 Introduction 1.1 Alice. Bob. Eve, and the others 1.2 The Pre-history of Encryption 1.3 Perfect Security and One-Time Pad 2 Notions of Security 2577 1 Semantic Security 2.2 Security for Multiple Encryptions: Plain Version 12 2.3 Sccurity against Choscn Plaintext Attack 13 3 Pseudorandom generators 15 3.1 Pseudorandom Generators And One-Time Encryption 15 3.2 Description of RC1 18 4 Encryption Using Pseudorandom Functions 21 4.1 Pseudorandom functions 4.2 Encryption Using Pseudorandom Functions 4.3 The Randomized Counter Mode 24 5 Encryption Using Pseudorandom Permutations 27 5.1 Pseudorandom permutations 27 5.1.1 Some Motivation 27 5.1.2 Definition 27 5.2 The AES Pseudorandom Permutation 28 5.3 Encryption Using Pseudorandom Permutations CONTENTS 5.3.1 ECB Mode 29 5.3.2 CBC Mode 6 Authentication 31 6.1 Message Authentication 6.2 Construction for short messages 32 6.3 Construction for Messages of Arbitrary Length 33 7 CCA-Secure Encryption 37 7.1 CBC-MAC 37 7.2 Combining MAC and Encryption 8 Collision -Resistant hash Functions 43 8.1 Combining Encryption and Authentication 43 8.1.1 Encrypt-Then-Authenticate 43 8.1.2 Encrypt-And-Authenticate 8.1.3 Authenticate-Then-Encrypt 44 8.2 Cryptographic Hash Functions 8.2.1 Definition and birthday attack 8.2.2 The Merkle-Damgard Transform 47 8. 3 Hash Functions and Authentication 9 One-Way Functions and Hardcore Predicates 51 9.1 One-way Functions and One-way permutations 52 9.2 A Preview of what is Ahead 9.3 Hard-Core Predicate 54 9. 4 The goldreich-Levin theorem 9.5 The Goldreich-Levin Algorithm 9.6 References 10 PRGs from One-Way Permutations 63 10.1 Pseudorandom Generators from One-Way Permutations 11 Pseudorandom functions from prgs 69 11.1 Pseudorandom generators evaluated on independent seeds CONTENTS 11.2 Construction of pseudorandom functions 70 11.2.1 Considering a tree of small depth 71 11.2.2 Proving the security of the ggm construction 1 2 Pseudorandom permutations from prfs 75 12.1 Pseudorandom permutations 12.2 Feistel permutations 76 12.3 The Luby-Rackoff Construction 12.4 Analysis of the Luby-Rackoff Construction 13 Public-key Encryption 85 13.1 Public-Key Cryptography 85 13.2 Public Key Encry ption 86 13.3 Definitions of security 87 13.4 The Decision Diffie-Hellman Assumption 13.5 Decision Diffie Ilellman and Quadratic Residues 13.6 El Gamal Encryption 14 CPA-secure Public-Key Encryption 93 14.1 Hybrid Encryption 93 14.2 RSA 95 14.3 Trapdoor Permutations and Encryption 15 Signature Schemes 99 15.1 Signature Schemes 15.2 One-Time Signatures and Key refreshing 101 15.3 From One-Time Signatures to Fully Secure Signatures 104 16 Signature Schemes in the Random Oracle Model 109 16.1 The Hash-and-Sign Schemc 16.2 Analysis 110 17 CCA Security with a Random Oracle 113 17.1 Ilybrid Encryption with a random Oracle 113 17.2 Security Analysis 111 CONTENTS 18 Zero Knowledge Proofs 119 18.1 Intuition 119 18.2 The Graph Non-Isomorphism Protoco 120 18.3 The Graph Isomorphism Protocol 122 18.4 A Simulator for the graph Isomorphism Protocol 125 19 Zero Knowledge Proofs of Quadratic Residuosity 129 19. 1 The Quadratic Residuosity Problem 19.2 The Quadratic Residuosity Protocol 131 20 Proofs of Knowledge and Commitment Schemes 133 20.1 Proofs of Knowledge 133 20.2 Uses of Zero Knowledge proofs 134 20.3 Commitment Scheme 135 21 Zero Knowledge Proofs of 3-Colorability 139 21.1 A Protocol for 3-Coloring 139 21.2 Simulability 140 21.3 Computational Zero Knowled 142 21.4 Proving that the simulation is Indistinguishable 142 Lecture 1 Introduction This course assumes Cs170, or equivalent, as a prerequisite. We will assume that the reader is familiar with the notions of algorithm and running time, as well as with basic notions of algebra( for example arithmetic in finite fields ), discrete math and probability. General information about the class, including prerequisites, grading, and recommended references, are available on the class home page Cryptography is the mathematical foundation on which one builds secure systems. It studies ways of sccurcly storing transmitting, and processing information. Undcrstanding what cryptographic primitives can do, and how they can be composed together, is necessary to build secure systems, but not sufficient. Several additional considerations go into the design of secure systems, and they are covered in various Berkeley graduate courses on security In this course we will see a nuinber of rigorous definitions of securily, some of thein requiring seemingly outlandish safety, even against entirely implausible attacks, and we shall see how if any cryptography at al is possible, then it is also possible to satisfy such extremely strong notions of security. For example, we shall look at a notion of security for encryption in which an adversary should not be able to learn any information about a message given the ciphertext, even if Chie adversary is allowed to get encodings of any Messages of his choice, and dccodings of any ciphcrtcxts of his choices, with the only exception of the onc he is trying to decode define security for protocols involving several untrusted participante and elegant) ways to We shall also see extremely powerful (but also surprisingly simple and elegant)ways to Learning to think rigorously about security, and seeing what kind of strength is possible at least in principle, is one of the main goals of this course. We will also see a number of constructions, some interesting for the general point they make(that certain weak primitives are sufficient to make very strong constructions), some efficient enough to have made their way in commercial products Ⅰ ECTURE1.Ⅰ NTRODUCTION 1.1 Alice. Bob. Eve and the others Most of this class will be devoted to the following simplified setting: Alice and Bob com- municate over an insecure channel, such as the internet or a cell phone. An eavesdropper Eve, is able to see the whole communication and to inject her own messages in the channel Alice and Bob hence want to find a way to encode their communication so as to achieve Privacy: Eve should have no information about the content of the messages ex changed between Alice and bob e Authentication: Eve should not be able to impersonate Alice, and every time that Bob receives a message from alice, he should be sure of the identity of the sender (Same for messages in the other direction. For example, if Alice is your laptop and Bob is your wireless router, you night want lo make sure that your neighbor Eve cannot see what you are doing on the internet and cannot connect using your router For this to be possiblc, Alicc and Bob must have somc sccrct information that Evc ignores otherwise Eve could simply run the same algorithms that Alice does, and thus be able to read the messages received by Alice and to communicate with Bob impersonating Alice In the classical symmetric-key cryptography setting, Alice and Bob have met before and agreed on a secret keg, which they use to encode and decode message, to produce authen- tication information and to verify the validity of the authentication information In the pablic-heg setting, Alice has a private key known only to her, and a ublic key known to everybody, including Eve; bob too has his own private key and a public key known to every body. In this setting, private and authenticated communication is possible without Alice and Bob having lo neel to agree on a shared secret key This gives rise to four possible problems(symmetric-key encryption, symmetric-key authen- tication, public-key encrpytion, and public-key authentication, or signatures), and we shall spend time on each of them. This will account for more than half of the course The last part of the course will deal with a fully general set-up in which any number of parties, including any number of (possibly colluding) bad guys, execute a distributed protocol over a communication network In between, we shall consider some important protocol design problems, which will play a rolc in the fully gencral constructions. These will be commitment schemes, zero-knowledge proofs and oblivious transfer 1.2 The Pre-history of Encryption The task of encoding a message to preserve privacy is called encryption(the decoding of the message is called decrpytion), and methods for symmetric-key encryption have been studied for literally thousands of years 1.2. THE PRE-HISTORY OF ENCRYPTION Various substitution ciphers were invented in cultures having an alphabetical writing system The secret key is a permutation of the set of letters of the alphabet, encryption is done by applying the permutation to each letter of the message, and decryption is done by applying the inverse permutation. Examples are the Atbash ciphers used for Hebrew, in which the first letter of the alphabet is replaced with the last. the second letter with the second-to-last and so on. It is used in the book of jeremiah o the cipher used by Julius Caesar, in which each letter is shifted by three positions in the alphabet There are reports of similar methods used in Greece. If we identify the alphabet with the Integers 1), where k is the size of the alphabet, then the Atbash code is the mapping a-7k-1-c and Caesar's code is a-a+3 mod k. In general, a substitution code of the form x=+i mod k is trivially breakable because of the very small number of possible keys that one has to try. Reportedly, former Mafia boss Bernardo provenzano used Caesar's code to communicate with associates while he was a fugitive.(It didnt work too well for him. The obvious flaw of such kind of substitution ciphers is the very small number of possible keys, so that an adversary can simply try all of them Substitution codes in which the pernulalion is allowed lo be arbitrary were used through the middle ages and modern times. In a 26-letter alphabet the number of keys is 26!. which is too large for a brute-force attack. Such systems. however, suffer from easy total breaks because of the facts that, in any given language different letters appear with different frequencies, so that Eve can immediately make good guesses for what are the encryptions of the most common letters, and work out the whole code with some trial and errors This was noticed already in the 9th century A D. by Arab scholar al-Kindy. Sherlock Holmes breaks a substitution cipher in The Adventure of the Dancing Men For fun, try decoding the following message. (A permutation over the English alphabet has been applied; spaces have been removed before encoding. IKNIIQIINWKZIITIINIIPZKTPKAZYASNKOOAVIINPSAETKOIIQIINCII HZSKBZRHYKBRCBRNHIBOHYRKCHXZKSXHYKBRAZYIKNHQHNWK ZHETKTAOORBVCFHYCBRORKKYNPDTRCASXBLAZYIKNHQHNWK ZHETKEKNXOTANYAZYZHQHNDPQHOBLRTPOKZHPOIKNWKBWKB XZKEETARRTHWOAWAOKTPKDKHOOKDKHORTHZARPKZEHFFRT POZARPKZOSKVPZDCASXAZYOKPORTPOSAVLAPDZRTIILIIKLFIIK IKTPKTAQHOAPYPRFKBYFWAZYSFHANFWEHNHDKPZDKZEHNHDK PZDORNKZDAZYEHNHDKPZDAFFRTHEAWWKBXZKERTHWSAFFKT PKACHFFEHRTHNORARHPROACARRFHDNKBZYORARHPROAORA RHRTARXZKEOTKERKLPSXALNHOPYHZRAZYZKSAZYPYARHPZNH SIIZRTPORKNWYIIVKSNARKNNIILBCFPSAZTAOEKZRTIIETPRIITK BOHEPRTKBREPZZPZDRTHKTPKLNPVANW

...展开详情
img
xml6651

关注 私信 TA的资源

上传资源赚积分,得勋章
最新资源